01 Aussagenlogik

1. Aussagenlogik

1.1 Aussagen

Definition: Aussage

Ein Satz, welcher wahr oder falsch ist, bzw. der genau einen der Wahrheitswerte “wahr” oder “falsch” hat. Schreibweisen: w/f, t/f, 1/0

Wichtig: Eine Aussage muss nicht bekanntermaßen wahr oder falsch sein — sie muss nur tatsächlich einen der beiden Wahrheitswerte besitzen (auch wenn wir den Beweis (noch) nicht kennen).

Beispiele:

• “5 ist Primzahl” → wahr
• “4 ist Primzahl” → falsch
• “Jede gerade Zahl > 2 ist Summe zweier Primzahlen” (Vermutung von Goldbach, 1742) → bis heute unbewiesen, aber es ist eine Aussage (sie ist entweder wahr oder falsch, wir wissen es nur nicht)
• “Die Gleichung $x^2+y^2=z^2$ ist in positiven ganzen Zahlen lösbar” → wahr (z.B. 3,4,5)
• “Für kein $n\ge 3$ ist die Gleichung $x^n+y^n=z^n$ in positiven ganzen Zahlen x,y,z lösbar” (Vermutung von Fermat, 1640) → wahr (Satz von Wiles, Beweis ist extrem komplex)
• “Die Länder einer Landkarte lassen sich so mit höchstens 4 Farben färben, dass Länder mit gemeinsamer Grenzlinie verschiedene Farben bekommen” → wahr (4-Farbensatz)

Diese Beispiele zeigen: Der Schwierigkeitsgrad des Beweises hat nichts mit der Frage zu tun, ob etwas eine Aussage ist.

---

1.2 Verknüpfungen von Aussagen

Sind $p,q$ Aussagen, so sind auch folgende Ausdrücke Aussagen:

Symbol	Name	Sprechweise
$p\wedge q$	Konjunktion	”p und q”
$p\vee q$	Disjunktion	”p oder q”
$\neg p$	Negation	”nicht p”
$p\to q$	Implikation	”p impliziert q”
$p\leftrightarrow q$	Äquivalenz	”p genau dann, wenn q”

Wahrheitstabelle:

$$\begin{array}{ccccccc}p& q& p\wedge q& p\vee q& \neg p& p\to q& p\leftrightarrow q\\ w& w& w& w& f& w& w\\ w& f& f& w& f& f& f\\ f& w& f& w& w& w& f\\ f& f& f& f& w& w& w\end{array}$$

Merke zur Implikation

$p\to q$ ist nur dann falsch, wenn $p$ wahr und $q$ falsch ist. Insbesondere ist “aus Falschem folgt Beliebiges” — ist $p$ falsch, ist $p\to q$ immer wahr, unabhängig vom Wahrheitswert von $q$.

Begriffe

• Aussagenlogische Variable: Eine Variable, die den Wert w oder f annehmen kann (z.B. $p,q,r$).
• Aussagenformel: Entsteht ausgehend von aussagenlogischen Variablen durch Verknüpfung mit $\wedge ,\vee ,\neg ,\to ,\leftrightarrow$.
• Belegung: Eine Zuordnung eines Wahrheitswertes (w/f) zu jeder Variable.
  • Bei $n$ Variablen gibt es genau $2^n$ mögliche Belegungen.
• Wahrheitsverlauf: Beschreibt, welchen Wahrheitswert eine Formel bei jeder der $2^n$ möglichen Belegungen annimmt.

---

1.3 Tautologie und Kontradiktion

Tautologie

Eine Aussageformel, deren Wahrheitsverlauf konstant wahr ist. Beispiel: $p\vee (\neg p)$ — entweder p oder nicht-p ist immer wahr.

Kontradiktion

Eine Aussageformel, deren Wahrheitsverlauf konstant falsch ist. Beispiel: $p\wedge (\neg p)$ — p und nicht-p können nie gleichzeitig wahr sein.

Beispiel: Kontraposition ist eine Tautologie

$(p\to q)⟷((\neg q)\to (\neg p))$

Beweis per Wahrheitstabelle:

$$\begin{array}{ccccccc}p& q& p\to q& \neg q& \neg p& (\neg q)\to (\neg p)& (p\to q)\leftrightarrow ((\neg q)\to (\neg p))\\ w& w& w& f& f& w& w\\ w& f& f& w& f& f& w\\ f& w& w& f& w& w& w\\ f& f& w& w& w& w& w\end{array}$$

Da die letzte Spalte nur $w$ enthält, ist die Formel eine Tautologie: Die Äquivalenz von Aussage und Kontraposition gilt also immer.

Beispiel: Modus Ponens ist eine Tautologie

$(p\wedge (p\to q))\to q$

$$\begin{array}{ccccc}p& q& p\to q& p\wedge (p\to q)& (p\wedge (p\to q))\to q\\ w& w& w& w& w\\ w& f& f& f& w\\ f& w& w& f& w\\ f& f& w& f& w\end{array}$$

Auch hier: letzte Spalte nur $w$ → Tautologie. Dies ist das logische Fundament der Schlussregel “Wenn p gilt und p auf q schließen lässt, dann gilt q”.

---

1.4 Logische Äquivalenz

Definition: Logische Äquivalenz

Zwei Aussageformeln $p,q$ heißen logisch äquivalent, wenn $p\leftrightarrow q$ eine Tautologie ist. Schreibweise: $p\equiv q$

Definition: Implikation (semantisch)

”$p$ impliziert $q$” bedeutet: $p\to q$ ist eine Tautologie.

Beispiel: $p⟹q\equiv \neg q⟹\neg p$ (Kontraposition, s.o.), und $p\wedge (p⟹q)$ impliziert $q$ (Modus Ponens, s.o.)

Wichtige Äquivalenzregeln

Regel	Name
$p\vee q\equiv q\vee p$	Kommutativität $\vee$
$p\wedge q\equiv q\wedge p$	Kommutativität $\wedge$
$p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)$	Distributivgesetz
$p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$	Distributivgesetz
$p\wedge (q\wedge r)\equiv (p\wedge q)\wedge r$	Assoziativität $\wedge$
$p\vee (q\vee r)\equiv (p\vee q)\vee r$	Assoziativität $\vee$
$\neg \neg p\equiv p$	doppelte Negation
$\neg (p\wedge q)\equiv \neg p\vee \neg q$	De Morgan
$\neg (p\vee q)\equiv \neg p\wedge \neg q$	De Morgan
$p⟹q\equiv \neg p\vee q$	Implikation als Disjunktion

Beweis von De Morgan ($\neg (p\vee q)\equiv \neg p\wedge \neg q$) per Wahrheitstabelle:

$$\begin{array}{ccccccc}p& q& p\vee q& \neg (p\vee q)& \neg p& \neg q& \neg p\wedge \neg q\\ w& w& w& f& f& f& f\\ w& f& w& f& f& w& f\\ f& w& w& f& w& f& f\\ f& f& f& w& w& w& w\end{array}$$

Spalten 4 und 7 stimmen überein → Äquivalenz bewiesen.

Beweis von $p⟹q\equiv \neg p\vee q$:

$$\begin{array}{ccccc}p& q& p⟹q& \neg p& \neg p\vee q\\ w& w& w& f& w\\ w& f& f& f& f\\ f& w& w& w& w\\ f& f& w& w& w\end{array}$$

Spalten 3 und 5 stimmen überein → Äquivalenz bewiesen.

Nützliche Folgerung: Negation einer Implikation

Mit De Morgan und $p⟹q\equiv \neg p\vee q$ lässt sich herleiten:

$\neg (p⟹q)\equiv \neg (\neg p\vee q)\equiv \neg \neg p\wedge \neg q\equiv p\wedge \neg q$

Merksatz

“p impliziert q” ist genau dann falsch, wenn p wahr und q falsch ist — das deckt sich direkt mit der Wahrheitstabelle der Implikation.

---

1.5 Übungsaufgaben (Hausaufgabe 1)

Aufgabe 1: Wahrheitstabelle aufstellen

Bestimme den Wahrheitsverlauf von: $\neg (\neg q\to (r\wedge p))\wedge (q\leftrightarrow (\neg p\vee q))$

Linke Seite:

$$\begin{array}{ccccccc}q& p& r& \neg q& r\wedge p& \neg q\to (r\wedge p)& \neg (\neg q\to (r\wedge p))\\ 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0& 1\\ 0& 1& 0& 1& 0& 0& 1\\ 0& 1& 1& 1& 1& 1& 0\\ 1& 0& 0& 0& 0& 1& 0\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 1& 0& 0& 0& 1& 0\\ 1& 1& 1& 0& 1& 1& 0\end{array}$$

Rechte Seite:

$$\begin{array}{cccccc}q& p& r& \neg p& \neg p\vee q& q\leftrightarrow (\neg p\vee q)\\ 0& 0& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 0\\ 0& 1& 0& 0& 0& 1\\ 0& 1& 1& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 1& 0& 1& 1& 1& 1\\ 1& 1& 0& 0& 1& 1\\ 1& 1& 1& 0& 1& 1\end{array}$$

Gesamtausdruck (Konjunktion beider Seiten):

$$\begin{array}{ccc}\neg (\neg q\to (r\wedge p))& q\leftrightarrow (\neg p\vee q)& \text{Gesamt}\\ 1& 0& 0\\ 1& 0& 0\\ 1& 1& 1\\ 0& 1& 0\\ 0& 1& 0\\ 0& 1& 0\\ 0& 1& 0\\ 0& 1& 0\end{array}$$

Ergebnis: Der Ausdruck ist nur wahr für die Belegung $q=0,p=1,r=0$.

---

Aufgabe 2a: Äquivalenz beweisen

Zeige: $p\leftrightarrow q\equiv (p\to q)\wedge (q\to p)$

$$\begin{array}{ccccccc}q& p& q\leftrightarrow p& p\to q& q\to p& (p\to q)\wedge (q\to p)& \text{beide a¨quivalent?}\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1\\ 1& 0& 0& 1& 0& 0& 1\\ 1& 1& 1& 1& 1& 1& 1\end{array}$$

Die beiden mittleren Spalten ($q\leftrightarrow p$ und $(p\to q)\wedge (q\to p)$) stimmen in jeder Zeile überein → Tautologie der Äquivalenz → bewiesen.

Merksatz

“Genau dann wenn” ($\leftrightarrow$) ist nichts anderes als “Implikation in beide Richtungen” — das ist die Grundlage für die typische Beweistechnik ”⟹” und ”⟸” getrennt zu zeigen (siehe Mengenlehre-Beweise).

Aufgabe 2b: Formeln konstruieren

Gesucht: drei aussagenlogische Formeln $A,B,C$ (in höchstens den Variablen $p,q,r$), sodass

• für je zwei der drei Formeln eine Belegung existiert, bei der beide wahr sind,
• aber keine Belegung existiert, bei der alle drei gleichzeitig wahr sind.

Lösungsansatz: $A=p\wedge \neg (p\wedge q\wedge r),B=q\wedge \neg (p\wedge q\wedge r),C=r\wedge \neg (p\wedge q\wedge r)$

Verfeinerung (um alle Paarbedingungen sauber zu erfüllen): $A=p\wedge \neg (p\wedge q\wedge r)\vee (B\wedge \neg C)$ $B=q\wedge \neg (p\wedge q\wedge r)\vee (C\wedge \neg A)$ $C=r\wedge \neg (p\wedge q\wedge r)\vee (A\wedge \neg B)$

Probe per Wahrheitstabelle:

$$\begin{array}{cccccc}p& q& r& A& B& C\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1\\ 1& 0& 0& 1& 0& 1\\ 1& 0& 1& 1& 0& 1\\ 1& 1& 0& 1& 1& 0\\ 1& 1& 1& 0& 0& 0\end{array}$$

Man prüft: Es gibt Zeilen mit $A=B=1$ (z.B. Zeile 3), mit $B=C=1$ (z.B. Zeile 2) und mit $A=C=1$ (z.B. Zeile 5), aber in keiner Zeile sind alle drei gleichzeitig 1.

Aufgabe 3: Logikrätsel (Wächter-/Türenrätsel)

3a) Das Prinzip der doppelten Verneinung

Klassisches Rätsel: Ein Wächter lügt immer, der andere sagt immer die Wahrheit. Man darf nur eine Frage stellen, um die richtige Tür zu finden.

Trick: Zwei Lügen ergeben die Wahrheit, zwei Wahrheiten bleiben die Wahrheit. Also fragt man:

“Wenn ich dich fragen würde, welche Tür zum Ausgang führt, welche würdest du mir zeigen?”

• Der Wahrheitssager würde (gedanklich) zweimal die Wahrheit sagen → zeigt die richtige Tür.
• Der Lügner würde eigentlich lügen, muss aber bei dieser verschachtelten Frage das Gegenteil seiner Lüge angeben → zeigt ebenfalls die richtige Tür.

Dies ist die aussagenlogische Anwendung von $\neg \neg p\equiv p$: Die doppelte Verneinung hebt sich auf.

3b) Erweiterung auf drei Wächter

Ein Wächter kann zusätzlich zufällig antworten (weder reiner Lügner noch reiner Wahrheitssager).

1. Frage an Wächter A: “Wenn ich dich fragen würde, ob B ein zufälliger Wächter ist, was würdest du antworten?”

$$\begin{array}{ccc}\text{A ist}& \text{A sagt "ja"}& \text{A sagt "nein"}\\ \text{nicht zufa¨llig}& \text{C ist sicher}& \text{B ist sicher}\\ \text{zufa¨llig}& \text{B und C sind sicher}& \text{B und C sind sicher}\\ \text{Fazit}& \text{C ist sicher}& \text{B ist sicher}\end{array}$$

In jedem Fall identifiziert die Antwort einen garantiert nicht-zufälligen Wächter (entweder reinen Lügner oder reinen Wahrheitssager).

2. Frage an den als sicher identifizierten Wächter, mit dem Trick aus 3a: Auf eine Tür zeigen und fragen: “Wenn ich dich fragen würde, ob diese Tür sicher ist, was würdest du mir antworten?”
   • Antwort “Tür ist sicher” → diese Tür nehmen.
   • Antwort “Tür ist nicht sicher” → die andere Tür nehmen.