\documentclass[10pt]{article}

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

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}

\thispagestyle{empty}

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

\newpage

\section*{Aufgabe 1}
$ a,b \in \SetN $. \\
Beweis durch vollständige Induktion über $ b\in\SetN $: \\
Sei $a\in\SetN$ beliebig.
\begin{enumerate}
\item Induktionsanfang: $b=0$ \\
$ a+b = a+0 = a = 0+a = b+a \; \; \;$ (ok)

\item
\begin{enumerate}
\item Induktionsannahme: Für $b\in\SetN$ gelte: $a+b=b+a$

\item Induktionsbehauptung: Dann gilt für $b+1 \in \SetN$: $a+(b+1) = (b+1)+a$

\item Induktionsbegründung:
\begin{eqnarray*}
a+(b+1) & \stackrel{n.Vor. A1}{=} & (a+b)+1 \\
& \stackrel{(2a)}{=} & (b+a)+1 \\
& = & b+(a+1) \\
& \stackrel{(2a)}{=} & b+(1+a) \\
& = & (b+1)+a
\end{eqnarray*}
\hfill $\Box$
\end{enumerate}

\end{enumerate}

\section*{Aufgabe 2}
Seien $a,b,c\in\SetN$. \\
Beweis durch vollständige Induktion über $c\in\SetN$: \\
Seien $a,b\in\SetN$ beliebig.
\begin{enumerate}
\item Induktionsanfang: $c=0$ \\
$ a\cdot(b+c) = a\cdot(b+0) = a\cdot b = (a\cdot b) + (a\cdot 0) = (a\cdot b) + (a\cdot c) \; \; \;$ (ok)

\item
\begin{enumerate}
\item Induktionsannahme: Für $c\in\SetN$ gelte: $a\cdot(b+c) = (a\cdot b) + (a\cdot c)$

\item Induktionsbehauptung: Dann gilt für $c+1\in\SetN$: $a\cdot(b+(c+1))$

\item Induktionsbegründung:
\begin{eqnarray*}
a\cdot(b+(c+1)) & \stackrel{n.Vor. A1}{=} & a\cdot((b+c)+1) \\
& \stackrel{n.Vor. A2}{=} & a\cdot(b+c)+a \\
& \stackrel{(2a)}{=} & ((a\cdot b)+(a\cdot c)) +a \\
& \stackrel{n.Vor. A1}{=} & (a\cdot b) + ((a\cdot c)+a) \\
& = & (a\cdot b) + (a\cdot c +a) \\
& \stackrel{n.Vor. A2}{=} & (a\cdot b) + (a\cdot(c+1))
\end{eqnarray*}
\hfill $\Box$
\end{enumerate}

\end{enumerate}

\section* {Aufgabe 3}
Seien $a,b,c\in\SetN$. \\
Beweis durch vollständige Induktion über $c\in\SetN$: \\
Seien $a,b\in\SetN$ beliebig
\begin{enumerate}
\item Induktionsanfang: $c=0$ \\
$ a\cdot(b\cdot c) = a\cdot (b\cdot 0) = a\cdot 0 = (a\cdot b) \cdot 0 = (a\cdot b) \cdot c \; \; \; $ (ok)

\item
\begin{enumerate}
\item Induktionsannahme: Für $c\in\SetN$ gelte: $a\cdot(b\cdot c) = (a\cdot b) \cdot c$

\item Induktionsbehauptung: Dann gilt für $c+1\in\SetN$: $a\cdot(b\cdot(c+1)) = (a\cdot b)\cdot(c+1)$

\item Induktionsbegründung:
\begin{eqnarray*}
a\cdot(b\cdot(c+1)) & \stackrel{A2}{=} & a\cdot((b\cdot c) +b) \\
& \stackrel{A2}{=} & (a\cdot(b\cdot c)) + (a\cdot b) = a\cdot(b\cdot c) + (a\cdot b) \\
& \stackrel{(2a)}{=} & ((a\cdot b)\cdot c) + (a\cdot b) \\
& = & ((a\cdot b)\cdot c) + ((a\cdot b)\cdot 1) \\
& \stackrel{A2}{=} & (a\cdot b) \cdot (c+1)
\end{eqnarray*}
\hfill $\Box$
\end{enumerate}

\end{enumerate}

\section*{Aufgabe 4}
Seien $x_1,...,x_n\in \{0,1 \}$ \\
Beweise $f(x_1,...,x_n) = (x_1 \AND f(1,x_2,...,x_n) \OR (\overline{x_1} \AND f(0,x_2,...,x_n))$ durch Fallunterscheidung (2 Fälle): \\
1. Fall: $x_1=0$
\begin{eqnarray*}
f(0,x_2,...,x_n) & = & \underbrace{(0 \AND f(1,x_2,...,x_n))}_0 \OR \underbrace{(1 \AND f(0,x_2,...,x_n))}_{f(0,x_2,...,x_n)} \\
& = & 0 \OR f(0,x_2,...,x_n) \\
& = & f(0,x_2,...,x_n)
\end{eqnarray*}
2. Fall: $x_1=1$
\begin{eqnarray*}
f(1,x_2,...,x_n) & = & \underbrace{(1 \AND f(1,x_2,...,x_n))}_{f(1,x_2,...,x_n)} \OR \underbrace{(0 \AND f(0,x_2,...,x_n))}_0 \\
& = & f(1,x_2,...,x_n) \OR 0 \\
& = & f(1,x_2,...,x_n)
\end{eqnarray*}
\hfill $\Box$

\section*{Aufgabe 5}
Seien $a,b\in \{0,1\}$. Beweise: $ \underbrace{a \OR b}_x \equiv \underbrace{\overline{\overline{a} \AND \overline{b}}}_y$ \\

\begin{tabular}{cc|c|c|c|c|c|c}
a & b & x & $\overline{a}$ & $\overline{b}$ & $\overline{a} \AND \overline{b}$ & y & $x \equiv y$ \\ \hline
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\
0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 & 1 & 1
\end{tabular} \\ \\
Die Tabelle ergibt für $x\equiv y$ immer 1. Somit ist die Behauptung bewiesen. \hfill $\Box$

\section*{Aufgabe 6}
Seien $a,b,c\in\{0,1\}$.
\subsubsection*{(a)}
Zeige: $\underbrace{a \equiv b}_x \Rightarrow \underbrace{a \OR c \equiv b \OR c}_y$ \\
\begin{tabular}{ccc|c|c|c|c|c}
a & b & c & x & $a \OR c$ & $ b \OR c $ & y & $ x \Rightarrow y $ \\ \hline
0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
\end{tabular} \\ \\
Die Tabelle ergibt für $x \Rightarrow y$ immer 1. Somit ist die Behauptung gezeigt. \hfill $\Box$ \\
\subsubsection*{(b)}
Zeige: $\underbrace{a \equiv b}_u \Rightarrow \underbrace{a \AND c \equiv b \AND c}_v$ \\
\begin{tabular}{ccc|c|c|c|c|c}
a & b & c & u & $ a \AND c $ & $ b \AND c $ & v & $ u \Rightarrow v $ \\ \hline
0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
\end{tabular} \\ \\
Die Tabelle ergibt für $u \Rightarrow v$ immer 1. Somit ist die Behauptung gezeigt. \hfill $\Box$

\section*{Aufgabe 7}
$e_1 \OR ... \OR e_n = 1 \Leftrightarrow \exists i: e_i = 1$ \\
$\varphi((e_1 \OR ... \OR e_n)) = 1 \Leftrightarrow \exists i \in \{1,...,n\} $ sodass $\varphi(e_i) = 1$ \\ \\
Reduktion auf $n=2$ (o.B.d.A.): \\
$ \varphi((e_1 \OR e_2)) = 1 $ \\
$ \Leftrightarrow \varphi(e_1) \OR \varphi(e_2)=1 $ \\
$ \Leftrightarrow \varphi(e_1)=1 $ oder $ \varphi(e_2)=1 $ \hfill $\Box$

\section*{Aufgabe 8}
\begin{eqnarray*}
L(1) & = & 1 = 1 + (2^0-1) \cdot 5 \\
L(2) & = & 2 \cdot L(1)+4 = L(1) + 5 = 1+(2^1-1)\cdot 5 \\
L(3) & = & 2 \cdot L(2)+4 = L(2)+L(2)+4 \\
& = & 2 \cdot [L(1)+5]+4 \\
& = & 2 \cdot L(1) + 4 + 2 \cdot 5 \\
& \stackrel{L(2)}{=} & L(1)+5 + 2\cdot 5 \\
L(3) & = & L(1) + 3\cdot 5 = 1 + (2^2-1)\cdot 5
\end{eqnarray*}
Hieraus ergibt sich die Vermutung:
$$ L(n) = 1 + 5\cdot(2^{n-1}-1) \;\;\;\forall n \in \SetN_{\ge 1} $$
Beweis durch vollständige Induktion:
\begin{enumerate}
\item Induktionsanfang: $n=1$:
$$ L(1) = 1+5\cdot(2^0-1) = 1 \; \; \; \text{(ok)} $$

\item
\begin{enumerate}
\item Induktionsannahme: Für $n\in\SetN_{\ge 1}$ gelte: $L(n) = 1+ 5\cdot(2^{n-1}-1)$

\item Induktionsbehauptung: Dann gilt für $n+1 \in\SetN_{\ge 1}$: $L(n+1) = 1+5\cdot(2^n-1)$

\item Induktionsbegründung:
\begin{eqnarray*}
L(n+1) & = & 2 \cdot L(n) +4\\
& \stackrel{(2a)}{=} & 2\cdot [1+5\cdot(2^{n-1}-1)]+4 \\
& = & 2+ 10 \cdot(2^{n-1}-1)+4 \\
& = & 10 \cdot 2^{n-1} -4 \\
& = & 5 \cdot 2 \cdot 2^{n-1} -4 \\
& = & 5 \cdot 2^n -4 \\
& = & 1 + 5\cdot 2^n -5 \\
& = & 1 + 5 \cdot(2^n-1)
\end{eqnarray*}
\hfill $\Box$
\end{enumerate}

\section*{Aufgabe 9}
Nach Satz 1'b aus der Vorlesung:
\begin{eqnarray*}
e = 0 & \Leftrightarrow & \exists a \not\in T(f):c(a)=0 \\
& \Leftrightarrow & \exists a \not\in T(f):x=a \\
& \Leftrightarrow & \exists a \not\in T(f):X=a \Leftrightarrow X \ge T(f) \Leftrightarrow f(x) = 0
\end{eqnarray*}
$\varphi$ löst $e=0 \Leftrightarrow \varphi$ löst $f(x)=0 \; \; \; \forall \varphi$ \\
$ \varphi(e)=0 \Leftrightarrow \varphi(f(x)) = 0$ \\
$ e \equiv f(x) $ \hfill $\Box$


\end{enumerate}

\end{document}