\documentclass{uebungsblatt}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Diskrete Strukturen}
\blatt{6}
\gruppe{11}

\begin{document}

\aufgabe

\teilaufgabe

$ x \equiv n^2, y \equiv$ gerade natürliche Zahlen
\begin{flalign*}
1 & \rightarrow 2 \\
4 & \rightarrow 4 \\
9 & \rightarrow 6 \\
16 & \rightarrow 8 \\
25 & \rightarrow 10 \\
36 & \rightarrow 12 \\
49 & \rightarrow 14 \\
\end{flalign*}

Abbildung von $x$ nach $y$: $y = 2 \sqrt{x}$, Abbildung von $y$ nach $x$: $x = (\frac{y}{2})^2$.

\teilaufgabe

Gesucht ist eine injektive Abbildung von $V = \{ a + b \sqrt{2} | a, b \in \Q
\} $ in $\N$. Da $a, b \in \Q$ können sie als $a = \frac{c}{d} c \in \Z, d \in
\N$ und $b = \frac{e}{f} e \in \Z, f \in \N$ dargestellt werden. Wichtig ist,
dass maximal vereinfachte Brüche verwendet werden. $a = 0$ wird durch
$\frac{c}{d} = \frac{2}{2} $ dargestellt, $b = 0$ analog dazu durch
$\frac{e}{f} = \frac{3}{3}$. Nun müssen alle Zahlen auf $\N$ abgebildet werden,
also werden positive Zahlen auf ihr doppeltes Abgebildet und negative Zahlen
auf das doppelte ihres Betrages, so dass eine Bijektion von $\Z \rightarrow \N$
aufgestellt wird.  Dadurch sind $c, d, e, f \in \N$. Man kann nun die auf
4-Tupel erweiterte Cantorsche Paarungsfunktion $\pi^4$ verwenden um dem Tupel
von natürlichen Zahlen bijektiv eine eine Zahl $\in \N$ zuzuordnen. Damit kann nun jeder Kombination von $a$ und $b$ eine Zahl aus $\N$ zugeordnet werden (bijektiv), woraus dann auch folgt dass es injektiv ist.

Es gilt $|V| = |\Q|$ da im obrigen bewiesen wurde, dass $|V| = |\N|$ (bijektive
Zuordnung also gleich mächtig). Durch eine weitere Cantorsche Diagonalisierung
kann man ebenso zeigen, dass $|\Q| = |\N|$ und somit gilt transitiv auch, dass
$|V| = |\N|$.

\aufgabe

\teilaufgabe

\begin{flalign*}
  \overline{F \vdash true} & &\\
  \overline{F \vdash F} & & \text{Annahmeregel}\\
  \overline{\vdash F \Rightarrow F} & & \text{Implikationseinführung}
\end{flalign*}

Ja, es ist gezeigt dass $F \Rightarrow F$ eine Tautologie ist, weil $ \vdash F
\Rightarrow F$ eine Tautologie ist.

\teilaufgabe
Es gelten $ F \vdash \neg(\neg F) $ sowie $ \neg(\neg F) \vdash F $, das 
bedeutet dass $ F \Leftrightarrow \neg(\neg F) $ und 
$ \neg(\neg F) \Leftrightarrow F $ gelten, man also $F$ durch $\neg(\neg F)$
ersetzen kann und umgekehrt. Da $ F \equiv F $ gilt und die Inferenzen besagen,
dass man ersetzen kann, muss also auch $ F \equiv \neg(\neg F) $ gelten.

\aufgabe

\teilaufgabe

$A_1 \vdash F_1 $ ergäbe sich im ersten Schritt der Herleitung. Wenn $F_1 \in
A_1$, dann gilt die Annahmeregel, welches eine Basisregel ist.

\teilaufgabe

Ja, das gilt für alle Herleitungen, da es keine Inferenzregel gibt, die aus
der Annahmenmenge Annahmen entfernt, somit ist $A_n$ für alle $i$ in $A_i$
enthalten.

\aufgabe

$ F = \exists x \forall y \exists z (\neg (z = x) \wedge \neg (z = y) \wedge P(a, y, z)) $

\teilaufgabe

Die Formel besitzt drei verschiedene Gültigkeitsbereiche, dies kann man am
einfachsten zeigen indem man die Funktion in Teile zerlegt:

$ F \equiv F_0 \equiv \exists x F_1 $

$ F_1 \equiv \forall y F_2 $

$ F_2 \equiv \exists z F_3 $

$ F_3 \equiv (\neg (z = x) \wedge \neg (z = y) \wedge P(a, y, z)) $

Somit ist $x$ überall in $F_1$ gültig, $y$ ist in $F_2$ gültig und $z$ in
$F_3$. Keine dr Variablen wird überdeckt, somit gelten die Variablen ab ihrer
Quatifizierung bis zum Ende der Formel.

\teilaufgabe

$ S = (U, I) $

$ U_S = \{0, 1, 2\} $

$ I(a) = 1 $

$ I(P) = \{(1, 0, 1), (1, 1, 2), (1, 2, 0) \} $

\end{document}