Lektion 2.4

Wichtige Äquivalenzen

15 min Lesezeit

Oft drücken verschiedene Formeln denselben Sachverhalt aus. "Es regnet nicht oder die Straße ist nass" und "Wenn es regnet, ist die Straße nass" haben unter jeder Belegung denselben Wahrheitswert.

Solche Formeln nennen wir logisch äquivalent. Das Erkennen von Äquivalenzen erlaubt uns, Aussagen umzuformen – zum Beispiel in eine einfachere Form.

Definition

Logische Äquivalenz

Zwei Aussagen heißen logisch äquivalent, wenn sie unter jeder Belegung denselben Wahrheitswert haben.

Schreibweise: $A \equiv B$

Beispiel: $A \rightarrow B \equiv \neg A \lor B$

"Wenn A, dann B" ist dasselbe wie "Nicht A oder B".

\varphi \equiv \psi \;\text{bedeutet: gleiche Wahrheitswerte}

Definition

De Morgansche Regeln

Die De Morganschen Regeln sind fundamental:

$\neg(A \land B) \equiv \neg A \lor \neg B$

$\neg(A \lor B) \equiv \neg A \land \neg B$

In Worten:
- Die Negation von "A und B" ist "nicht A oder nicht B"
- Die Negation von "A oder B" ist "nicht A und nicht B"

Diese Regeln haben wir bereits bei Mengen gesehen!

\neg(A \land B) \equiv \neg A \lor \neg B

Beispiel

De Morgan anwenden

"Es ist nicht der Fall, dass ich Hunger habe und müde bin."

Mit De Morgan: "Ich habe keinen Hunger oder ich bin nicht müde."

Noch ein Beispiel:
"Es ist nicht der Fall, dass die Ampel rot oder gelb ist."

Mit De Morgan: "Die Ampel ist nicht rot und nicht gelb."

(Also muss sie grün sein!)

Definition

Kontraposition

Die Kontraposition ist eine wichtige Äquivalenz:

$A \rightarrow B \equiv \neg B \rightarrow \neg A$

In Worten: "Wenn A, dann B" ist äquivalent zu "Wenn nicht B, dann nicht A".

Beispiel:
"Wenn es regnet, ist die Straße nass."
≡ "Wenn die Straße nicht nass ist, regnet es nicht."

A \rightarrow B \equiv \neg B \rightarrow \neg A

Zusammenfassung

Logisch äquivalente Aussagen haben immer denselben Wahrheitswert
De Morgan: $\neg(A \land B) \equiv \neg A \lor \neg B$
De Morgan: $\neg(A \lor B) \equiv \neg A \land \neg B$
Kontraposition: $A \rightarrow B \equiv \neg B \rightarrow \neg A$

Übungen

Aufgabe 1Multiple Choice

Was ist äquivalent zu $\neg(A \lor B)$ ?

$\neg A \lor \neg B$

$\neg A \land \neg B$

$A \land B$

$\neg A \rightarrow B$

Wichtige Äquivalenzen

Oft drücken verschiedene Formeln denselben Sachverhalt aus. "Es regnet nicht oder die Straße ist nass" und "Wenn es regnet, ist die Straße nass" haben unter jeder Belegung denselben Wahrheitswert.

Solche Formeln nennen wir logisch äquivalent. Das Erkennen von Äquivalenzen erlaubt uns, Aussagen umzuformen – zum Beispiel in eine einfachere Form.

Definition

Logische Äquivalenz

Zwei Aussagen heißen logisch äquivalent, wenn sie unter jeder Belegung denselben Wahrheitswert haben.

Schreibweise: $A \equiv B$

Beispiel: $A \rightarrow B \equiv \neg A \lor B$

"Wenn A, dann B" ist dasselbe wie "Nicht A oder B".

\varphi \equiv \psi \;\text{bedeutet: gleiche Wahrheitswerte}

Definition

De Morgansche Regeln

Die De Morganschen Regeln sind fundamental:

$\neg(A \land B) \equiv \neg A \lor \neg B$

$\neg(A \lor B) \equiv \neg A \land \neg B$

In Worten:
- Die Negation von "A und B" ist "nicht A oder nicht B"
- Die Negation von "A oder B" ist "nicht A und nicht B"

Diese Regeln haben wir bereits bei Mengen gesehen!

\neg(A \land B) \equiv \neg A \lor \neg B

Beispiel

De Morgan anwenden

"Es ist nicht der Fall, dass ich Hunger habe und müde bin."

Mit De Morgan: "Ich habe keinen Hunger oder ich bin nicht müde."

Noch ein Beispiel:
"Es ist nicht der Fall, dass die Ampel rot oder gelb ist."

Mit De Morgan: "Die Ampel ist nicht rot und nicht gelb."

(Also muss sie grün sein!)

Definition

Kontraposition

Die Kontraposition ist eine wichtige Äquivalenz:

$A \rightarrow B \equiv \neg B \rightarrow \neg A$

In Worten: "Wenn A, dann B" ist äquivalent zu "Wenn nicht B, dann nicht A".

Beispiel:
"Wenn es regnet, ist die Straße nass."
≡ "Wenn die Straße nicht nass ist, regnet es nicht."

A \rightarrow B \equiv \neg B \rightarrow \neg A

Zusammenfassung

Logisch äquivalente Aussagen haben immer denselben Wahrheitswert
De Morgan: $\neg(A \land B) \equiv \neg A \lor \neg B$
De Morgan: $\neg(A \lor B) \equiv \neg A \land \neg B$
Kontraposition: $A \rightarrow B \equiv \neg B \rightarrow \neg A$

—