\documentclass{uebungsblatt}
\usepackage{tikz}
\usetikzlibrary{snakes,arrows,shapes}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Praktikum: Grundlagen der Programmierung}
\blatt{2}
\gruppe{OV6}

\begin{document}

\aufgabe

\teilaufgabe

\begin{tabular}{rcl}
<factor> & ::= & '(' <expr> ')' | <var> | <const> | '!' <factor> \\
<summand> & ::= & <factor> | <summand> '\&\&' <factor> \\
<expr> & ::= & <summand> | <expr> '||' <summand> \\
<var> & ::= & 'X' | 'Y' | 'Z' \\
<const> & ::= & 'true' | 'false'
\end{tabular}

\teilaufgabe

Der aus diesen Regeln resultierende Baum ist natürlich durch die darin
definierten Präzedenzen und ihrer Rekursion sehr komplex und die Struktur des
Ausdruckes ist schwer zu erkennen. Die BNF-Regeln werden so angewendet, dass
der ||-Operator angewendet wird, der eine Möglichkeit der <expr>-Regel ist.
Wenn es im Ausdruck kein || gibt, wird die <summand>-Regel angewendet, die den
\&\&-Operator anwendet. Der ! kann jederzeit Vorkommen aber muss von einem
<factor> gefolgt werden, das kann wiederrum eine Variable <var> oder eine
Konstante <const> sein oder auch ein geklammerter Ausdruck <expr>, der es
ermöglicht die Auswertung des darin enthaltenen Ausdrucks bei <expr> zu starten
und von dort wieder alle Operatoren, Variablen und Konstanten einzusetzen.

\begin{tikzpicture}[>=latex,join=bevel,scale=0.9]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: expr4 -- expr5
  \draw [] (284bp,363bp) .. controls (272bp,351bp) and (255bp,334bp)  .. (242bp,321bp);
  % Edge: const2 -- true1
  \draw [] (138bp,360bp) .. controls (138bp,349bp) and (138bp,335bp)  .. (138bp,324bp);
  % Edge: summand2 -- summand3
  \draw [] (204bp,578bp) .. controls (190bp,566bp) and (171bp,550bp)  .. (157bp,538bp);
  % Edge: factor4 -- lparen1
  \draw [] (283bp,434bp) .. controls (271bp,422bp) and (254bp,405bp)  .. (242bp,393bp);
  % Edge: var1 -- x
  \draw [] (227bp,72bp) .. controls (227bp,61bp) and (227bp,47bp)  .. (227bp,36bp);
  % Edge: expr1 -- summand6
  \draw [] (276bp,725bp) .. controls (294bp,713bp) and (320bp,694bp)  .. (339bp,681bp);
  % Edge: summand5 -- factor6
  \draw [] (384bp,288bp) .. controls (384bp,277bp) and (384bp,263bp)  .. (384bp,252bp);
  % Edge: factor3 -- notop1
  \draw [] (281bp,506bp) .. controls (269bp,494bp) and (252bp,477bp)  .. (240bp,465bp);
  % Edge: expr2 -- orop2
  \draw [] (145bp,648bp) .. controls (143bp,637bp) and (142bp,623bp)  .. (140bp,612bp);
  % Edge: summand6 -- factor7
  \draw [] (364bp,648bp) .. controls (365bp,637bp) and (367bp,623bp)  .. (368bp,612bp);
  % Edge: var2 -- z
  \draw [] (445bp,432bp) .. controls (445bp,421bp) and (445bp,407bp)  .. (445bp,396bp);
  % Edge: expr5 -- summand4
  \draw [] (227bp,288bp) .. controls (227bp,277bp) and (227bp,263bp)  .. (227bp,252bp);
  % Edge: expr2 -- summand2
  \draw [] (163bp,651bp) .. controls (175bp,639bp) and (193bp,623bp)  .. (206bp,610bp);
  % Edge: factor6 -- const3
  \draw [] (384bp,216bp) .. controls (384bp,205bp) and (384bp,191bp)  .. (384bp,180bp);
  % Edge: factor2 -- const2
  \draw [] (138bp,432bp) .. controls (138bp,421bp) and (138bp,407bp)  .. (138bp,396bp);
  % Edge: summand3 -- factor2
  \draw [] (138bp,504bp) .. controls (138bp,493bp) and (138bp,479bp)  .. (138bp,468bp);
  % Edge: const3 -- true2
  \draw [] (384bp,144bp) .. controls (384bp,133bp) and (384bp,119bp)  .. (384bp,108bp);
  % Edge: summand2 -- factor3
  \draw [] (240bp,578bp) .. controls (253bp,565bp) and (269bp,549bp)  .. (281bp,537bp);
  % Edge: factor4 -- expr4
  \draw [] (299bp,432bp) .. controls (299bp,421bp) and (299bp,407bp)  .. (299bp,396bp);
  % Edge: expr1 -- orop1
  \draw [] (257bp,720bp) .. controls (257bp,709bp) and (257bp,695bp)  .. (257bp,684bp);
  % Edge: expr3 -- summand1
  \draw [] (50bp,576bp) .. controls (48bp,565bp) and (45bp,551bp)  .. (43bp,540bp);
  % Edge: summand4 -- factor5
  \draw [] (227bp,216bp) .. controls (227bp,205bp) and (227bp,191bp)  .. (227bp,180bp);
  % Edge: expr4 -- orop3
  \draw [] (299bp,360bp) .. controls (299bp,349bp) and (299bp,335bp)  .. (299bp,324bp);
  % Edge: factor1 -- const1
  \draw [] (40bp,432bp) .. controls (40bp,421bp) and (40bp,407bp)  .. (40bp,396bp);
  % Edge: factor3 -- factor4
  \draw [] (298bp,504bp) .. controls (298bp,493bp) and (298bp,479bp)  .. (299bp,468bp);
  % Edge: factor7 -- factor8
  \draw [] (387bp,579bp) .. controls (399bp,567bp) and (417bp,550bp)  .. (429bp,537bp);
  % Edge: expr2 -- expr3
  \draw [] (129bp,652bp) .. controls (112bp,639bp) and (88bp,620bp)  .. (71bp,608bp);
  % Edge: summand1 -- factor1
  \draw [] (40bp,504bp) .. controls (40bp,493bp) and (40bp,479bp)  .. (40bp,468bp);
  % Edge: expr1 -- expr2
  \draw [] (238bp,725bp) .. controls (218bp,712bp) and (186bp,692bp)  .. (166bp,679bp);
  % Edge: factor7 -- notop2
  \draw [] (371bp,576bp) .. controls (371bp,565bp) and (371bp,551bp)  .. (371bp,540bp);
  % Edge: const1 -- false1
  \draw [] (40bp,360bp) .. controls (40bp,349bp) and (40bp,335bp)  .. (40bp,324bp);
  % Edge: factor5 -- var1
  \draw [] (227bp,144bp) .. controls (227bp,133bp) and (227bp,119bp)  .. (227bp,108bp);
  % Edge: expr4 -- summand5
  \draw [] (316bp,364bp) .. controls (330bp,352bp) and (351bp,335bp)  .. (365bp,322bp);
  % Edge: factor4 -- rparen1
  \draw [] (315bp,434bp) .. controls (327bp,422bp) and (344bp,405bp)  .. (356bp,393bp);
  % Edge: summand2 -- andop1
  \draw [] (223bp,576bp) .. controls (223bp,565bp) and (223bp,551bp)  .. (223bp,540bp);
  % Edge: factor8 -- var2
  \draw [] (445bp,504bp) .. controls (445bp,493bp) and (445bp,479bp)  .. (445bp,468bp);
  % Node: rparen1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (371bp,378bp) ellipse (27bp and 18bp);
  \draw (371bp,378bp) node {)};
\end{scope}
  % Node: const1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (40bp,378bp) ellipse (27bp and 18bp);
  \draw (40bp,378bp) node {const};
\end{scope}
  % Node: const3
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (384bp,162bp) ellipse (27bp and 18bp);
  \draw (384bp,162bp) node {const};
\end{scope}
  % Node: const2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (138bp,378bp) ellipse (27bp and 18bp);
  \draw (138bp,378bp) node {const};
\end{scope}
  % Node: orop3
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (299bp,306bp) ellipse (27bp and 18bp);
  \draw (299bp,306bp) node {||};
\end{scope}
  % Node: orop2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (138bp,594bp) ellipse (27bp and 18bp);
  \draw (138bp,594bp) node {||};
\end{scope}
  % Node: orop1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (257bp,666bp) ellipse (27bp and 18bp);
  \draw (257bp,666bp) node {||};
\end{scope}
  % Node: andop1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (223bp,522bp) ellipse (27bp and 18bp);
  \draw (223bp,522bp) node {\&\&};
\end{scope}
  % Node: expr2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (147bp,666bp) ellipse (27bp and 18bp);
  \draw (147bp,666bp) node {expr};
\end{scope}
  % Node: expr3
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (53bp,594bp) ellipse (27bp and 18bp);
  \draw (53bp,594bp) node {expr};
\end{scope}
  % Node: expr1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (257bp,738bp) ellipse (27bp and 18bp);
  \draw (257bp,738bp) node {expr};
\end{scope}
  % Node: expr4
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (299bp,378bp) ellipse (27bp and 18bp);
  \draw (299bp,378bp) node {expr};
\end{scope}
  % Node: expr5
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (227bp,306bp) ellipse (27bp and 18bp);
  \draw (227bp,306bp) node {expr};
\end{scope}
  % Node: true1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (138bp,306bp) ellipse (27bp and 18bp);
  \draw (138bp,306bp) node {true};
\end{scope}
  % Node: true2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (384bp,90bp) ellipse (27bp and 18bp);
  \draw (384bp,90bp) node {true};
\end{scope}
  % Node: var1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (227bp,90bp) ellipse (27bp and 18bp);
  \draw (227bp,90bp) node {var};
\end{scope}
  % Node: lparen1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (227bp,378bp) ellipse (27bp and 18bp);
  \draw (227bp,378bp) node {(};
\end{scope}
  % Node: var2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (445bp,450bp) ellipse (27bp and 18bp);
  \draw (445bp,450bp) node {var};
\end{scope}
  % Node: factor4
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (299bp,450bp) ellipse (28bp and 18bp);
  \draw (299bp,450bp) node {factor};
\end{scope}
  % Node: factor5
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (227bp,162bp) ellipse (28bp and 18bp);
  \draw (227bp,162bp) node {factor};
\end{scope}
  % Node: factor6
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (384bp,234bp) ellipse (28bp and 18bp);
  \draw (384bp,234bp) node {factor};
\end{scope}
  % Node: factor7
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (371bp,594bp) ellipse (28bp and 18bp);
  \draw (371bp,594bp) node {factor};
\end{scope}
  % Node: factor1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (40bp,450bp) ellipse (28bp and 18bp);
  \draw (40bp,450bp) node {factor};
\end{scope}
  % Node: factor2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (138bp,450bp) ellipse (28bp and 18bp);
  \draw (138bp,450bp) node {factor};
\end{scope}
  % Node: factor3
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (297bp,522bp) ellipse (28bp and 18bp);
  \draw (297bp,522bp) node {factor};
\end{scope}
  % Node: summand3
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (138bp,522bp) ellipse (40bp and 18bp);
  \draw (138bp,522bp) node {summand};
\end{scope}
  % Node: summand2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (223bp,594bp) ellipse (40bp and 18bp);
  \draw (223bp,594bp) node {summand};
\end{scope}
  % Node: summand1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (40bp,522bp) ellipse (40bp and 18bp);
  \draw (40bp,522bp) node {summand};
\end{scope}
  % Node: factor8
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (445bp,522bp) ellipse (28bp and 18bp);
  \draw (445bp,522bp) node {factor};
\end{scope}
  % Node: summand6
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (361bp,666bp) ellipse (40bp and 18bp);
  \draw (361bp,666bp) node {summand};
\end{scope}
  % Node: summand5
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (384bp,306bp) ellipse (40bp and 18bp);
  \draw (384bp,306bp) node {summand};
\end{scope}
  % Node: summand4
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (227bp,234bp) ellipse (40bp and 18bp);
  \draw (227bp,234bp) node {summand};
\end{scope}
  % Node: false1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (40bp,306bp) ellipse (27bp and 18bp);
  \draw (40bp,306bp) node {false};
\end{scope}
  % Node: notop1
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (225bp,450bp) ellipse (27bp and 18bp);
  \draw (225bp,450bp) node {!};
\end{scope}
  % Node: x
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (227bp,18bp) ellipse (27bp and 18bp);
  \draw (227bp,18bp) node {X};
\end{scope}
  % Node: z
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (445bp,378bp) ellipse (27bp and 18bp);
  \draw (445bp,378bp) node {Z};
\end{scope}
  % Node: notop2
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (371bp,522bp) ellipse (27bp and 18bp);
  \draw (371bp,522bp) node {!};
\end{scope}
%
\end{tikzpicture}

\aufgabe

\teilaufgabe

% i for lower case roman numbers
\begin{enumerate}[i]
  \item
    \begin{flalign*}
left \vee forward \vee right & & \text{Angabe} \\
left \vee \neg (left \vee right) \vee right & & \text{Einsetzen von } forward \\
left \vee (\neg left \wedge \neg right) \vee right & & \text{de Morgan} \\
left \vee right \vee (\neg left \wedge \neg right) & & \text{Kommutativgesetz} \\
a \vee (\neg left \wedge \neg right) & & \text{Substitution } a = left \vee right \\
(a \vee \neg left) \wedge (a \vee \neg right) & & \text{Distributivgesetz} \\
(left \vee right \vee \neg left) \wedge (left \vee right \vee \neg right) & & \text{Resubstitution} \\
(true \vee right) \wedge (true \vee left) & & x \vee \neg x = true \\
true \wedge true & & x \vee true = true \\
true
    \end{flalign*}
  \item
    \begin{flalign*}
\neg (left \wedge forward) & & \text{Angabe} \\
\neg (left \wedge \neg (left \vee right)) & & \text{Einsetzen von } forward \\
\neg (left \wedge \neg left \wedge \neg right) & & \text{de Morgan} \\
\neg (false \wedge \neg right) & & x \wedge \neg x = false \\
\neg false & & false \wedge x = false \\
true
    \end{flalign*}
  \item
    \begin{flalign*}
\neg (left \wedge right) & & \text{Angabe} \\
true & & \text{laut Angabe}
    \end{flalign*}
  \item
    \begin{flalign*}
\neg(forward \wedge right) & & \text{Angabe} \\
\neg(\neg(left \vee right) \wedge right) & & \text{Einsetzen von } forward \\
\neg(\neg left \wedge \neg right \wedge right) & & \text{de Morgan} \\
\neg(\neg left \wedge false) & & x \wedge \neg x = false \\
\neg false & & \ x \wedge false = false \\
true
    \end{flalign*}
\end{enumerate}

\teilaufgabe

Die Lösung der Aufgabe ist als \texttt{kubica-righthand.logics} der 
E-Mail angehängt.

\teilaufgabe

Die Lösung der Aufgabe ist als \texttt{kubica-lefthand.logics} der 
E-Mail angehängt.

\end{document}