Lösung für Aufgabe 3.3.4
Seien $p$, $q$, $r$ und $s$ beliebige Aussagen. Zeigen Sie, dass die folgenden Argumente gültig sind.- $\neg(p\limplies q)$ impliziert $p$.
- Aus $p\limplies q$ und $p\limplies\neg q$ folgt $\neg p$.
- Wegen $p\limplies q$ gilt $(p\wedge r)\limplies(q\wedge r)$.
- $(p\wedge q)\liff r$ folgt aus $p\wedge(q\liff r)$.
- Die Tatsache, dass $p\limplies(q\wedge r)$, hat als Konsequenz $(p\wedge q)\liff(p\wedge r)$.
- $(p\liff r)\wedge(q\liff s)$ und daher $(p\vee q)\liff(r\vee s)$.
- Aus $\forall x:(P(x)\limplies Q(x))$ und $\forall x:P(x)$ folgt $\forall x:Q(x)$.
1. Variante 1: Zu zeigen ist: $(\neg (p \Rightarrow q))\Rightarrow p$ ist eine Tautologie. \begin{align*} \neg (p \Rightarrow q)\Rightarrow p = \neg (\neg(p \Rightarrow q))\vee p = (p \Rightarrow q)\vee p = (\neg p \vee q)\vee p=\neg p\vee p\vee q=1\vee q=1. \end{align*} Damit ist gezeigt, dass $(\neg (p \Rightarrow q))\Rightarrow p$ eine Tautologie und damit die Implikation korrekt ist. $\Box$ Variante 2: Argumentation: Sei $\neg (p \Leftrightarrow q)$ wahr. Ist p wahr, stimmt die Implikation. Ist p falsch, so stimmt sie ebenfalls, weil die erste Aussage falsch ist. Genauso folgt wenn q wahr ist, ist auch p wahr und wenn q falsch ist, ist auch p falsch. Damit ist die Implikation immer korrekt. $\Box$ 2. \begin{align*} (p \Rightarrow q) \wedge (p \Rightarrow \neg q) \Rightarrow \neg p &= (\neg p \vee q) \wedge (\neg p \vee \neg q) \Rightarrow \neg p\\ &=(\neg p \vee q) \wedge (\neg p \vee \neg q) \Rightarrow \neg p = \neg((\neg p \vee q) \wedge (\neg p \vee \neg q)) \vee \neg p\\ &=(p \wedge \neg q) \vee (p \wedge q) \vee \neg p = (p \wedge (\neg q \vee q)) \vee \neg p = p \vee \neg p = 1. \end{align*} Daraus folgt $(p \Rightarrow q) \wedge (p \Rightarrow \neg q) \Rightarrow \neg p$ ist eine Tautologie. Damit ist die Implikation korrekt. 3. \begin{align*} (p \Rightarrow q)\Rightarrow&((p \wedge r)\Rightarrow (q \wedge r))=(\neg p \vee q) \Rightarrow ((\neg p \vee \neg r) \vee (q \wedge r))\\ &=(p\wedge \neg q) \vee \neg p \vee \neg r \vee (q \wedge r) = (p \wedge \neg q) \vee \neg p \vee (\neg r \vee q)\\ &=((p \wedge \neg q) \vee \neg p \vee \neg r \vee q = (\neg q \vee \neg p) \vee \neg r \vee q = \neg q \vee q \vee \neg p \vee \neg r = 1. \end{align*} Daraus folgt $(p \Rightarrow q) \Rightarrow ((p \wedge r) \Rightarrow (q \wedge r))$ ist eine Tautologie. Damit ist die Implikation korrekt. 4. Variante 1: Wir zeigen, dass $p \wedge (q \Leftrightarrow r) \Rightarrow (p \wedge q) \Leftrightarrow r$ eine Tautologie ist. Entweder durch $p \wedge (q \Leftrightarrow r) \Rightarrow (p \wedge q) \Leftrightarrow r = 1$ oder durch die Wahrheitstabelle. $$\begin{array}{ccccccc} %\hline p & q & r & q \Leftrightarrow r & p \wedge (q \Leftrightarrow r) & p \wedge q & (p \wedge q) \Leftrightarrow r\\ %\hline\hline 0 & 0 & 0 & 1 & 0\\ %\hline \\ %\hline\hline 0 & 0 & 1 & 0 & 0\\ %\hline \\ %\hline\hline 0 & 1 & 0 & 0 & 0\\ %\hline \\ %\hline\hline 0 & 1 & 1 & 1 & 0\\ %\hline \\ %\hline\hline 1 & 0 & 0 & 1 & 1 & 0 & 1\\ %\hline \\ %\hline\hline 1 & 0 & 1 & 0 & 0\\ %\hline \\ %\hline\hline 1 & 1 & 0 & 0 & 0\\ %\hline \\ %\hline\hline 1 & 1 & 1 & 1 & 1 & 1 & 1\\ %\hline \end{array}$$ Die Fälle, in denen in Spalte 5 eine 0 eingetragen ist, müssen nicht weiter betrachtet werden, da wir nur die Situation betrachten müssen, in der die erste Aussage wahr ist. Daraus folgt $p \wedge (q \Leftrightarrow r) \Rightarrow (p \wedge q) \Leftrightarrow r$ ist eine Tautologie. $\Box$ Variante 2: Argumentation: Sei $p \wedge (q \Leftrightarrow r)$ wahr. Dann sind $p$ und $q \Leftrightarrow r$ wahr. Ist $q$ wahr, so auch $r$ und $(p \wedge q) \Leftrightarrow r$ ist ebenfalls wahr. Ist andererseits $q$ falsch, so auch $r$ und $(p \wedge q) \Leftrightarrow r$ ist wiederum wahr. Also ist die Implikation korrekt. $\Box$ 5. Variante 1: Zeige, dass $p \Rightarrow (q \wedge r) \Rightarrow (p \wedge q) \Leftrightarrow (p \wedge r)$ eine Tautologie ist. $$\begin{array}{ccccccc} %\hline p & q & r & s & p \Rightarrow (q \wedge r) & (p \wedge q) \Leftrightarrow (p \wedge r) & (p \Rightarrow (q \wedge r)) \Rightarrow ((p \wedge q) \Leftrightarrow (p \wedge r))\\ %\hline\hline 0 & 0 & 0 & 0 & 1 & 1 & 1\\ %\hline \\ %\hline\hline 0 & 0 & 0 & 1 & 1 & 1 & 1\\ %\hline \\ %\hline\hline 0 & 0 & 1 & 0 & 1 & 1 & 1\\ %\hline \\ %\hline\hline 0 & 0 & 1 & 1 & 1 & 1 & 1\\ %\hline \\ %\hline\hline 0 & 1 & 0 & 0 & 1 & 1 & 1\\ %\hline \\ %\hline\hline 0 & 1 & 0 & 1 & 1 & 1 & 1\\ %\hline \\ %\hline\hline 0 & 1 & 1 & 0 & 1 & 1 & 1\\ %\hline \\ %\hline\hline 0 & 1 & 1 & 1 & 1 & 1 & 1\\ %\hline \\ %\hline\hline 1 & 0 & 0 & 0 & 0\\ %\hline \\ %\hline\hline 1 & 0 & 0 & 1 & 0\\ %\hline \\ %\hline\hline 1 & 0 & 1 & 0 & 0\\ %\hline \\ %\hline\hline 1 & 0 & 1 & 1 & 0\\ %\hline \\ %\hline\hline 1 & 1 & 0 & 0 & 0\\ %\hline \\ %\hline\hline 1 & 1 & 0 & 1 & 0\\ %\hline \\ %\hline\hline 1 & 1 & 1 & 0 & 1 & 1 & 1\\ %\hline \\ %\hline\hline 1 & 1 & 1 & 1 & 1 & 1 & 1\\ %\hline \end{array}$$ Damit ist $(p \Rightarrow (q \wedge r)) \Rightarrow ((p \wedge q) \Leftrightarrow (p \wedge r))$ eine Tautologie und die Implikation korrekt.$\Box$ Variante 2: Argumentation: Sei $p \Rightarrow (q \wedge r)$ wahr. Das ist äquivalent dazu, dass $\neg p \vee (q \wedge r)$ wahr ist.Dann ist $\neg p$ wahr oder $(q \wedge r)$ oder beide. Sei $p$ falsch. Dann sind $p \wedge q$ und $p \wedge r$ beide falsch also ist $(p \wedge q) \Leftrightarrow (p \wedge r)$ wahr. Sei andererseits $p$ wahr. Dann muss auch $q\wedge r$ wahr sein und damit sind $q$ und $r$ beide wahr. Daher ist die Implikation korrekt. $\Box$ 6. Wir beweisen die Aussage indirekt. Sei also die rechte Seite falsch, also gelte $(p\vee q)\xor (r\vee s)$. Wir müssen also die zwei Fälle $p\vee q=0$, $r\vee s=1$ und $p\vee q=1$, $r\vee s=0$ betrachten. Im ersten Fall gilt $p=0=q$, aber mindestens eine der Aussagen $r$ und $s$ ist wahr, also ist die linke Seite der zu beweisenden Aussage falsch. Dasselbe gilt im zweiten Fall, denn hier gilt $r=0=s$ aber mindestens eine der Aussagen $p$, $q$ ist wahr. Alternativ kann die Aussage auch direkt bewiesen werden. Dazu nimmt man an, dass die linke Seite wahr ist. Dann sind nur folgende Wahrheitswerte für $(p,r,q,s)$ möglich $(1,1,0,0)$, $(1,1,1,1)$, $(0,0,0,0)$ und $(0,0,1,1)$. In allen vier Fällen ist leicht zu sehen, dass die rechte Seite wahr ist. 7. Sei für alle $x$ die Eigenschaft, dass aus $P(x) \Rightarrow Q(x)$ und $P(x)$ wahr. Dann ist $Q(x)$ auch für alle $x$ wahr.