Gleichheit von Ausdrücken

Die Aufgabe

Zeigen oder widerlegen Sie die Gleichheit der nachfolgenden Ausdrücke:

(i)

p \Rightarrow q = \neg p \lor q

(ii)

p \Leftrightarrow q = (p \land q) \lor (\neg p \land \neg q)

Gegeben sind zwei Gleichungen zwischen Ausdrücken. Für jede ist zu entscheiden: Stimmt sie (zeigen) oder stimmt sie nicht (widerlegen)?

Jede Gleichung hat zwei Seiten: Was vor dem Gleichheitszeichen steht, heißt linke Seite, was dahinter steht, rechte Seite.

Vor dem Gleichheitszeichen steht beide Male $\Rightarrow$ oder $\Leftrightarrow$ . Dahinter steht ein Ausdruck, der nur $\neg$ , $\land$ und $\lor$ benutzt.

Das Gleichheitszeichen trennt die beiden Seiten, es gehört nicht zum Ausdruck. Gemeint ist $(p \Rightarrow q) = (\neg p \lor q)$ . Das Skript schreibt dafür auch $\Leftrightarrow$ .

So gehen wir vor:

Klären, was „gleich“ heißt und wie man zeigt oder widerlegt.
(i) beide Seiten in einer Tafel ausrechnen und Zeile für Zeile vergleichen.
(ii) genauso.

Merke: Zum Zeigen braucht man alle Zeilen. Zum Widerlegen reicht eine Zeile, in der die Seiten verschieden sind.

Gleich heißt: gleiche Spalte in jeder Zeile

Beispiel zum Widerlegen (nicht aus der Aufgabe): ist p ⇒ q = q ⇒ p?

\begin{aligned} &\text{Zeile 3: } p = 1,\ q = 0 \\ &p \Rightarrow q\ \text{ wird zu }\ 1 \Rightarrow 0,\ \text{ also } 0 \\ &q \Rightarrow p\ \text{ wird zu }\ 0 \Rightarrow 1,\ \text{ also } 1 \end{aligned}

Eine Zeile mit 0 gegen 1 genügt: $p \Rightarrow q$ und $q \Rightarrow p$ sind nicht gleich.

In der Vorlesung heißen zwei Ausdrücke $A$ und $B$ gleich, wenn $A \Leftrightarrow B$ eine Tautologie ist. Eine Tautologie ist ein Ausdruck, der in jeder Zeile 1 ist.

$A \Leftrightarrow B$ ist 1, wenn $A$ und $B$ denselben Wert haben. Also heißt gleich: Die Spalten von $A$ und $B$ stimmen in jeder Zeile überein.

Zum Widerlegen sucht man dagegen eine einzige Zeile, in der sie verschieden sind. Der Lösungsweg zeigt das an einem Paar, das nicht zur Aufgabe gehört.

Die linke Seite p ⇒ q

Zeile für Zeile

p \Rightarrow q:\ 1,\,1,\,0,\,1

Aus Aufgabe 1 („Wahrheitstafeln aufstellen“):

p \Rightarrow q

ist nur falsch, wenn

p = 1

und

q = 0

p \Leftrightarrow q

ist 1, wenn beide denselben Wert haben. Zwei Variablen ergeben

2 \cdot 2 = 4

Zeilen: Zeile 1 bis 4 sind

p

q

= 0 0, 0 1, 1 0, 1 1. Jede Folge wie 1, 1, 0, 1 nennt die Werte in dieser Reihenfolge.

Die linke Seite $p \Rightarrow q$ liest man direkt ab: nur Zeile 3 ( $p = 1$ , $q = 0$ ) ist 0.

Gleichheit von Ausdrücken

Die Aufgabe

Gleich heißt: gleiche Spalte in jeder Zeile

Die linke Seite p ⇒ q

Tafel zu (i)

Abbildung 1Tafel zu (i)

Schritt 0Die Aufgabe

Schritt 1Gleich heißt: gleiche Spalte in jeder Zeile

Schritt 2Die linke Seite p ⇒ q

Tafel zu (i)

Abbildung 1Tafel zu (i)

Die Aufgabe

Gleich heißt: gleiche Spalte in jeder Zeile

Die linke Seite p ⇒ q