Dlaczego


22

Chciałbym wiedzieć, czy istnieje zasada, aby to udowodnić. Na przykład, jeśli użyję prawa dystrybucyjnego, dostanę tylko (ZAZA)(ZA¬b) .


2
Witamy w informatyce! Czego próbowałeś? Gdzie utknąłeś? Nie chcemy wręczać ci rozwiązania; chcemy, abyście zrozumieli. Ponieważ jednak nie wiemy, jaki jest twój podstawowy problem, nie możemy zacząć pomagać. Zobacz tutaj wskazówki dotyczące zadawania pytań na temat problemów z ćwiczeniami. Jeśli nie jesteś pewien, jak poprawić swoje pytanie, dlaczego nie zapytać na czacie informatyki ?
Raphael

Istnienie prawdziwe jest konieczne w obu warunkach i wystarcza dla tego po lewej.
Millie Smith,

Odpowiedzi:


55

Uważam, że zdjęcia świetnie nadają się do wszystkiego, co jest na tyle proste, aby z nich korzystać, to jest to.

Renderowany schemat

Zapamiętaj:

AND oznacza obszar zajmowany przez obie rzeczy. Zatem środkowy jest zajęty poza B, ale także wewnątrz A. Ich skrzyżowanie nie jest liczone, ponieważ znajduje się w A, ale nie poza B.

LUB oznacza, że ​​jest objęty jednym lub obydwoma. Oba obejmują część A, która znajduje się poza B, a skrzyżowanie jest pokryte przez A (pierwsze zdjęcie), więc również jest liczone. Podsumowując, znowu masz A.

Przepraszamy, jeśli jest to zbyt uproszczone, nie jestem pewien, na jakim jesteś poziomie.


Dla kompletności dobrze byłoby pokazać przypadek, w którym B i A są rozłączne, oraz inny przypadek, w którym B jest A.
Eric Duminil

11
@EricDuminil Nie zgadzam się. Wspaniałą rzeczą w tej pracy diagramu Venna jest to, że jest ważne, czy któryś z regionów jest pusty.
Mark S.

3
+1 do odpowiedzi Marka S. Chodzi o diagramy Venna i powód, dla którego wciąż (mam nadzieję!) Nauczali na lekcjach matematyki w gimnazjum, jest to, że faktycznie działają . Jeśli ty (Eric) zastanawiasz się „ale co jeśli B i A są rozłączni?”, To nie zrozumiałeś jeszcze, co tak naprawdę przedstawia diagram Venna. Reprezentuje cztery logiczne możliwości jako cztery regiony geometryczne: (A&B) [środkowy klin], (A i ~ B) [lewy półksiężyc], (~ A i B) [prawy półksiężyc] i (~ A i ~ B) [reszta Strona]. Kolorowanie ich tak, jak zrobiła to Erin, pomaga nam wyobrazić sobie logiczny problem jako problem geometryczny .
Quuxplusone

@EricDuminil (przeznaczony dla każdego, kto to czyta w przyszłości), jeśli są rozłączni, środkowy będzie po prostu A (brak części A w środku B), więc masz A lub A = A, a jeśli A = B, środkowy będzie pusty (żadna część A nie jest poza B), więc będziesz mieć A lub nic = A
Erin

1
@djechlin: Byłem zmęczony. Jeśli A to B, możesz zignorować zarówno lewą, jak i prawą część.
Eric Duminil,

48

Można to zobaczyć na wiele sposobów. Jednym z nich jest tabela prawdy. Inny sposób polega na użyciu Rozdzielczej zasadę: ( Kontakty B ) = ( A ) ( A ¬ B ) = ( Kontakty B ) = = .

ZA(ZA¬b)=(ZA)(ZA¬b)=ZA(¬b)=ZA=ZA.

Czy na drugim etapie ten znak równości nie powinien oznaczać relacji równoważności?
KumarAnkit

Używam = w zwykłym znaczeniu, jak w 2 + 2 = 4.
Yuval Filmus

ok, czy możesz wyjaśnić przejście od drugiego kroku do trzeciego?
KumarAnkit

9

Użyłbym mojej najmniej ulubionej reguły wnioskowania: Eliminacja rozłączeń . Zasadniczo mówi, że jeśli wynika z P , a R wynika z Q , to R musi być prawdziwe, jeśli P Q : ( P R ) , ( Q R ) , ( P Q ) RRP.RQRP.Q

(P.R),(QR),(P.Q)R

Załóżmy więc, że . Ustaw P = A , Q = A ¬ B , R = A i zastosuj regułę:ZA(ZA¬b)P.=ZAQ=ZA¬bR=ZA

  • Jeśli ( = A ) to koniec.P.=ZA
  • Jeśli to A (przez eliminację koniunkcyjną, S T S )Q=ZA¬bZAS.T.S.
  • Poprzez eliminację alternatywy ( ¬ B ) A .ZA(ZA¬b)ZA

Odwrotność jest trywialna: załóżmy , a następnie jeden z wariantów wprowadzenia koniunkcji ( S S T dla dowolnego T ) A A ( ) .ZAS.S.T.T.ZAZA()

Oto schemat tego dowodu:

Oddany dowód


4
Przepraszam, jak narysowałeś ten schemat? Czuję najdelikatniejszy zapach Coq.
Tobia Tesan,

1
@TobiaTesan Byłem tym, który „narysował” schemat. Użyłem do tego oprogramowania o nazwie łupek .
Sriotchilism O'Zaic

1
@EpsilonNeighborhoodWatch: dziękuję bardzo. Przepraszam za dalsze nadużywanie cierpliwości, ale czy to oprogramowanie można uzyskać w jakikolwiek sposób? Link w nagłówku (www.cogsci.rpi.edu/slate) wydaje się martwy
Tobia Tesan

@TobiaTesan Program Visio firmy Microsoft może być również używany do rysowania takich diagramów. Jeśli jesteś powiązany z uniwersytetem lub dużą firmą, która oferuje oprogramowanie Microsoft studentom / pracownikom lub masz subskrypcję MSDN, być może masz już opłacony dostęp do niej.
Nat.

@Nat Sure (lub możesz to zrobić w TikZ: P), ale miałem wrażenie, że rzecz używana przez EpsilonNeighborhoodWatch ma funkcje asystenta dowodu, stąd moje zainteresowanie :) FWIW Dowód generalny może zrobić coś takiego , ale wizualizacja drzewa dowodowego jest znacznie brzydsza.
Tobia Tesan

5

doredore=reredore

do=ZA¬bre=ZA


3

Bardziej intuicyjny wygląd:

Ajest zawsze prawdziwe, gdy Ajest prawdziwe.

A & -Bjest prawdziwe tylko wtedy, gdy Ajest prawdziwe.

Intuicyjnie zastosowanie OR do tych dwóch przyniosłoby wynik, Cktóry zawsze jest prawdziwy, gdy Ajest prawdziwy. Jako taki Cjest zawsze prawdziwy, gdy Ajest prawdziwy.

(Przestań czytać tutaj, jeśli to wyjaśnienie Ci odpowiada).

Tak myślę o tym problemie. Jednak to wyjaśnienie nie jest kompletne, ponieważ wszystko, co pokazaliśmy, to to A -> Ci nie A <-> C.

Pokażmy to również C -> A.

Azawsze jest fałszem, gdy Ajest fałszem.

A & -Bzawsze jest fałszem, gdy Ajest fałszem.

Intuicyjnie zastosowanie OR do tych dwóch dawałoby wynik, Cktóry zawsze jest fałszywy, gdy Ajest fałszywy. Jako taki, Czawsze jest fałszywy, gdy Ajest fałszywy; -A -> -C, co jest tym samym co C -> A.

Tak A -> Ci C -> Atak A <-> C.


3

Czasami ludzie są zdezorientowani literami. Ludzie lubią jedzenie, bo łatwo o tym pomyśleć.

Udawaj, że proszę rzucić monetą, aby wybrać jedną z LUB LUB z dwóch następujących opcji:

  • Jabłko, LUB ...
  • Jabłko, a na pewno nie banan.

[Pierwszy jest równy „A”, drugi „A, a nie B”. Ale nie myśl o literach. Pomyśl o jabłku i o tym, czy dostaniesz banana.]

Ten pierwszy naprawdę oznacza „Jabłecznik, a może dostaniesz banana”.

Więc pominięcie czegoś jest tym samym, co powiedzenie „może”.

Patrząc na nich jako parę, cokolwiek dostaniesz, na pewno będzie zaangażowany Apple. Tak A jeśli twój coinflip wybierze właściwy, możesz dostać banana.

Ale czy to nie to samo, co powiedzenie „może dostaniesz banana”? Tylko z połową prawdopodobieństwa?

Wszystko, co możesz logicznie powiedzieć, to że dostaniesz Apple. Nie możesz powiedzieć nic o tym, czy dostaniesz banana.


3

Podobna do odpowiedzi Yuval Filmus. Wykorzystanie algebry boolowskiej w notacji inżynierskiej i faktoring (lub faktoryzacja) A.

A+AB¯=A(1+B¯)=A1=A


3

Wygląda na to, że nikt jeszcze o tym nie wspominał, więc pójdę naprzód.

Prawem do radzenia sobie z tego rodzaju problemami jest prawo absorpcji , które stwierdza, że ​​pv (p ^ q) = p, a także, że p ^ (pvq) = p. Jeśli spróbujesz użyć w tym celu prawa dystrybucyjnego, będzie ci to krążyło w kółko:

(A v A) ^ (A v ~ B) = A ^ (A v ~ B) = (A ^ A) v (A ^ ~ B) = A v (A ^ ~ B) = (A v A) ^ (A v ~ B)

Użyłem niewłaściwego symbolu „nie” i „równa się”, ale chodzi tutaj o to, że kiedy idziesz w kółko / kiedy występuje i / lub niedopasowanie zwykle powinieneś zwrócić uwagę na prawo absopcji.

B nie ma znaczenia dla wyniku, jak zauważysz, jeśli umieścisz to w tabeli prawdy.


Jest to zgodne z odpowiedzią na jabłka i banana
Erin,

1
@Erin +1 Co więcej, dostarcza regułę, podczas gdy odpowiedź na jabłko i banana odwoływała się tylko do intuicji, a OP poprosił o regułę, a nie intuicję.
Rosie F

2

Kolejny intuicyjny sposób spojrzenia na to:

Jeśli A jest zbiorem, możemy powiedzieć, że dany obiekt jest (w A) lub (nie w A).

Teraz spójrz na S = A lub (A i nie B) :

  • Jeśli obiekt znajduje się w A, wówczas „A lub cokolwiek” zawiera wszystkie elementy w A, więc obiekt będzie również w S.

  • Jeśli obiekt nie znajduje się w A, wówczas „A i cokolwiek” wyklucza wszystkie elementy spoza A, więc obiekt nie znajduje się w A ani w (A i nie B), więc nie ma go w S.

Rezultat jest taki, że każdy obiekt w A znajduje się w S, a każdy obiekt nie w A nie znajduje się w S. Tak intuicyjnie, obiekty w S muszą być dokładnie takie same w A i żadnych innych obiektów.

Gdy dwa zestawy mają identyczne elementy, są one zdefiniowane jako ten sam zestaw. Tak A = S.


2

Prostą metodą, z której zawsze możesz skorzystać, jeśli utkniesz, jest analiza przypadków.

A

Założyć A

A może mieć już więcej możliwych wartości, sprawdziłeś tę propozycję.


0
lets consider: 
  1) A as 1 and B as 0. 
  2) A as 0 and B as 1. 
  3) A as 1 and B as 1.
  4) A as 0 and B as 0.

using the first scenario : A or (A and !B) => 1 or ( 1 and 1) => 1 0r 1 => 1
using the second scenario: A or (A and !B) => 0 or ( 0 and 0) => 0 or 0 => 0
using the third scenario : A or (A and !B) => 1 or ( 1 and 0) => 1 or 0 => 1
using the fourth scenario: A or (A and !B) => 0 or ( 0 and 1) => 0 or 0 => 0

From the above four cases, the result always depends on A not on B, so the result is A.
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.