Aussagenlogik

Aussagen und logische Verknüpfungen

Die Logik entstand als Modell für das menschliche logische Denken. Sie beschäftigt sich mit den Prinzipien zum Ziehen von Schlussfolgerungen, mit der Gültigkeit von Begründungen und Widerspruchsfreiheit von Aussagen, mit der formalen Darstellung für die Form von Begründungen und mit dem Wahrheitsbegriff in abstrakter Form. Die Wurzeln der Logik gehen bis in die Antike auf den Philosophen Aristoteles zurück.

Definition: Logische Aussage

Eine logische Aussage (oder kurz Aussage) ist ein Satz, für den entscheidbar ist, ob er wahr oder falsch ist.

Anstelle von wahr verwendet man in der Informatik häufig auch true oder 1, anstelle von falsch schreibt man häufig false oder 0. In der Logik interessiert man sich im Allgemeinen nicht für den Inhalt einer Aussage, sondern nur dafür, ob sie wahr oder falsch ist. Man spricht hierbei auch vom Warheitswert einer Aussage.

Beispiele:

"4 ist eine ungerade Zahl" ist eine falsche Aussage.

"Wasser ist nass" ist eine wahre Aussage.

"Guten Tag" ist keine Aussage, weil dieser Satz weder wahr noch falsch ist.

"\(x\) ist eine ungerade Zahl" ist ebenfalls keine Aussage, weil ohne zusätzliche Informationen nicht entschieden werden kann, ob \(x\) gerade oder ungerade ist. Erst wenn wir \(x\) mit einer Zahl belegen, wird daraus eine Aussage, die wahr oder falsch sein kann. "3 ist eine ungerade Zahl" wäre dementsprechend eine wahre Aussage, während "4 ist eine ungerade Zahl" eine falsche Aussage ist.

Definition: Logische Äquivalenz von Aussagen

Seien \(A\) und \(B\) Aussagen. \(A\) und \(B\) heißen logisch äquivalent, wenn sie denselben Wahrheitswert besitzen. Man schreibt dafür \(A \equiv B\) und sagt "\(A\) ist logisch äquivalent zu \(B\) ".

Es ist zu beachten, dass sich die logische Äquivalenz von Aussagen nicht auf deren Inhalt, sondern nur auf ihren Wahrheitswert bezieht! Das folgende Beispiel soll dies verdeutlichen.

Beispiel: Logische Äquivalenz von Aussagen

Seien \(A_1\) und \(A_2\) Aussagen mit \(A_1\) := "7 ist eine ungerade Zahl" und \(A_2\) := "Nachts ist es dunkel". Die Aussagen sind inhaltlich verschieden, es ist also \(A_1 \not = A_2\). Dennoch sind \(A_1\) und \(A_2\) aussagenlogisch äquivalent (denn beide sind wahr), es gilt also \(A_1 \equiv A_2\).

In der Literatur werden Aussagen, die denselben Wahrheitswert besitzen, häufig auch als gleich bezeichnet. Viele Autoren nutzen statt \(\equiv\) hierfür das Symbol \(=\). Hier wird bewusst obige Definition verwendet, um Missverständnisse zu vermeiden.

Durch logische Operatoren (auch Junktoren oder Verknüpfungen genannt) lassen sich logische Aussagen zu sogenannten aussagenlogischen Formeln oder Ausdrücken verknüpfen. Wir unterscheiden dabei fünf Arten von Verknüpfungen.

Definition: Konjunktion

Seien \(A\) und \(B\) Aussagen. Die Konjunktion (auch und-Verknüpfung genannt) von \(A\) und \(B\) wird geschrieben als \(A \land B\) oder \(A\) AND \(B\) oder (abgekürzt) \(AB\). Ausgesprochen wird dies "\(A\) und \(B\) ".

\(A \land B\) ist genau dann (und nur dann) wahr, wenn beide Aussagen \(A\) und \(B\) wahr sind. Ist mindestens eine der Aussagen falsch, so ist auch \(A \land B\) falsch.

Beispiel: Konjunktion

Sei
\(A\) := "7 ist ein gerade Zahl",
\(B\) := "3 ist größer als 4",
\(C\) := "7 ist eine ungerade Zahl" und
\(D\) := "4 ist größer als 3".
Dann sind die Aussagen \(A\) und \(B\) falsch und die Aussagen \(C\) und \(D\) wahr.

Damit ist \(A \land B\) offensichtlich falsch, denn beide Aussagen \(A\) und \(B\) sind falsch.

Ebenso ist \(A \land C\) falsch, denn mindestens eine der beiden Aussagen, nämlich \(A\), ist falsch.

\(C \land D\) ist hingegen wahr, denn beide Aussagen \(C\) und \(D\) sind wahr.

Definition: Disjunktion

Seien \(A\) und \(B\) Aussagen. Die Disjunktion (auch oder-Verknüpfung genannt) von \(A\) und \(B\) wird geschrieben als \(A \lor B\) oder \(A\) OR \(B\). Ausgesprochen wird dies "\(A\) oder \(B\) ".

\(A \lor B\) ist genau dann wahr, wenn mindestens eine der beiden Aussagen wahr ist. Nur wenn beide Aussagen falsch sind, ist auch \(A \lor B\) falsch.

Beispiel: Disjunktion

Sei
\(A\) := "7 ist ein gerade Zahl",
\(B\) := "3 ist größer als 4",
\(C\) := "7 ist eine ungerade Zahl" und
\(D\) := "4 ist größer als 3".
Dann sind die Aussagen \(A\) und \(B\) falsch und die Aussagen \(C\) und \(D\) wahr.

\(A \lor B\) ist falsch, denn sowohl \(A\) als auch \(B\) sind falsch.

\(A \lor C\) ist hingegen wahr, denn mindestens eine der beiden Aussagen, nämlich \(C\), ist wahr.

\(C \lor D\) ist ebenfalls wahr, denn in dieser aussagenlogischen Formel sind alle vorkommenden Aussagen wahr.

Definition: Negation

Sei \(A\) eine Aussage. Die Negation (auch nicht-Verknüpfung genannt) von \(A\) wird geschrieben als \(\neg A\) oder NOT \(A\) oder \(\overline{\rm A}\). Ausgesprochen wird dies "nicht \(A\)".

\(\neg A\) ist genau dann wahr, wenn \(A\) falsch ist und genau dann falsch, wenn \(A\) wahr ist.

Beispiel: Negation

Sei
\(A\) := "7 ist ein gerade Zahl" und
\(D\) := "4 ist größer als 3".
Dann ist Aussage \(A\) falsch und Aussage \(D\) wahr.

\(\neg A\) ist somit wahr, denn \(A\) ist eine falsche Aussage. Entsprechend ist \(\neg D\) falsch, weil \(D\) eine wahre Aussage ist.

Definition: Implikation

Seien \(A\) und \(B\) Aussagen. Die Implikation (auch wenn-dann-Verknüpfung oder Subjunktion genannt) von \(A\) und \(B\) wird geschrieben als \(A \Rightarrow B\). Ausgesprochen wird dies "aus \(A\) folgt \(B\) " oder "\(A\) impliziert \(B\) ".

\(A \Rightarrow B\) ist genau dann (und nur dann) falsch, wenn \(A\) wahr und \(B\) falsch ist (denn aus einer wahren Aussage kann keine falsche Aussage folgen). In jedem anderen Fall, also wenn \(A\) und \(B\) beide wahr sind oder wenn \(A\) falsch ist und \(B\) entweder wahr oder falsch ist, ist \(A \Rightarrow B\) wahr. Letzteres begründet sich dadurch, dass aus einer falschen Aussage alles (also sowohl eine wahre als auch eine falsche Aussage) folgen kann.

In der gängigen Literatur wird statt \(\Rightarrow\) auch häufig das Symbol \(\rightarrow\) für die Implikation verwendet. Beide Zeichen bedeuten das gleiche.

Beispiel: Implikation

Sei
\(A\) := "7 ist ein gerade Zahl",
\(B\) := "3 ist größer als 4",
\(C\) := "7 ist eine ungerade Zahl" und
\(D\) := "4 ist größer als 3".
Dann sind die Aussagen \(A\) und \(B\) falsch und die Aussagen \(C\) und \(D\) wahr.

Die Implikation \(A \Rightarrow B\) ist wahr, denn \(A\) ist eine falsche Aussage und aus einer solchen kann alles folgen. Demnach wäre auch \(A \Rightarrow C\) wahr.

Hingegen ist die Implikation \(C \Rightarrow A\) falsch, denn \(C\) ist eine wahre und \(A\) eine falsche Aussage, aber aus einer wahren Aussage darf niemals eine falsche folgen.

\(C \Rightarrow D\) ist wahr, denn sowohl \(C\) als auch \(D\) sind wahr.

Dieses Beispiel verdeutlicht noch einmal, dass wir uns zunächst tatsächlich nur für den Wahrheitsgehalt einer Aussage, aber nicht für deren Inhalt interessieren. Dieser spielt bei der Betrachtung, ob eine aussagenlogische Formel wahr oder falsch ist, keine Rolle.

Definition: Äquivalenz

Seien \(A\) und \(B\) Aussagen. Die Äquivalenz (auch genau-dann-wenn-Verknüpfung oder Bijunktion genannt) von \(A\) und \(B\) wird geschrieben als \(A \Leftrightarrow B\). Ausgesprochen wird dies "\(A\) genau dann wenn \(B\) " oder "\(A\) äquivalent \(B\) ".

\(A \Leftrightarrow B\) ist genau dann falsch, wenn eine der beide Aussagen wahr und die andere Aussage falsch ist. Andernfalls, also wenn beide Aussagen wahr oder beide Aussagen falsch sind, ist \(A \Leftrightarrow B\) wahr.

In der gängigen Literatur wird statt \(\Leftrightarrow\) häufig das Symbol \(\leftrightarrow\) für die Äquivalenz verwendet. Beide Zeichen bedeuten das gleiche.

Beispiel: Äquivalenz

Sei
\(A\) := "7 ist ein gerade Zahl",
\(B\) := "3 ist größer als 4",
\(C\) := "7 ist eine ungerade Zahl" und
\(D\) := "4 ist größer als 3".
Dann sind die Aussagen \(A\) und \(B\) falsch und die Aussagen \(C\) und \(D\) wahr.

Die Äquivalenz \(A \Leftrightarrow B\) ist wahr, denn sowohl \(A\) als auch \(B\) sind falsch. Ebenso ist \(C \Leftrightarrow D\) wahr, denn sowohl \(C\) als auch \(D\) sind wahr.

Hingegen ist \(A \Leftrightarrow C\) falsch, denn \(A\) ist falsch und \(C\) ist wahr.

Bitte verwechseln Sie nicht die Äquivalenz \(\Leftrightarrow\) mit der logischen Äquivalenz \(\equiv\)! Durch \(\Leftrightarrow\) werden Aussagen zu aussagenlogischen Formeln verknüpft (die selbst wiederum einen Wahrheitswert besitzen), durch \(\equiv\) wird angezeigt, dass zwei Aussagen denselben Wahrheitswert haben.

Definition: Aussagenlogische Formel

Durch die logischen Operatoren (auch Junktoren oder Verknüpfungen genannt)

• \(\land\) (Konjunktion),
• \(\lor\) (Disjunktion),
• \(\neg\) (Negation),
• \(\Rightarrow\) (Implikation) und
• \(\Leftrightarrow\) (Bijunktion)

• \(0, 1 \in \mathcal{A}\)
• Für jede Aussage \(A\) ist \(A \in \mathcal{A}\)
• Wenn \(A, B \in \mathcal{A}\) sind, dann liegen auch die folgenden Ausdrücke in \(\mathcal{A}\):
  • \(A \land B\)
  • \(A \lor B\)
  • \(\neg A\)
  • \(A \Rightarrow B\)
  • \(A \Leftrightarrow B\)
  • \((A)\)

Der \(()\)-Operator beeinflusst dabei - wie in der Mathematik üblich - die Bindungsstärke der Operatoren. Geklammerte Ausdrücke werden stets von innen nach außen aufgelöst.

Die einzelnen logischen Aussagen einer solchen Formel nennen wir atomare Operanden, Aussagenvariablen oder kurz Variablen der Formel.

Beispiel: Aussagenlogische Formel

Seien \(A, B\) und \(C\) logische Aussagen. Dann können wir diese durch logische Operatoren zu einer aussagenlogischen Formel verknüpfen:

1. Die aussagenlogische Formel \(A \land B\) enthält die atomaren Operanden \(A\) und \(B\), die durch eine Konjunktion verknüpft werden. Abgekürzt könnten wir diesen Ausdruck auch schreiben als \(AB\).


2. Die aussagenlogische Formel \(((\neg A) \land B) \lor C\) enthält die atomaren Operanden \(A, B\) und \(C\). Die Klammern werden von innen nach außen aufgelöst, d.h., zuerst wird \(A\) durch den Negations-Operator negiert und danach durch eine Konjunktion mit \(B\) verknüpft. Dieser Teilausdruck wird anschließend mit \(C\) durch eine Disjunktion verknüpft. Abgekürzt könnten wir diesen Ausdruck auch schreiben als \(\overline{\rm A}B \lor C\).


3. \(A\) ist ebenfalls eine (sehr einfache) aussagenlogische Formel, in der nur die Variable \(A\) und keine logischen Operatoren vorkommen. Wir nennen solche Ausdrücke atomar. Formeln, in denen hingegen mindestens ein logischer Operator vorkommt, heißen zusammengesetzt.

Definition: Logisch äquivalent

Zwei aussagenlogische Ausdrücke \(P\) und \(Q\) heißen logisch äquivalent, wenn \(P\) und \(Q\) stets denselben Wahrheitswert besitzen. Man schreibt dafür \(P \equiv Q\).

Es ist der Unterschied zwischen = und \(\equiv\) zu beachten! Zwei aussagenlogische Ausdrücke müssen nicht gleich sein, um logisch äquivalent sein zu können. Das folgende Beispiel soll dies verdeutlichen.

Beispiel: Logisch äquivalent

Seien drei Aussagen \(A, B\) und \(C\) gegeben mit
\(A\) := "7 ist eine gerade Zahl",
\(B\) := "Nachts ist es dunkel" und
\(C\) := "Wasser ist nass".
Offensichtlich ist die Aussage \(A\) falsch, die Aussagen \(B\) und \(C\) sind richtig.

1. Es ist \(B \equiv C\), denn beide Aussagen können wir als atomare Ausdrücke auffassen und beide sind richtig.


2. Wir können mit diesen Aussagen auch zusammengesetzte aussagenlogische Ausdrücke bilden, z.B. \(P := A \land B\) und \(Q := A \land C\). Dann ist \(P \not = Q\), denn die Ausdrücke enthalten unterschiedliche Aussagen. Dennoch gilt \(P \equiv Q\), denn \(P\) und \(Q\) haben den gleichen Wahrheitswert. Beide sind falsch, denn \(A \land B\) ist falsch (weil \(A\) falsch und \(B\) wahr ist) und \(A \land C\) ist ebenfalls falsch (weil \(A\) falsch und \(C\) wahr ist).

Am vorherigen Beispiel wird deutlich, warum wir auch für Aussagen, die den gleichen Wahrheitswert besitzen, den \(\equiv\) Operator gewählt haben: Da wir jede Aussage als atomaren Ausdruck auffassen können, ist die Definition der logischen Äquivalenz von Aussagen somit konsistent zur Definition der logischen Äquivalenz von Ausdrücken. Dieser Sachverhalt macht vieles leichter, da wir nicht mehr sklavisch zwischen Aussagen und Ausdrücken unterscheiden müssen, sondern vieles allgemeiner - nämlich für Ausdrücke - zeigen und einfach auf Aussagen übertragen können.

Vereinbarung: Präzedenzen der logischen Operatoren

Um in aussagenlogischen Formeln Klammern zu sparen, vereinbaren wir die folgende Bindungsstärke für logische Operatoren:
\[\neg \text{ vor } \land \text{ vor } \lor \text{ vor } \Rightarrow \text{ vor } \Leftrightarrow\]

Somit hat der Negationsoperator \(\neg\) die höchste Bindungsstärke, die Äquivalenz \(\Leftrightarrow\) die niedrigste.

Beispiele: Präzedenz der logischen Operatoren

1. \((\neg (\neg A)) \lor B\) ist logisch äquivalent zu \(\neg \neg A \lor B\), also \((\neg (\neg A)) \lor B \equiv \neg \neg A \lor B\).


2. \(((\neg A) \land B) \lor C\) ist logisch äquivalent zu \(\neg A \land B \lor C\), also \(((\neg A) \land B) \lor C \equiv \neg A \land B \lor C\).


3. \((A \lor B) \Rightarrow (C \land D)\) ist logisch äquivalent zu \(A \lor B \Rightarrow C \land D\), also \((A \lor B) \Rightarrow (C \land D) \equiv A \lor B \Rightarrow C \land D\).