Aussagenlogische Formeln und Tautologien
In der Aussagenlogik werden aus Aussagenvariablen A0, A1, A2, … und den Zeichen ⊥ und ⊤ mit Hilfe der Junktoren ¬, ∧, ∨, ⩒, →, ↔ und der Klammernsymbole aussagenlogische Formeln wie zum Beispiel
(A0 ∧ A1) → A3, ¬ A0 → ⊥, …
gebildet. Eine Formel ist eine nach syntaktischen Regeln korrekt gebildete Zeichenkette. Genauer sind Formeln durch die folgenden Schemata definiert:
(a) | Jede Aussagenvariable ist eine Formel. |
(b) | ⊥ und ⊤ sind Formeln. |
(c) | Sind A und B Formeln, so sind auch ¬ A, (A ∧ B), (A ∨ B), (A ⩒ B), (A → B), (A ↔ B) Formeln. |
Beispiele
Für alle Aussagenvariablen A, B sind
A, (A ∧ B), ¬ (A ∧ B), ((A ∧ B) → ⊥), ¬(⊥ ↔ (A → A))
Formeln. Allgemeiner sind diese Ausdrücke Formeln, wenn A und B Formeln sind. Keine Formeln sind dagegen
A B, A →→ B, A ¬ B, ((A ∧ B)).
Um Klammern zu sparen, lassen wir äußere Klammern weg und vereinbaren folgende Bindungsstärke (von stark nach schwach):
¬, ∧, ∨, ⩒, →, ↔(Bindungsstärke der Junktoren).
Die Junktoren können wir uns als Magnete mit unterschiedlicher Stärke vorstellen. Die stärkste Kraft hat die Negation, am schwächsten ist die Äquivalenz. Diese Anordnung hat sich bewährt, um die Anzahl der Klammern zu reduzieren.
Eine zusätzliche Vereinbarung ist Rechtsklammerung bei Ketten mit dem gleichen Junktor:
| A ∧ B ∧ C | ist | A ∧ (B ∧ C), |
| A ∨ B ∨ C | ist | A ∨ (B ∨ C), |
| A → B → C | ist | A → (B → C) usw. |
In den folgenden Beispielen setzen wir unnötige Klammern, um den Aufbau der Formeln zu illustrieren.
Beispiele
| ¬ A → B | ist | (¬ A) → B, |
| A ∧ B ∨ C | ist | (A ∧ B) ∨ C, |
| A → B ↔ C | ist | (A → B) ↔ C, |
| A → B ↔ ¬ B → ¬ A | ist | (A → B) ↔ (¬ B → ¬ A). |
Mit Hilfe unserer Junktoren lassen sich neue Junktoren definieren, etwa ein „weder noch“ A ↓ B als ¬ A ∧ ¬ B. Umgekehrt können wir uns zum Beispiel mit ¬ und ∧ begnügen und A ∨ B als ¬ (¬ A ∨ ¬ B), A → B als ¬ A ∨ B, A ↔ B als (A → B) ∧ (B → A), A ⩒ B als ¬ (A ↔ B) definieren.
Wahrheitstafeln
Jede aussagenlogische Formel lässt sich mit Hilfe des Wahrheitstafelverfahrens auswerten. Hierzu wird jeder Aussagenvariablen der Formel der Wert „f“ für „falsch“ oder „w“ für „wahr“ zugewiesen (neutraler können wir natürlich auch mit 0 und 1 arbeiten). Zudem erhält ein Falsum ⊥ immer den Wert f und ein Verum ⊤ immer den Wert w. Der Gesamtwert der Formel für eine w-f-Belegung wird mit Hilfe der folgenden Tafeln für die Junktoren bestimmt:
¬ | A |
f | w |
w | f |
A | ∧ | B |
w | w | w |
w | f | f |
f | f | w |
f | f | f |
A | ∨ | B |
w | w | w |
w | w | f |
f | w | w |
f | f | f |
A | ⩒ | B |
w | f | w |
w | w | f |
f | w | w |
f | f | f |
A | → | B |
w | w | w |
w | f | f |
f | w | w |
f | w | f |
A | ↔ | B |
w | w | w |
w | f | f |
f | f | w |
f | w | f |
Kommen in der Formel genau n verschiedene Aussagenvariablen vor, so gibt es genau 2n w-f-Belegungen. Die gemäß ihrem Aufbau erfolgte schrittweise Auswertung der Formel lässt sich entsprechend durch eine Wahrheitstafel mit 2n Zeilen darstellen. Wir betrachten einige Beispiele.
Beispiele
¬ | ¬ | A | ↔ | A |
w | f | w | w | w |
f | w | f | w | f |
2 | 1 |
| 4 | 3 |
¬ | A | ↔ | A | → | ⊥ |
f | w | w | w | f | f |
w | f | w | f | w | f |
1 |
| 3 |
| 2 |
A | → | B | ↔ | B | → | A |
w | w | w | w | w | w | w |
w | f | f | f | f | w | w |
f | w | w | f | w | f | f |
f | w | f | w | f | w | f |
| 1 |
| 3 |
| 2 |
|
A | → | (B | → | C) | ↔ | A | ∧ | B | → | C |
w | w | w | w | w | w | w | w | w | w | w |
w | f | w | f | f | w | w | w | w | f | f |
w | w | f | w | w | w | w | f | f | w | w |
f | w | w | w | w | w | f | f | w | w | w |
w | w | f | w | f | w | w | f | f | w | f |
f | w | w | f | f | w | f | f | w | w | f |
f | w | f | w | w | w | f | f | f | w | w |
f | w | f | w | f | w | f | f | f | w | f |
| 2 |
| 1 |
| 5 |
| 3 |
| 4 |
|
Die Zahlen in den untersten Zeilen der Tafeln geben die Reihenfolge der Auswertung an. Ist die letzte Spalte der Auswertung durchgehend mit dem Wert „w“ gefüllt, so nennen wir die Formel eine (aussagenlogische) Tautologie. Weiter heißen zwei Formeln A und B logisch äquivalent, in Zeichen A ≡ B, wenn die Formel A ↔ B eine Tautologie ist. Ist A eine Formel derart, dass ¬ A eine Tautologie ist, so heißt A eine Kontradiktion.
Die folgende Tabelle versammelt einige Beispiele für Tautologien.
Tautologie | Name |
¬ ¬ A ↔ A | Stabilität, duplex negatio affirmat |
A ∨ ¬ A | Gesetz vom ausgeschlossenen Dritten, tertium non datur |
⊥ ↔ A ∧ ¬ A | |
⊥ → A | ex falso quodlibet |
¬ A ↔ A → ⊥ | Negation als Implikation |
(A → B) ∧ (B → C) → (A → C) | Kettenschluss |
A ∧ (A → B) → B | modus ponens, tautologische Form |
¬ B ∧ (A → B) → ¬ A | modus tollens, tautologische Form |
(A → B) ↔ (¬ B → ¬ A) | Kontrapositionsgesetz |
(B → A) ∧ (¬ B → A) ↔ A | Fallunterscheidung |
¬ (A → B) ↔ A ∧ ¬ B | |
¬ A → B ↔ A ∨ B | |
¬ (A ∧ B) ↔ ¬ A ∨ ¬ B ¬ (A ∨ B) ↔ ¬ A ∧ ¬ B | de Morgansche Regeln |
A ∨ (B ∧ C) ↔ (A ∨ B) ∧ (A ∨ C) A ∧ (B ∨ C) ↔ (A ∧ B) ∨ (A ∧ C) | Distributivgesetze |
(A ↔ B) ↔ (¬ A ↔ ¬ B) | |
¬ (A ↔ B) ↔ A ⩒ B | nicht äquivalent ist entweder oder |
A → (B → C) ↔ A ∧ B → C A → (B → C) ↔ B → (A → C) | Implikationsketten |
(A → C) ∧ (B → C) ↔ (A ∨ B) → C | |
(A → C) ∨ (B → C) ↔ (A ∧ B) → C | |
(A → B) ∧ (A → C) ↔ A → B ∧ C | |
(A → B) ∨ (A → C) ↔ A → B ∨ C |