Aussagenlogik & Beweise: Übungsaufgaben mit Schritt-für-Schritt-Lösungen
Auch genannt: Aussagenlogik · Wahrheitstafel
Kostenlose Übungsaufgaben zu Aussagenlogik & Beweise mit Skizzen, Tipps und vollständigen Musterlösungen. Jedes Mal neue Werte, in drei Stufen: Wahrheitstafeln, Äquivalenzen und Beweismethoden, Quantoren und Argumente.
Kostenlose ÜbungsaufgabeLeicht
Vervollständige die Wahrheitstafel (1 = wahr, 0 = falsch). In wie vielen Zeilen N ist (p → r) ↔ (r ∨ q) wahr?
Eine Aussage ist eine Behauptung, die entweder wahr oder falsch ist, etwa „7 ist eine Primzahl“. Wir schreiben sie mit einem Buchstaben, p oder q, und ihren Wahrheitswert als 1 (wahr) oder 0 (falsch).
Junktoren bauen aus kleineren Formeln größere auf:
¬p (nicht p) kehrt den Wert um.
p ∧ q (und) ist nur 1, wenn beide 1 sind.
p ∨ q (oder) ist nur 0, wenn beide 0 sind. Es ist das einschließende Oder: Beide dürfen wahr sein.
p → q (wenn p, dann q) ist nur 0, wenn p = 1 und q = 0.
p ↔ q (genau dann, wenn) ist 1, wenn p und q denselben Wert haben.
Die Implikation überrascht viele Studierende: Ist p falsch, ist p → q wahr, egal was q ist. Ein Versprechen „Wenn es regnet, nehme ich einen Regenschirm mit“ wird nur an einem Regentag ohne Regenschirm gebrochen.
Selbsttest p = 0 und q = 1. Welchen Wert hat p → q?
0
1
Das hängt vom Zusammenhang ab
Nicht definiert
Antwort: 1. Eine Implikation ist nur falsch, wenn die Bedingung gilt und die Folgerung nicht (p = 1, q = 0). Bei p = 0 ist sie wahr, egal was q ist.
2Wahrheitstafeln
Eine Wahrheitstafel listet jede Kombination von Wahrheitswerten der Variablen auf. Bei n verschiedenen Variablen gibt es 2ⁿ Zeilen: 4 bei zwei Variablen, 8 bei drei, 16 bei vier. Eine Variable, die zweimal vorkommt, zählt trotzdem nur einmal.
Arbeite von innen nach außen. Gib jeder Teilformel eine eigene Spalte, sodass jede neue Spalte nur einen Junktor auf bereits vorhandene Spalten anwenden muss.
Liste die Variablen auf und schreibe alle 2ⁿ Kombinationen hin, beginnend mit lauter Einsen.
Füge für jede Teilformel eine Spalte hinzu, die innerste zuerst.
Fülle jede Spalte mit der Regel ihres Hauptjunktors.
Lies die Antwort aus der letzten Spalte ab: Zähle die Einsen oder finde die gesuchte Zeile.
Selbsttest Wie viele Zeilen hat die Wahrheitstafel von (p ∧ q) → (r ∨ p)?
16
4
6
8
Antwort: 8. Die Formel hat drei verschiedene Variablen, p, q und r, also 2³ = 8 Zeilen. p kommt zweimal vor, ist aber eine Variable; 16 wäre 2⁴ bei vier Vorkommen.
3Ein durchgerechnetes Beispiel
Folge jedem Schritt. Versuche, den nächsten vorherzusagen, bevor du ihn öffnest.
Durchgerechnetes Beispiel
In wie vielen Zeilen seiner Wahrheitstafel ist (p → q) ∧ ¬q wahr?
1
Variablen und Zeilen
Zwei Variablen, p und q, also 4 Zeilen: (1, 1), (1, 0), (0, 1), (0, 0).
2
Spalte p → q
Sie ist nur in der Zeile p = 1, q = 0 gleich 0:
p → q: 1, 0, 1, 1
3
Spalte ¬q
¬q: 0, 1, 0, 1
4
Die Konjunktion
Beide Spalten müssen 1 sein. Das passiert nur in der letzten Zeile, p = 0 und q = 0.
(p → q) ∧ ¬q: 0, 0, 0, 1
Antwort
Die Formel ist in 1 Zeile wahr, nämlich in der Zeile p = 0, q = 0. Deshalb ergeben p → q und ¬q zusammen ¬p (Modus tollens).
4Äquivalenzen und Beweismethoden
Zwei Formeln sind äquivalent (≡), wenn ihre Spalten in der Wahrheitstafel identisch sind. Eine Tautologie ist in jeder Zeile 1, eine Kontradiktion in jeder Zeile 0, und eine Kontingenz ist keines von beiden.
Die Gesetze, die du am häufigsten brauchst:
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p ¬(p → q) ≡ p ∧ ¬q
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Diese Gesetze sind die Grundlage der Beweismethoden. Ein Beweis durch Kontraposition von p → q beweist stattdessen ¬q → ¬p, was äquivalent ist. Ein Beweis durch Widerspruch nimmt p ∧ ¬q an, die einzige Möglichkeit, wie die Implikation scheitern kann, und leitet etwas Unmögliches her.
Achtung: Die Umkehrung q → p und die Inverse ¬p → ¬q sind nicht äquivalent zu p → q.
Selbsttest Welche Formel ist äquivalent zu ¬(p ∧ q)?
p ∨ q
¬p ∧ q
¬p ∧ ¬q
¬p ∨ ¬q
Antwort: ¬p ∨ ¬q. Nach De Morgan wird ∧ zu ∨, und beide Teile werden negiert. ¬p ∧ ¬q ist die Negation von p ∨ q, einer anderen Aussage: Sie ist falsch, wenn genau eines von p und q wahr ist, während ¬(p ∧ q) dann wahr ist.
5Quantoren und gültige Argumente
Bei Variablen über einem Grundbereich besagt ∀x P(x) „P gilt für jedes x“ und ∃x P(x) „P gilt für mindestens ein x“. Eine Negation vertauscht den Quantor:
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
Ziehe die Negation Schritt für Schritt nach innen; innen nutzt du die aussagenlogischen Gesetze. Zum Beispiel ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)): „Nicht jedes P ist ein Q“ bedeutet „manches P ist kein Q“.
Ein Argument ist gültig, wenn die Konklusion in jeder Zeile 1 ist, in der alle Prämissen 1 sind. Klassische gültige Formen sind Modus ponens (p → q, p, also q), Modus tollens (p → q, ¬q, also ¬p) und der hypothetische Syllogismus (p → q, q → r, also p → r).
Eine Zeile, in der alle Prämissen 1 und die Konklusion 0 sind, ist ein Gegenbeispiel. Die Bejahung des Konsequens (p → q, q, also p) ist ungültig: Die Zeile p = 0, q = 1 ist ein Gegenbeispiel.
Selbsttest Was ist die Negation von „jeder Student hat bestanden“, ∀x P(x)?
¬P(x) für einen festen Studenten x
∀x ¬P(x): Kein Student hat bestanden
∃x P(x): Manche Studierende haben bestanden
∃x ¬P(x): Manche Studierende haben nicht bestanden
Antwort: ∃x ¬P(x): Manche Studierende haben nicht bestanden. Ein durchgefallener Student genügt, damit „jeder Student hat bestanden“ falsch wird. „Kein Student hat bestanden“ ist viel stärker als die Negation.
6Häufige Fehler
p → q als falsch ansehen, wenn p falsch ist. Sie ist nur falsch, wenn p = 1 und q = 0.
Eine mehrfach vorkommende Variable bei der Zeilenzahl doppelt zählen.
Die Kontraposition ¬q → ¬p mit der Umkehrung q → p oder der Inversen ¬p → ¬q verwechseln.
¬∀x P(x) als ∀x ¬P(x) schreiben: Der Quantor muss zu ∃ wechseln.
¬(p ∧ q) als ¬p ∧ ¬q schreiben: De Morgan vertauscht auch den Junktor.
Selbsttest Welche Aussage ist die Kontraposition von „Wenn n² gerade ist, dann ist n gerade“?
Wenn n gerade ist, dann ist n² gerade
Wenn n ungerade ist, dann ist n² ungerade
Wenn n² ungerade ist, dann ist n ungerade
n² ist gerade und n ist ungerade
Antwort: Wenn n ungerade ist, dann ist n² ungerade. Vertausche die beiden Teile und negiere beide: nicht (n gerade) → nicht (n² gerade). „Wenn n gerade ist, dann ist n² gerade“ ist die Umkehrung; die letzte Option ist das, was ein Beweis durch Widerspruch annimmt.
7So sehen Prüfungsaufgaben aus
Leicht: Wahrheitstafeln. Du bestimmst die Zeilenzahl, zählst die Zeilen, in denen eine Formel wahr ist, oder klickst die eine Zeile an, die eine Formel wahr oder falsch macht.
Mittel: Äquivalenzen und Beweismethoden. Du entscheidest, ob eine Formel eine Tautologie, eine Kontradiktion oder eine Kontingenz ist, wählst die äquivalente Formel oder die Aussage, die bei einem Beweis durch Kontraposition oder durch Widerspruch zu beweisen ist.
Schwer: Quantoren und Argumente. Du negierst quantifizierte Aussagen, wählst die Konklusion, die aus Prämissen folgt, klickst die Gegenbeispiel-Zeile eines ungültigen Arguments an oder zählst wahre Zeilen in einer Tabelle mit vier Variablen.
Genau eine Zeile der Wahrheitstafel macht ¬(p ∨ q) → q falsch. Klicke diese Zeile an.
¬(p ∨ q) → q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
Tipps anzeigen
a → b ist nur 0, wenn a = 1 und b = 0. ¬a kehrt den Wert um. a ∨ b ist nur 0, wenn beide 0 sind.
Bestimme zuerst den Hauptjunktor: Wie müssen seine beiden Seiten aussehen, damit die ganze Formel 0 ist?
Gib jedem Teil eine eigene Spalte: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Antwort und Erklärung anzeigen
Wahrheitstafeln: Eine Formel mit n verschiedenen Variablen hat 2ⁿ Zeilen, eine für jede Kombination von Wahrheitswerten (1 = wahr, 0 = falsch). Arbeite von innen nach außen und gib jeder Teilformel eine eigene Spalte. ¬a kehrt den Wert um; a ∧ b ist nur 1, wenn beide 1 sind; a ∨ b ist nur 0, wenn beide 0 sind; a → b ist nur 0, wenn a = 1 und b = 0; a ↔ b ist 1, wenn beide Seiten gleich sind.
Welche Formel ist logisch äquivalent zu (b ∧ c) → a? Klicke sie an.
(b ∧ c) → a
1(b → a) ∧ (c → a)
2b → (c → a)
3b ∧ (c → a)
4(b → c) → a
Tipps anzeigen
Äquivalente Formeln stimmen in jeder Zeile der Wahrheitstafel überein. Eine Zeile, in der sie sich unterscheiden, schließt eine Option aus.
Probiere eine Zeile, die (b ∧ c) → a zu 0 macht, und prüfe, welche Optionen dort ebenfalls 0 sind.
Exportation: (a ∧ b) → c ≡ a → (b → c). Beide sind nur 0, wenn a = 1, b = 1 und c = 0.
Antwort und Erklärung anzeigen
Logische Äquivalenz: Zwei Formeln sind äquivalent (≡), wenn sie in jeder Zeile der Wahrheitstafel denselben Wert haben. Eine Tautologie ist in jeder Zeile 1, eine Kontradiktion in jeder Zeile 0, und eine Kontingenz ist keines von beiden. Nützliche Gesetze: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b und ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (Kontraposition); ¬(a → b) ≡ a ∧ ¬b; und die Distributivgesetze, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Das Gesetz
Exportation: (a ∧ b) → c ≡ a → (b → c). Beide sind nur 0, wenn a = 1, b = 1 und c = 0.
(b ∧ c) → a ≡ b → (c → a)
Mit der Wahrheitstafel prüfen
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0
Antwort
b → (c → a)
Die Spalten nach dem Strich sind die Optionen in der angezeigten Reihenfolge.
Beispiel 3Schwer
Die Prämissen (q ∧ p) → r; q; ¬r sind gegeben. Welche Konklusion folgt daraus? Klicke sie an.
(q ∧ p) → rq¬r
1p
2p ∧ ¬r
3¬p
4r
Tipps anzeigen
Eine Konklusion folgt, wenn sie in jeder Zeile 1 ist, in der alle Prämissen 1 sind.
Finde die Zeilen, in denen alle Prämissen 1 sind, und teste dann jede Option in diesen Zeilen.
Das ist eine Standardregel: Modus tollens mit einer Konjunktion.
Antwort und Erklärung anzeigen
Quantoren und Argumente: ¬∀x P(x) ≡ ∃x ¬P(x) und ¬∃x P(x) ≡ ∀x ¬P(x). Ziehe eine Negation nach innen, vertausche jeden Quantor, den sie passiert, und negiere die innere Formel mit den aussagenlogischen Gesetzen, etwa ¬(a → b) ≡ a ∧ ¬b. Ein Argument ist gültig, wenn die Konklusion in jeder Zeile 1 ist, in der alle Prämissen 1 sind. Eine einzige Zeile mit wahren Prämissen und falscher Konklusion ist ein Gegenbeispiel und zeigt, dass das Argument ungültig ist.
Zeilen, in denen alle Prämissen wahr sind
p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0
Schlussfolgerung
¬p (Modus tollens mit einer Konjunktion)
Antwort
¬p
Fragen und Antworten
Aussagenlogik & Beweise: Worum geht es?
Eine Aussage ist eine Behauptung, die entweder wahr oder falsch ist, etwa „7 ist eine Primzahl“. Wir schreiben sie mit einem Buchstaben, p oder q, und ihren Wahrheitswert als 1 (wahr) oder 0 (falsch).
Junktoren bauen aus kleineren Formeln größere auf:
Aussagenlogik & Beweise: Wie löst man die Aufgaben Schritt für Schritt?
Zähle die verschiedenen Variablen: Die Wahrheitstafel hat 2ⁿ Zeilen und beginnt mit lauter Einsen.
Gib jeder Teilformel eine eigene Spalte und fülle die Spalten von innen nach außen.
Wende die Regel jedes Junktors an: → ist nur bei 1 → 0 gleich 0, ↔ ist 1, wenn beide Seiten übereinstimmen.
Vergleiche bei Äquivalenzen die letzten Spalten Zeile für Zeile; schau bei einem Argument nur auf die Zeilen, in denen alle Prämissen 1 sind.
Um eine quantifizierte Aussage zu negieren, ziehe ¬ nach innen, vertausche ∀ und ∃ und negiere die innere Formel.
Aussagenlogik & Beweise: Welche Fehler passieren am häufigsten?
p → q als falsch ansehen, wenn p falsch ist.
Eine mehrfach vorkommende Variable bei der Zeilenzahl doppelt zählen.
Die Kontraposition ¬q → ¬p mit der Umkehrung q → p verwechseln.
¬∀x P(x) als ∀x ¬P(x) statt als ∃x ¬P(x) schreiben.
De Morgan anwenden, ohne ∧ und ∨ zu vertauschen.
Aussagenlogik & Beweise: Was wird geübt?
Leicht: Wahrheitstafeln
Mittel: Äquivalenzen und Beweismethoden
Schwer: Quantoren und Argumente
Jede Aufgabe hat neue Werte, so lernst du den Lösungsweg statt einer Antwort. Du hängst fest? Öffne zuerst einen kleinen Tipp und die vollständige Erklärung erst, wenn du sie brauchst.
So funktioniert das Üben
Jede Aufgabe hat neue Werte, so lernst du den Lösungsweg statt einer Antwort.
Du hängst fest? Öffne zuerst einen kleinen Tipp und die vollständige Erklärung erst, wenn du sie brauchst.
Dein Fortschritt, deine Fehler und gespeicherten Aufgaben bleiben erhalten, damit du vor der Prüfung wiederholen kannst.