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

\begin{document}

\aufgabe

\begin{flalign*}
| 10 \sqrt{n_0} | & \leq c \cdot n_0 & \text{Angabe}\\
10 \sqrt{n_0} & \leq c \cdot n_0 & n_n \in \N\\
\frac{10 \sqrt{n_0}}{n_0} & \leq c & \\
10 \frac{\sqrt{n_0}}{n_0} & \leq c & \\
10 n_0^{-\frac{1}{2}} & \leq c & \\
n_0^{-\frac{1}{2}} & \leq \frac{c}{10} & \\
\frac{1}{\sqrt{n_0}} & \leq \frac{c}{10} & \\
1 & \leq \sqrt{n_0} \cdot \frac{c}{10} & \\
\frac{10}{c} & \leq \sqrt{n_0} & \\
\frac{100}{c^2} & \leq n_0 & \\
n_0 & \geq \frac{100}{c^2} & c \in \R > 0\\
\end{flalign*}

Somit is $n_0$ gleich $\frac{100}{c^2}$. Man kann nun $n = n_0$
in die Formeln einsetzen:

\begin{flalign*}
\left|10 \sqrt{\frac{100}{c^2}}\right| & \leq c \cdot \frac{100}{c^2} & n = n_0 \\
10 \sqrt{\frac{100}{c^2}} & \leq c \cdot \frac{100}{c^2} & \\
10 \cdot \frac{10}{c} & \leq \frac{100 \cdot c}{c^2} & \\
\frac{100}{c} & \leq \frac{100}{c} & \\
\end{flalign*}

Somit gilt diese Aussage für den kleinsten Wert von $n$, $n_0$. Zu prüfen ist
noch, ob es auch für größere Werte gilt, etwa $n = \frac{100}{c^2} + 1$:

\begin{flalign*}
\left| 10 \sqrt{\frac{100}{c^2} + 1} \right| & \leq c \cdot \left( \frac{100}{c^2} + 1 \right) & \\
100 \cdot \left( \frac{100}{c^2} + 1 \right) & \leq \left( \frac{100}{c} + c \right)^2 & \\
\frac{100^2}{c^2} + 100 & \leq \frac{100^2}{c^2} + \frac{200 \cdot c}{c} + c^2 & \\
100 & \leq 200 + c^2 & \\
-100 & \leq c^2 & \\
\end{flalign*}

Das Ergebnis gilt immer, da $c > 0$ in der Angabe vorrausgesetzt wird.

\aufgabe

\teilaufgabe

\begin{flalign*}
\neg \forall c, c \in \R, c > 0: \exists n_0, n_n \in \N: \forall n, n \in \N, n \geq n_0: & |f(n)| \leq c \cdot g(n) & \\
\exists c, c \in \R, c > 0: \neg \exists n_0, n_n \in \N: \forall n, n \in \N, n \geq n_0: & |f(n)| \leq c \cdot g(n) & \\
\exists c, c \in \R, c > 0: \forall n_0, n_n \in \N: \neg \forall n, n \in \N, n \geq n_0: & |f(n)| \leq c \cdot g(n) & \\
\exists c, c \in \R, c > 0: \forall n_0, n_n \in \N: \exists n, n \in \N, n \geq n_0: & \neg (|f(n)| \leq c \cdot g(n)) & \\
\exists c, c \in \R, c > 0: \forall n_0, n_n \in \N: \exists n, n \in \N, n \geq n_0: & |f(n)| > c \cdot g(n) & & \equiv ** \\
\end{flalign*}

\teilaufgabe 

\begin{flalign*}
\left| 2n_0^2 \right| & > c \cdot n_0^2 & \\
2n_0^2 & > c \cdot n_0^2 & n_0 \in \N, n_0 > 0\\
2 & > c & \text{Teilen durch } n_0^2 \\
c & < 2 & \\
\end{flalign*}

Das heißt, dass die Aussage ** für alle $c$ gilt die größer als 0 sind
(siehe Annahme in der Formel) und kleiner als 2 sind, unabhängig von der
konkreten Wahl von $n$.

\aufgabe

\teilaufgabe

$ S = \{U, I\} $

$ U = \R $

$ I(\lhd) = \{(x, y) | x < y \} $

$ z = \frac{x + y}{2} $

\teilaufgabe

Relation $<$ über $\N$ ist nicht dicht, da für $x = 1, y = 2$ kein $z$ in der
Relation $<$ existiert, so dass die Formel erfüllt wäre.

\aufgabe

% prooftree is awesome, LaTeX supports everything
\begin{prooftree}
\[
  \justifies
  \[
    \mathcal{A} \vdash \forall x P(x) \Rightarrow Q(x)
    \justifies
    \mathcal{A} \vdash P(a) \Rightarrow Q(a)
  \]
\]
\[
  \justifies
  \[
     \mathcal{A} \vdash \forall x P(x)
     \justifies
     \mathcal{A} \vdash P(a)
  \]
\]
\justifies
\[
  \mathcal{A} \vdash Q(a)
  \justifies
  \mathcal{A} \vdash \forall x Q(x)
\]
\end{prooftree}

\end{document}