\documentclass[10.5pt, a4paper]{article}
\usepackage{german}
\usepackage{a4}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{fancyhdr}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{lastpage}
\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage{graphicx}

\thispagestyle{empty}

\geometry{left=2.5cm,textwidth=15cm,top=3.0cm,textheight=23.5cm}

\begin{document}

\pagestyle{fancy}

\lhead{}
\chead{}
\rhead{}

\lfoot{}
\cfoot{Seite \thepage /\pageref{LastPage}}
\rfoot{}

\renewcommand{\headrulewidth}{0.2pt}
\renewcommand{\footrulewidth}{0.2pt}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}
\thispagestyle{fancy}

\section*{Aufgabe 1:}

\subsection*{Kosten:}
\begin{eqnarray*}
C_{hdec}(1) &=& 0 \\
C_{hdec}(n) &=& C_{hdec}(n-1) + 2^{n-1} \cdot (C_{and} + C_{or}) \\
&=& C_{hdec}(n-1) + 2^{n-1} \cdot 2 \\
&=& C_{hdec}(n-1) + 2^n \\
&=& 2^n + 2^{n-1} + ... + 2^2 + C_{hdec}(1) \\
&=& 2^n + 2^{n-1} + ... + 2^2 + 0 \\
&=& 2^n + 2^{n-1} + ... + 2^2 + 2^1 + 2^0 - 3 \\
&=& (\sum_{i=0}^{n} 2^i) - 3 \\
&=& (2^{n+1} - 1 ) -3 \\
&=& 2^{n+1} - 4 \\
\end{eqnarray*}
Beweis:
\begin{eqnarray*}
C_{hdec}(1) &=& 0 = 2^{1+1} - 4 \\
C_{hdec}(n) &=& 2 \cdot 2^{n-1} + C_{hdec}(n-1) \\
&\stackrel{\text{IV}}{=}& 2^n + (2^n - 4) \\
&=& 2^{n+1} - 4 \\
\end{eqnarray*}
\QED
\subsection*{Tiefe:}
\begin{eqnarray*}
D_{hdec}(1) &=& 0 \\
D_{hdec}(n) &=& D_{hdec}(n-1) + max\left\{D_{and},D_{or}\right\} \\
&=& D_{hdec}(n-1) + 1 \\
&=& D_{hdec}(n-2) + 1 + 1 \\
&=& ... \\
&=& n-1 + D_{hdec}(1) \\
&=& n-1 + 0 \\
&=& n-1 \\
\end{eqnarray*}
Beweis:
\begin{eqnarray*}
D_{hdec}(1) &=& 0 = 1-1 \\
D_{hdec}(n) &=& D_{hdec}(n-1) + 1 \\
&\stackrel{\text{IV}}{=}& n - 2 + 1 \\
&=& n - 1 \\
\end{eqnarray*}
\QED

\newpage

\section*{Aufgabe 2:}

\subsection*{a)}
\bild{7}{Aufgabe2a.jpg}{1-bit Half-Adder}{1-bit Half-Adder}

\subsection*{b)}
\indent $$CCI(0)\ :=\ (c_{in}\ =\ c_{out})$$
\bild{7}{Aufgabe2b.jpg}{n-bit Half-Adder}{n-bit Half-Adder}

\newpage

\subsection*{c)}

\noindent Wertetabelle (*): \\

\begin{tabular}{c|c|c|c}
$a$ & $c_{in}$ & $c_{out}$ & $s$ \\
\hline
0 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 \\
\end{tabular}
\\[0.5cm]
\noindent Korrektheit des Half-Adder:\\
$$\left\langle a_0\right\rangle\ +\ c_{in}\ \stackrel{\text{(*)}}{=} \left\langle c_{out},s\right\rangle$$

\noindent Induktionsanfang: $n=0$ \\
$$\left\langle a\left[-1:0\right]\right\rangle + c_{in} = 0 + c_{in} = c_{in} \stackrel{\text{n.Def.}}{=} c_{out} = \left\langle c_{out},s\left[-1:0\right] \right\rangle$$

\noindent Induktionsschritt: $n \hookrightarrow n+1$ \\
\begin{eqnarray*}
\left\langle a[n:0]\right\rangle + c_{in} & = & a_n \cdot 2^n + \left\langle a[n-1:0]\right\rangle + c_{in}\\
&\stackrel{\text{IA}}{=}& a_n \cdot 2^n + \left\langle c_{n-1}, s[n-1:0]\right\rangle \\
&=& a_n \cdot 2^n + c_{n-1} \cdot 2^n + \left\langle s[n-1:0]\right\rangle \\
&=& (a_n + c_{n-1}) \cdot 2^n + \left\langle s[n-1:0]\right\rangle \\
&\stackrel{\text{HA}}{=}& \left\langle c_{n},s_n\right\rangle \cdot 2^n + \left\langle s[n-1:0]\right\rangle \\
&=& \left\langle c_{n}, s[n:0]\right\rangle \\
&=& \left\langle c_{out}, s[n:0]\right\rangle \\
\end{eqnarray*}
\QED

\newpage

\section*{Aufgabe 4:}
\bild{7}{Aufgabe4.jpg}{Co-Berechnung}{Co-Berechnung}



\end{document}