Beispielskriptum

In diesem kurzen Skriptum finden Sie einige ergänzende Beispiele für Herleitungen zum Skriptum ,,Einführung in die Logik''.

PDF-Version dieses Skriptums

Kapitel 1
Aussagenlogik

1.1 Kommutativgesetze

Zur Entspannung zwei einfache Argumente, die als Kommutativgesetz der Konjunktion bekannt sind:

Argument 1.1 P ∧ Q ⊢ Q ∧ P

Beweis

1(1)P ∧ QA
1(2)P 1 ∧ B
1(3)Q 1 ∧ B
1(4)Q ∧ P3,2 ∧ E

Argument 1.2 Q ∧ P ⊢ P ∧ Q

Die Gültigkeit dieser beiden Argumente bedeutet, dass die Reihenfolge, in der die Konjunkte einer Konjunktion aufgeschrieben sind, gleichgültig wäre.

Eine Spur komplizierter ist es, das Kommutativgesetz der Disjunktion zu beweisen:

Argument 1.3 P ∨ Q ⊢ Q ∨ P

Beweis

1(1)P ∨ QA
2(2)P A
2(3)Q ∨ P2 ∨ E
4(4)Q A
4(5)Q ∨ P4 ∨ E
1(6)Q ∨ P1,2,3,4,5 ∨ B

Die Konklusion ist eine Disjunktion; die nächstliegende Möglichkeit zur Herleitung einer Disjunktion ist die ∨E, für die es ausreicht, eines der beiden Disjunkte —im Beispiel Q oder P— hergeleitet zu haben.

Da zu Beginn keines der beiden Disjunkte verfügbar ist und es auch keine Möglichkeit gibt, aus der einzigen Prämisse, P ∨Q, auf P oder auf Q zu schließen, müssen wir unser Interesse an den beiden (ohne es zu vergessen) zunächst hintanstellen und nach einer anderen Strategie suchen.

Die einzige Prämisse, P ∨Q, ist eine Disjunktion, und die nächstliegende Möglichkeit, aus einer Disjunktion zu schließen, ist die ∨B. Für sie müssten wir sowohl aus dem ersten als auch aus dem zweiten Disjunkt einen uns interessierenden Satz herleiten. Nun lauten aber diese beiden Disjunkte P bzw Q; aus jedem von ihnen können wir —das im vorangehenden Absatz gespeicherte Wissen bedenkend— auf die von uns gewnschte Konklusion Q∨P schließen. Da Q∨P aus jedem der beiden Disjunkte der Prämisse, P ∨ Q, folgt, folgt es aus der gesamten Disjunktion und haben wir den Weg zum Ziel gefunden. Formal ausgeführt wird er in den Zeilen (2) bis (6).

Argument 1.4 Q ∨ P ⊢ P ∨ Q

1.2 Assoziativgesetze

Auch die Assoziativgesetze sind sehr brauchbar:

Argument 1.5 P ∧ (Q ∧ R) ⊢ (P ∧ Q) ∧ R

Beweis

1(1)P ∧ (Q ∧ R)A
1(2)P 1 ∧ B
1(3)Q ∧ R 1 ∧ B
1(4)Q 3 ∧ B
1(5)P ∧ Q 2,4 ∧ E
1(6)R 3 ∧ B
1(7)(P ∧ Q) ∧ R5,6 ∧ E

Die Konklusion ist eine Konjunktion mit den Konjunkten P ∧ Q und R. Am einfachsten erhält man eine Konjunktion mittels der ∧E, für deren Anwendung allerdings erst die beiden Konjunkte hergeleitet werden müssen. Nun ist das erste Konjunkt, P ∧ Q, seinerseits eine Konjunktion und knnte dadurch ebenfalls mittels einer ∧E hergeleitet werden, soferne seine Konjunkte, P und Q hergeleitet wären. Damit die beiden Anwendungen der ∧E möglich sind, müssen wir somit die einfachen Stze P, Q und R herleiten.

Ein Blick auf die einzige Prämisse zeigt uns, dass zumindest P sehr leicht erschlossen werden kann: Die Prämisse ist eine Konjunktion, als deren erstes Konjunkt P auftritt. Mittels der ∧B schließen wir mhelos aus Zeile (1) auf Zeile (2), P.

Die beiden anderen Stze, Q und R, sind kaum schwieriger zu finden: Das zweite Konjunkt der Prämisse lautet Q ∧ R, und aus diesem Satz lässt sich mittels zweier ∧B sowohl auf Q als auch auf R schließen. Wir schließen daher zunächst in Zeile (3) auf das zweite Disjunkt, Q ∧ R, und dann in Zeile (4) bzw. (6) auf Q bzw. R. In Zeile (5) werden die beiden Zwischenergebnisse aus (2) und (4) zu P ∧ Q, dem ersten Konjunkt der Konklusion, zusammengesetzt. Vollendet wird das Werk in Zeile (7), wo das zweite Konjunkt aus Zeile (6) hinzutritt.

Argument 1.6 (P ∧ Q) ∧ R ⊢ P ∧ (Q ∧ R)

Gleich ein gutes Stück komplizierter ist das Assoziativgesetz der Disjunktion, weshalb ich für beide Argumente eine Lösung beilege:

Argument 1.7 P ∨ (Q ∨ R) ⊢ (P ∨ Q) ∨ R

Beweis

1 (1)P ∨ (Q ∨ R)A
2 (2)P A
2 (3)P ∨ Q 2 ∨ E
2 (4)(P ∨ Q) ∨ R3 ∨ E
5 (5)Q ∨ R A
6 (6)Q A
6 (7)P ∨ Q 6 ∨ E
6 (8)(P ∨ Q) ∨ R7 ∨ E
9 (9)R A
9(10)(P ∨ Q) ∨ R9 ∨ E
5(11)(P ∨ Q) ∨ R5,6,8,9,10 ∨ B
1(12)(P ∨ Q) ∨ R1,2,4,5,11 ∨ B

Da die einzige Prämisse eine Disjunktion ist und sich kein anderer offenkundiger Weg zeigt, liegt es nahe, unser Glück bei der ∨B zu suchen. Wir nehmen daher in Zeile (2) das erste Disjunkt, P, an und versuchen, daraus etwas Brauchbares herzuleiten. In unserem Fall gelingt es mittels zweier ∨E (Zeile 3 und Zeile 4), die Konklusion —also etwas sehr Brauchbares— aus dem ersten Disjunkt herzuleiten.

Um die ∨B anwenden und damit aus der Disjunktion auf die Konklusion schließen zu können, brauchen wir nur noch zu zeigen, dass die Konklusion auch aus dem rechten Disjunkt, Q ∨ R folgt. Wir nehmen daher in Zeile (5) dieses Disjunkt an.

Wie wir nun feststellen werden, ist die Herleitung der Konklusion aus dem zweiten Disjunkt erheblich komplizierter als jene aus dem ersten: Das zweite Disjunkt, Q∨R, ist ebenfalls eine Disjunktion, und der nächstliegende Weg, aus ihr zu schließen, ist eine weitere ∨B. Wir müssen also erst aus dem ersten Disjunkt, Q, und anschließend aus dem zweiten Disjunkt, R, unsere Konklusion, (P ∨Q) ∨R, herleiten. Die Herleitung aus dem ersten Disjunkt, Q, nimmt die Zeilen 6 bis 8 ein, jene aus dem zweiten Disjunkt, R, die Zeilen 9 bis 10. In Zeile 11 wird nun die innere ∨B, jene aus Q ∨ R, vollzogen.

Da nun gezeigt ist, dass der Satz (P ∨ Q) ∨ R sowohl aus dem ersten Disjunkt der Prämisse, P, als auch aus dem zweiten Disjunkt der Prämisse, Q ∨ R, folgt, kann nun die ∨B aus der Prämisse in Zeile 12 abgeschlossen werden.

Argument 1.8 (P ∨ Q) ∨ R ⊢ P ∨ (Q ∨ R)

Beweis

1 (1)(P ∨ Q) ∨ RA
2 (2)P ∨ Q A
3 (3)P A
3 (4)P ∨ (Q ∨ R)3 ∨ E
5 (5)Q A
5 (6)Q ∨ R 5 ∨ E
5 (7)P ∨ (Q ∨ R)6 ∨ E
2 (8)P ∨ (Q ∨ R)2,3,4,5,7 ∨ B
9 (9)R A
9(10)Q ∨ R 9 ∨ E
9(11)P ∨ (Q ∨ R)10 ∨ E
1(12)P ∨ (Q ∨ R)1,2,8,9,11 ∨ B

1.3 Distributivgesetze

Eine weitere Steigerung —sowohl was die Wichtigkeit für Anwendungen als auch was die Schwierigkeit betrifft— sind die Distributivgesetze.

Argument 1.9 P ∨ (Q ∧ R) ⊢ (P ∨ Q) ∧ (P ∨ R)

Beweis

1 (1)P ∨ (Q ∧ R) A
2 (2)P A
2 (3)P ∨ Q 2 ∨ E
2 (4)P ∨ R 2 ∨ E
2 (5)(P ∨ Q) ∧ (P ∨ R)3,4 ∧ E
6 (6)Q ∧ R A
6 (7)Q 6 ∧ B
6 (8)P ∨ Q 7 ∨ E
6 (9)R 6 ∧ B
6(10)P ∨ R 9 ∨ E
6(11)(P ∨ Q) ∧ (P ∨ R)8,10 ∧ E
1(12)(P ∨ Q) ∧ (P ∨ R)1,2,5,6,11 ∨ B

Argument 1.10 (P ∨ Q) ∧ (P ∨ R) ⊢ P ∨ (Q ∧ R)

Beweis

1 (1)(P ∨ Q) ∧ (P ∨ R)A
1 (2)P ∨ Q 1 ∧ B
3 (3)P A
3 (4)P ∨ (Q ∧ R) 3 ∨ E
5 (5)Q A
1 (6)P ∨ R 1 ∧ B
7 (7)P A
7 (8)P ∨ (Q ∧ R) 7 ∨ E
9 (9)R A
5,9(10)Q ∧ R 5,9 ∧ E
5,9(11)P ∨ (Q ∧ R) 10 ∨ E
1,5(12)P ∨ (Q ∧ R) 6,7,8,9,11 ∨ B
1(13)P ∨ (Q ∧ R) 2,3,4,5,12 ∨ B

Argument 1.11 P ∧ (Q ∨ R) ⊢ (P ∧ Q) ∨ (P ∧ R)

Beweis

1 (1)P ∧ (Q ∨ R) A
1 (2)P 1 ∧ B
1 (3)Q ∨ R 1 ∧ B
4 (4)Q A
1,4 (5)P ∧ Q 2,4 ∧ E
1,4 (6)(P ∧ Q) ∨ (P ∧ R)5 ∨ E
7 (7)R A
1,7 (8)P ∧ R 2,7 ∧ E
1,7 (9)(P ∧ Q) ∨ (P ∧ R)8 ∨ E
1(10)(P ∧ Q) ∨ (P ∧ R)3,4,6,7,9 ∨ B

Argument 1.12 (P ∧ Q) ∨ (P ∧ R) ⊢ P ∧ (Q ∨ R)

Beweis

1 (1)(P ∧ Q) ∨ (P ∧ R)A
2 (2)P ∧ Q A
2 (3)Q 2 ∧ B
2 (4)Q ∨ R 3 ∨ E
2 (5)P 2 ∧ B
2 (6)P ∧ (Q ∨ R) 4,5 ∧ E
7 (7)P ∧ R A
7 (8)R 7 ∧ B
7 (9)Q ∨ R 8 ∨ E
7(10)P 7 ∧ B
7(11)P ∧ (Q ∨ R) 9,10 ∧ E
1(12)P ∧ (Q ∨ R) 1,2,6,7,11 ∨ B

1.4 Modus tollendo tollens

Folgende Schlussfigur ist unter dem klassischen Namen modus tollendo tollens bekannt:

Argument 1.13 P → Q,¬Q ⊢¬P

Dieses Beiepiel lässt sich mit einem recht einfachen indirekten Beweis lsen:

Beweis

1(1)P → Q A
2(2)¬Q A
3(3)P A
1,3(4)Q 1,3 → B
1,2,3(5)Q ∧¬Q2,4 ∧ E
1,2(6)¬P 3,5¬E

1.5 Modus ponendo tollens

Kaum komplizierter zu beweisen ist die klassische Schlussfigur modus ponendo tollens.

Argument 1.14 ¬(P ∧ Q),P ⊢¬Q

Auch hier fhrt wieder ein geradliniger und kurzer indirekter Beweis zum Ziel:

Beweis

1(1)¬(P ∧ Q) A
2(2)P A
3(3)Q A
2,3(4)P ∧ Q 2,3 ∧ E
1,2,3(5)(P ∧ Q) ∧¬(P ∧ Q)1,4 ∧ E
1,2(6)¬Q 3,5¬E

1.6 Modus tollendo ponens

Dieser klassische Modus ist schon ein wenig aufwendiger zu beweisen:

Argument 1.15 P ∨ Q,¬P ⊢ Q

Beweis

1 (1)P ∨ Q A
2 (2)¬P A
3 (3)P A
4 (4)¬Q A
3,4 (5)P ∧¬Q3,4 ∧ E
3,4 (6)P 5 ∧ B
2,3,4 (7)P ∧¬P2,6 ∧ E
2,3 (8)¬¬Q 4,7¬E
2,3 (9)Q 8¬¬B
10(10)Q A
10(11)Q ∧ Q 10,10 ∧ E
10(12)Q 11 ∧ B
1,2(13)Q 1,3,9,10,12 ∨ B

1.7 Tertium non datur

Nicht vllig trivial ist folgendes Argument zu beweisen:

Argument 1.16 ⊢ P ∨¬P

Beweis

1(1)¬(P ∨¬P) A
2(2)P A
2(3)P ∨¬P 2 ∨ E
1,2(4)(P ∨¬P) ∧¬(P ∨¬P)1,3 ∧ E
1(5)¬P 2,4¬E
1(6)P ∨¬P 5 ∨ E
1(7)(P ∨¬P) ∧¬(P ∨¬P)1,6 ∧ E
(8)¬¬(P ∨¬P) 1,7¬E
(9)P ∨¬P 8¬¬B

1.8 Satz vom ausgeschlossenen Widerspruch

Recht einfach zu beweisen ist folgendes Argument:

Argument 1.17 ⊢¬(P ∧¬P)

Beweis

1(1)P ∧¬P A
1(2)P 1 ∧ B
1(3)¬P 1 ∧ B
1(4)P ∧¬P 2,3 ∧ E
(5)¬(P ∧¬P)1,4¬E

...oder kürzer, aber weniger leicht lesbar:

Beweis

1(1)P ∧¬P A
(2)¬(P ∧¬P)1,1¬E

1.9 Satz von DeMorgan

Die Behauptung, dass die folgenden Argumente gültig seien, ist als Satz von DeMorgan bekannt:

Argument 1.18 P ∧ Q ⊢¬(¬P ∨¬Q)

Beweis

1 (1)P ∧ Q A
2 (2)¬P ∨¬Q A
3 (3)¬P A
1 (4)P 1 ∧ B
1,3 (5)P ∧¬P 3,4 ∧ E
3 (6)¬(P ∧ Q) 1,5¬E
7 (7)¬Q A
1 (8)Q 1 ∧ B
1,7 (9)Q ∧¬Q 7,8 ∧ E
7(10)¬(P ∧ Q) 1,9¬E
2(11)¬(P ∧ Q) 2,3,6,7,10 ∨ B
1,2(12)(P ∧ Q) ∧¬(P ∧ Q)1,11 ∧ E
1(13)¬(¬P ∨¬Q) 2,12¬E

Argument 1.19 ¬(¬P ∨¬Q) ⊢ P ∧ Q

Beweis

1 (1)¬(¬P ∨¬Q) A
2 (2)¬P A
2 (3)¬P ∨¬Q 2 ∨ E
1,2 (4)(¬P ∨¬Q) ∧¬(¬P ∨¬Q)1,3 ∧ E
1 (5)¬¬P 2,4¬E
1 (6)P 5¬¬B
7 (7)¬Q A
7 (8)¬P ∨¬Q 7 ∨ E
1,7 (9)(¬P ∨¬Q) ∧¬(¬P ∨¬Q)1,8 ∧ E
1(10)¬¬Q 7,9¬E
1(11)Q 10¬¬B
1(12)P ∧ Q 6,11 ∧ E

Argument 1.20 P ∨ Q ⊢¬(¬P ∧¬Q)

Beweis

1 (1)P ∨ Q A
2 (2)¬P ∧¬Q A
3 (3)P A
2 (4)¬P 2 ∧ B
2,3 (5)P ∧¬P 3,4 ∧ E
3 (6)¬(¬P ∧¬Q)2,5¬E
7 (7)Q A
2 (8)¬Q 2 ∧ B
2,7 (9)Q ∧¬Q 7,8 ∧ E
7(10)¬(¬P ∧¬Q)2,9¬E
1(11)¬(¬P ∧¬Q)1,3,6,7,10 ∨ B

Argument 1.21 ¬(¬P ∧¬Q) ⊢ P ∨ Q

Beweis

1 (1)¬(¬P ∧¬Q) A
2 (2)¬(P ∨ Q) A
3 (3)P A
3 (4)P ∨ Q 3 ∨ E
2,3 (5)(P ∨ Q) ∧¬(P ∨ Q) 2,4 ∧ E
2 (6)¬P 3,5¬E
7 (7)Q A
7 (8)P ∨ Q 7 ∨ E
2,7 (9)(P ∨ Q) ∧¬(P ∨ Q) 2,8 ∧ E
2(10)¬Q 7,9¬E
2(11)¬P ∧¬Q 6,10 ∧ E
1,2(12)(¬P ∧¬Q) ∧¬(¬P ∧¬Q)1,11 ∧ E
1(13)¬¬(P ∨ Q) 2,12¬E
1(14)P ∨ Q 13¬¬B

Kapitel 2
Prdikatenlogik

2.1 Einfache Argumente

Für den Beginn wollen wir beweisen, dass alle Schweine rosa sind, soferne alle Schweine rosa sind und grunzen.

Argument 2.1 ∧ x(Sx → (Rx ∧ Gx)) ⊢∧ x(Sx → Rx)

Unter Zugrundelegung dieser Übersetzung lautet das Argument damit wie folgt: Alle Schweine sind rosa und grunzen ⊢ Alle Schweine sind rosa.

Beweis

1(1)∧ x(Sx → (Rx ∧ Gx))A
1(2)Su → (Ru ∧ Gu) 1∧ B
3(3)Su A
1,3(4)Ru ∧ Gu 2,3 → B
1,3(5)Ru 4 ∧ B
1(6)Su → Ru 3,5 → E
1(7)∧ x(Sx → Rx) 6∧ E

Argument 2.2 ∨ x(Fx ∨ Gx) ⊢∨ xFx ∨∨ xGx

Beweis

1 (1)∨ x(Fx ∨ Gx) A
2 (2)Fu ∨ Gu A
3 (3)Fu A
3 (4)∨ xFx 3∨ E
3 (5)∨ xFx ∨∨ xGx4 ∨ E
6 (6)Gu A
6 (7)∨ xGx 6∨ E
6 (8)∨ xFx ∨∨ xGx7 ∨ E
2 (9)∨ xFx ∨∨ xGx2,3,5,6,8 ∨ B
1(10)∨ xFx ∨∨ xGx1,2,9∨ B

Argument 2.3 ∨ xFx ∨∨ xGx ⊢∨ x(Fx ∨ Gx)

Beweis

1 (1)∨ xFx ∨∨ xGxA
2 (2)∨ xFx A
3 (3)Fu A
3 (4)Fu ∨ Gu 3 ∨ E
3 (5)∨ x(Fx ∨ Gx) 4∨ E
2 (6)∨ x(Fx ∨ Gx) 2,3,5∨ B
7 (7)∨ xGx A
8 (8)Gu A
8 (9)Fu ∨ Gu 8 ∨ E
8(10)∨ x(Fx ∨ Gx) 9∨ E
7(11)∨ x(Fx ∨ Gx) 7,8,10∨ B
1(12)∨ x(Fx ∨ Gx) 1,2,6,7,11 ∨ B

Argument 2.4 ∨ x(Fx ∧ Gx) ⊢∨ xFx ∧∨ xGx

Beweis

1(1)∨ x(Fx ∧ Gx) A
2(2)Fu ∧ Gu A
2(3)Fu 2 ∧ B
2(4)∨ xFx 3∨ E
2(5)Gu 2 ∧ B
2(6)∨ xGx 5∨ E
2(7)∨ xFx ∧∨ xGx4,6 ∧ E
1(8)∨ xFx ∧∨ xGx1,2,7∨ B

Die Umkehrung dieses Arguments ist nicht gültig:

Argument 2.5 ∨ xFx ∧∨ xGx ⁄⊢∨ x(Fx ∧ Gx).

Widerlegung Zur Widerlegung reicht die Interpretation von Fx als x ist ein Schaf und von Gx als x ist eine Kuh: Die Prämisse, Es gibt Schafe und Kühe, ist wahr, die Konklusion, Es gibt Schafe, die Kühe sind ist falsch.

Argument 2.6 ∧ xFx ∧∧ xGx ⊢∧ x(Fx ∧ Gx)

Beweis

1(1)∧ xFx ∧∧ xGxA
1(2)∧ xFx 1 ∧ B
1(3)Fu 2∧ B
1(4)∧ xGx 1 ∧ B
1(5)Gu 4∧ B
1(6)Fu ∧ Gu 3,5 ∧ E
1(7)∧ x(Fx ∧ Gx) 6∧ E

Argument 2.7 ∧ x(Fx ∧ Gx) ⊢∧ xFx ∧∧ xGx

Beweis

1(1)∧ x(Fx ∧ Gx) A
1(2)Fu ∧ Gu 1∧ B
1(3)Fu 2 ∧ B
1(4)∧ xFx 3∧ E
1(5)Gu 2 ∧ B
1(6)∧ xGx 5∧ E
1(7)∧ xFx ∧∧ xGx4,6 ∧ E

Argument 2.8 ∧ xFx ∨∧ xGx ⊢∧ x(Fx ∨ Gx)

Beweis

1 (1)∧ xFx ∨∧ xGxA
2 (2)∧ xFx A
2 (3)Fu 2∧ B
2 (4)Fu ∨ Gu 3 ∨ E
2 (5)∧ x(Fx ∨ Gx) 4∧ E
6 (6)∧ xGx A
6 (7)Gu 6∧ B
6 (8)Fu ∨ Gu 7 ∨ E
6 (9)∧ x(Fx ∨ Gx) 8∨ E
1(10)∧ x(Fx ∨ Gx) 1,2,5,6,9 ∨ B

Auch dieses Arguments Umkehrung ist nicht gültig:

Argument 2.9 ∧ x(Fx ∨ Gx) ⁄⊢∧ xFx ∨∧ xGx

Widerlegung: Legt man als Diskursuniversum die Menge der positiven natrlichen Zahlen zu Grunde und interpretiert man Fx als x ist eine gerade Zahl und Gx als x ist eine ungerade Zahl, dann ist die Prämisse, Alle Zahlen sind gerade oder ungerade, wahr, die Konklusion, Alle Zahlen sind gerade, oder alle Zahlen sind ungerade, aber falsch.

2.2 Logisches Quadrat

Instruktiv ist es, die Verhältnisse im logischen Quadrat einer Begutachtung zu unterziehen:

Argument 2.10 ∧ xFx ⊢∨ xFx

Beweis

1(1)∧ xFxA
1(2)Fu 1∧ B
1(3)∨ xFx2∨ E

Argument 2.11 ∧ xFx ⊢¬∧ x¬Fx

Beweis

1(1)∧ xFx A
2(2)∧ x¬Fx A
1(3)Fa 1∧ B
2(4)¬Fa 2∧ B
1,2(5)Fa ∧¬Fa3,4 ∧ E
1(6)¬∧ x¬Fx2,5¬E

Argument 2.12 ⊢¬∧ x¬Fx ↔∨ xFx

Beweis

1 (1)¬∧ x¬Fx A
2 (2)¬∨ xFx A
3 (3)Fu A
3 (4)∨ xFx 3∨ E
2,3 (5)∨ xFx ∧¬∨ xFx 2,4 ∧ E
2 (6)¬Fu 3,5¬E
2 (7)∧ x¬Fx 6∧ E
1,2 (8)∧ x¬Fx ∧¬∧ x¬Fx 1,7 ∧ E
1 (9)¬¬∨ xFx 2,8¬E
1(10)∨ xFx 9¬¬B
(11)¬∧ x¬Fx →∨ xFx 1,10 → E
12(12)∨ xFx A
13(13)∧ x¬Fx A
14(14)Fu A
13(15)¬Fu 13∧ B
13,14(16)Fu ∧¬Fu 14,15 ∧ E
14(17)¬∧ x¬Fx 13,16¬E
12(18)¬∧ x¬Fx 12,14,17∨ B
(19)∨ xFx →¬∧ x¬Fx 12,18 → E
(20)(¬∧ x¬Fx →∨ xFx)∧
(∨ xFx →¬∧ x¬Fx) 11,19 ∧ E
(21)∨ xFx ↔¬∧ x¬Fx 20D ↔

Argument 2.13 ⊢∧ xFx ↔¬∨ x¬Fx

Beweis

1 (1)∧ xFx A
2 (2)∨ x¬Fx A
3 (3)¬Fu A
1 (4)Fu 1∧ B
1,3 (5)Fu ∧¬Fu 3,4 ∧ E
3 (6)¬∧ xFx 1,5¬E
2 (7)¬∧ xFx 2,3,6∨ B
1,2 (8)∧ xFx ∧¬∧ xFx 1,7 ∧ E
1 (9)¬∨ x¬Fx 2,8¬E
(10)∧ xFx →¬∨ x¬Fx 1,9 → E
11(11)¬∨ x¬Fx A
12(12)¬∧ xFx A
13(13)¬Fu A
13(14)∨ x¬Fx 13∨ E
11,13(15)∨ x¬Fx ∧¬∨ x¬Fx 11,14 ∧ E
11(16)¬¬Fu 13,15¬E
11(17)Fu 16¬¬B
11(18)∧ xFx 17∧ E
(19)¬∨ x¬Fx →∧ xFx 11,18 → E
(20)(∧ xFx →¬∨ x¬Fx)∧
(¬∨ x¬Fx →∧ xFx) 10,19 ∧ E
(21)∧ xFx ↔¬∨ x¬Fx 20D ↔

2.3 Wissenswertes ber Relationen

Besonders die Besucherinnen meines Modallogik-Tutoriums werden es schätzen, sich einige elementare Sachverhalte betreffend Relationen vor Augen zu führen. Zur Erinnerung:

Argument 2.14 Jede transitive, symmetrische Relation ist auch euklidisch.

Beweis

1 (1)∧ x∧ y ∧ z(Rxy ∧ Ryz → Rxz)A
2 (2)∧ x∧ y(Rxy → Ryx) A
3 (3)Ruv ∧ Ruw A
3 (4)Ruv 3 ∧ B
2 (5)∧ y(Ruy → Ryu) 2∧ B
2 (6)Ruv → Rvu 5∧ B
2,3 (7)Rvu 4,6 → B
1 (8)∧ y ∧ z(Rvy ∧ Ryz → Rvz) 1∧ B
1 (9)∧ z(Rvu ∧ Ruz → Rvz) 8∧ B
1(10)Rvu ∧ Ruw → Rvw 9∧ B
3(11)Ruw 3 ∧ B
2,3(12)Rvu ∧ Ruw 7,11 ∧ E
1,2,3(13)Rvw 10,12 → B
1,2(14)Ruv ∧ Ruw → Rvw 3,13 → E
1,2(15)∧ z(Ruv ∧ Ruz → Rvz) 14∧ E
1,2(16)∧ y ∧ z(Ruy ∧ Ruz → Ryz) 15∧ E
1,2(17)∧ x∧ y ∧ z(Rxy ∧ Rxz → Ryz)16∧ E

Argument 2.15 Jede symmetrische, euklidische Relation ist auch transitiv.

Beweis

1 (1)∧ x∧ y ∧ z(Rxy ∧ Rxz → Ryz)A
2 (2)∧ x∧ y(Rxy → Ryx) A
3 (3)Ruv ∧ Rvw A
1 (4)∧ y ∧ z(Rvy ∧ Rvz → Ryz) 1∧ B
1 (5)∧ z(Rvu ∧ Rvz → Ruz) 4∧ B
1 (6)Rvu ∧ Rvw → Ruw 5∧ B
3 (7)Ruv 3 ∧ B
2 (8)∧ y(Ruy → Ryu) 2∧ B
2 (9)Ruv → Rvu 8∧ B
2,3(10)Rvu 7,9 → B
3(11)Rvw 3 ∧ B
2,3(12)Rvu ∧ Rvw 10,11 ∧ E
1,2,3(13)Ruw 6,12 → B
1,2(14)Ruv ∧ Rvw → Ruw 3,13 → E
1,2(15)∧ z(Ruv ∧ Rvz → Ruz) 14∧ E
1,2(16)∧ y ∧ z(Ruy ∧ Ryz → Ruz) 15∧ E
1,2(17)∧ x∧ y ∧ z(Rxy ∧ Ryz → Rxz)16∧ E