Aussagenlogik

Rechenregeln der Aussagenlogik

Satz: Rechenregeln der Aussagenlogik

Seien \(P, Q\) und \(R\) aussagenlogische Ausdrücke. Dann gelten die folgenden Rechenregeln:

1. Assoziativgesetze: \[(P \land Q) \land R \equiv P \land (Q \land R)\] \[(P \lor Q) \lor R \equiv P \lor (Q \lor R)\]
2. Kommutativgesetze: \[P \land Q \equiv Q \land P\] \[P \lor Q \equiv Q \lor P\]
3. Distributivgesetze: \[P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)\] \[P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)\]

Beweis:

Wir zeigen durch die Verwendung von Wahrheitstafeln, dass die Distributivgesetze gelten:

Damit ist gezeigt, dass \(P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)\) gilt.

Damit ist gezeigt, dass \(P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)\) gilt. \(\square\)

Die folgenden Gesetze des britischen Mathematikers Augustus de Morgan formulieren einen Zusammenhang zwischen der Negation und der Konjunktion bzw. Disjunktion.

Satz: Gesetze von de Morgan

Seien \(P\) und \(Q\) aussagenlogische Formeln. Dann gilt: \[\neg (P \land Q) \equiv \neg P \lor \neg Q\] und \[\neg (P \lor Q) \equiv \neg P \land \neg Q\]

Beweis:

Wir beweisen die Aussage durch die Anwendung von Wahrheitstafeln. Es ist:

Der Beweis des zweiten Gesetzes ist nach selben Schema durchzuführen. \(\square\)

Es ist zu beachten, dass die Gesetze von de Morgan verallgemeinert werden können.

Satz: Verallgemeinerung der Gesetze von de Morgan

Seien \(P_1, \dots, P_n\) aussagenlogische Asdrücke. Dann gilt: \[\neg (P_1 \land P_2 \land \dots \land P_n) \equiv \neg P_1 \lor \neg P_2 \lor \dots \lor \neg P_n\] und \[\neg (P_1 \lor P_2 \lor \dots \lor P_n) \equiv \neg P_1 \land \neg P_2 \land \dots \land \neg P_n\]

Beweis:

Weil Konjunktion und Disjunktion assoziativ sind und weil die Gesetze von de Morgan gelten, folgt: \[\neg (P_1 \land P_2 \land \dots \land P_n) \equiv \neg (P_1 \land (P_2 \land (\dots (P_{n-1} \land P_n))))\] \[\equiv \neg P_1 \lor \neg (P_2 \land (\dots (P_{n-1} \land P_n)))\] \[\equiv \neg P_1 \lor \neg P_2 \lor \neg (\dots (P_{n-1} \land P_n))\] \[\equiv \neg P_1 \lor \neg P_2 \lor \dots \lor \neg P_{n-1} \lor \neg P_n\] und \[\neg (P_1 \lor P_2 \lor \dots \lor P_n) \equiv \neg (P_1 \lor (P_2 \lor (\dots (P_{n-1} \lor P_n))))\] \[\equiv \neg P_1 \land \neg (P_2 \lor (\dots (P_{n-1} \lor P_n)))\] \[\equiv \neg P_1 \land \neg P_2 \land \neg (\dots (P_{n-1} \lor P_n))\] \[\equiv \neg P_1 \land \neg P_2 \land \dots \land \neg P_{n-1} \land \neg P_n\] \(\square\)

Neben den Gesetzen von de Morgan sowie den Assoziativ-, Kommutativ- und Distributivgesetzen existieren noch eine Reihe weiterer wichtiger Rechenregeln.

Satz: Weitere Rechenregeln der Aussagenlogik

Seien \(P\) und \(Q\) aussagenlogische Ausdrücke. Dann gelten die folgenden Regeln:

1. Identität der Konjunktion: \(P \land 1 \equiv P\)
2. Neutralität der Konjunktion: \(P \land 0 \equiv 0\)
3. Neutralität der Disjunktion: \(P \lor 1 \equiv 1\)
4. Identität der Disjunktion: \(P \lor 0 \equiv P\)
5. Doppelte Negation: \(\neg \neg P \equiv P\)
6. Idempotenz der Konjunktion: \(P \land P \equiv P\)
7. Idempotenz der Disjunktion: \(P \lor P \equiv P\)
8. Kontradiktion: \(P \land \neg P \equiv 0\)
9. Tautologie: \(P \lor \neg P \equiv 1\)
10. Absorption bezüglich der Konjunktion: \(P \land (P \lor Q) \equiv P\)
11. Absorption bezüglich der Disjunktion: \(P \lor (P \land Q) \equiv P\)
12. Absorption bezüglich der Konjunktion mit Negation: \(P \land (\neg P \lor Q) \equiv P \land Q\)
13. Absorption bezüglich der Disjunktion mit Negation: \(P \lor (\neg P \land Q) \equiv P \lor Q\)
14. Umwandlung der Implikation in eine Disjunktion: \(P \Rightarrow Q \equiv \neg P \lor Q\)
15. Umwandlung der Äquivalenz in eine Konjunktion: \(P \Leftrightarrow Q \equiv (\neg P \lor Q) \land (P \lor \neg Q)\)
16. Umwandlung der Äquivalenz in eine Disjunktion: \(P \Leftrightarrow Q \equiv (P \land Q) \lor (\neg P \land \neg Q)\)

Beweis:

Die Beweise zu 1. - 4. sind trivial.

Die Beweise zu 8. und 9. (Kontradiktion und Tautologie) wurden bereits zuvor geführt. Die restlichen Aussagen zeigen wir mithilfe von Wahrheitstafeln:

zu 5.:
Mit

zu 6.:
Mit

zu 7.:
Mit

zu 10.:
Mit

zu 11.:
Mit

zu 12.:
Mit

zu 13.:
Mit

zu 14.:
Mit

zu 15.:
Mit

zu 16.:
Mit