Wahrheitstabellen

Eine **Wahrheitstabelle** listet **jede mögliche Kombination** von Wahrheitswerten der Variablen eines Ausdrucks auf und zeigt in jeder Zeile den Wert des ganzen Ausdrucks. **Wie viele Zeilen?** Jede Variable kann W (wahr) oder F (falsch) sein, also verdoppelt jede neue Variable die Anzahl der Zeilen: $$\text{Zeilen} = 2^n \quad (n = \text{Anzahl der Variablen})$$ 2 Variablen brauchen also $2^2 = 4$ Zeilen und 3 Variablen brauchen $2^3 = 8$ Zeilen. **Eine Tabelle in 4 Schritten aufstellen:** 1. Zähle die Variablen und schreibe $2^n$ leere Zeilen. 2. Fülle die Variablenspalten in fester Reihenfolge: Die erste Spalte ist zur Hälfte W, dann zur Hälfte F; jede weitere Spalte wechselt doppelt so oft; die letzte Spalte wechselt W, F, W, F. 3. Füge für jeden Teil des Ausdrucks eine **Hilfsspalte** hinzu, den innersten Teil zuerst (ein NICHT vor einer einzelnen Variable, dann die Klammern). 4. Kombiniere die Hilfsspalten zur Ergebnisspalte. **Beispiel:** $P \land \neg Q$ | $P$ | $Q$ | $\neg Q$ | $P \land \neg Q$ | |:---:|:---:|:---:|:---:| | W | W | F | F | | W | F | W | **W** | | F | W | F | F | | F | F | W | F | Die Ergebnisspalte verrät alles: Dieser Ausdruck ist in genau einer Zeile wahr, nämlich wenn $P$ wahr und $Q$ falsch ist. **Die Ergebnisspalte lesen:** - Nur W: Der Ausdruck ist eine **Tautologie** (immer wahr). - Nur F: Er ist ein **Widerspruch** (immer falsch). - Zwei Ausdrücke mit **derselben Ergebnisspalte in jeder Zeile** sind **logisch äquivalent**.

Eine Tabelle mit zwei Variablen

Stelle die Wahrheitstabelle für $P \lor \neg Q$ auf.

Zeilen zählen: Es gibt 2 Variablen, $P$ und $Q$, also brauchen wir $2^2 = 4$ Zeilen = 4 Zeilen

Variablenspalten füllen: $P$: W, W, F, F (halb W, halb F). $Q$: W, F, W, F (abwechselnd) = Alle 4 Kombinationen kommen genau einmal vor

Hilfsspalte $\neg Q$ hinzufügen: Kehre jeden Wert von $Q$ um: aus W, F, W, F wird F, W, F, W = $\neg Q$: F, W, F, W

Mit ODER verknüpfen: Zeile für Zeile: W ODER F = W, W ODER W = W, F ODER F = F, F ODER W = W = $P \lor \neg Q$: W, W, F, W

Answer: Die Ergebnisspalte ist W, W, F, W. Der Ausdruck ist nur in Zeile 3 falsch, wo $P$ falsch und $Q$ wahr ist.

Drei Variablen vorbereiten

Fülle die Variablenspalten einer Wahrheitstabelle für $P$, $Q$ und $R$ aus.

Zeilen zählen: 3 Variablen, also $2^3 = 2 \times 2 \times 2 = 8$ Zeilen = 8 Zeilen

Spalte $P$ füllen: Die Hälfte von 8 ist 4: viermal W, dann viermal F = $P$: W, W, W, W, F, F, F, F

Spalte $Q$ füllen: Doppelt so oft wechseln, in Zweierblöcken = $Q$: W, W, F, F, W, W, F, F

Spalte $R$ füllen: Die letzte Spalte wechselt in Einerblöcken = $R$: W, F, W, F, W, F, W, F

Answer: Die 8 Zeilen sind WWW, WWF, WFW, WFF, FWW, FWF, FFW, FFF. Jede Kombination kommt genau einmal vor und keine fehlt.

Ein Ausdruck mit drei Variablen

Stelle die Wahrheitstabelle für $(P \land Q) \lor \neg R$ auf. In wie vielen Zeilen ist der Ausdruck wahr?

8 Zeilen vorbereiten: Nutze die Reihenfolge aus dem vorigen Beispiel: $P$ in Viererblöcken, $Q$ in Zweierblöcken, $R$ abwechselnd = 8 Zeilen

Hilfsspalte $P \land Q$: UND ist nur wahr, wenn $P$ und $Q$ beide wahr sind: Zeilen 1 und 2 = $P \land Q$: W, W, F, F, F, F, F, F

Hilfsspalte $\neg R$: Kehre $R$ um: aus W, F, W, F, W, F, W, F wird F, W, F, W, F, W, F, W = $\neg R$: F, W, F, W, F, W, F, W

Mit ODER verknüpfen: Eine Zeile ist wahr, wenn mindestens eine Hilfsspalte W hat: Zeilen 1, 2, 4, 6, 8 = Ergebnis: W, W, F, W, F, W, F, W

Wahre Zeilen zählen: Zähle die W in der Ergebnisspalte = 5 Zeilen

Answer: Der Ausdruck ist in 5 der 8 Zeilen wahr und in den Zeilen 3, 5 und 7 falsch.

Tautologie, Widerspruch oder keins von beiden?

Ordne $P \lor \neg P$, $P \land \neg P$ und $(P \land Q) \lor \neg P$ ein.

$\neg P$ bestimmen: Mit einer Variable gibt es $2^1 = 2$ Zeilen. $P$: W, F, also $\neg P$: F, W = $\neg P$: F, W

$P \lor \neg P$ prüfen: W ODER F = W und F ODER W = W = Nur W: Tautologie

$P \land \neg P$ prüfen: W UND F = F und F UND W = F = Nur F: Widerspruch

$(P \land Q) \lor \neg P$ prüfen: 4 Zeilen. $P \land Q$: W, F, F, F. $\neg P$: F, F, W, W. ODER: W, F, W, W = Gemischt: keins von beiden

Answer: $P \lor \neg P$ ist eine Tautologie, $P \land \neg P$ ist ein Widerspruch, und $(P \land Q) \lor \neg P$ ist keins von beiden, weil der Ausdruck in Zeile 2 falsch ist.

Äquivalenz prüfen (De Morgan)

Sind $\neg(P \land Q)$ und $\neg P \lor \neg Q$ äquivalent? Und $\neg(P \land Q)$ und $\neg P \land \neg Q$?

Ergebnisspalte von $\neg(P \land Q)$: $P \land Q$: W, F, F, F. Umkehren = F, W, W, W

Ergebnisspalte von $\neg P \lor \neg Q$: $\neg P$: F, F, W, W. $\neg Q$: F, W, F, W. Zeile für Zeile mit ODER = F, W, W, W

Jede Zeile vergleichen: F = F, W = W, W = W, W = W = Gleich in allen 4 Zeilen: äquivalent

Ergebnisspalte von $\neg P \land \neg Q$: $\neg P$: F, F, W, W UND $\neg Q$: F, W, F, W = F, F, F, W: anders in den Zeilen 2 und 3

Answer: $\neg(P \land Q) \equiv \neg P \lor \neg Q$ (eines der De Morganschen Gesetze). Aber $\neg(P \land Q)$ und $\neg P \land \neg Q$ sind nicht äquivalent: Eine abweichende Zeile genügt.

Eine Wahrheitstabelle ist der zuverlässigste Weg, eine logische Aussage zu prüfen, weil sie keinen Fall auslässt: - **Programmieren**: Bevor eine Bedingung wie (Mitglied ODER Gutschein) UND NICHT gesperrt online geht, prüfen Tester jede Kombination der Eingaben - **Elektronik**: Ingenieure entwerfen Schaltungen mit Wahrheitstabellen und ersetzen eine komplizierte Schaltung durch eine einfachere, günstigere, die dasselbe leistet - **Sicherheit und Alarmanlagen**: Eine Alarmanlage mit 4 Sensoren hat $2^4 = 16$ mögliche Zustände, und in jedem davon muss sie richtig reagieren - **Argumente und Diskussionen**: Eine Wahrheitstabelle zeigt, ob zwei Sätze wirklich dasselbe bedeuten oder nur ähnlich klingen - **Rätsel und Spiele**: Logikrätsel löst man, indem man Zeilen ausschließt, die nicht wahr sein können Du weißt schon, wie UND, ODER und NICHT einzeln funktionieren. Mit Wahrheitstabellen kannst du sie zu beliebigen Ausdrücken kombinieren und dir trotzdem sicher sein, dass das Ergebnis stimmt.

Mistake: Zu wenige Zeilen schreiben, zum Beispiel 6 Zeilen für 3 Variablen

Why: Die Anzahl der Zeilen ist nicht $2 \times n$. Jede Variable verdoppelt die Anzahl der Kombinationen, also ergeben 3 Variablen $2 \times 2 \times 2 = 8$ Zeilen.

Correct: Nimm immer $2^n$ Zeilen: 4 für 2 Variablen, 8 für 3 Variablen, 16 für 4 Variablen.

Mistake: Die Variablenspalten in zufälliger Reihenfolge füllen

Why: Ohne System schreibt man leicht dieselbe Kombination zweimal und vergisst eine andere. Die Tabelle liefert dann ein falsches Urteil.

Correct: Nutze das feste Muster: erste Spalte in Blöcken der halben Zeilenzahl, jede weitere Spalte in halb so langen Blöcken, letzte Spalte abwechselnd W, F.

Mistake: $\neg P \land Q$ so behandeln, als wäre es $\neg(P \land Q)$

Why: Ohne Klammern bezieht sich NICHT nur auf die Variable direkt dahinter. Die Version mit Klammern kehrt das Ergebnis des ganzen UND um.

Correct: Lege eine Hilfsspalte für genau das an, worauf sich NICHT bezieht: nur $\neg P$, oder zuerst $P \land Q$ und dann dessen Verneinung.

Mistake: Zwei Ausdrücke für äquivalent halten, nachdem man nur einige Zeilen geprüft hat

Why: Zwei Ausdrücke können in mehreren Zeilen übereinstimmen und sich trotzdem in einer unterscheiden. $\neg(P \land Q)$ und $\neg P \land \neg Q$ stimmen in den Zeilen 1 und 4 überein, aber nicht in den Zeilen 2 und 3.

Correct: Vergleiche die Ergebnisspalten in jeder einzelnen Zeile. Äquivalent heißt: gleich in allen $2^n$ Zeilen.

Alarmanlagen

Sicherheitstechniker listen jeden Zustand der Sensoren auf, um sicherzugehen, dass die Alarmanlage in jedem Fall richtig reagiert.

Eine Alarmanlage mit 3 Türsensoren hat $2^3 = 8$ Zustände, von allen Türen geschlossen bis allen Türen offen.

Software testen

Programmierer testen eine Bedingung mit jeder Kombination von Eingaben, und genau das ist eine Wahrheitstabelle.

Eine Login-Regel (richtiges Passwort UND NICHT gesperrt) braucht $2^2 = 4$ Testfälle, um vollständig geprüft zu sein.

Schaltungen vereinfachen

Wenn zwei Schaltungen dieselbe Wahrheitstabelle haben, können Ingenieure die mit weniger oder günstigeren Bauteilen verwenden.

Mit den De Morganschen Gesetzen kann man ein NICHT-UND durch ein ODER aus zwei NICHT ersetzen, ohne zu ändern, was die Schaltung tut.

Eine Wahrheitstabelle listet jede Kombination von Wahrheitswerten und den Wert des Ausdrucks in jeder Zeile auf

Mit $n$ Variablen hat die Tabelle $2^n$ Zeilen: 4 bei 2 Variablen, 8 bei 3 Variablen

Fülle die Variablenspalten in fester Reihenfolge: zuerst Blöcke der halben Zeilenzahl, die letzte Spalte abwechselnd W, F

Nutze Hilfsspalten für jeden Teil des Ausdrucks, den innersten Teil zuerst

Nur W in der Ergebnisspalte bedeutet Tautologie, nur F bedeutet Widerspruch

Zwei Ausdrücke sind äquivalent, wenn ihre Ergebnisspalten in jeder Zeile übereinstimmen

Q: Warum verdoppelt jede neue Variable die Zeilen?

A: Jede bisherige Zeile lässt sich fortsetzen, indem die neue Variable W oder F ist. Jede Zeile teilt sich also in zwei: Aus 2 Zeilen werden 4, aus 4 werden 8 und so weiter, das ergibt $2^n$.

Q: Spielt die Reihenfolge der Zeilen eine Rolle?

A: Jede Reihenfolge ist richtig, solange jede Kombination genau einmal vorkommt. Die Standardreihenfolge (beginnend mit lauter W) macht das Prüfen und Vergleichen von Tabellen leicht. Manche Bücher beginnen stattdessen mit F; die Zeilen sind dieselben, nur umgekehrt aufgelistet. Die interaktiven Tabellen in dieser Lektion verwenden die Standardreihenfolge.

Q: Wie heißt ein Ausdruck, der weder Tautologie noch Widerspruch ist?

A: Man nennt ihn **erfüllbar, aber nicht allgemeingültig** (auch **Kontingenz**): Sein Wert hängt von den Eingaben ab. Die meisten alltäglichen Ausdrücke wie $P \land Q$ sind von dieser Art.

Q: Brauche ich immer Hilfsspalten?

A: Sie sind nicht vorgeschrieben, aber sie verhindern die meisten Fehler. Mit Übung kannst du kleine Schritte im Kopf zusammenfassen, doch bei 3 Variablen oder Klammern in Klammern sind Hilfsspalten der sicherste Weg.

Präsentation beenden

Wahrheitstabellen

1 / 14

Logik & Mengen / Boolesche Logik

Wahrheitstabellen

Lerne, Schritt für Schritt eine Wahrheitstabelle für einen zusammengesetzten Ausdruck aufzustellen und damit Tautologien, Widersprüche und äquivalente Ausdrücke zu erkennen.

Mittelstufe25 Min

Verwende Pfeiltasten oder Leertaste zum Navigieren