Warum ist ?

22

Ich würde gerne wissen, ob es eine Regel gibt, die dies beweist. Wenn ich zum Beispiel das Verteilungsgesetz verwende, erhalte ich nur .(AA)(A¬B)

user78333
quelle
2
Willkommen in der Informatik! Was hast du versucht Wo bist du stecken geblieben? Wir möchten Ihnen nicht nur die Lösung geben. Wir möchten, dass Sie Verständnis gewinnen. Da wir jedoch nicht wissen, um welches Problem es sich handelt, können wir Ihnen nicht weiterhelfen. Sehen Sie hier für Tipps auf Fragen zu Übungsaufgaben zu stellen. Wenn Sie sich nicht sicher sind, wie Sie Ihre Frage verbessern können, warum nicht im Computer Science Chat nachfragen ?
Raphael
Ein wahres Wesen ist unter beiden Bedingungen notwendig und für das linke ausreichend.
Millie Smith

Antworten:

55

Ich finde Bilder sind großartig für alles, was einfach genug ist, um sie zu benutzen, was das ist.

Gerendertes Diagramm

Merken:

UND bedeutet die Fläche, die von beiden Dingen eingenommen wird. Das mittlere ist also das, was außerhalb von B, aber auch innerhalb von A aufgenommen wird. Ihre Verbindung wird nicht gezählt, da sie sich innerhalb von A, aber nicht außerhalb von B befindet.

ODER bedeutet, dass es von einem oder beiden abgedeckt wird. Beide decken den Teil von A ab, der sich außerhalb von B befindet, und die Kreuzung wird von A (erstes Bild) abgedeckt, sodass sie ebenfalls gezählt wird. Alles in allem hast du gerade wieder ein.

Tut mir leid, wenn dies zu simpel ist und Sie nicht sicher sind, auf welchem ​​Niveau Sie sich befinden.

Erin
quelle
Der Vollständigkeit halber könnte es gut sein, den Fall zu zeigen, in dem B und A disjunkt sind, und einen anderen Fall, in dem B A ist.
Eric Duminil
11
@EricDuminil Ich bin anderer Meinung. Das Tolle an dieser Venn-Diagrammarbeit ist, dass es gültig ist, ob eine der Regionen leer ist oder nicht.
Mark S.
3
+1 auf Mark S.'s Antwort. Die Sache mit Venn-Diagrammen und der Grund, warum sie (wie ich hoffe!) Noch im Mathematikunterricht der Mittelschule unterrichtet werden, ist, dass sie tatsächlich funktionieren . Wenn Sie (Eric) sich fragen, "aber was ist, wenn B und A unzusammenhängend sind? ...", dann haben Sie noch nicht verstanden, was ein Venn-Diagramm tatsächlich darstellt. Es repräsentiert die vier logischen Möglichkeiten als vier geometrische Regionen: (A & B) [der mittlere Keil], (A & B) [der linke Halbmond], (~ A & B) [der rechte Halbmond] und (~ A & B) [der Rest von Die Seite]. Wenn Sie sie wie Erin einfärben, können Sie sich ein logisches Problem als geometrisches Problem vorstellen.
Quuxplusone
@EricDuminil (für alle, die dies in Zukunft lesen möchten) Wenn sie disjunkt sind, ist die mittlere nur A (kein Teil von A in B), sodass Sie A oder A = A haben und wenn A = B, die mittlere wird leer sein (kein Teil von A ist außerhalb von B), so haben Sie A oder nichts = A
Erin
1
@djechlin: Ich war müde. Wenn A B ist, können Sie sowohl den linken als auch den rechten Teil ignorieren.
Eric Duminil
48

Es gibt viele Möglichkeiten, dies zu sehen. Eines ist eine Wahrheitstabelle. Ein weiteres ist die Verteilungsregel zu verwenden:

A(A¬B)=(A)(A¬B)=A(¬B)=A=A.
Yuval Filmus
quelle
Sollte dieses Gleichheitszeichen im zweiten Schritt nicht Äquivalenzrelation bedeuten?
KumarAnkit
Ich benutze = in seiner üblichen Bedeutung, wie in 2 + 2 = 4.
Yuval Filmus
ok, kannst du den Übergang vom zweiten zum dritten Schritt erklären?
KumarAnkit
9

Ich würde meine am wenigsten bevorzugte Inferenzregel anwenden: Disjunction Elimination . Grundsätzlich heißt es, wenn aus P folgt und R aus Q folgt , dann muss R wahr sein, wenn P Q : ( P R ) , ( Q R ) , ( P Q ) RRPRQRPQ

(PR),(QR),(PQ)R

Nehmen wir also . Setze P = A , Q = A ¬ B , R = A und wende die Regel an:A(A¬B)P=AQ=A¬BR=A

  • Wenn ( = A ), sind wir fertig.P=A
  • Wenn dann A (durch Konjunktionseliminierung ist S T S )Q=A¬BASTS
  • Durch Eliminierung Disjunktion .A(A¬B)A

Das Gegenteil ist trivial: Nehmen Sie , dann durch eine der Varianten der Konjunktionseinführung ( S S T für ein beliebiges T ) A A ( ) .ASSTTAA()

Hier ist ein Diagramm dieses Beweises:

Proof gerendert

CompuChip
quelle
4
Es tut mir leid, wie haben Sie das Diagramm gezeichnet? Ich rieche den schwächsten Geruch von Coq.
Tobia Tesan
1
@TobiaTesan Ich war derjenige, der das Diagramm "gezeichnet" hat. Ich habe dazu eine Software namens slate verwendet.
Sriotchilism O'Zaic
1
@EpsilonNeighborhoodWatch: vielen dank. Entschuldigen Sie, dass ich Ihre Geduld weiter missbraucht habe, aber kann diese Software auf irgendeine Weise beschafft werden? Der Link auf dem Header (www.cogsci.rpi.edu/slate) scheint tot zu sein
Tobia Tesan
@TobiaTesan Mit Visio von Microsoft können auch solche Diagramme gezeichnet werden. Wenn Sie mit einer Universität oder einem großen Unternehmen verbunden sind, das Studenten / Mitarbeitern Microsoft-Software anbietet, oder wenn Sie ein MSDN-Abonnement haben, haben Sie möglicherweise bereits bezahlten Zugriff darauf.
Nat
@Nat Sicher (oder Sie können es in TikZ Menschen und tun: P), aber ich habe den Eindruck , dass das von EpsilonNeighborhoodWatch verwendet , was Beweis Assistenten Merkmale hatte, daher mein Interesse :) FWIW Proof General kann etwas tun , wie diese, aber Die Proof-Tree-Visualisierung ist viel hässlicher.
Tobia Tesan
5

Beachten Sie, dass, wenn wir wissen, dass D impliziert , wir C D = D haben . Dies ist analog zur Vereinigung einer Menge (entsprechend D ) und einer ihrer Teilmengen ( C ): Wir erhalten die größte Menge ( D ) zurück.CDCD=DDCD

In Ihrem Fall ist und D = A , und die Implikation ist trivial.C=A¬BD=A

chi
quelle
3

Ein intuitiverer Blick:

Aist immer wahr, wenn Aes wahr ist.

A & -Bist nur wahr, wenn Aes wahr ist.

Intuitiv würde das Anwenden von ODER auf diese beiden ein Ergebnis erzeugen, Cdas immer dann wahr ist, wenn Aes wahr ist. Als solches Cist immer wahr, wenn Aes wahr ist.

(Hören Sie hier auf zu lesen, wenn diese Erklärung für Sie funktioniert.)

So denke ich über dieses Problem. Diese Erklärung ist jedoch nicht vollständig, da wir nur das gezeigt haben A -> Cund nicht A <-> C.

Lassen Sie uns das also auch zeigen C -> A.

Aist immer falsch, wenn Afalsch ist.

A & -Bist immer falsch, wenn Afalsch ist.

Intuitiv würde das Anwenden von ODER auf diese beiden ein Ergebnis erzeugen, Cdas immer dann falsch ist, wenn Aes falsch ist. Als solches Cist es immer falsch, wenn Aes falsch ist; -A -> -CDas ist das Gleiche wie C -> A.

So A -> Cund C -> Aso A <-> C.

Quelklef
quelle
3

Manchmal sind die Menschen durch die Buchstaben verwirrt. Die Leute mögen Essen, weil man leicht darüber nachdenken kann.

Stell dir vor, ich bitte dich, eine Münze zu werfen, um zwischen der einen oder der anderen der beiden folgenden Optionen zu wählen:

  • Ein Apfel ODER ...
  • Ein Apfel und definitiv keine Banane.

[Das erste ist gleich "A", das zweite "A und nicht B". Aber denk nicht an die Buchstaben. Denken Sie an den Apfel und darüber nach, ob Sie auch eine Banane bekommen.]

Das erste bedeutet wirklich "Eine Apfeltorte, und vielleicht bekommst du eine Banane."

Etwas wegzulassen ist also dasselbe wie "vielleicht" zu sagen.

Wenn man sie als Paar betrachtet, wird es auf jeden Fall einen Apple geben. Yay. Und wenn Ihr Coinflip den richtigen auswählt, erhalten Sie möglicherweise eine Banane.

Aber ist das nicht dasselbe wie "Vielleicht kriegst du eine Banane"? Nur mit der halben Wahrscheinlichkeit?

Alles, was Sie logischerweise sagen können, ist, dass Sie einen Apple bekommen. Sie können nichts darüber sagen, ob Sie eine Banane bekommen.

Dewi Morgan
quelle
3

Ähnlich wie die Antwort von Yuval Filmus. Verwenden der Booleschen Algebra in der technischen Notaion und Ausklammern (oder Faktorisieren) von A.

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

Onur
quelle
3

Es scheint, als hätte es noch niemand erwähnt, also werde ich weitermachen.

Das Gesetz, das diese Art von Problemen behandelt, ist das Absorptionsgesetz, das besagt, dass pv (p ^ q) = p und auch p ^ (pvq) = p. Wenn Sie versuchen, das Distributionsgesetz zu verwenden, bleiben Sie für immer im Kreis:

(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)

Ich habe das falsche Symbol für nicht und gleich verwendet, aber der Punkt hier ist, dass, wenn Sie in Kreisen gehen / wenn es eine und-oder Nichtübereinstimmung gibt, Sie normalerweise auf das Absoprtionsgesetz achten sollten.

B ist für das Ergebnis irrelevant, wie Sie feststellen werden, wenn Sie dies in eine Wahrheitstabelle schreiben.

Arthur
quelle
Dies passt gut zur Antwort auf Apfel und Banane
Erin
1
@Erin +1 Außerdem liefert es eine Regel, während die Antwort von Apfel und Banane nur die Intuition ansprach und das OP nach einer Regel fragte, nicht nach Intuition.
Rosie F
2

Eine andere intuitive Möglichkeit, dies zu betrachten:

Wenn A eine Menge ist, können wir sagen, dass jedes gegebene Objekt entweder (in A) oder (nicht in A) ist.

Schauen Sie sich nun S = A oder (A und nicht B) an :

  • Wenn sich ein Objekt in A befindet, enthält "A oder irgendetwas" alle Elemente in A, sodass sich das Objekt auch in S befindet.

  • Wenn sich ein Objekt nicht in A befindet, schließt "A und alles" alle Elemente aus, die sich nicht in A befinden. Das Objekt befindet sich also weder in A noch in (A und nicht in B), also nicht in S.

Das Ergebnis ist also, dass jedes Objekt in A in S ist und jedes Objekt, das nicht in A ist, nicht in S. Intuitiv gesehen müssen die Objekte in S genau die in A sein und keine anderen Objekte.

Wenn zwei Mengen identische Elemente haben, werden sie als dieselbe Menge definiert. Also A = S.

Stilez
quelle
2

Eine einfache Methode, die Sie immer anwenden können, wenn Sie nicht weiterkommen, ist die Fallanalyse.

A

A

A

John Doe der Gerechte
quelle
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.
prudhvi seeramreddi
quelle