Lösung für Aufgabe 3.2.16
Seien $p$, $q$, $r$ und $s$ Aussagen. Beweisen Sie, dass die folgenden Aussagen Tautologien sind:- $((p\limplies q)\wedge p)\limplies q$,
- $p\limplies(p\vee q)$,
- $((p\vee q)\wedge\neg p)\limplies q$,
- $(p\liff q)\limplies(p\limplies q)$,
- $((p\limplies q)\wedge(q\limplies r))\limplies(p\limplies r)$,
- $((p\limplies q)\wedge(r\limplies s)\wedge(p\vee r))\limplies(q\vee s)$.
Beweise mittels Wahrheitstabelle oder durch Umformung: 1. $$\begin{array}{cccc} %\hline p & q & (p \Rightarrow q) = a & (a \wedge p)=b & b \Rightarrow q\\ %\hline\hline 0 & 0 & 1 & 0 & 1\\ %\hline \\ %\hline\hline 0 & 1 & 1 & 0 & 1\\ %\hline \\ %\hline\hline 1 & 0 & 0 & 0 & 1\\ %\hline \\ %\hline\hline 1 & 1 & 1 & 1 & 1\\ %\hline \end{array}$$ Somit ist gezeigt, dass die Behauptung eine Tautologie ist. $\Box$ 2. $$p \Rightarrow (p \vee q) = \neg p \vee (p \vee q) = (\neg p \vee p) \vee (\neg p \vee q) = 1 \vee (\neg p \vee q) = 1.$$ Diese Aussage ist eine Tautologie, da sie immer wahr ist. $\Box$ 3. \begin{align*} ((p \vee q) \wedge \neg p) &\Rightarrow q = \neg ((p \vee q) \wedge \neg p) \vee q \\ &= (\neg(p \vee q) \vee p)\vee q = ((\neg p \wedge \neg q)\vee q) \vee q = ((\neg p \vee p) \wedge (\neg q \vee p)) \vee q \\ &= (1 \wedge (\neg q \vee p)) \vee q = (\neg q \vee q) \vee (p \vee q) = 1 \vee (p \vee q) = 1. \end{align*} Somit ist gezeigt, dass die Behauptung eine Tautologie ist. $\Box$ 4. $$\begin{array}{ccccc} %\hline p & q & (p \Leftrightarrow q) = a & (p \Rightarrow q) = b & a \Rightarrow b\\ %\hline\hline 0 & 0 & 1 & 1 & 1\\ %\hline \\ %\hline\hline 0 & 1 & 0 & 1 & 1\\ %\hline \\ %\hline\hline 1 & 0 & 0 & 0 & 1\\ %\hline \\ %\hline\hline 1 & 1 & 1 & 1 & 1\\ %\hline \end{array}$$ Somit ist gezeigt, dass die Behauptung eine Tautologie ist. $\Box$ 5. \begin{align*} ((p \Rightarrow q) &\wedge (q \Rightarrow r)) \Rightarrow (p \Rightarrow r)\\ &=((\neg p \vee q) \wedge (\neg q \vee r)) \Rightarrow (\neg p \vee r)\\ &=\neg (\neg p \vee q) \vee \neg (\neg q \vee r) \vee (\neg p \vee r)\\ &=(p \wedge \neg q) \vee (q\wedge \neg r) \vee (\neg p \vee r)\\ &=(p \wedge \neg q) \vee ((q \vee \neg p \vee r) \wedge (\neg r \vee \neg p \vee r))\\ &=(p \wedge \neg q) \vee (q \vee \neg p \vee r) \\ &=(p \vee q \vee \neg p \vee r) \wedge (\neg q \vee q \vee \neg p \vee r)\\ &=1. \end{align*} Diese Aussage ist also eine Tautologie. $\Box$ 6. \begin{align*} ((p \Rightarrow q) &\wedge (r \Rightarrow s) \wedge (p \vee r)) \Rightarrow (q \vee s)\\ &=(p \wedge \neg q) \vee (r \wedge \neg s) \vee (\neg p \wedge \neg r) \vee q \vee s\\ &=(p \wedge \neg q) \vee q \vee (r \wedge \neg s)\vee s \vee (\neg p \wedge \neg r)\\ &=(p \vee q) \vee (r \vee s) \vee (\neg p \wedge \neg r)\\ &=q \vee r \vee s \vee p \vee (\neg p \wedge \neg r) = (p \vee \neg r) \vee q \vee r \vee s\\ &=p \vee \neg r \vee r \vee q \vee s = p \vee 1 \vee q \vee s = 1. \end{align*} Somit ist gezeigt, dass die Behauptung eine Tautologie ist. $\Box$