\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}
