\defineUnit{mengen}{%
\begin{frame}
    \frametitle{Mengen}
    \setbeamercovered{dynamic}

    \begin{definition}[Menge]
        Eine \structure{Menge} ist eine \alert{ungeordnete} Sammlung \alert{unterscheidbarer} Objekte.\\
        Mit \structure{Mengenklammern} werden Objekte zusammengefasst.
        \[ A \defeq \left\{ a, b, \ldots, z \right\} \]
        Man nennt $a$ ein \structure{Element} von $A$, es gilt $a \in A$.
    \end{definition}

    \begin{itemize}
        \item Reihenfolge ist \alert{egal}
        \item Elemente kommen \alert{nicht} mehrfach vor
    \end{itemize}

    \vfill

    \begin{example}[]
        \begin{itemize}
            \item $\left\{ a, b, c, a, c \right\} = \left\{ a, b, c \right\} = \left\{ c, a, b \right\}$
            \item $\N \defeq \left\{ 1, 2, 3, \ldots \right\}$
            \item $\emptyset \defeq \left\{  \right\}$
        \end{itemize}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Schreibweisen}
    \setbeamercovered{dynamic}

    \begin{definition}[Extensionale Schreibweise]
        Die \structure{extensionale Schreibweise} einer Menge zählt ihre Elemente auf.
        \[ M \defeq \left\{ x_1, x_2, x_3, \ldots \right\} \]
    \end{definition}
    \vfill
    \begin{example}[]
        \begin{itemize}
            \item $A \defeq \left\{ 2, 4, 6, \ldots \right\}$
            \item $B \defeq \left\{ 1, 2, 3, 4 \right\}$ = [4]
            \item $C \defeq \left\{ 2, 3, 5, 7, 11, \ldots \right\}$
            \item $D \defeq \left\{ \alpha, a, \smiley, 8, \left\{ 1, 2 \right\}, \N \right\}$
        \end{itemize}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Schreibweisen}
    \setbeamercovered{dynamic}

    \begin{definition}[Intensionale Schreibweise]
        Die \structure{intensionale Schreibweise} beschreibt eine Menge durch charakteristische Eigenschaften.
        \[ M \defeq \left\{ x \in \Omega \mid P(x) \right\} \]
        $M$ enthält alle Elemente im \structure{Universum} $\Omega$ mit der Eigenschaft $P$.
    \end{definition}
    \vfill
    \begin{example}[]
        \begin{itemize}
            \item $A \defeq \left\{ 2, 4, 6, \ldots \right\} = \left\{ x \in \N \mid x\ \text{gerade} \right\} = \left\{ 2x : x \in \N \right\}$
            \item $B \defeq \left\{ 1, 2, 3, 4 \right\} = \left\{ x \in \N \mid x \leq 4 \right\}$
            \item $C \defeq \left\{ 2, 3, 5, 7, 11, \ldots \right\} = \left\{ x \in \N \mid x\ \text{prim} \right\}$
        \end{itemize}
    \end{example}
\end{frame}
}

\defineUnit{mengenoperationen}{%
\begin{frame}
    \frametitle{Mengenoperationen}
    \setbeamercovered{dynamic}

    \begin{block}{Bezeichnungen}
        \begin{itemize}
            \item Objekte in Mengen
                \begin{description}[\qquad\qquad]
                    \item[$a \in A$] $a$ ist Element von $A$
                    \item[$b \not\in A$] $b$ ist kein Element von $A$
                    \item[$\abs{A}$] Anzahl der Elemente in $A$, Kardinalität
                \end{description}
            \item Relationen zwischen Mengen
                \begin{description}[\qquad\qquad]
                    \item[$B \subseteq A$] $B$ ist Teilmenge von $A$, \quad $x \in B \Rightarrow x \in A$
                    \item[$B \subset A$] $B$ ist echte Teilmenge von $A$
                    \item[$B = A$] $B \subseteq A$ und $A \subseteq B$
                \end{description}
        \end{itemize}
    \end{block}

    \begin{example}[]
        \begin{itemize}
            \item $1 \in \left\{ 1, 2, 3, 4 \right\}$, aber $9 \not\in \left\{ 1, 2, 3, 4 \right\}$
            \item $\left\{ 1, 2 \right\} \subseteq \left\{ 1, 2, 3, 4 \right\}$, aber $\left\{ 1, 5 \right\} \not\subseteq \left\{ 1, 2 \right\}$
            \item $\emptyset \subseteq [5] \subseteq \N \subseteq \N_0 \subseteq \Z \subseteq \Q \subseteq \R \subseteq \C$
        \end{itemize}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Mengenoperationen}
    \setbeamercovered{dynamic}

    \begin{block}{Operationen}
        \begin{description}[\qquad\qquad]
            \item[$\setnot{A}$] $\defeq \left\{ x \mid x \not\in A \right\}$\hfill\alert{Komplement}
            \item[$A \cup B$] $\defeq \left\{ x \mid x \in A\ \text{oder}\ x \in B \right\}$\hfill\alert{Vereinigung}
            \item[$A \cap B$] $\defeq \left\{ x \mid x \in A\ \text{und}\ x \in B \right\}$\hfill\alert{Schnitt}
            \item[$A \setminus B$] $\defeq A \cap \setnot{B}$\hfill\alert{Differenz}
            \item[$A \setsymdiff B$] $\defeq \left( A \setminus B \right) \cup \left( B \setminus A \right)$\hfill\alert{Symmetrische Differenz}
        \end{description}
    \end{block}
    \vill
    Für mehrere Mengen schreibt man
    \begin{align}
        \bigcap_{i=1}^n A_i &\defeq A_1 \cap A_2 \cap \ldots \cap A_n\\
        \bigcup_{i=1}^n A_i &\defeq A_1 \cup A_2 \cup \ldots \cup A_n
    \end{align}
\end{frame}
}

\defineUnit{venn}{%
\begin{frame}
    \frametitle{Venn-Diagramme}
    \setbeamercovered{dynamic}

    \structure{Venn-Diagramme} visualisieren Mengen $A, B, \ldots$ im Universum $\Omega$.

    {
        \def\universe{(-1.5, -1.25) rectangle (2.5, 1.25) node[anchor=north east, black] {$\Omega$}}
        \def\first{(0, 0) circle (1)}
        \def\second{(1, 0) circle (1)}
        \tikzstyle{universe} = [draw, thick, tumblue, fill=tumlightblue!15]
        \tikzstyle{inset} = [fill=tumred!35]
        \tikzstyle{outline} = [draw, thick, black]
        \begin{columns}
            \begin{column}{.5\textwidth}
                \begin{itemize}
                    \item $A \cup B$
                        \begin{figure}
                            \begin{tikzpicture}
                                \draw[universe] \universe;
                                \fill[inset] \first;
                                \fill[inset] \second;
                                \draw[outline] \first node[left=1em] {$A$};
                                \draw[outline] \second node[right=1em] {$B$};
                            \end{tikzpicture}
                        \end{figure}
                    \item $A \setminus B$
                        \begin{figure}
                            \begin{tikzpicture}
                                \draw[universe] \universe;
                                \begin{scope}
                                    \clip \first;
                                    \fill[inset, even odd rule] \first \second;
                                \end{scope}
                                \draw[outline] \first node[left=1em] {$A$};
                                \draw[outline] \second node[right=1em] {$B$};
                            \end{tikzpicture}
                        \end{figure}
                \end{itemize}
            \end{column}
            \begin{column}{.5\textwidth}
                \begin{itemize}
                    \item $A \cap B$
                        \begin{figure}
                            \begin{tikzpicture}
                                \draw[universe] \universe;
                                \begin{scope}
                                    \clip \first;
                                    \fill[inset] \second;
                                \end{scope}
                                \draw[outline] \first node[left=1em] {$A$};
                                \draw[outline] \second node[right=1em] {$B$};
                            \end{tikzpicture}
                        \end{figure}
                    \item $A \setsymdiff B = (A \setminus B) \cup (B \setminus A)$
                        \begin{figure}
                            \begin{tikzpicture}
                                \draw[universe] \universe;
                                \fill[inset, even odd rule] \first \second;
                                \draw[outline] \first node[left=1em] {$A$};
                                \draw[outline] \second node[right=1em] {$B$};
                            \end{tikzpicture}
                        \end{figure}
                \end{itemize}
            \end{column}
        \end{columns}
    }
\end{frame}
}

\defineUnit{mengenrechenregeln}{%
\begin{frame}
    \frametitle{Rechnen mit Mengen}
    \setbeamercovered{dynamic}

    \begin{theorem}[De Morgansche Gesetze]
        Sind $A, B$ Mengen, dann gilt
        \begin{alignat}{2}
            \setnot{A \cup B} &= \setnot{A} \cap \setnot{B} \qquad\qquad& \setnot{A \cap B} &= \setnot{A} \cup \setnot{B}\\
            \intertext{Für Mengen $A_i$ gilt}
            \setnot{\bigcup_{i=1}^nA_i} &= \bigcap_{i=1}^n\setnot{A_i} & \setnot{\bigcap_{i=1}^nA_i} &= \bigcup_{i=1}^n\setnot{A_i} &
        \end{alignat}
    \end{theorem}

    \vfill

    \begin{itemize}
        \item Zusammen mit $\setnot{\setnot{A}} = A$ wichtigste Regel
        \item Gilt auch in der Aussagenlogik
    \end{itemize}
\end{frame}
}

\defineUnit{potenzmenge}{%
\begin{frame}
    \frametitle{Potenzmenge}
    \setbeamercovered{dynamic}

    \begin{definition}[Potenzmenge]
        Die \structure{Potenzmenge} $\powerset{M}$ zu einer Menge $M$ ist die Menge all ihrer Teilmengen.
        \[ \powerset{M} \defeq \left\{ X \mid X \subseteq M \right\} \]
    \end{definition}

    \begin{itemize}
        \item $\powerset{M}$ enthält für endliche Mengen genau $2^{\abs{M}}$ Elemente
        \item Man schreibt deshalb auch $2^M$
        \item Es ist $M \in \powerset{M}$ und $\emptyset \in \powerset{M}$
    \end{itemize}

    \vfill

    \begin{example}[]
        Für $M = \left\{ a, b, c \right\}$ ist
        \[ \powerset{M} = \left\{
            \emptyset,
            \left\{ a \right\},
            \left\{ b \right\},
            \left\{ c \right\},
            \left\{ a, b \right\},
            \left\{ a, c \right\},
            \left\{ b, c \right\},
            \left\{ a, b, c \right\}
        \right\} \]
        mit $\abs{\powerset{M}} = 2^3 = 8$
    \end{example}
\end{frame}
}

\defineUnit{tupel}{%
\begin{frame}
    \frametitle{Tupel}
    \setbeamercovered{dynamic}

    \begin{definition}[Tupel]
        Ein \structure{$n$-Tupel} ist eine \alert{geordnete} Sammlung $n$ \alert{beliebiger} Objekte.\\
        Mit \structure{Tupelklammern} werden Objekte zusammengefasst.
        \[ T \defeq \left( t_1, t_2, \ldots, t_n \right)\]
    \end{definition}

    \begin{itemize}
        \item Reihenfolge \alert{nicht} egal
        \item Elemente \alert{dürfen} mehrmals vorkommen
    \end{itemize}

    \vfill

    \begin{example}[]
        \begin{itemize}
            \item $\left( a, b, c \right) \neq \left( c, a, b \right) \neq \left( a, b, c, a, c \right)$
            \item $\left( 1, 2, 3 \right) \neq \left\{ 3, 2, 1 \right\} = \left\{ 1, 2, 3 \right\}$
            \item $\left( \left\{ \alpha, \beta \right\}, \emptyset, \N \right)$
        \end{itemize}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Kreuzprodukt}
    \setbeamercovered{dynamic}

    \begin{definition}[Kreuzprodukt]
        Sind $A, B$ Mengen, dann ist ihr \structure{kartesisches Produkt} (Kreuzprodukt)
        \begin{align}
            A \times B &\defeq \left\{ \left( a, b \right) \mid a \in A, b \in B \right\}\\
            \intertext{Für Mengen $A_i$ ist}
            A_1 \times \ldots \times A_n &\defeq \left\{ \left(a_1, \ldots, a_n\right) \mid a_1 \in A_1, \ldots, a_n \in A_n \right\}
        \end{align}
    \end{definition}

    \begin{itemize}
        \item Für endliche $A_i$ ist $\abs{A_1 \times \ldots \times A_n} = \abs{A_1} \cdot \ldots \cdot \abs{A_n}$
        \item Man schreibt \structure{$A^n \defeq \underbracket[0.5pt]{A \times \ldots \times A}_{\text{n mal}}$} mit $A^0 = \left\{ \emptyset \right\}$
    \end{itemize}

    \vfill

    \begin{example}[]
        \begin{itemize}
            \item $\left\{ 1, 2 \right\} \times \left\{ a, b \right\} = \left\{ (1, a), (2, a), (1, b), (2, b) \right\}$
            \item $\left\{ \alpha, \beta \right\}^2 = \left\{ (\alpha, \alpha), (\alpha, \beta), (\beta, \alpha), (\beta, \beta) \right\}$
        \end{itemize}
    \end{example}
\end{frame}
}

\defineUnit{relationen}{%
\begin{frame}
    \frametitle{Relation}
    \setbeamercovered{dynamic}

    \begin{definition}[Relation]
        Eine binäre \structure{Relation} $R$ verbindet Elemente zweier Mengen $A$ und $B$.
        \[ R \subseteq A \times B\]
        Ist $(a, b) \in R$, so schreibt man auch \structure{$a\rel{R}b$}.
    \end{definition}

    \begin{itemize}
        \item Eine Relation über $M \times M$ nennt man homogen
        \item Es gibt $\abs{\powerset{A \times B}}$ Relationen über $A, B$
    \end{itemize}

    \begin{example}[]
        \begin{itemize}
            \item Die \alert{Gleichheitsrelation} über $\N \times \N$ \\
               $\left\{ (1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7) \ldots \right\}$
               \medskip
            \item Die \alert{Teilbarkeitsrelation} über $\N$ \\
               $\left\{ (1,1), (1,2), (1,3), \ldots, (2,2), (2,4), \ldots, (3,3), (3,6), \ldots \right\}$
        \end{itemize}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Grafische Darstellung}
    \setbeamercovered{dynamic}

    \begin{block}{Grafische Darstellung von Relationen}
        Jede Relation $R \subseteq M \times M$ kann als \structure{Graph} dargestellt werden. Die Elemente aus M werden zu \structure{Knoten} und für jedes Tupel $(a, b) \in R$ wird ein \structure{Pfeil} von $a$ nach $b$ eingefügt.
    \end{block}

    \begin{example}[]
        Sei $R \subseteq [4] \times [4]$ eine Relation über den natürlichen Zahlen.
        \[ R \defeq \left\{ (1, 1), (1, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 3) \right\}\]

        \centering
        \begin{tikzpicture}[x=5em, y=2.5em]
            \path   (0, 0) node[pretty] (1) {$1$}
            +(1, 0) node[pretty] (2) {$2$}
            +(2, 1) node[pretty] (3) {$3$}
            +(2, -1) node[pretty] (4) {$4$};

            \path[edge]
            (1) edge[loop left] (1)
            (1) edge (2)
            (2) edge (3)
            (2) edge (4)
            (3) edge[loop above] (3)
            (3) edge[bend left] (4)
            (4) edge[bend left] (3);
        \end{tikzpicture}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Eigenschaften von Relationen}
    \setbeamercovered{dynamic}


    \begin{block}{Eigenschaften homogener Relationen}
        Sei $R \in M \times M$ eine homogene Relation. Man nennt $R$
        \begin{description}[antisymmetrisch]
            \item[reflexiv] $ \forall a\hphantom{, b, c} \in M.\ (a, a) \in R$
            \item[total] $ \forall a, b\hphantom{, c} \in M.\  (a, b) \in R \vee (b, a) \in R$
                \medskip
            \item[symmetrisch] $ \forall a, b\hphantom{, c} \in M.\  (a, b) \in R \hphantom{{}\wedge (b, a) \in R}\Rightarrow (b,a ) \in R$
            \item[asymmetrisch] $ \forall a, b\hphantom{, c} \in M.\  (a, b) \in R \hphantom{{}\wedge (b, a) \in R}\Rightarrow (b,a ) \not\in R$
            \item[antisymmetrisch] $ \forall a, b\hphantom{, c} \in M.\  (a, b) \in R \wedge (b, a) \in R \Rightarrow a \equiv b$
                \medskip
            \item[transitiv] $ \forall a, b, c \in M.\  (a, b) \in R \wedge (b, c) \in R \Rightarrow (a, c) \in R$
        \end{description}
    \end{block}

    \vfill

    \begin{itemize}
        \item Jede totale Relation ist reflexiv
        \item Jede asymmetrische Relation ist antisymmetrisch
        \item \structure{Äquivalenzrelationen} sind reflexiv, symmetrisch und transitiv
        \item $R^+$ ist die \structure{transitive Hülle}, $R^*$ die \structure{reflexive transitive Hülle}
    \end{itemize}
\end{frame}
}

\defineUnit{funktionen}{%
\begin{frame}
    \frametitle{Funktion}
    \setbeamercovered{dynamic}

    \begin{definition}[Funktion]
        Eine Relation $f \subseteq A \times B$ ist eine \structure{Funktion von A nach B} wenn es für alle $a \in A$ genau ein Element $b \in B$ mit $a \rel{f} b$ gibt.
        \[ \forall a \in A. \abs{\left\{ (a, b) \mid b \in B \right\}} \alert{=} 1 \]
        Man schreibt
        \begin{align}
            f : A &\to B \\
            a &\mapsto f(a) = b
        \end{align}
        \structure{$A \to B$} bezeichnet die Menge aller Funktionen von $A$ nach $B$.
    \end{definition}

    \vfill
    \centering
    {
        \tikzstyle{set} = [draw, thick, tumgreen, fill=tumgreen!15]
        \tikzstyle{element} = [thick]
        \tikzstyle{arrow} = [thick, tumblue, shorten >=-.4em, shorten <=-.4em]
        \begin{tikzpicture}[x=1.5em, y=1.5em]
            \draw[set] (0, 0) ellipse (1 and 2);
            \draw[set] (5, 0) ellipse (1 and 2);

            \path[element]
                (0,0)
                +(0, 1.5) node (a1) {$\times$}
                +(0.2, 0.85) node (a2) {$\times$}
                +(0.1, -0.6) node (a4) {$\times$}
                +(-0.1, -1.5) node (a5) {$\times$};

            \path[element]
                (5,0)
                +(0, 1.5) node (b1) {$\times$}
                +(0.2, 0.85) node (b2) {$\times$}
                +(-0.3, 0.0) node (b3) {$\times$}
                +(0.1, -0.6) node (b4) {$\times$}
                +(-0.1, -1.5) node (b5) {$\times$};

            \path[arrow]
                (a1) edge (b1)
                (a2) edge (b5)
                (a4) edge (b2)
                (a5) edge (b5);

            \path
                (0, -2.5) node {$A$}
                (5, -2.5) node {$B$}
                (2.5, -2.5) node {$f$};
        \end{tikzpicture}
    }
\end{frame}

\begin{frame}
    \frametitle{Bild und Urbild}
    \setbeamercovered{dynamic}

    \begin{definition}[Bild]
        Sei $f : A \to B$ eine Funktion, $X \subseteq A$, $Y \subseteq B$, $b \in B$. Dann ist
        \begin{align}
        f(X) &\defeq \left\{ f(x) \mid x \in X \right\} \\
        \intertext{das \structure{Bild} der Menge $X$ unter $f$. Außerdem ist}
        f^{-1}(b) &\defeq \left\{ a \mid a \in A, f(a) = b \right\} \\
        f^{-1}(Y) &\defeq \bigcup_{y \in Y} \left\{ f^{-1}(y) \right\}
        \end{align}
        das \structure{Urbild} des Elements $b$ und der Menge $Y$ unter $f$.
    \end{definition}

    \vfill

    \begin{itemize}
        \item Man nennt $A = f^{-1}(B)$ \structure{Urbild} oder \structure{Definitionsmenge} von $f$
        \item Man nennt $f(A) \subseteq B$ \structure{Bild} oder \structure{Wertemenge} von $f$
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Komposition}
    \setbeamercovered{dynamic}

    \begin{definition}[Funktionskomposition]
        Seien $f : B \to C$ und $g : A \to B$ Funktionen. Dann ist
        \begin{align}
            h : A &\to C \\
            a &\mapsto (f \circ g)(a) = f(g(a))
        \end{align}
        die \structure{Komposition} der Funktionen $f$ und $g$.\\
        Man ließt $f \circ g$ als \enquote{f \structure{nach} g}.
    \end{definition}

    \vfill

    Man definiert die Potenzierung von Funktionen ähnlich der Mengentheorie.
    \begin{align}
        f^0 &\defeq id\\
        f^n &\defeq \underbracket[0.5pt]{f \circ \ldots \circ f}_{\text{n mal}}
    \end{align}
    Dabei bezeichnet $id$ die \structure{Identität} mit $id(x) \defeq x$.
\end{frame}

\begin{frame}
    \frametitle{Eigenschaften von Funktionen}
    \setbeamercovered{dynamic}

    \begin{block}{Eigenschaften von Funktionen}
        Sei $f: A \to B$ eine Funktion. Man nennt $f$
        \begin{description}[surjektiv]
            \item[injektiv] $\forall b \in B. \abs{f^{-1}(b)} \leq 1$ \hfill(Kein $b$ wird doppelt getroffen)
            \item[surjektiv] $\forall b \in B. \abs{f^{-1}(b)} \geq 1$\hfill(Jedes $b$ wird getroffen)
            \item[bijektiv] $\forall b \in B. \abs{f^{-1}(b)} = 1$\hfill(Jedes $b$ wird genau einmal getroffen)
        \end{description}
    \end{block}

    \vfill
    \centering
    {
        \tikzstyle{set} = [draw, thick, tumgreen, fill=tumgreen!15]
        \tikzstyle{element} = [thick]
        \tikzstyle{head} = [draw, fill=tumblue!15, thick]
        \tikzstyle{arrow} = [thick, tumblue, shorten >=-.4em, shorten <=-.4em]
        \newcommand{\function}[3]{%
            \draw[set] (0, 0) ellipse (1 and 2);
            \draw[set] (4, 0) ellipse (1 and 2);

            \path[element]
                (0,0)
                +(0, 1.5) node (a1) {$\times$}
                +(0.2, 0.85) node (a2) {$\times$}
                +(0.1, 0.3) node (a3) {$\times$}
                +(-0.1, -0.1) node (a4) {$\times$}
                +(-0.2, -0.7) node (a5) {#2}
                +(-0.1, -1.5) node (a6) {#3};

            \path[element]
                (4,0)
                +(0, 1.5) node (b1) {$\times$}
                +(0.2, 0.85) node (b2) {$\times$}
                +(-0.3, 0.0) node (b3) {$\times$}
                +(0.1, -0.6) node (b4) {$\times$}
                +(-0.1, -1.5) node (b5) {$\times$};

            \path
                (0, -2.5) node {$A$}
                (4, -2.5) node {$B$}
                (2, -2.5) node {$f$}
                (2, 3) node[head] {#1};

        }
        \begin{tikzpicture}[x=1.5em, y=1.5em]
            \function{Injektiv}{}{}

            \path[arrow]
                (a1) edge (b1)
                (a2) edge (b3)
                (a3) edge (b2)
                (a4) edge (b4);
        \end{tikzpicture}
        \hfill
        \begin{tikzpicture}[x=1.5em, y=1.5em]
            \function{Surjektiv}{$\times$}{$\times$}

            \path[arrow]
                (a1) edge (b1)
                (a2) edge (b3)
                (a3) edge (b2)
                (a4) edge (b4)
                (a5) edge (b5)
                (a6) edge (b5);
        \end{tikzpicture}
        \hfill
        \begin{tikzpicture}[x=1.5em, y=1.5em]
            \function{Bijektiv}{}{$\times$}

            \path[arrow]
                (a1) edge (b1)
                (a2) edge (b3)
                (a3) edge (b2)
                (a4) edge (b4)
                (a6) edge (b5);
        \end{tikzpicture}
    }
\end{frame}
}

\defineUnit{aussagenlogiksyntax}{%
\begin{frame}[c]
    \frametitle{Syntax der Aussagenlogik}
    \setbeamercovered{dynamic}

    \begin{definition}[Syntax der Aussagenlogik]
        Aussagenlogische \structure{Formeln} bestehen aus Konstanten, Variablen und Operatoren. Die Menge \structure{$\mathcal{F}$} aller Formeln ist induktiv definiert.
        \begin{itemize}
            \item $\mathrm{false} = 0 \in \mathcal{F},\quad \mathrm{true} = 1 \in \mathcal{F}$\hfill(\alert{Konstanten})
            \item $V = \left\{ a, b, c,\ldots \right\} \subseteq \mathcal{F}$\hfill(\alert{Variablen})\\
            \medskip
            \item Ist $A \in \mathcal{F}$ eine aussagenlogische Formel, dann auch
                \begin{align}
                    \neg A &\in \mathcal{F}\tag{\alert{Negation}}\\
            \intertext{\item Sind $A, B \in \mathcal{F}$ aussagenlogische Formeln, dann auch}
                    (A \wedge B)&\in \mathcal{F}\tag{\alert{Konjunktion}}\\
                    (A \vee B)&\in \mathcal{F}\tag{\alert{Disjunktion}}\\
                    (A \Rightarrow B)&\in \mathcal{F}\tag{\alert{Implikation}}
                \end{align}
        \end{itemize}
        Alle Formeln lassen sich so konstruieren.
    \end{definition}
\end{frame}

\begin{frame}
    \frametitle{Operatorenbindung}
    \setbeamercovered{dynamic}

    \begin{definition}[Bindungsregeln]
        Die \structure{Bindungsstärke} der Operatoren in absteigender Reihenfolge ist
        \[ \neg \quad \wedge \quad \vee \quad \Rightarrow \quad \Leftrightarrow \]
        Die Implikation ist \structure{rechtsassoziativ}
        \[ a \Rightarrow b \Rightarrow c \Rightarrow d\text{\quad steht für\quad} \left( a \Rightarrow \left( b \Rightarrow \left( c \Rightarrow d \right) \right) \right) \]
    \end{definition}
    \begin{itemize}
        \item Üblicherweise klammert man $\wedge$ und $\vee$
            \[ (a \wedge b) \vee c \text{\quad statt\quad} a \wedge b \vee c \]
    \end{itemize}
    \begin{example}[]
        \begin{itemize}
            \item $\neg a \wedge b$\quad steht für \quad$ \left( \left( \neg a \right) \wedge b \right)$
            \item $a \wedge b \Rightarrow c \vee \neg d$\quad steht für \quad$((a \wedge b) \Rightarrow (c \vee \left( \neg d \right)))$
        \end{itemize}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Syntaxbaum}
    \setbeamercovered{dynamic}

    \begin{block}{Syntaxbaum}
        \structure{Syntaxbäume} visualisieren in welcher Reihenfolge die Regeln zur induktiven Definition angewandt werden müssen, um eine Formel zu erzeugen.
    \end{block}
    \begin{example}[]
        Sei $F \defeq a \wedge b \Rightarrow c \vee \neg d$ dann ist der dazu passende Syntaxbaum
        \centering
        \begin{tikzpicture}[grow=down, level distance = 33]
            \tikzstyle{every node} = []
            \tikzstyle{op} = [pretty]
            \tikzstyle{var} = [pretty, rectangle]
            \tikzstyle{edge from parent} = [edge]

            \tikzstyle{level 1} = [sibling distance = 80]
            \tikzstyle{level 2} = [sibling distance = 40]
            \node[op] {$\Rightarrow$}
                child {
                    node[op] {$\wedge$}
                    edge from parent
                    child {
                        node[var] {$a$}
                        edge from parent
                    }
                    child {
                        node[var] {$b$}
                        edge from parent
                    }
                }
                child {
                    node[op] {$\vee$}
                    edge from parent
                    child {
                        node[var] {$c$}
                        edge from parent
                    }
                    child {
                        node[op] {$\neg$}
                        edge from parent
                        child {
                            node[var] {$d$}
                            edge from parent
                        }
                    }
                };
        \end{tikzpicture}
    \end{example}
\end{frame}
}

\defineUnit{aussagenlogiksemantik}{%
\begin{frame}
    \frametitle{Belegung}
    \setbeamercovered{dynamic}

    \begin{definition}[Belegung]
        Eine passende \structure{Belegung} $\beta$ zu einer Formel $F$ ordnet jeder Variable in $V$ einen Wahrheitswert aus $\left\{ 0, 1 \right\}$ zu. Es ist
        \[ \beta : V \to \left\{ 0, 1 \right\} \]
    \end{definition}
    \begin{itemize}
        \item Belegungen formalisieren Einsetzen
        \item Für $n$ Variablen existieren $2^n$ Belegungen
    \end{itemize}
    \begin{example}[]
        Sei $F \defeq \neg \left( a \wedge b \right)$ mit $V = \left\{ a, b \right\}$ und
        \begin{align}
            \beta : \left\{ a, b \right\} &\to \left\{ 0, 1 \right\}\\
            a &\mapsto 1\\
            b &\mapsto 0
        \end{align}
        Dann ist $\beta$ eine zu $F$ passende \structure{Belegung}.
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Semantik der Aussagenlogik}
    \setbeamercovered{dynamic}

    \begin{definition}[Semantik einer Formel]
        Die \structure{Semantik} $[F]$ einer aussagenlogischen Formel $F$ ist eine Funktion, die jeder passenden Belegung $\beta$ einen Wahrheitswert zuordnet.\\
        Sei $\mathcal{B} = \left\{ \beta_0, \beta_1, \ldots \right\}$ die Menge aller Belegungen zu $F$. Dann ist
        \[[F] : \mathcal{B} \to \left\{ 0, 1 \right\}\]
    \end{definition}
    \begin{itemize}
        \item Die Semantik löst eingesetzte Formeln auf
        \item Wird anhand der induktiven Syntax definiert
        \item Es gibt \alert{syntaktisch verschiedene} Formeln gleicher \structure{Semantik}
    \end{itemize}
    \begin{example}[]
        Sei $F \defeq \left( G \Rightarrow H \right)$ mit $G, H$ Formeln. Dann ist
        \[ [F](\beta) = \begin{cases}
                0 & \text{falls } [G](\beta) = 1 \text{ und } [H](\beta) = 0 \\
                1 & \text{sonst}
                \end{cases}\]
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Wahrheitstabelle}
    \setbeamercovered{dynamic}

    \begin{block}{Wahrheitstabelle}
        Die Semantik einer Formel kann mit Hilfe einer \structure{Wahrheitstabelle} visualisiert werden. Die Tabelle gibt den Wahrheitswert der Formel für jede mögliche Belegung an.
    \end{block}
    \begin{example}[]
        Sei $F \defeq a \vee b \Rightarrow \neg c \wedge b$. Die zu $[F]$ gehörige Wahrheitstabelle ist
        \begin{center}
            \begin{tabu} to .5\textwidth {cccX|[1.2pt]Xccccc}
                a & b & c & & & $a \vee b$ & $\Rightarrow$ & $\neg c$ & $\wedge$ & $b$ \\ \tabucline[1.2pt]{-}
                0 & 0 & 0 & & & \onslide<2->{0} & \onslide<3->{\structure{1}} & \onslide<2->{1} & \onslide<2->{0} & \\
                0 & 0 & 1 & & & \onslide<2->{0} & \onslide<3->{\structure{1}} & \onslide<2->{0} & \onslide<2->{0} & \\
                0 & 1 & 0 & & & \onslide<2->{1} & \onslide<3->{\structure{1}} & \onslide<2->{1} & \onslide<2->{1} & \\
                0 & 1 & 1 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{0} & \onslide<2->{0} & \\
                1 & 0 & 0 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{1} & \onslide<2->{0} & \\
                1 & 0 & 1 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{0} & \onslide<2->{0} & \\
                1 & 1 & 0 & & & \onslide<2->{1} & \onslide<3->{\structure{1}} & \onslide<2->{1} & \onslide<2->{1} & \\
                1 & 1 & 1 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{0} & \onslide<2->{0} & \\
            \end{tabu}
        \end{center}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Äquivalente Formeln}
    \setbeamercovered{dynamic}

    \begin{definition}[Äquivalente Formeln]
        Man nennt zwei Formeln \structure{äquivalent}, wenn sie dieselbe Semantik besitzen.\\
        Seien $F, G$ Formeln mit Belegungen $\mathcal{B} = \mathcal{B}_F = \mathcal{B}_G$. $F$ und $G$ sind äquivalent wenn
        \[ \forall \beta \in \mathcal{B}. [F](\beta) = [G](\beta) \]
        Man schreibt \structure{$F \equiv G$} oder \structure{$F \Leftrightarrow G$}.
    \end{definition}

    \begin{example}[]
        Für $F \defeq a \Rightarrow b$ und $G \defeq \neg a \vee b$ gilt $F \equiv G$.
        \begin{center}
            \begin{tabu} to .4\textwidth {cc|[1.2pt]XcX||Xccc}
                a & b & & $a \Rightarrow b$ & & & $\neg a$ & $\vee$ & $b$ \\ \tabucline[1.2pt]{-}
                0 & 0 & & \structure{1} & & & 1 & \structure{1} \\
                0 & 1 & & \structure{1} & & & 1 & \structure{1} \\
                1 & 0 & & \structure{0} & & & 0 & \structure{0} \\
                1 & 1 & & \structure{1} & & & 0 & \structure{1} \\
            \end{tabu}
        \end{center}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Eigenschaften von Formeln}
    \setbeamercovered{dynamic}

    \begin{block}{Eigenschaften aussagenlogischer Formeln}
        Sei $F$ eine aussagenlogische Formel mit Variablen $V$ und der Menge der passenden Belegungen $\mathcal{B}$. Man nennt F
        \begin{description}[\quad unerfüllbar]
            \item[erfüllbar] $\exists \beta \in \mathcal{B}. [F](\beta) = 1$\hfill($F$ kann wahr sein)
            \item[unerfüllbar] $\forall \beta \in \mathcal{B}. [F](\beta) = 0$\hfill($F$ ist nie wahr)
            \item[gültig] $\forall \beta \in \mathcal{B}. [F](\beta) = 1$\hfill($F$ ist immer wahr)
        \end{description}
    \end{block}
    \begin{itemize}
        \item Eine unerfüllbare Formel nennt man \structure{Widerspruch}
        \item Eine gültige Formel nennt man \structure{Tautologie}
    \end{itemize}

\end{frame}
}
