Aussagenlogik

Category: 

Die Aussagenlogik ist ein Teilgebiet der Logik, welches sich mit Aussagen und deren Verknüpfungen befasst. Die bekanntesten dieser Verknüpfungen sind selbstverständlich "und", sowie "oder". In der klassischen Aussagenlogik wird jede Aussage entweder zu "wahr" oder "falsch" ausgewertet ("true" oder "false" bzw. "1" oder "0").

Definition

Eine Aussage ist ein sprachliches Gebilde, von dem es sinnvoll ist zu sagen, es sei wahr oder falsch. - Aristoteles, griech. Mathematiker, 384-322 v.Chr.

Allgemein wird die klassische Logik durch zwei Eigenschaften charakterisiert:

  • Jede Aussage ist entweder wahr oder falsch (true/false bzw. 1/0).
  • Der Wahrheitswert jeder zusammengesetzten Aussage ist eindeutig durch die Wahrheitswerte der Teilaussagen bestimmt.

Beispiele für elementare Aussagen (auch Atome genannt):
"$2<3$" ist eine wahre Aussage.
"4 ist eine Primzahl" ist eine falsche Aussage.

Zusammengesetzte Aussagen

Zusammengesetzte Aussagen werden mit Hilfe von Junktoren gebildet.
Die einfachste zusammengesetzte Aussage ist die Negation (Zeichen: $\lnot$). Diese negiert den Wahrheitswert einer Aussage. D.h. aus wahr wird falsch und umgekehrt ($\lnot true=false$).

Betrachte wir nun die zweistelligen Junktoren der Aussagenlogik:
Die Konjunktion (Zeichen: $\land$) entspricht dem logischen "und". $A \land B$ ist genau dann wahr, wenn sowohl A, als auch B wahr sind.
Die Disjunktion (Zeichen: $\lor$) ist ein logisches "oder". $A \lor B$ ist wahr, wenn mindestens eine der beiden Aussagen wahr ist.
Eine Implikation (Zeichen: $\rightarrow$) entspricht dem "wenn ... dann ...". Hier ist ein wenig Vorsicht geboten, da z.B. $false \rightarrow true$ eine wahre Aussage ist. Denn aus einer falschen Aussage kann alles gefolgert werden. Falls jedoch die linke Seite wahr ist, so muss auch die rechte Seite wahr sein.
Die Äquivalenz entspricht dem "genau dann ..., wenn ..." und ist im Grunde eine Implikation in beide Richtungen.

$A$ $B$ $A \land B$ $A \lor B$ $A \rightarrow B$ $A \leftrightarrow B$
0 0 0 0 1 1
0 1 0 1 1 0
1 0 0 1 0 0
1 1 1 1 1 1

Abkürzungen

$A \rightarrow B$ ist gleichbedeutend mit $\lnot A \lor B$.
$A \leftrightarrow B$ ist gleichbedeutend mit $(A \rightarrow B) \land (B \rightarrow A)$.
$true = A \lor \lnot A$
$false = A \land \lnot A$

Rangfolge unterschiedlicher Operatoren

Wir können nun Aussagen beliebig verschachteln, jedoch wissen wir noch nicht in welcher Reihenfolge wir diese Auswerten sollen. Wie bei den Grundrechenarten auch ("Punkt vor Strichrechnung"), haben die Operatoren verschiedene Präzedenzen.
In der Logik wird die folgende Rangfolge verwendet:

  1. Negation (höchste Priorität)
  2. Konjunktion
  3. Disjunktion
  4. Implikation
  5. Äquivalenz (niedrigste Priorität)

D.h. die Formel $\lnot A \lor B \land C$ wird ausgewertet wie $(\lnot A) \lor (B \land C)$

Rangfolge gleichwertiger Operatoren

Zusätzlich wird für Operatoren eine Assoziativität festgelegt, mit der bestimmt wird, in welcher Reihenfolge nebeneinander stehende, gleichwertige Operatoren ausgewertet werden.
Grundsätzlich werden Junktoren als linksassoziativ betrachtet. D.h. der Ausdruck $A \land B \land C$ wird ausgewertet wie $(A \land B) \land C$.
Konjunktion, Disjunktion und Äquivalenz wird zwar als linksassoziativ betrachtet, jedoch stellt man schnell fest, dass es bei ihnen egal ist in welcher Reihenfolge man sie auswertet ($A \land (B \land C) = (A \land B) \land C$. Jedoch gilt dies nicht bei der Implikation! Daher muss man bei dieser streng darauf achten, in welcher Reihenfolge man sie auswertet.

Meistens wird die Implikation zwar als linksassoziativ betrachtet, jedoch gibt es einige Autoren und Professoren, welche die Implikation als rechtsassoziativ ansehen! Daher sollte man bei Implikationen die Reihenfolge durch Klammerung deutlich machen: $(A \rightarrow B) \rightarrow C$

Umformungsregeln

Aussagenlogische Formeln können sehr lang und unübersichtlich werden, daher bietet es sich manchmal an, die Formel so umzuformen, dass man sie leichter auswerten kann, ohne jedoch die Bedeutung zu verändern.
Seien $\alpha$, $\beta$ und $\gamma$ aussagenlogische Formeln, dann gelten die folgenden Regeln:

  • Negation: $\lnot \lnot \alpha = \alpha$
  • Idempotenz: $\alpha \lor \alpha = \alpha$, sowie $\alpha \land \alpha = \alpha$
  • Neutrales Element: $false \lor \alpha = \alpha$, sowie $true \land \alpha = \alpha$
  • Kontradiktion: $false \land \alpha = false$
  • Tautologie: $true \lor \alpha = true$
  • Kommutativität: $\alpha \lor \beta = \beta \lor \alpha$, bzw. $\alpha \land \beta = \beta \land \alpha$
  • Assoziativität: $(\alpha \lor \beta) \lor \gamma = \alpha \lor (\beta \lor \gamma)$, sowie $(\alpha \land \beta) \land \gamma = \alpha \land (\beta \land \gamma)$
  • Distributivität: $(\alpha \land \beta) \lor \gamma = (\alpha \lor \gamma) \land (\beta \lor \gamma)$, sowie $(\alpha \lor \beta) \land \gamma = (\alpha \land \gamma) \lor (\beta \land \gamma)$
  • De Morgan: $\lnot(\alpha \land \beta) = \lnot \alpha \lor \lnot \beta$, bzw. $\lnot(\alpha \lor \beta) = \lnot \alpha \land \lnot \beta$
  • Absorption: $\alpha \land (\alpha \lor \beta) = \alpha$, sowie $\alpha \lor (\alpha \land \beta) = \alpha$

Die Gültigkeit dieser Regeln lässt sich leicht durch Wahrheitstafeln zeigen.

Erfüllbarkeit

Abschließend möchte ich euch noch Definitionen zum Thema Erfüllbarkeit präsentieren.
Sei $\alpha$ eine aussagenlogische Formel.

  • $\alpha$ ist Erfüllbar, wenn es eine Belegung der Atome in $\alpha$ gibt, sodass $\alpha$ wahr wird.
  • $\alpha$ ist Tautologisch, wenn $\alpha$ für jede Belegung der Atome wahr wird.
  • $\alpha$ ist Falsifizierbar, wenn es eine Belegung der Atome in $\alpha$ gibt, sodass $\alpha$ falsch wird.
  • $\alpha$ ist Widerspruchsvoll, wenn $\alpha$ für jede Belegung der Atome falsch wird.

Das einzelne Atom $A$ ist z.B. sowohl erfüllbar, als auch falsifizierbar.
$A \land \lnot A$ ist Widerspruchsvoll (und damit auch falsifizierbar).
$A \lor \lnot A$ ist Tautologisch (und somit auch erfüllbar).

Damit sind wir auch schon am Ende des Artikels angelangt. Um euer Wissen zu diesem Thema zu vertiefen, bietet es sich an die Aufgaben auf der folgenden Seite zu lösen.