Umschlagbild
Wenn Sie das Buch noch nicht kennen, dann können Sie hier weitere Informationen finden.

Lösung für Aufgabe 3.3.5

Seien $p$, $q$, $r$ und $s$ beliebige Aussagen. Zeigen Sie, dass die folgenden Argumente gültig sind.
  1. $p\liff q$ gilt genau dann, wenn $p\limplies q$ und $\neg p\limplies\neg q$.
  2. $p\limplies(r\wedge s)$ ist äquivalent zu $(p\limplies r)\wedge(p\limplies s)$.
  3. $p\limplies(r\vee s)$ ist notwendig und hinreichend für $(p\wedge\neg r)\limplies s$.
  4. $(r\vee s)\limplies q$ ist gleichbedeutend mit $(r\limplies q)\wedge(s\limplies q)$.
  5. Aus $(r\wedge s)\limplies q$ folgt $(r\limplies q)\vee(s\limplies q)$ und umgekehrt.
  6. $(r\wedge s)\limplies q$ dann und nur dann, wenn $r\limplies(s\limplies q)$.


1.

Zu zeigen ist, dass $(p \Leftrightarrow q) \Leftrightarrow ((p \Rightarrow q) \wedge (\neg p \Rightarrow \neg q)$ eine Tautologie ist. $$(p \Leftrightarrow q) \Leftrightarrow ((p \Rightarrow q) \wedge (\neg p \Rightarrow \neg q) = (\neg (p \Leftrightarrow q) \wedge \neg (p \Rightarrow q) \wedge (\neg p \Rightarrow \neg q))) \vee ((p \Leftrightarrow q) \wedge ((p \Leftrightarrow q) \wedge (\neg p \Rightarrow \neg q))$$ Wir setzen $$(p \Rightarrow q) \wedge (\neg p \Rightarrow \neg q) =(\neg p \vee q) \wedge (p \vee \neg q) = (\neg p \vee \neg q) \vee (p \wedge q) = p \Leftrightarrow q,$$ in obige Gleichung ein: $$\neg (p \Leftrightarrow q) \vee (p \Leftrightarrow q) = 1.$$

Damit ist $(p \Leftrightarrow q) \Leftrightarrow ((p \Rightarrow q) \wedge (\neg p \Rightarrow \neg q)$ eine Tautologie. $\Box$

2.

Zu zeigen ist, dass $(p \Rightarrow (r \wedge s)) \Leftrightarrow ((p \Rightarrow r) \wedge (p \Rightarrow s))$ eine Tautologie ist. $$(p \Rightarrow (r \wedge s)) \Leftrightarrow ((p \Rightarrow r) \wedge (p \Rightarrow s)) = (\neg (p \Rightarrow (r \wedge s)) \wedge \neg ((p \Rightarrow r) \wedge (p \Rightarrow s))) \vee ((p \Rightarrow (r \wedge s)) \wedge ((p \Rightarrow r) \wedge (p \Rightarrow s)))$$ Wir setzen $$p \Rightarrow (r \wedge s) = \neg p \vee (r \wedge s) = (\neg p \vee r) \wedge (\neg p \vee s) = (p \Rightarrow r) \wedge (p \Rightarrow s),$$ in obige Gleichung ein: $$\neg ((p \Rightarrow r) \wedge (p \Rightarrow s)) \vee ((p \Rightarrow r) \wedge (p \Rightarrow s)) = 1.$$

Damit ist $(p \Leftrightarrow q) \Leftrightarrow ((p \Rightarrow q) \wedge (\neg p \Rightarrow \neg q)$ eine Tautologie. $\Box$

3.

Zu zeigen ist, dass $((p \Rightarrow (r \vee s)) \Leftrightarrow ((p \wedge \neg r) \Rightarrow s)$ eine Tautologie ist. \begin{align*} ((p \Rightarrow (r \vee s)) \Leftrightarrow &((p \wedge \neg r) \Rightarrow s)\\ &=(\neg (p \Rightarrow (r \vee s)) \wedge \neg ((p \wedge \neg r) \Rightarrow s))\vee ((p \Rightarrow (r \vee s)) \wedge ((p \wedge \neg r) \Rightarrow s))\\ &=((\neg (\neg p \vee r \vee s)) \wedge \neg (\neg p \vee r \vee s))\vee ((\neg p \vee r \vee s) \wedge (\neg p \vee r \vee s))\\ &=(\neg (\neg p \vee r \vee s)) \vee (\neg p \vee r \vee s) = 1. \end{align*} Da

$$p \Rightarrow (r \vee s) = \neg p \vee (r \vee s) = (\neg p \vee r) \vee (\neg p \vee s) = \neg p \vee r \vee s = \neg (p \vee \neg r) \vee s = (p \wedge \neg r) \Rightarrow s$$ gilt, ist $((p \Rightarrow (r \vee s)) \Leftrightarrow ((p \wedge \neg r) \Rightarrow s)$ eine Tautologie. $\Box$

4.

\begin{align*} (r \vee s) \Rightarrow q \Leftrightarrow &(p \Rightarrow q) \wedge (s \Rightarrow q)\\ &=(\neg ((r \vee s) \Rightarrow q)\wedge \neg((p \Rightarrow q)\wedge (s \Rightarrow q))\vee ((r \vee s) \Rightarrow q) \wedge ((p \Rightarrow q) \wedge (s \Rightarrow q))\\ &=(\neg ((\neg r \wedge \neg s) \vee q) \wedge \neg((\neg r \wedge \neg s) \vee q)\vee ((\neg r \wedge \neg s) \vee q) \wedge ((\neg r \wedge \neg s) \vee q)\\ &=(\neg ((\neg r \wedge \neg s) \vee q))\vee ((\neg r \wedge \neg s) \vee q)= 1. \end{align*} Da $$(r \vee s) \Rightarrow q = \neg (r \vee s) \vee q) = (\neg r \wedge \neg s) \vee q = (\neg r \vee q) \wedge ( \neg s \vee q) = (p \Rightarrow q) \wedge (s \Rightarrow q)$$ gilt, ist die Aussage $(r \vee s) \Rightarrow q \Leftrightarrow (p \Rightarrow q) \wedge (s \Rightarrow q)$ eine Tautologie und die Äquivalenz somit korrekt. $\Box$

5.

\begin{align*} (r \wedge s) \Rightarrow q \Leftrightarrow (r \Rightarrow q) \vee (s \Rightarrow q)\\ &=(\neg((r \wedge s) \Rightarrow q) \wedge \neg ((r \Rightarrow q) \vee (s \Rightarrow q)) \vee (((r \wedge s) \Rightarrow q) \wedge ((r \Rightarrow q) \vee (s \Rightarrow q)))\\ &=(\neg((r \Rightarrow q) \vee (s \Rightarrow q)) \wedge \neg ((r \Rightarrow q) \vee (s \Rightarrow q))) \vee (((r \Rightarrow q) \vee (s \Rightarrow q)) \wedge ((r \Rightarrow q) \vee (s \Rightarrow q)))\\ &=\neg ((r \Rightarrow q) \vee (s \Rightarrow q)) \vee ((r \Rightarrow q) \vee (s \Rightarrow q))=1.\\ \end{align*} Da $$(r \wedge s) \Rightarrow q = \neg (r \wedge s) \vee q = \neg r \vee \neg s \vee q = \neg r \vee q \vee \neg s \vee q = (r \Rightarrow q) \vee (s \Rightarrow q)$$ gilt, ist die Aussage $(r \wedge s) \Rightarrow q \Leftrightarrow (r \Rightarrow q) \vee (s \Rightarrow q)$ eine Tautologie und die äquivalenz somit korrekt. $\Box$