Übungsblatt 2

Aufgabe 1

(a)

\begin{equation} \phi_{1}:=\bigwedge_{(i;\,j)\in[1;\,30]}((A_{(i;\,j)}\land\neg G_{(i;\,j)}\land\neg K_{(i;\,j)}\land\neg O_{(i;\,j)})\lor(\neg A_{(i;\,j)}\land G_{(i;\,j)}\land\neg K_{(i;\,j)}\land\neg O_{(i;\,j)})\nonumber \\ \end{equation} \begin{equation} \lor(\neg A_{(i;\,j)}\land\neg G_{(i;\,j)}\land K_{(i;\,j)}\land\neg O_{(i;\,j)})\lor(\neg A_{(i;\,j)}\land\neg G_{(i;\,j)}\land\neg K_{(i;\,j)}\land O_{(i;\,j)}))\nonumber \\ \end{equation}

(b)

Die Formel \(\phi_{2}\) repräsentiert, dass es gibt mindest ein Katzenliebhaber, welcher allen Nachbarn Katzenlieber sind.

(c)

\begin{equation} \phi_{3}:=\bigwedge_{\begin{subarray}{c}(i;\,j)\in[1;\,30]^{2}\\ k\in\{1;\,30\}\end{subarray}}(G_{(i;\,k)}\land G_{(k;\,j)})\nonumber \\ \end{equation}

(d)

\begin{equation} \phi_{4}:=\bigwedge_{(i;\,j)\in[2;\,29]}\left(A_{(i;\,j)}\to\left(\bigvee_{k\in\{-1;\,1\}}\left(O_{(i+k;\,j)}\lor O_{(i;\,j+k)}\right)\land\neg\bigvee_{k\in\{-1;\,1\}}\left(K_{(i+k;\,j)}\lor K_{(i;\,j+k)}\right)\right)\right)\nonumber \\ \end{equation}

Aufgabe 2

(a)

Von volgenden Tabeln sehen wir, dass \(\phi_{1}\) und \(\phi_{2}\) sind nicht äquivalent aber \(\phi_{3}\) und \(\phi_{4}\) sind äquivalent.

\(A_{2}\) \(A_{1}\) \(A_{0}\) \(\neg A_{1}\) \(\phi_{1}:=(A_{0}\land\neg A_{1})\)
0 0 0 1 0
0 0 1 1 1
0 1 0 0 0
0 1 1 0 0
1 0 0 1 0
1 0 1 1 1
1 1 0 0 0
1 1 1 0 0
\(A_{2}\) \(A_{1}\) \(A_{0}\) \((A_{0}\land A_{1})\) \((A_{0}\land A_{2})\) \(((A_{0}\land A_{1})\to(A_{0}\land A_{2}))\) \(\phi_{2}:=\neg((A_{0}\land A_{1})\to(A_{0}\land A_{2}))\)
0 0 0 0 0 1 0
0 0 1 0 0 1 0
0 1 0 0 0 1 0
0 1 1 1 0 0 1
1 0 0 0 0 1 0
1 0 1 0 1 1 0
1 1 0 0 0 1 0
1 1 1 1 1 1 0
\(A_{1}\) \(A_{0}\) \(\phi_{3}:=(A_{0}\to A_{1})\)
0 0 1
0 1 0
1 0 1
1 1 1
\(A_{1}\) \(A_{0}\) \(\neg A_{1}\) \((A_{0}\land\neg A_{1})\) \(\phi_{4}:=((A_{0}\land\neg A_{1})\to 0)\)
0 0 1 0 1
0 1 1 1 0
1 0 0 0 1
1 1 0 0 1

(b)

Die Äquvalenz gilt nicht in jeden Fall. Seien \(I=\{i_{1};\,i_{2}\}\) und \(J=\{j_{1};\,j_{2}\}\) sind:

\begin{equation} \bigwedge_{i\in I}\bigvee_{j\in J}\phi_{(i;\,j)}\equiv\bigwedge_{i\in I}(\phi_{i;\,j_{1}}\lor\phi_{i;\,j_{2}})\equiv(\phi_{(i_{1};\,j_{1})}\lor\phi_{(i_{1};\,j_{2})})\land(\phi_{(i_{2};\,j_{1})}\lor\phi_{(i_{2};\,j_{2})})\nonumber \\ \end{equation} \begin{equation} \equiv(\phi_{(}{i_{1};\,j_{1})}\land\phi_{(i_{2};\,j_{1})})\lor(\phi_{(i_{1};\,j_{2})}\land\phi_{(i_{2};\,j_{2})})\lor(\phi_{(i_{1};\,j_{1})}\land\phi_{(i_{2};\,j_{1})})\lor(\phi_{(i_{1};\,j_{2})}\land\phi_{(i_{2};\,j_{2})})\nonumber \\ \end{equation}

aber

\begin{equation} \bigvee_{i\in I}\bigwedge_{j\in J}\phi_{(i;\,j)}\equiv\bigvee_{i\in I}(\phi_{(i;\,j_{1}})\land\phi_{(i;\,j_{2}}))\equiv(\phi_{(i_{1};\,j_{1})}\land\phi_{(i_{1};\,j_{2})})\lor(\phi_{(i_{2};\,j_{1})}\land\phi_{(i_{2};\,j_{2})})\nonumber \\ \end{equation}

Diese Aussagen sind nicht äquivalente.