Assoziativgesetze

Bei der Disjunktion und bei der Konjunktion ist es egal, in welcher Reihenfolge du die Aussagen auswertest:

• ${\displaystyle (A\lor B)\lor C\Leftrightarrow A\lor (B\lor C)}$
• ${\displaystyle (A\land B)\land C\Leftrightarrow A\land (B\land C)}$

Kommutativgesetze

Bei der Disjunktion und bei der Konjunktion ist es egal, in welcher Reihenfolge die einzelnen Teilaussagen verknüpft werden. Dies ist in der deutschen Sprache nicht unbedingt der Fall. Betrachte dazu folgende zwei Aussagen, welche in der Bedeutung einen leichten Unterschied aufweisen: „Ralf aß Haferbrei und er bekam Bauchschmerzen“ und „Er bekam Bauchschmerzen und Ralf aß Haferbrei“.

• ${\displaystyle (A\lor B)\Leftrightarrow (B\lor A)}$
• ${\displaystyle (A\land B)\Leftrightarrow (B\land A)}$

Distributivgesetze

Eine Disjunktion kann in eine Konjunktion hineingezogen werden und umgekehrt.

• ${\displaystyle A\lor (B\land C)\Leftrightarrow (A\lor B)\land (A\lor C)}$
• ${\displaystyle A\land (B\lor C)\Leftrightarrow (A\land B)\lor (A\land C)}$

Absorptionsgesetze

• ${\displaystyle A\land (A\lor B)\Leftrightarrow A}$
• ${\displaystyle A\lor (A\land B)\Leftrightarrow A}$

Idempotenzgesetze

• ${\displaystyle A\land A\Leftrightarrow A}$
• ${\displaystyle A\lor A\Leftrightarrow A}$

Doppelte Verneinung

• ${\displaystyle \neg \neg A\Leftrightarrow A}$

Satz vom ausgeschlossenen Dritten

• ${\displaystyle A\lor \neg A}$ (lateinisch: tertium non datur, übersetzt: ein Drittes gibt es nicht.)

Satz vom Widerspruch

• ${\displaystyle \neg (A\land \neg A)}$

Durch Anwendung der de Morganschen Regel, der doppelten Verneinung und der Kommutativität lässt sich der Satz vom Widerspruch in den Satz vom ausgeschlossenen Dritten umformen: ${\displaystyle \neg (A\land \neg A)\iff \neg A\lor \neg \neg A\iff \neg A\lor A\iff A\lor \neg A}$

Die Morgansche Regel

Bei der Negation einer Und- beziehungsweise einer Oder-Verknüpfung wird die Negation reingezogen und die Klammer aufgelöst. Aus einem ${\displaystyle \land }$ wird dabei ein ${\displaystyle \lor }$ und umgekehrt.

• ${\displaystyle \neg (A\land B)\Leftrightarrow \neg A\lor \neg B}$
• ${\displaystyle \neg (A\lor B)\Leftrightarrow \neg A\land \neg B}$

Negation von Implikation und Äquivalenz

• ${\displaystyle \neg (A\Rightarrow B)\Leftrightarrow A\land \neg B}$
• ${\displaystyle \neg (A\Leftrightarrow B)\Leftrightarrow (A\Leftrightarrow \neg B)}$
• ${\displaystyle \neg (A\Leftrightarrow B)\Leftrightarrow (\neg A\Leftrightarrow B)}$

Prinzip der Kontraposition

Diese Äquivalenz wird oft genutzt, um eine Implikation zu beweisen, Redewendung: Beweis der Kontraposition.

• ${\displaystyle (A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)}$

Beweis durch Widerspruch

Auch mit Hilfe der folgenden Äquivalenz kann eine Implikation bewiesen werden, Redewendung: Beweis durch Widerspruch.

• ${\displaystyle (A\Rightarrow B)\Leftrightarrow \neg (A\land \neg B)}$
• ${\displaystyle (A\Rightarrow B)\Leftrightarrow (A\land \neg B)\Rightarrow {\mathsf {F}}}$

Darstellung von Implikation und Äquivalenz

Mit Hilfe dieser Gesetze kann die Implikation und die Äquivalenz auf Aussagen mit anderen Junktoren zurückgeführt werden.

• ${\displaystyle A\Rightarrow B\Leftrightarrow \neg A\lor B}$
• ${\displaystyle (A\Leftrightarrow B)\Leftrightarrow (A\Rightarrow B)\land (B\Rightarrow A)}$
• ${\displaystyle (A\Leftrightarrow B)\Leftrightarrow (\neg A\lor B)\land (A\lor \neg B)}$

Gesetze mit Wahr und Falsch

Im Folgenden steht ${\displaystyle {\mathsf {W}}}$ für „wahr“ und ${\displaystyle {\mathsf {F}}}$ für „falsch“. ${\displaystyle {\mathsf {W}}}$ und ${\displaystyle {\mathsf {F}}}$ können als 0-stellige Junktoren angesehen werden.

• ${\displaystyle {\mathsf {F}}\Rightarrow A}$ (Aus Falschem folgt Beliebiges.)
• ${\displaystyle A\Rightarrow {\mathsf {W}}}$
• ${\displaystyle A\land {\mathsf {W}}\Leftrightarrow A}$
• ${\displaystyle A\lor {\mathsf {F}}\Leftrightarrow A}$
• ${\displaystyle A\lor {\mathsf {W}}}$
• ${\displaystyle \neg (A\land {\mathsf {F}})}$
• ${\displaystyle \lnot A\Leftrightarrow (A\Rightarrow {\mathsf {F}})}$ (Wird gelegentlich als Definition für ${\displaystyle \neg }$ verwendet.)

Negation von quantifizierten Aussagen

• ${\displaystyle \neg (\forall x:A(x))\Leftrightarrow \exists x:\neg A(x)}$
• ${\displaystyle \neg (\forall x\in M:A(x))\Leftrightarrow \exists x\in M:\neg A(x)}$
• ${\displaystyle \neg (\exists x:A(x))\Leftrightarrow \forall x:\neg A(x)}$
• ${\displaystyle \neg (\exists x\in M:A(x))\Leftrightarrow \forall x\in M:\neg A(x)}$

Äquivalenzen über quantifizierte Aussagen

• ${\displaystyle \forall x:A(x)\Leftrightarrow \neg (\exists x:\neg A(x))}$
• ${\displaystyle \exists x:A(x)\Leftrightarrow \neg (\forall x:\neg A(x))}$
• ${\displaystyle \forall x:(A(x)\land B(x))\Leftrightarrow \forall x:A(x)\land \forall x:B(x)}$ (Distributivität ${\displaystyle \forall }$ mit ${\displaystyle \land }$)
• ${\displaystyle \exists x:(A(x)\lor B(x))\Leftrightarrow \exists x:A(x)\lor \exists y:B(y)}$ (Distributivität ${\displaystyle \exists }$ mit ${\displaystyle \lor }$)
• ${\displaystyle (\forall x:A(x)\Rightarrow C)\Leftrightarrow \exists x:(A(x)\Rightarrow C)}$
• ${\displaystyle (\exists x:A(x)\Rightarrow C)\Leftrightarrow \forall x:(A(x)\Rightarrow C)}$
• ${\displaystyle \exists !x:A(x)\Leftrightarrow \exists x:A(x)\land \forall x,y:(A(x)\land A(y)\Rightarrow x=y)}$ (Umschreibung des eindeutigen Existenzquantors)

Implikationen über quantifizierte Aussagen

• ${\displaystyle \forall x:A(x)\lor \forall x:B(x)\Rightarrow \forall x:(A(x)\lor B(x))}$
• ${\displaystyle \exists x:(A(x)\land B(x))\Rightarrow \exists x:A(x)\land \exists x:B(x)}$
• ${\displaystyle \forall x:(A(x)\Rightarrow B(x))\Rightarrow (\forall x:A(x)\Rightarrow \forall x:B(x))}$
• ${\displaystyle \forall x:(A(x)\Leftrightarrow B(x))\Rightarrow (\forall x:A(x)\Leftrightarrow \forall x:B(x))}$
• ${\displaystyle \exists x\forall y:A(x,y)\Rightarrow \forall y\exists x:A(x,y)}$