Beispiele zur Aussagenlogik

In diesem Artikel zeigen wir einige Formeln und ihre möglichen Belegungen mithilfe der Wahrheitstafel.

Erstes Beispiel

Wir versuchen herauszufinden, wann diese Formel wahr ist: ϕ = (p ∧ q) ∨ ¬q. Wir schreiben die Aussagenvariablen p und q in die Tabelle:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Dann schreiben wir in die Tabelle den ersten Teil der Formel dazu: (p ∧ q), die Negation ¬q und dann die ganze Formel:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Jetzt berechnen wir die Werte für die dritte Spalte, das ist eine einfache Konjunktion, und zugleich auch für die Negation – dort tragen wir nur die umgekehrten Werte der zweiten Spalte ein:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Zum Schluss berechnen wir die Werte in der letzten Spalte. Das ist die ganze Formel. Gemäß unserer Tabelle berechnen wir also die Disjunktion „zwischen der dritten und der vierten Spalte“. Ergebnis:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Zweites Beispiel

Gleiche Aufgabe, andere Formel: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Wir sehen, dass in der Formel die Aussagenvariablen p und q und ihre Negationen vorkommen. Als Erstes erstellen wir also eine Tabelle mit den zwei Variablen und ihren Negationen:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Weiter fügen wir die Formeln p ∧ ¬q und ¬p ⇒ q hinzu, die wir schon leicht auswerten können, weil wir in der Tabelle sowohl die Belegung der einzelnen Aussagen als auch ihrer Negationen haben. Die Tabelle sieht so aus:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Als Letztes müssen wir noch die ganze Formel auswerten, das ist die Äquivalenz zwischen den letzten beiden Spalten:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Drittes Beispiel

Das dritte Beispiel wird schon etwas komplizierter, wir probieren drei Aussagenvariablen aus, wodurch die Berechnung der Tabelle aufwendiger wird. Die Formel sieht so aus: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Weil wir dort drei Aussagenvariablen haben, ist die Gesamtzahl der Belegungen gleich acht:

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

Weiter gehen wir genauso vor wie im vorherigen Fall, jede Spalte werten wir in allen acht Zeilen aus. Die ganze Tabelle sieht so aus:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Viertes Beispiel

Dieses Beispiel geben wir nicht als gewöhnliche Formel vor, sondern als Textaufgabe. Drei Freunde, die auf eine wilde Party gehen wollen, auf der Models oberkörperfrei Getränke und Snacks verteilen, mögen sich nicht so ganz und stellen einander Bedingungen, unter denen sie auf die Party gehen. Sie heißen Marc, Jakob und Paul. Die Regeln lauten:

1. Wenn Marc geht, dann geht auch Jakob.
2. Auf die Party kommt Paul oder, wenn Marc dort hinkommt, dann kommt Jakob nicht.
3. Paul kommt genau dann, wenn Marc nicht kommt oder Jakob nicht kommt.

Die Frage lautet: Können alle auf die Party kommen? Wenn nicht, wer kann auf der Party vorbeischauen, ohne eine Regel zu verletzen?

Als Erstes müssen wir die vorherigen Aussagen in Aussagenvariablen und Formeln umschreiben. Bezeichnen wir also die Aussagenvariablen mit M, J und P (Marc, Jakob, Paul); sie stehen immer für eine Aussage der Art „Marc geht auf die Party“. Die erste Regel könnten wir so umschreiben: M ⇒ J – „wenn M, dann J“, oder „wenn Marc auf die Party geht, dann geht Jakob auf die Party“.

Die zweite Regel würden wir so umschreiben. Die Regel beginnt mit dem Satz „Auf die Party kommt Paul oder …“, also brauchen wir offensichtlich eine Disjunktion. Vorerst schreiben wir das auf: P ∨ … Der nächste Teil des Satzes sagt: „wenn Marc dort hinkommt, dann kommt Jakob nicht“. Das ist eine Implikation, wobei wir auf der rechten Seite noch eine Negation verwenden müssen. „Jakob kommt nicht“ = ¬J. Die ganze Implikation würde so aussehen: M ⇒ ¬J. Das fügen wir an die vorherige Disjunktion an: P ∨ (M ⇒ ¬J).

Die dritte Regel schreiben wir so um: Wir beginnen mit „Paul kommt genau dann“. Das bedeutet eine Äquivalenz: P ⇔ … Weiter haben wir „Marc kommt nicht oder Jakob kommt nicht“, was wir so umschreiben: ¬M ∨ ¬J. Zusammengesetzt: (P ⇔ (¬M ∨ ¬J)).

Jetzt setzen wir alle Formeln in die Tabelle ein und berechnen die Werte:

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

Die Frage lautete, ob alle drei Jungs auf die wilde Party gehen können. Die Antwort finden wir in der ersten Zeile. Sie entspricht dem Fall, dass alle Jungs gehen – das wird durch die drei Einsen in den ersten drei Spalten signalisiert. Sind alle Bedingungen erfüllt? Die erste ja (vierte Spalte), die zweite auch (fünfte Spalte), aber die letzte nicht (letzte Spalte), dort steht eine Null. Das bedeutet: Wenn alle drei gehen, ist die dritte Bedingung nicht erfüllt.

Wir suchen also die Zeilen, in denen an den Positionen, die die Bedingungen darstellen (d. h. in den letzten drei Spalten), lauter Einsen stehen. Eine Eins bedeutet, dass die Bedingung erfüllt ist. Wir sehen, dass das in zwei Fällen eintritt. Wenn Jakob und Paul gehen, Marc aber nicht, und dann, wenn nur Paul geht.

Du kannst es auch so berechnen, dass du der Tabelle die Formel ϕ hinzufügst, die die Konjunktion aller drei Bedingungen ist. Sie sieht also so aus: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Das stellt dar, was wir wollen – dass alle Formeln (alle Bedingungen) erfüllt sind. Die Tabelle würde dann so aussehen:

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Ein paar Beispiele zur Wahrheitstafel

Weil ich ein Programm geschrieben habe, das aus einer gegebenen Formel automatisch die ganze Tabelle erstellen kann, muss ich es auch ordentlich nutzen, und deshalb folgen noch ein paar gelöste Formeln:

Formel: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Tabelle:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Formel: (a ∨ ¬a) ⇔ (b ∧ ¬b). Tabelle:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Formel: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Tabelle:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Formel: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Tabelle:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Formel: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Tabelle:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$