Mercurial > 13ws.ds
view notes/tex/basics.tex @ 18:8408cf61d46b
fix error in equivalences
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Wed, 13 Nov 2013 14:33:22 +0100 |
parents | 099613ee2f37 |
children | 845ff8b2cbc6 |
line wrap: on
line source
\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} { \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{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 \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} } \defineUnit{aussagenlogikaequivalenzen}{% { \newcommand{\true}{1} \newcommand{\false}{0} \newcommand{\spc}{\hspace{3em}} \newcommand{\F}{F} \newcommand{\G}{G} \newcommand{\K}{H} \begin{frame} \frametitle{Äquivalenzregeln} \setbeamercovered{dynamic} \begin{description}[Triviale Kontradiktion\quad] \item[Identität] $\F \wedge \true \equiv \F \spc \F \vee \false \equiv \F$ \item[Dominanz] $\F \vee \true \equiv \true \spc \F \wedge \false \equiv \false$ \item[Idempotenz] $\F \vee \F \equiv \F \spc \F \wedge \F \equiv \F$ \item[Doppelte Negation] $\neg \neg \F \equiv \F$ \item[Triviale Tautologie] $\F \vee \neg \F \equiv \true$ \item[Triviale Kontradiktion] $\F \wedge \neg \F \equiv \false$ \bigskip \item[Kommutativität] $\F \vee \G \equiv \G \vee \F$\\ $\F \wedge \G \equiv \G \wedge \F$ \item[Assoziativität] $(\F \vee \G) \vee \K \equiv \F \vee (\G \vee \K)$\\ $(\F \wedge \G) \wedge \K \equiv \F \wedge (\G \wedge \K)$ \item[Distributivität] $\F \vee (\G \wedge \K) \equiv (\F \vee \G) \wedge (\F \vee \K)$\\ $\F \wedge (\G \vee \K) \equiv (\F \wedge \G) \vee (\F \wedge \K)$ \item[De Morgan] $\neg(\F \wedge \G) \equiv \neg \F \vee \neg \G$\\ $\neg(\F \vee \G) \equiv \neg\F \wedge \neg\G$ \bigskip \item[Implikation] $\F \rightarrow \G \equiv \neg \F \vee \G$ \item[Bikonditional] $\F \leftrightarrow \G \equiv (\F \rightarrow \G) \wedge (\G \rightarrow \F)$ \end{description} \end{frame} %\begin{frame} %\frametitle{Äquivalenzregeln} %\setbeamercovered{dynamic} %\vspace{-2em} %\begin{align} %\F \wedge \true &\equiv \F \spc \F \vee \false \equiv \F \tag{\structure{Identität}}\\ %\F \vee \true &\equiv \true \spc \F \wedge \false \equiv \false \tag{\structure{Dominanz}}\\ %\F \vee \F &\equiv \F \spc \F \wedge \F \equiv \F \tag{\structure{Idempotenz}}\\ %\neg \neg \F &\equiv \F \tag{\structure{Doppelte Negation}}\\ %\F \vee \neg \F &\equiv \true \tag{\structure{Triviale Tautologie}}\\ %\F \wedge \neg \F &\equiv \false \tag{\structure{Triviale Kontradiktion}}\\ %\bigskip %\F \vee \G &\equiv \G \vee \F \tag{\structure{Kommutativität}}\\ %\F \wedge \G &\equiv \G \wedge \F\\ %(\F \vee \G) \vee \K &\equiv \F \vee (\G \vee \K) \tag{\structure{Assoziativität}}\\ %(\F \wedge \G) \wedge \K &\equiv \F \wedge (\G \wedge \K)\\ %\F \vee (\G \wedge \K) &\equiv (\F \vee \G) \wedge (\F \vee \K) \tag{\structure{Distributivität}}\\ %\F \wedge (\G \vee \K) &\equiv (\F \wedge \G) \vee (\F \wedge \K)\\ %\neg(\F \wedge \G) &\equiv \neg \F \vee \neg \G \tag{\structure{De Morgan}}\\ %\neg(\F \vee \G) &\equiv \neg\F \wedge \neg\G\\ %\bigskip %\F \rightarrow \G &\equiv \neg \F \vee \G \tag{\structure{Implikation}}\\ %\F \leftrightarrow \G &\equiv (\F \rightarrow \G) \wedge (\G \rightarrow \F) \tag{\structure{Bikonditional}}\\ %\end{align} %\end{frame} } } \defineUnit{aussagenlogiknormalformen}{% \begin{frame}[c] \frametitle{Literale und Klauseln} \setbeamercovered{dynamic} \begin{definition}[Literal] Ein \structure{Literal} ist eine Variable $v \in V$ oder die Negation $\neg v$ einer Variable. \end{definition} \begin{definition}[Klausel] Eine \structure{Klausel} verknüpft mehrere Literale mit einem assoziativen Operator. \end{definition} \vfill \begin{example}[] Seien $a, \neg b, c$ Literale. Dann sind \begin{itemize} \item $a \wedge \neg b \wedge c$ \item $a \vee \neg b \vee c$ \end{itemize} Klauseln. \end{example} \end{frame} { \newcommand{\klausel}[2]{\underbracket{(##2)}_{\text{##1-Klausel}}} \begin{frame} \frametitle{DNF} \setbeamercovered{dynamic} \begin{definition}[Disjunktive Normalform] Eine \structure{DNF-Klausel} ist eine Konjunktion von Literalen $L_i$.\\ Eine Formel $F$, ist in \structure{Disjunktiver Normalform}, wenn sie eine Disjunktion von DNF-Klauseln ist. \[ F \defeq \bigvee \bigwedge_i L_i \] \end{definition} \begin{itemize} \item Ausnahme: $\textrm{false}$ ist auch in DNF \end{itemize} \begin{example}[] $F$ ist in DNF. \[ F \defeq \klausel{DNF}{a \structure{\wedge} b \structure{\wedge} \neg c} \alert{\vee} \klausel{DNF}{\neg b \structure{\wedge} c} \alert{\vee} \klausel{DNF}{\neg a \structure{\wedge} b \structure{\wedge} \neg c} \] \end{example} \end{frame} \begin{frame} \frametitle{KNF} \setbeamercovered{dynamic} \begin{definition}[Konjunktive Normalform] Eine \structure{KNF-Klausel} ist eine Disjunktion von Literalen $L_i$.\\ Eine Formel $F$, ist in \structure{Konjunktiver Normalform}, wenn sie eine Konjunktion von KNF-Klauseln ist. \[ F \defeq \bigwedge \bigvee_i L_i \] \end{definition} \begin{itemize} \item Ausnahme: $\textrm{true}$ ist auch in KNF \end{itemize} \begin{example}[] $F$ ist in KNF. \[ F \defeq \klausel{KNF}{\neg a \alert{\vee} b} \structure{\wedge} \klausel{KNF}{\neg b \alert{\vee} c} \structure{\wedge} \klausel{KNF}{a \alert{\vee} b \alert{\vee} \neg c} \] \end{example} \end{frame} } \begin{frame} \frametitle{Konstruktion der NF} \setbeamercovered{dynamic} \begin{itemize} \item \structure{Jede} nicht-triviale Formel ist in DNF und KNF umwandelbar \item Durch Äquivalenzumformungen berechenbar (exponentiell groß!) \item Oder: Konstruktion mit Wahrheitstabellen \end{itemize} \vfill \begin{block}{Normalformen aus Wahrheitstabellen} Gegeben eine Formel $F$ und ihre Wahrheitstabelle \begin{itemize} \item DNF \begin{enumerate} \item Betrachte Zeilen mit Eintrag \structure{$1$} \item Bilde \structure{Konjunktion} aus der \structure{Belegung} \item Bilde \structure{Disjunktion} aller erhaltenen Klauseln \end{enumerate} \bigskip \item KNF \begin{enumerate} \item Betrachte Zeilen mit Eintrag \alert{$0$} \item Bilde \alert{Disjunktion} aus der \alert{Negation} der Belegung \item Bilde \alert{Konjunktion} aller erhaltenen Klauseln \end{enumerate} \end{itemize} \end{block} \end{frame} { \newcommand{\klausel}[4]{(##2 a ##1 ##3 b ##1 ##4 c)} \begin{frame} \frametitle{Konstruktion der NF} \setbeamercovered{dynamic} \begin{example}[] Gegeben eine Formel $F$ mit folgender Semantik \begin{center} \begin{tabu} to .4\textwidth {ccc|[1.2pt]c} a & b & c & $F$ \\ \tabucline[1.2pt]{-} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{tabu} \end{center} $F$ dargestellt in \begin{itemize} \item DNF $\hfill\klausel{\wedge}{\neg}{}{} \vee (a \wedge \neg b) \vee \klausel{\wedge}{}{}{\neg}\hfill$ \medskip \item KNF $\hfill(a \vee b) \wedge \klausel{\vee}{\neg}{}{\neg} \wedge \klausel{\vee}{\neg}{\neg}{\neg}\hfill$ \end{itemize} \end{example} \end{frame} \begin{frame} \frametitle{Mengendarstellung der KNF} \setbeamercovered{dynamic} \begin{block}{Mengendarstellung der KNF} Eine Formel $F = \bigwedge \bigvee L_i$ in \structure{KNF} kann in einer \structure{Mengendarstellung} repräsentiert werden. \begin{itemize} \item Klauseln werden durch Mengen von Literalen dargestellt \[\left\{ a, \neg b, c \right\} \text{ steht für } (a \vee \neg b \vee c)\] \item KNF-Formeln sind Mengen von Klauseln \[ \left\{ \left\{ \neg a \right\}, \left\{ a, \neg b, c \right\} \right\} \text{ steht für } \neg a \wedge (a \vee \neg b \vee c) \] \item $\emptyset$ steht für \textrm{true}, $\left\{ \emptyset \right\}$ für \textrm{false} \end{itemize} \end{block} \begin{example}[] Gegeben $F \defeq (a \vee b) \wedge \klausel{\vee}{\neg}{}{\neg} \wedge \klausel{\vee}{\neg}{\neg}{\neg}$ in KNF. \[ \left\{ \left\{ a, b \right\}, \left\{ \neg a, b, \neg c \right\}, \left\{ \neg a, \neg b, \neg c \right\} \right\}\] \end{example} \end{frame} } } \defineUnit{DPLL}{% \begin{frame} \frametitle{KNF aus Syntaxbaum} \setbeamercovered{dynamic} \begin{block}{Idee} Erzeuge die KNF aus dem Syntaxbaum \begin{enumerate} \item<1-> Weise jedem \structure{inneren Knoten} eine Variable zu \item<1,3-> Variablen sind \structure{abhängig} von ihren Kindern \item<1,4-> Berechne \structure{kleine} KNFs und führe diese \structure{zusammen} \end{enumerate} \end{block} \begin{columns}[T] \begin{column}{.7\textwidth} % FIXME: onlys around A_\vee needed for "correct" fadein \begin{align} (x \wedge y) \vee z \uncover<3->{\equiv &\hphantom{{}\wedge {}}\only<3->{A_\vee}\\ &\structure{\wedge (A_\vee \leftrightarrow A_\wedge \vee z)}\\ &\alert{\wedge (A_\wedge \leftrightarrow x \wedge y)}\\} \uncover<4->{\equiv &\hphantom{{}\wedge {}}\only<4->{A_\vee}\\ &\structure{\wedge (A_\vee \vee \neg A_\wedge) \wedge (A_\vee \vee \neg z)}\\ &\qquad\structure{\wedge (\neg A_\vee \vee A_\wedge \vee z)}\\ &\alert{\wedge (\neg A_\wedge \vee x) \wedge (\neg A_\wedge \vee y)} \\ &\qquad\alert{\wedge(A_\wedge \vee \neg x \vee \neg y)}} \end{align} \end{column} \begin{column}{.3\textwidth} \begin{tikzpicture}[grow=down, level distance = 33] \tikzstyle{op} = [pretty] \tikzstyle{var} = [pretty, rectangle] \tikzstyle{edge from parent} = [edge] \tikzstyle{level 1} = [sibling distance = 50] \tikzstyle{level 2} = [sibling distance = 30] \node at (0, 0) {}; \node[op] at (0, -1) {\alt<1>{$\vee$}{$A_\vee$}} child { node[op] {\alt<1>{$\wedge$}{$A_\wedge$}} edge from parent child { node[var] {$x$} edge from parent } child { node[var] {$y$} edge from parent } } child { node[var] {$z$} }; \end{tikzpicture} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{DPLL} \setbeamercovered{dynamic} \begin{definition}[DPLL-Belegung] Sei $F$ eine Formel in KNF und $p$ eine Variable von $F$.\\ Dann bezeichnet \structure{$F[p\backslash\mathrm{true}]$} die Formel, die entsteht, wenn jedes Vorkommnis von $p$ in F durch $\mathrm{true}$ ersetzt und vereinfacht wird. \end{definition} \begin{block}{DPLL} Gegeben eine Formel $F$ in KNF \begin{itemize} \item Wenn $F = \mathrm{true}$ dann antworte \enquote{erfüllbar} \item Wenn $F = \mathrm{false}$ dann antworte \enquote{unerfüllbar} \item Sonst \begin{enumerate} \item Wähle eine Variable $p$ in $F$ \item Prüfe ob $F[p\backslash\mathrm{true}]$ oder $F[p\backslash\mathrm{false}]$ erfüllbar \end{enumerate} \end{itemize} \end{block} \begin{itemize} \item Schlaue Wahl der Variable beschleunigt Ausführung \item Wähle Variablen die einzeln stehen (\structure{One-Literal-Rule}) \end{itemize} \end{frame} }