Aussagen

Sind $p$ und $q$ zwei Aussagen so ist die

Konjunktion (und) geschrieben $p\wedge q$ wahr, wenn $p$ wahr ist und $q$ wahr ist.
Die Wahrheitstabelle:
$\begin{array}{c|c} p&q&p\wedge q\\\hline f&f&f\\ f&w&f\\ w&f&f\\ w&w&w\\ \end{array} $
Disjunktion (oder) geschrieben $p\vee q$ wahr, wenn $p$ wahr ist oder wenn $q$ wahr ist.
Die Wahrheitstabelle:
$\begin{array}{c|c} p&q&p\vee q\\\hline f&f&f\\ f&w&w\\ w&f&w\\ w&w&w\\ \end{array} $
Implikation geschrieben $p\Rightarrow q$.
Die Implikation ist per Definition wahr, wenn die Voraussetzung $p$ falsch ist.
Wenn die Voraussetzung und die Folgerung wahr ist, ist die Implikation ebenfalls wahr.
Wenn die Voraussetzung wahr ist aber die Folgerung falsch, ist die Implikation falsch.
Die Implikation $p\Rightarrow q$ kann gelesen werden als:
- „wenn A, so B“
- „aus A folgt B“
- „A impliziert B“
- „B ist notwendige Bedingung für A“
- „A ist hinreichende Bedingung für B“
Die Wahrheitstabelle:
$\begin{array}{c|c} p&q&p\Rightarrow q\\\hline f&f&w\\ f&w&w\\ w&f&f\\ w&w&w\\ \end{array} $
Man überlege sich, wann man sicher sagen kann, dass $A\Rightarrow B$ falsch ist.
Hierbei kommt man zu dem Schluss, dass man dies nur sicher schließen kann, wenn die Folgerung $B$ falsch aber die Voraussetzung $A$ wahr ist.

Äquivalenz geschrieben $p\Leftrightarrow q$ besagt, dass $p$ und $q$ gleichwertig sind.
Es gilt also $p$ genau dann, wenn $q$ gilt.
Die Wahrheitstabelle:

$\begin{array}{c|c} p&q&p\Leftrightarrow q\\\hline f&f&w\\ f&w&f\\ w&f&f\\ w&w&w\\ \end{array} $

Die Äquivalenz $p\Leftrightarrow q$ liegt genau dann vor, wenn gilt $p\Rightarrow q$ und $q\Rightarrow p$.
Oder eben $(p\Leftrightarrow q) \Leftrightarrow ((p\Rightarrow q) \wedge (q\Rightarrow p))$

Man kann dies leicht mittels einer Wahrheitstabelle zeigen:

$p$	$q$	$A$ $p\Rightarrow q$	$B$ $p\Leftarrow q$	$A\wedge B$ $p\Leftrightarrow q$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$f$
$w$	$w$	$w$	$w$	$w$

Aufgaben

Überlegen Sie, ob folgende Aussagen wahr oder falsch sind:
- $3\cdot 3=9$
- $5+2\lt 6$
- $b\cdot 0 = 0$
- Alle hier Anwesenden sind Schüler.
- Die Erde ist eine Scheibe.
- $3\cdot 3=9$ ist wahr
- $5+2\lt 6$ ist falsch
- $b\cdot 0 = 0$ ist wahr
- Alle hier Anwesenden sind Schüler. Ist falsch (wenn der Lehrer da ist)
- Die Erde ist eine Scheibe. Ist falsch.
Gegeben sind folgende Aussagen:
$p:\; $ 15 ist eine Primzahl
$q:\; $ Jede Primzahl ist ungerade
$r:\; $ 2 ist eine Primzahl
Formuliere zu jeder Aussage die Negation.
Überlegen sie welche Aussage wahr und welche falsch ist.
Prüfen Sie ob $p\wedge r$ und $p\vee r$ wahr sind.

$\neg p:\;$ 15 ist keine Primzahl
$\neg q:\;$ Nicht jede Primzahl ist ungerade (oder mindestens eine Primzahl ist gerade)
$\neg r:\;$ 2 ist keine Primzahl
$p:\; $ ist falsch, da 15 durch 3 und 5 teilbar ist
$q:\; $ ist falsch da 2 eine Primzahl ist und diese ist gerade
$r:\; $ ist wahr

Da $p$ falsch ist und $r$ wahr ist gilt: $p\wedge r$ ist somit $f\wedge w$ und das ist falsch.

Da $p$ falsch ist und $r$ wahr ist gilt: $p\vee r$ ist somit $f\vee w$ und das ist wahr.

Zeigen Sie, dass das erste De Morgan'sche Gesetz $\neg(a\wedge b)\Leftrightarrow (\neg a\vee \neg b)$ wahr ist.

$a$	$b$	$a\wedge b$	$\neg(a\wedge b)$
$f$	$f$	$f$	$w$
$f$	$w$	$f$	$w$
$w$	$f$	$f$	$w$
$w$	$w$	$w$	$f$

Zeigen Sie, dass das zweite De Morgan'sche Gesetz $\neg(a\vee b)\Leftrightarrow (\neg a\wedge \neg b)$ wahr ist.

$a$	$b$	$a\vee b$	$\neg(a\vee b)$
$f$	$f$	$f$	$w$
$f$	$w$	$w$	$f$
$w$	$f$	$w$	$f$
$w$	$w$	$w$	$f$

Zeigen Sie, dass $a\Rightarrow b$ äquivalent zu $\neg b\Rightarrow \neg a$ ist.

Zeigen Sie, dass $a\Rightarrow b$ äquivalent zu $\neg a \vee b$ ist.

Linke Seite:

$a$	$b$	$a\Rightarrow b$
$f$	$f$	$w$
$f$	$w$	$w$
$w$	$f$	$f$
$w$	$w$	$w$

Rechte Seite:

$a$	$b$	$\neg a$	$ b$	$\neg a \vee b$
$f$	$f$	$w$	$f$	$w$
$f$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$f$
$w$	$w$	$f$	$w$	$w$

Die Wahrheitswerte auf der linken und rechten Seite stimmen überein.
Damit sind beide Aussagen äquivalent.

Bestimmen Sie das Gegenteil von $\neg a \vee b$.
Wie hängt dies mit $a \Rightarrow b$ zusammen?

$\neg(\neg a \vee b) $
mit DeMorgan ergibt sich: $\neg \neg a \wedge \neg b$
Die doppelte Negation kann man entfernen: $ a \wedge \neg b$
Da $a\Rightarrow b$ äquivalent zu $\neg a \vee b$ ist, sind auch deren Negation äquivalent.
Wenn also $a \wedge \neg b$ gilt gilt auch $a \not\Rightarrow b$
Und wenn $ a \wedge \neg b$ nicht gilt, gilt $a \Rightarrow b$
Anja sagt: „Beate sagt die Wahrheit.“
Beate sagt: „Christel lügt.“
Christel sagt: „Anja und Beate sagen beide die Wahrheit oder lügen beide.“
Wer lügt denn nun und wer sagt die Wahrheit? Erläutern Sie Ihre logischen Schlüsse.
Falls Anja die Wahrheit sagt, dann sagt Beate die Wahrheit und somit lügt Christel.
Falls Christel die Wahrheit sagt, sagen Anja und Beate beide die Wahrheit oder lügen beide.
Falls Christel lügt, gilt das Gegenteil ihrer Aussage, also Anja lügt und Beate sagt die Wahrheit oder Anja lügt und Beate sagt die Wahrheit.
Wenn also Christel lügt, dann muss entweder Anja oder Beate lügen, was im Widerspruch zur Annahme steht.
Falls Anja lügt, dann lügt Beate und Christel sagt die Wahrheit.
Christels Aussage ist wahr, weil Anja und Beate beide lügen.
Ergebnis: Anja und Beate lügen, Christel sagt die Wahrheit.
Formal sind die Aussagen Äquivalenzen.
Wenn wir
- A: Anja sagt die Wahrheit
- B: Beate sagt die Wahrheit
- C: Christel sagt die Wahrheit
nehmen, ergibt sich:
$A\Leftrightarrow B$ und $B \Leftrightarrow \neg C$ (und somit auch $A\Leftrightarrow \neg C$) und
$C \Leftrightarrow (A\wedge B)\vee(\neg A\wedge \neg B)$.
Wie könnte man jetzt mit Wahrheitstabelle dieses Rätsel auch lösen?

Zeigen Sie mithilfe von Wahrheitstabellen, dass aus $A\Rightarrow B$ und $B\Rightarrow C$ folgt, dass $A\Rightarrow C$ gilt.
Formal bedeutet dies: $((A\Rightarrow B)\wedge(B\Rightarrow C)) \Rightarrow (A\Rightarrow C)$.
Welche Bedeutung hat dies?

$A$	$B$	$P=(A\Rightarrow B)$
$f$	$f$	$w$
$f$	$w$	$w$
$w$	$f$	$f$
$w$	$w$	$w$

$B$	$C$	$Q=(A\Rightarrow B)$
$f$	$f$	$w$
$f$	$w$	$w$
$w$	$f$	$f$
$w$	$w$	$w$

$A$	$C$	$X=(A\Rightarrow C)$
$f$	$f$	$w$
$f$	$w$	$w$
$w$	$f$	$f$
$w$	$w$	$w$

$A$	$B$	$C$	$P$	$Q$	$P\wedge Q$	$X$	$(P\wedge Q)\Rightarrow X$
$f$	$f$	$f$	$w$	$w$	$w$	$w$	$w$
$f$	$f$	$w$	$w$	$w$	$w$	$w$	$w$
$f$	$w$	$f$	$w$	$f$	$f$	$w$	$w$
$f$	$w$	$w$	$w$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$w$	$f$	$f$	$w$
$w$	$f$	$w$	$f$	$w$	$f$	$w$	$w$
$w$	$w$	$f$	$w$	$f$	$f$	$f$	$w$
$w$	$w$	$w$	$w$	$w$	$w$	$w$	$w$

Somit ist $(P\wedge Q)\Rightarrow X$ immer wahr.
Mit $P=(A\Rightarrow B)\,$, $Q=(B\Rightarrow C)$ und $X=(A\Rightarrow C)$ gilt somit immer:
$((A\Rightarrow B)\wedge (B\Rightarrow C))\Rightarrow (A\Rightarrow C)$

Bedeutung: Wenn wir Folgerungen haben können wir Folgerungsketten bilden. Ist $A$ wahr und folgt daraus $B$ und aus $B$ folgt $C$ und aus $C$ folgt $D$, so folgt aus $A$ auch $D$.

Man schafft sich somit Abkürzungen. Wenn jeder kleine Schritt eine richtige Folgerung ist, so ist auch der große Schritt eine richtige Folgerung.
Desto mehr Implikationen man also kennt, desto größere Schritte kann man machen.
Man kann große Probleme in kleinere Aufteilen. Will man zeigen, dass $A\Rightarrow Z$ gilt, so kann man zuerst zeigen, dass $A\Rightarrow B$ gilt, dann $B\Rightarrow C$ und dann ... bis zu $Y \Rightarrow Z$.
Kleine Schritte sind meist leichter und große oft unmöglich, daher geht man auch in der Logik lange Wege in vielen kleinen Schritten.

Beim Klassentreffen kommen vier ehemalige Mitschüler, Klaus, Lothar, Martin und Peter, zusammen.
Einer von ihnen ist Architekt, einer Bauingenieur, einer Informatiker und der vierte Sozialpädagoge.
Welchen Beruf übt jeder aus, wenn folgende Aussagen falsch sind?
- Martin ist kein Informatiker und auch nicht Bauingenieur.
- Martin ist kein Sozialpädagoge und Peter nicht Bauingenieur.
- Lothar ist Sozialpädagoge.
Erst bilden wir die Negationen zu den drei Aussagen:
- Martin ist Informatiker oder Bauingenieur.
- Martin ist Sozialpädagoge oder Peter ist Bauingenieur.
- Lothar ist kein Sozialpädagoge.
Es gibt genau 4 Berufe und genau 4 Personen. Da jede Person genau einen Beruf hat und jeder Beruf genau einer Person zugeordnet ist, können wir hier das Ausschluss-Verfahren anwenden. D.h. wenn wir 3 Berufe für jemanden ausschließen, hat er automatisch den vierten.
Aus der ersten Aussage folgt, dass Martin weder Architekt noch Sozialpädagoge ist.
Mit der zweiten Aussage folgt, dass Peter Bauingenieur sein muss, denn Martin ist ja kein Sozialpädagoge.
Martin ist dann Informatiker.
Da Lothar nicht Sozialpädagoge ist, muss Klaus Sozialpädagoge sein und Lothar ist der Architekt.
Ergebnis: Klaus ist Sozialpädagoge, Martin ist Informatiker, Lothar ist Architekt, Peter ist Bauingenieur.
Betrachtet man von Aussagen nur den Wahrheitswert (nicht den Inhalt), so gibt es nur zwei unterschiedliche Aussagen: wahre Aussagen und falsche Aussagen.
Wie viele Aussagenpaare gibt es?
Wie viele Tripel?
Wie viele Möglichkeiten bei $n$ Aussagen?

Es gibt zwei Möglichkeiten für eine Aussage: $f, w$
Es gibt vier Möglichkeiten für zwei Aussage: $(f,f), (f, w), (w, f), (w,w)$
Es gibt acht Möglichkeiten für drei Aussage: $(f,f,f), (f,f, w), (f,w, f), (f,w,w), (w,f,f), (w,f, w), (w,w, f), (w,w,w)$
Bei jeder Aussage mehr verdoppelt sich die Anzahl der Möglichkeiten, somit hat man $2^n$ Möglichkeiten bei $n$ Aussagen.
Zeigen Sie mittels Wahrheitstabellen, dass folgende Äquivalenz wahr sind, (wobei $f$ für falsch und $w$ für wahr steht):
- Idempotenz: $A\wedge A \Leftrightarrow A$
- Kommutativität: $A\wedge B \Leftrightarrow B\wedge A$
- Identität: $A\wedge w \Leftrightarrow A$
- Nullgesetz: $A\wedge f \Leftrightarrow f$
- Komplementarität: $A\wedge \neg A \Leftrightarrow f$

$p$	$q$	$A$ $p\Rightarrow q$	$B$ $p\Leftarrow q$	$A\wedge B$ $p\Leftrightarrow q$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$f$
$w$	$w$	$w$	$w$	$w$

$a$	$b$	$\neg a$	$\neg a$	$\neg a\vee \neg b$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$w$	$f$	$w$
$w$	$f$	$f$	$w$	$w$
$w$	$w$	$f$	$f$	$f$

$a$	$b$	$\neg a$	$\neg a$	$\neg a\wedge \neg b$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$f$
$w$	$w$	$f$	$f$	$f$

$a$	$b$	$\neg b$	$\neg a$	$\neg b\Rightarrow \neg a$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$f$	$w$	$w$
$w$	$f$	$w$	$f$	$f$
$w$	$w$	$f$	$f$	$w$

$a$	$b$	$\neg a$	$ b$	$\neg a \vee b$
$f$	$f$	$w$	$f$	$w$
$f$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$f$
$w$	$w$	$f$	$w$	$w$

$A$	$B$	$C$	$P$	$Q$	$P\wedge Q$	$X$	$(P\wedge Q)\Rightarrow X$
$f$	$f$	$f$	$w$	$w$	$w$	$w$	$w$
$f$	$f$	$w$	$w$	$w$	$w$	$w$	$w$
$f$	$w$	$f$	$w$	$f$	$f$	$w$	$w$
$f$	$w$	$w$	$w$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$w$	$f$	$f$	$w$
$w$	$f$	$w$	$f$	$w$	$f$	$w$	$w$
$w$	$w$	$f$	$w$	$f$	$f$	$f$	$w$
$w$	$w$	$w$	$w$	$w$	$w$	$w$	$w$

$p$	$q$	$A$ $p\Rightarrow q$	$B$ $p\Leftarrow q$	$A\wedge B$ $p\Leftrightarrow q$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$f$
$w$	$w$	$w$	$w$	$w$

$a$	$b$	$\neg a$	$\neg a$	$\neg a\vee \neg b$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$w$	$f$	$w$
$w$	$f$	$f$	$w$	$w$
$w$	$w$	$f$	$f$	$f$

$a$	$b$	$\neg a$	$\neg a$	$\neg a\wedge \neg b$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$f$
$w$	$w$	$f$	$f$	$f$

$a$	$b$	$\neg b$	$\neg a$	$\neg b\Rightarrow \neg a$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$f$	$w$	$w$
$w$	$f$	$w$	$f$	$f$
$w$	$w$	$f$	$f$	$w$

$a$	$b$	$\neg a$	$ b$	$\neg a \vee b$
$f$	$f$	$w$	$f$	$w$
$f$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$f$
$w$	$w$	$f$	$w$	$w$

$A$	$B$	$C$	$P$	$Q$	$P\wedge Q$	$X$	$(P\wedge Q)\Rightarrow X$
$f$	$f$	$f$	$w$	$w$	$w$	$w$	$w$
$f$	$f$	$w$	$w$	$w$	$w$	$w$	$w$
$f$	$w$	$f$	$w$	$f$	$f$	$w$	$w$
$f$	$w$	$w$	$w$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$w$	$f$	$f$	$w$
$w$	$f$	$w$	$f$	$w$	$f$	$w$	$w$
$w$	$w$	$f$	$w$	$f$	$f$	$f$	$w$
$w$	$w$	$w$	$w$	$w$	$w$	$w$	$w$

Aussagen

Negation

Wichtige Verknüpfungen

Aufgaben

$p$	$q$	$A$ $p\Rightarrow q$	$B$ $p\Leftarrow q$	$A\wedge B$ $p\Leftrightarrow q$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$f$
$w$	$w$	$w$	$w$	$w$

$a$	$b$	$\neg a$	$\neg a$	$\neg a\vee \neg b$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$w$	$f$	$w$
$w$	$f$	$f$	$w$	$w$
$w$	$w$	$f$	$f$	$f$

$a$	$b$	$\neg a$	$\neg a$	$\neg a\wedge \neg b$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$f$
$w$	$w$	$f$	$f$	$f$

$a$	$b$	$\neg b$	$\neg a$	$\neg b\Rightarrow \neg a$
$f$	$f$	$w$	$w$	$w$
$f$	$w$	$f$	$w$	$w$
$w$	$f$	$w$	$f$	$f$
$w$	$w$	$f$	$f$	$w$

$a$	$b$	$\neg a$	$ b$	$\neg a \vee b$
$f$	$f$	$w$	$f$	$w$
$f$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$f$
$w$	$w$	$f$	$w$	$w$

$A$	$B$	$C$	$P$	$Q$	$P\wedge Q$	$X$	$(P\wedge Q)\Rightarrow X$
$f$	$f$	$f$	$w$	$w$	$w$	$w$	$w$
$f$	$f$	$w$	$w$	$w$	$w$	$w$	$w$
$f$	$w$	$f$	$w$	$f$	$f$	$w$	$w$
$f$	$w$	$w$	$w$	$w$	$w$	$w$	$w$
$w$	$f$	$f$	$f$	$w$	$f$	$f$	$w$
$w$	$f$	$w$	$f$	$w$	$f$	$w$	$w$
$w$	$w$	$f$	$w$	$f$	$f$	$f$	$w$
$w$	$w$	$w$	$w$	$w$	$w$	$w$	$w$