\documentclass{uebungsblatt} \author{Marek Kubica, kubica@in.tum.de} \fach{Diskrete Strukturen} \blatt{5} \gruppe{11} \begin{document} \aufgabe \teilaufgabe Annahme: $ \beta(1, 0, 1) = 1$ $ \Diamond(x, y, z) \equiv (x \wedge \neg y \wedge z) \vee (\neg(x \wedge \neg y \wedge z) \wedge \Diamond(x, y, z))$ \begin{tabular}{|l|l|l|cccl|} \hline $x$ & $y$ & $z$ & $ (x \wedge \neg y \wedge z) $ & $ \vee $ & $ (\neg(x \wedge \neg y \wedge z) \wedge \Diamond(x, y, z))$ & \\ \hline 0 & 0 & 0 & 0 & $ \vee $ & $ (1 \wedge \Diamond(0, 0, 0)) $ & $ = \Diamond(0, 0, 0) $\\ 0 & 0 & 1 & 0 & $ \vee $ & $ (1 \wedge \Diamond(0, 0, 1)) $ & $ = \Diamond(0, 0, 1) $\\ 0 & 1 & 0 & 0 & $ \vee $ & $ (1 \wedge \Diamond(0, 1, 0)) $ & $ = \Diamond(0, 1, 0) $\\ 0 & 1 & 1 & 0 & $ \vee $ & $ (1 \wedge \Diamond(0, 1, 1)) $ & $ = \Diamond(0, 1, 1) $\\ 1 & 0 & 0 & 0 & $ \vee $ & $ (1 \wedge \Diamond(1, 0, 0)) $ & $ = \Diamond(1, 0, 0) $\\ 1 & 0 & 1 & 1 & $ \vee $ & $ (0 \wedge 1) $ & $ = 1 = \Diamond(1, 0, 1) $\\ 1 & 1 & 0 & 0 & $ \vee $ & $ (1 \wedge \Diamond(1, 1, 0)) $ & $ = \Diamond(1, 1, 0) $\\ 1 & 1 & 1 & 0 & $ \vee $ & $ (1 \wedge \Diamond(1, 1, 1)) $ & $ = \Diamond(1, 1, 1) $\\ \hline \end{tabular} \teilaufgabe Annahme: $ \beta(1, 0, 1) = 1 \beta(1, 1, 0) = 1 $, ansonsten 0. $ \Diamond(x, y, z) \equiv (x \wedge \neg y \wedge z) \vee (x \wedge y \wedge \neg z) \vee (\neg (x \wedge \neg y \wedge z) \wedge \neg (x \wedge y \wedge \neg z) \wedge \Diamond(x, y, z))$ Äquivalenter disjunkter Ausdruck dazu: $ \Diamond(x, y, z) \equiv \underbrace{(x \wedge \neg y \wedge z)}_{\beta(1, 0, 1)} \vee \underbrace{(x \wedge y \wedge \neg z)}_{\beta(1, 1, 0)} $ \aufgabe \begin{tabular}{l|l||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} $x$ & $y$ & $\phi_0$ & $\phi_1$ & $\phi_2$ & $\phi_3$ & $\phi_4$ & $\phi_5$ & $\phi_6$ & $\phi_7$ & $\phi_8$ & $\phi_9$ & $\phi_{10}$ & $\phi_{11}$ & $\phi_{12}$ & $\phi_{13}$ & $\phi_{14}$ & $\phi_{15}$ \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\ \end{tabular} $ \phi_{10} \equiv (\neg x \wedge \neg y) \vee (x \wedge \neg y) \equiv \neg y$ \aufgabe \teilaufgabe Zu beweisen: $ p \Rightarrow (q \vee r) \equiv (p \Rightarrow q) \vee (p \Rightarrow r) $ \begin{tabular}{|l|l|l|cl|cl|} \hline $p$ & $q$ & $r$ & $p \Rightarrow (q \vee r)$ & & $(p \Rightarrow q) \vee (p \Rightarrow r) $ & \\ \hline 0 & 0 & 0 & $ (0 \Rightarrow \cdots) $ & $ = 1 $ & $(0 \Rightarrow \cdots) \vee (0 \Rightarrow \cdots)$ & $ = 1$ \\ 0 & 0 & 1 & $ (0 \Rightarrow \cdots) $ & $ = 1 $ & $(0 \Rightarrow \cdots) \vee (0 \Rightarrow \cdots)$ & $ = 1$ \\ 0 & 1 & 0 & $ (0 \Rightarrow \cdots) $ & $ = 1 $ & $(0 \Rightarrow \cdots) \vee (0 \Rightarrow \cdots)$ & $ = 1$ \\ 0 & 1 & 1 & $ (0 \Rightarrow \cdots) $ & $ = 1 $ & $(0 \Rightarrow \cdots) \vee (0 \Rightarrow \cdots)$ & $ = 1$ \\ 1 & 0 & 0 & $ (1 \Rightarrow 0)$ & $ = 0 $ & $(1 \Rightarrow 0) \vee (1 \Rightarrow 0)$ & $ = 0$ \\ 1 & 0 & 1 & $ (1 \Rightarrow 1)$ & $ = 1 $ & $(1 \Rightarrow 0) \vee (1 \Rightarrow 1)$ & $ = 1$ \\ 1 & 1 & 0 & $ (1 \Rightarrow 1)$ & $ = 1 $ & $(1 \Rightarrow 1) \vee (1 \Rightarrow 0)$ & $ = 1$ \\ 1 & 1 & 1 & $ (1 \Rightarrow 1)$ & $ = 1 $ & $(1 \Rightarrow 1) \vee (1 \Rightarrow 1)$ & $ = 1$ \\ \hline \end{tabular} Wie man sieht sind die Ergebnisse in der Wahrheitstabelle für beide Seiten identisch, somit ist die rechte und die linke Seite der Gleichung äquivalent. \teilaufgabe \begin{enumerate} \item $ p = true = 1 $ \begin{flalign*} 1 \Rightarrow (q \vee r) & \equiv (1 \Rightarrow q) \vee (1 \Rightarrow r) & \\ 0 \vee (q \vee r) & \equiv (0 \vee q) \vee (0 \vee r) & \\ q \vee r & \equiv q \vee r & \\ true \end{flalign*} \item $ p = false = 0 $ \begin{flalign*} 0 \Rightarrow (q \vee r) & \equiv (0 \Rightarrow q) \vee (0 \Rightarrow r) & \\ 1 & \equiv 1 \vee 1 & \\ true \end{flalign*} \end{enumerate} \begin{tabular}{|l|l|l|cccl|} \hline $p$ & $q$ & $r$ & $((p \Rightarrow q) \vee (p \Rightarrow r))$ & $\Leftrightarrow$ & $(p \Rightarrow (q \vee r))$ & \\ \hline 0 & 0 & 0 & $(1 \vee 1)$ & $\Leftrightarrow$ & 1 & $=1$ \\ 0 & 0 & 1 & $(1 \vee 1)$ & $\Leftrightarrow$ & 1 & $=1$ \\ 0 & 1 & 0 & $(1 \vee 1)$ & $\Leftrightarrow$ & 1 & $=1$ \\ 0 & 1 & 1 & $(1 \vee 1)$ & $\Leftrightarrow$ & 1 & $=1$ \\ 1 & 0 & 0 & $(0 \vee 0)$ & $\Leftrightarrow$ & 0 & $=1$ \\ 1 & 0 & 1 & $(0 \vee 1)$ & $\Leftrightarrow$ & 1 & $=1$ \\ 1 & 1 & 0 & $(1 \vee 0)$ & $\Leftrightarrow$ & 1 & $=1$ \\ 1 & 1 & 1 & $(1 \vee 1)$ & $\Leftrightarrow$ & 1 & $=1$ \\ \hline \end{tabular} Dieser Ausdruck ist für jede Belegung wahr und somit eine Tautologie. \aufgabe \teilaufgabe \begin{flalign*} (p \wedge q) \Rightarrow ((p \wedge r) \vee (q \wedge \neg r)) & & \text{Angabe} \\ \neg (p \wedge q) \vee ((p \wedge r) \vee (q \wedge \neg r)) & & \text{Auflösung der Implikation} \\ \neg (p \wedge q) \vee (p \wedge r) \vee (q \wedge \neg r) & & \text{Auflösung der Klammern} \\ (\neg p \vee \neg q) \vee (p \wedge r) \vee (q \wedge \neg r) & & \text{de Morgan} \\ (a \vee (p \wedge r)) \vee (q \wedge \neg r) & & \text{Substitution } a = (\neg p \vee \neg q)\\ ((a \vee p) \wedge (a \vee r)) \vee (q \wedge \neg r) & & \text{Distributivgesetz} \\ ((\neg p \vee \neg q \vee p) \wedge (\neg p \vee \neg q \vee r)) \vee (q \wedge \neg r) & & \text{Resubstitution} \\ (1 \wedge (\neg p \vee \neg q \vee r)) \vee (q \wedge \neg r) & & p \vee \neg p = 1 \\ (\neg p \vee \neg q \vee r) \vee (q \wedge \neg r) & & 1 \wedge x = x \\ b \vee (q \wedge \neg r) & & \text{Substitution } b = (\neg p \vee \neg q \vee r)\\ (b \vee q) \wedge (b \vee \neg r) & & \text{Distributivgesetz}\\ (\neg p \vee \neg q \vee r \vee q) \wedge (\neg p \vee \neg q \vee r \vee \neg r) & & \text{Resubstitution}\\ 1 \wedge 1 & & q \vee \neg q = 1, r \vee \neg r = 1\\ 1 \end{flalign*} \teilaufgabe $ \underbrace{((p \wedge r) \vee (q \wedge \neg r))}_{\text{muss 1 sein}} \Rightarrow \underbrace{(p \wedge q)}_{\text{muss 0 sein}} $ Angenommen man setzt $ p = 1, q = 0, r = 1 $ in den Ausdruck ein, so bekommt man $((1 \wedge 1) \vee (0 \wedge 0)) \Rightarrow (1 \wedge 0)$, welches $(1 \vee 0) \Rightarrow 0$ entspricht, dass man weiter zu $1 \Rightarrow 0$ vereinfachen kann, was dem Wahrheitswert 0 (false) entspricht und damit für diese Belegung nicht stimmt. Somit kann der Ausdruck nicht für alle Belegungen von p, q und r gelten. \end{document}