Binary file ds13-06.pdf has changed

--- a/notes/tex/basics.tex	Tue Nov 19 14:56:59 2013 +0100
+++ b/notes/tex/basics.tex	Mon Nov 25 23:16:14 2013 +0100
@@ -360,12 +360,13 @@
         \end{tikzpicture}
     \end{example}
 \end{frame}
+}
 
+\defineUnit{relationeneigenschaften}{%
 \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]

--- a/notes/tex/logic.tex	Tue Nov 19 14:56:59 2013 +0100
+++ b/notes/tex/logic.tex	Mon Nov 25 23:16:14 2013 +0100
@@ -6,7 +6,7 @@
     \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 $\false = 0 = \bot \in \mathcal{F},\quad \true = 1 = \top \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
@@ -215,9 +215,7 @@
 
 \defineUnit{aussagenlogikaequivalenzen}{%
 {
-    \newcommand{\true}{1}
-    \newcommand{\false}{0}
-    \newcommand{\spc}{\hspace{3em}}
+    \newcommand{\spc}{\hfill}
     \newcommand{\F}{F}
     \newcommand{\G}{G}
     \newcommand{\K}{H}
@@ -244,7 +242,7 @@
                 $\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)$
+            \item[Bikonditional] $\F \leftrightarrow \G \equiv \neg(\F \otimes \G) \left[ \equiv (\F \rightarrow \G) \wedge (\G \rightarrow \F) \right]$
         \end{description}
     \end{frame}
 
@@ -314,7 +312,7 @@
             \[ F \defeq \bigvee \bigwedge_i L_i \]
         \end{definition}
         \begin{itemize}
-            \item Ausnahme: $\textrm{false}$ ist auch in DNF
+            \item Ausnahme: $\false$ ist auch in DNF
         \end{itemize}
 
         \begin{example}[]
@@ -333,7 +331,7 @@
             \[ F \defeq \bigwedge \bigvee_i L_i \]
         \end{definition}
         \begin{itemize}
-            \item Ausnahme: $\textrm{true}$ ist auch in KNF
+            \item Ausnahme: $\true$ ist auch in KNF
         \end{itemize}
 
         \begin{example}[]
@@ -416,7 +414,7 @@
                     \[\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}
+                \item $\emptyset$ steht für $\true$, $\left\{ \emptyset \right\}$ für $\false$
             \end{itemize}
         \end{block}
         \begin{example}[]
@@ -491,18 +489,18 @@
 
     \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.
+        Dann bezeichnet \structure{$F[p\backslash\true]$} die Formel, die entsteht, wenn jedes Vorkommnis von $p$ in F durch $\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 \structure{erfüllbar}
-            \item Wenn $F = \mathrm{false}$ dann antworte \structure{unerfüllbar}
+            \item Wenn $F = \true$ dann antworte \structure{erfüllbar}
+            \item Wenn $F = \false$ dann antworte \structure{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
+                    \item Prüfe ob $F[p\backslash\true]$ oder $F[p\backslash\false]$ erfüllbar
                 \end{enumerate}
         \end{itemize}
     \end{block}
@@ -552,7 +550,7 @@
     \end{definition}
 
     \begin{definition}[Folgerung]
-        $F$ \structure{folgt aus} $A$, wenn mit Hilfe der \alert{Semantik} der \alert{Aussagenlogik} $F$ unter der Annahme dass $A$ gilt zu $\mathrm{true}$ ausgewertet wird. Wir schreiben
+        $F$ \structure{folgt aus} $A$, wenn mit Hilfe der \alert{Semantik} der \alert{Aussagenlogik} $F$ unter der Annahme dass $A$ gilt zu $\true$ ausgewertet wird. Wir schreiben
         \[ A \vDash F \]
     \end{definition}
 
@@ -746,3 +744,115 @@
     \end{frame}
 }
 }
+
+\defineUnit{praedikatenlogiksyntax}{%
+{
+    \newcommand{\terms}{\mathcal{T}}
+    \newcommand{\preds}{\mathcal{P}}
+    \newcommand{\logic}{\mathcal{L}}
+    \begin{frame}[c]
+        \frametitle{Syntax der Prädikatenlogik}
+        \setbeamercovered{dynamic}
+
+        \begin{definition}[Term]
+            Die Menge $\terms$ aller \structure{Terme} ist induktiv definiert.
+            \begin{itemize}
+                \item Jede Konstante ist in $\terms$
+                \item Jede Variable ist in $\terms$
+                \item Sind $f$ eine Funktion und $t_1, \dots, t_n$ Terme, dann auch
+                    \[ f(t_1, \dots, t_n) \]
+            \end{itemize}
+            Funktionen wandeln Terme in \alert{Terme} um. Wir beschreiben sie mit Kleinbuchstaben.
+        \end{definition}
+
+        \begin{definition}[Prädikat]
+            \structure{Prädikate} $P$ wandeln Terme in \alert{Wahrheitswerte} um.
+            Wir beschreiben sie mit Großbuchstaben.\\
+            Die Menge $\preds$ enthält alle \structure{Prädikate}.
+        \end{definition}
+    \end{frame}
+
+    \begin{frame}[c]
+        \frametitle{Syntax der Prädikatenlogik}
+        \setbeamercovered{dynamic}
+
+        \begin{definition}[Syntax der Prädikatenlogik]
+            Die Menge \structure{$\logic$} aller \structure{prädikatenlogischen Formeln} ist induktiv definiert.
+            Seien $A, B\in \logic$, $t_i \in \terms$ und $P \in \preds$. Dann sind alle Formeln
+            {
+                \setlength{\belowdisplayskip}{0pt}
+                \setlength{\abovedisplayskip}{0pt}
+                \begin{itemize}
+                        \item Grundbausteile
+                            \smallskip
+                        \begin{align}
+                            V = \left\{ a, b, \dots \right\} &\subseteq \logic\tag{\alert{Variablen}}\\
+                            P(t_1, \dots, t_n) &\in \logic\tag{\alert{Prädikate, Konstanten}}\\
+                            t_i = t_j &\in\logic\tag{\alert{Gleichheit}}\\
+                            \shortintertext{\item Verknüpfungen der Aussagenlogik}
+                            \neg A &\in \logic\tag{\alert{Negation}}\\
+                            (A \wedge B), (A \vee B)&\in \logic\tag{\alert{Konjunktion, Disjunktion}}\\
+                            (A \rightarrow B)&\in \logic\tag{\alert{Implikation}}\\
+                            \shortintertext{\item \structure{Quantoren}}
+                            \exists x. A &\in \logic\tag{\alert{Existenzquantor}}\\
+                            \forall x. A &\in \logic\tag{\alert{Allquantor}}\\
+                        \end{align}
+                \end{itemize}
+            }
+            \vspace{-1.5em}
+        \end{definition}
+    \end{frame}
+
+    \begin{frame}
+        \frametitle{Operatorenbindung}
+        \setbeamercovered{dynamic}
+
+        \begin{definition}[Bindungsregeln]
+            Die \structure{Bindungsstärke} der Operatoren in absteigender Reihenfolge ist
+            \[ \forall \quad \exists \quad \neg \quad \wedge \quad \vee \quad \rightarrow \quad \leftrightarrow \]
+            Die Implikation ist \structure{rechtsassoziativ}.
+        \end{definition}
+        \begin{itemize}
+            \item Üblicherweise klammert man wieder $\wedge$ und $\vee$
+            \item Genauso klammert man Quantoren
+                \[ \left( \forall x. F \right) \rightarrow G \text{\quad statt\quad} \forall x. F \rightarrow G \]
+            \vfill
+            \item \alert{Achtung!} Äußere Quantoren werden öfter anders interpretiert
+                \[ \forall x \forall y. F \wedge G \leftrightarrow H \]
+                Bindet formal \alert{nur an das F}!
+        \end{itemize}
+    \end{frame}
+}
+}
+
+\defineUnit{praedikatenlogikstruktur}{%
+\begin{frame}[c]
+    \frametitle{Struktur}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Struktur]
+        Eine passende \structure{Struktur} $S = \left( U_s, I_s \right)$ zu einer Formel $F$ besteht aus einem \structure{Universum} $U_s$ und einer \structure{Interpretation} $I_s$.
+        \begin{itemize}
+            \item Alle Terme werten zu einem Wert im \structure{Universum} $U_s$ aus
+            \item Die \structure{Interpretation} $I_s$ weist den Atomen der Formel Werte zu.\\
+                Sie spezifiziert
+                \begin{itemize}
+                    \item \alert{Variablen} $x$ mit
+                        {
+                            \setlength{\belowdisplayskip}{0pt}
+                            \setlength{\abovedisplayskip}{0pt}
+                            \begin{align}
+                                x_s \in {} &U_s\\
+                            \shortintertext{\item \alert{Konstanten} $a$ mit}
+                                a_s \in {} &U_s\\
+                            \shortintertext{\item \alert{k-stellige Prädikate} $P$ mit}
+                                P_s \subseteq {} &U_s^k\\
+                            \shortintertext{\item \alert{Funktionen} $f$ mit}
+                                f_s : {} &U_s^k \to U_s
+                            \end{align}
+                        }
+                \end{itemize}
+        \end{itemize}
+    \end{definition}
+\end{frame}
+}

--- a/notes/tex/preamble.tex	Tue Nov 19 14:56:59 2013 +0100
+++ b/notes/tex/preamble.tex	Mon Nov 25 23:16:14 2013 +0100
@@ -48,6 +48,9 @@
 \newcommand{\Prob}{\mathrm{P}}
 \newcommand{\Oh}{\mathcal{O}}
 
+\newcommand{\true}{\mathrm{true}}
+\newcommand{\false}{\mathrm{false}}
+
 \newcommand{\abs}[1]{\left\vert #1 \right\vert}
 \newcommand{\powerset}[1]{\mathcal{P}\left( #1 \right)}
 \newcommand{\setnot}[1]{\overline{#1}}

--- a/notes/tex/ue02_notes.tex	Tue Nov 19 14:56:59 2013 +0100
+++ b/notes/tex/ue02_notes.tex	Mon Nov 25 23:16:14 2013 +0100
@@ -8,5 +8,6 @@
 \begin{document}
 \showUnit{titel}
 \showUnit{relationen}
+\showUnit{relationeneigenschaften}
 \showUnit{funktionen}
 \end{document}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue06_notes.tex	Mon Nov 25 23:16:14 2013 +0100
@@ -0,0 +1,13 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 6: Prädikatenlogik}
+\subtitle{Diskrete Strukturen im Wintersemester 2013/2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{praedikatenlogiksyntax}
+\showUnit{praedikatenlogikstruktur}
+\showUnit{relationeneigenschaften}
+\end{document}

Binary file notes/ue06_notes.pdf has changed