\documentclass[10pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage[latin1]{inputenc}

\DeclareMathOperator{\CSA}{CSA}
\DeclareMathOperator{\FA}{FA}
\DeclareMathOperator{\MUX}{MUX}
\DeclareMathOperator{\Dec}{Dec}
\DeclareMathOperator{\FDec}{FDec}
\DeclareMathOperator{\BCD}{BCD}
\DeclareMathOperator{\BA}{BA}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}

\thispagestyle{empty}

\begin{center}
  {\Large Übungsblatt 6} \\
  Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
  Carsten Saar (Matrikelnummer 2030107) \\
  Thomas Ospelt (Matrikelnummer 2029959) \\
  Timo Adam (Matrikelnummer 2031946) \\
  Übungsgruppe 8 - Di, 15-17 Uhr \\
  Steffen Heil \\
\end{center}

\newpage
\section*{Aufgabe 1}
siehe Anhang (Zeichnung)

\section*{Aufgabe 2}
siehe Anhang (Zeichnung)

\section*{Aufgabe 4}
siehe Anhang (Zeichnung)

\section*{Aufgabe 5}
Wir haben bereits in der Vorlesung bewiesen, dass es zu jeder Schaltfunktion $f$ einen boole'schen Ausdruck $e \in \BA$ gibt,
der $f$ berechnet. Vollständig geklammerte boole'sche Ausdrücke sind wie folgt definiert:
\begin{eqnarray*}
  V & = & \{ x_1, \ldots, x_n \} \quad\text{endliche Menge von Variablen} \\
  B_1 & = & \{0,1\} \cup V \\
  \forall e_1,e_2 \in B_i & & e_1 \in B_{i+1} \\
  & & (e_1 \wedge e_2) \in B_{i+1} \quad\text{Und} \\
  & & (e_1 \vee e_2) \in B_{i+1} \quad\text{Oder} \\
  & & (e_1 \varoplus e_2) \in B_{i+1} \quad\text{Addition modulo 2} \\
  & & (\sim e_1) \in B_{i+1} \quad\text{Negierung} \\
  \BA & = & \bigcup_{i=1}^\infty B_i \\
\end{eqnarray*}
\paragraph{Zu zeigen:} Es ist möglich jede Schaltfunktion $f$ durch einen boole'schen Ausdruck $e \in \BA'$ zu berechnen,
der nur aus NAND-Gattern besteht.
\paragraph{Beweis:} Dass es einen boole'schen Ausdruck $e \in \BA$ gibt, der die Funktion $f$ berechnet, ist bereits gezeigt.
Es genügt also zu zeigen, dass es möglich ist, jeden boole'schen Ausdruck $e \in \BA$ nur durch NAND-Gatter zu berechnen.
\begin{eqnarray*}
  (e_1 \wedge e_2)    & \equiv & ((e_1 \barwedge e_2) \barwedge (e_1 \barwedge e_2)) \\
  (e_1 \vee e_2)      & \equiv & ((e_1 \barwedge e_1) \barwedge (e_2 \barwedge e_2)) \\
  (e_1 \varoplus e_2) & \equiv & (e_3 \barwedge e_3) \text{ mit } e_3 := (((e_1 \barwedge e_1) \barwedge (e_2 \barwedge e_2)) \barwedge (e_1 \barwedge e_2)) \\
  (\sim e_1)        & \equiv & (e_1 \barwedge e_1) \\
\end{eqnarray*}
Zeigen durch Wertetabellen, dass oben genannte Äquivalenzen gelten.
$$ \begin{array}{c|c||c|c||c}
  e_1 & e_2 & e_1 \barwedge e_2 & (e_1 \barwedge e_2) \barwedge (e_1 \barwedge e_2) & e_1 \wedge e_2 \\ \hline \hline
  0 & 0 & 1 & 0 & 0 \\ \hline
  0 & 1 & 1 & 0 & 0 \\ \hline
  1 & 0 & 1 & 0 & 0 \\ \hline
  1 & 1 & 0 & 1 & 1 \\
\end{array} $$ $$ \begin{array}{c|c||c|c|c||c}
  e_1 & e_2 & e_1 \barwedge e_1 & e_2 \barwedge e_2 & (e_1 \barwedge e_1) \barwedge (e_2 \barwedge e_2) & e_1 \vee e_2 \\ \hline \hline
  0 & 0 & 1 & 1 & 0 & 0 \\ \hline
  0 & 1 & 1 & 0 & 1 & 1 \\ \hline
  1 & 0 & 0 & 1 & 1 & 1 \\ \hline
  1 & 1 & 0 & 0 & 1 & 1 \\
\end{array} $$ $$ \begin{array}{c|c||c|c|c|c|c||c}
  e_1 & e_2 & e_1 \barwedge e_1 & e_2 \barwedge e_2 & (e_1 \barwedge e_1) \barwedge (e_2 \barwedge e_2) & e_1 \barwedge e_2 & e_3 & e_3 \barwedge e_3 \\ \hline \hline
  0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ \hline
  0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ \hline
  1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ \hline
  1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\
\end{array} $$ $$ \begin{array}{c||c||c}
  e_1 & e_1 \barwedge e_1 & \sim e_1 \\ \hline \hline
  0 & 1 & 1 \\ \hline
  1 & 0 & 0 \\
\end{array} $$
Definiere boole'sche Ausdrücke ausschließlich über NAND-Gatter in $\BA'$
\begin{eqnarray*}
  V & = & \{ x_1, \ldots, x_n \} \quad\text{endliche Menge von Variablen} \\
  B_1 & = & \{0,1\} \cup V \\
  \forall e_1,e_2 \in B_i & & e_1 \in B_{i+1} \\
  & & ((e_1 \barwedge e_2) \barwedge (e_1 \barwedge e_2)) \in B_{i+1} \quad\text{Und} \\
  & & ((e_1 \barwedge e_1) \barwedge (e_2 \barwedge e_2)) \in B_{i+1} \quad\text{Oder} \\
  & & (e_3 \barwedge e_3) \in B_{i+1}  \text{ mit } e_3 := (((e_1 \barwedge e_1) \barwedge (e_2 \barwedge e_2)) \barwedge (e_1 \barwedge e_2)) \quad\text{Addition modulo 2} \\
  & & (e_1 \barwedge e_1) \in B_{i+1} \quad\text{Negierung} \\
  \BA' & = & \bigcup_{i=1}^\infty B_i \\
\end{eqnarray*}
Da die oben genannten Äquivalenzen gelten, ist es folglich möglich jede Schaltfunktion $f$ durch einen boole'schen Ausdruck
$e \in \BA'$ zu berechnen. \QED

\section*{Aufgabe 6}
\begin{enumerate}[(a)]
  \item \textbf{Zu zeigen:}
        $$ \langle x^t \rangle + \langle y^t \rangle = \langle x^0 \rangle + \langle y^0 \rangle \quad\forall t \ge 0 $$
        \textbf{Induktionsanfang $t=0$:} gilt trivialerweise
        $$ \langle x^0 \rangle + \langle y^0 \rangle = \langle x^0 \rangle + \langle y^0 \rangle $$
        \textbf{Induktionsschritt $t \leadsto t+1$:} Aus der Konstruktion des von-Neumann-Addierers und des Halbaddierers ergibt sich
        \begin{eqnarray*}
          x_i^{t+1} & = & u_i^t = \begin{cases} 0 & \text{für } i=0 \\ x_{i-1}^t \wedge y_{i-1}^t & \text{für } i>0 \\ \end{cases} \\
          y_i^{t+1} & = & s_i^t = x_i^t \varoplus y_i^t \\
        \end{eqnarray*}
        Betrachtet man die Summe zum Zeitpunkt $t+1$ erhält man
        \begin{eqnarray*}
                \langle x^{t+1} \rangle + \langle y^{t+1} \rangle
          & = & \left[ \sum_{i=1}^n \left( x_{i-1}^t \wedge y_{i-1}^t \right) \cdot 2^i \right] +
                \left[ \sum_{i=0}^n \left( x_i^t \varoplus y_i^t \right) \cdot 2^i \right] \\
          & = & \left[ \sum_{i=0}^{n-1} \left( x_i^t \wedge y_i^t \right) \cdot 2^{i+1} \right] +
                \left[ \sum_{i=0}^n \left( x_i^t \varoplus y_i^t \right) \cdot 2^i \right] \\
          & = & \left[ \sum_{i=0}^{n-1} \underbrace{\left( 2 \cdot \left( x_i^t \wedge y_i^t \right) + \left( x_i^t \varoplus y_i^t \right) \right)}_{x_i^t+y_i^t \text{ nach Def. HA}} \cdot 2^i \right] + \left( x_n^t \varoplus y_n^t \right) \cdot 2^n \\
          & = & \left( \sum_{i=0}^{n-1} \left( x_i^t + y_i^t \right) \cdot 2^i \right) + \left( x_n^t \varoplus y_n^t \right) \cdot 2^n \\
          & = & \left( \sum_{i=0}^{n-1} x_i^t \cdot 2^i \right) + \left( \sum_{i=0}^{n-1} y_i^t \cdot 2^i \right) + \left( x_n^t \varoplus y_n^t \right) \cdot 2^n \\
          & = & \left( \sum_{i=0}^{n-1} x_i^t \cdot 2^i \right) + \left( \sum_{i=0}^{n-1} y_i^t \cdot 2^i \right) + \underbrace{\left( x_n^t \varoplus y_n^t \right) \cdot 2^n + 2 \cdot \left( x_n^t \wedge y_n^t \right) \cdot 2^n}_{\left( x_n^t+y_n^t \right) \cdot 2^n} \mod 2^{n+1} \\
          & = & \left( \sum_{i=0}^n x_i^t \cdot 2^i \right) + \left( \sum_{i=0}^n y_i^t \cdot 2^i \right) \mod 2^{n+1} \\
          & = & \langle x^t \rangle + \langle y^t \rangle \mod 2^{n+1} \\
        \end{eqnarray*}
        \QED
  \item \textbf{Zu zeigen:}
        $$ \exists t \le n+1: \quad \langle y^t \rangle = \langle x^0 \rangle + \langle y^0 \rangle $$
        \textbf{Beweis:} \\
        Wir haben bereits gezeigt
        $$ \langle x^t \rangle + \langle y^t \rangle = \langle x^0 \rangle + \langle y^0 \rangle \quad\forall t \ge 0 $$
        Soll zu einem bestimmten Zeitpunkt $t'$ das Register $\langle y^{t'} \rangle$ die Summe enthalten, muss gelten
        \begin{eqnarray*}
          & \langle y^{t'} \rangle = \langle x^0 \rangle + \langle y^0 \rangle & (1) \\
          \text{und} & \langle x^{t'} \rangle + \langle y^{t'} \rangle = \langle x^0 \rangle + \langle y^0 \rangle & (2) \\
          \Longrightarrow & \langle x^{t'} \rangle = 0 & (2)-(1) \\
        \end{eqnarray*}
        Untersuche nun, ob es einen Zeitpunkt $t'$ gibt, ab dem $\langle x^{t'} \rangle$ unabhängig von den Startwerten
        $\langle x^0 \rangle$ und $\langle y^0 \rangle$ gleich $0$ wird. $\langle x^{t'} \rangle =0$ gilt genau dann, wenn
        $x_i^{t'}=0 \:\forall i$. Da nach Konstruktion
        $$ x_i^{t'+1} = \begin{cases} 0 & \text{für } i=0 \\ x_{i-1}^{t'} \wedge y_{i-1}^{t'} & \text{für } i>0 \\ \end{cases} $$
        gilt, wird offensichtlich in jedem Durchlauf das $0$-te Bit auf $0$ gesetzt. Das $i$-te Bit des neuen $x$ ist gleich dem
        Ergebnis einer Und-Verknüpfung der $(i-1)$-ten Bits der alten $x$ und $y$ aus dem letzten Taktzyklus. Daraus läßt sich folgern
        \begin{eqnarray*}
          x_0^1 & = & 0 \\
          \Longrightarrow\quad x_0^t & = & 0 \quad\forall t \ge 1 \\
          x_1^2 & = & x_0^1 \wedge y_0^1=0 \\
          \Longrightarrow\quad x_1^t & = & 0 \quad\forall t \ge 2 \\
          x_2^3 & = & x_1^2 \wedge y_1^2=0 \\
          \Longrightarrow\quad x_2^t & = & 0 \quad\forall t \ge 3 \\
          \vdots & & \\
          x_{n-1}^n & = & x_{n-2}^{n-1} \wedge y_{n-2}^{n-1}=0 \\
          \Longrightarrow\quad x_{n-1}^t & = & 0 \quad\forall t \ge n \\
          x_n^{n+1} & = & x_{n-1}^n \wedge y_{n-1}^n=0 \\
          \Longrightarrow\quad x_n^t & = & 0 \quad\forall t \ge n+1 \\
        \end{eqnarray*}
        Das heißt, dass spätestens ab dem Taktzyklus $t'=n+1$ alle Bits $x_i^{t'}=x_i^{n+1}=0$ und somit
        $\langle x^{t'} \rangle = \langle x^{n+1} \rangle = 0$ unabhängig von den Startwerten
        $\langle x^0 \rangle$ und $\langle y^0 \rangle$. Somit enthält das Register $y$ nach obiger
        Vorbetrachtung spätestens ab dem $(n-1)$-ten Taktzyklus die Summe von $\langle x^0 \rangle + \langle y^0 \rangle$. \QED
  \item $$ x_i^0=1 \;\forall i \ge 0 \quad\wedge\quad y_0^0=1 \quad\wedge\quad y_i^0=0 \;\forall i \ge 1 $$
        $$ \Longleftrightarrow\quad \langle x^0 \rangle = 2^n-1 \quad\wedge\quad \langle y^0 \rangle = 1 $$
\end{enumerate}

\end{document}