changeset 12:c903f55b68de

third slides and sheet
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 05 Nov 2013 00:02:23 +0100
parents c2d858c9c53e
children 7fed03e118ea
files ds13-03.pdf notes/tex/basics.tex notes/tex/preamble.tex notes/tex/ue03_notes.tex notes/ue03_notes.pdf
diffstat 5 files changed, 230 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
Binary file ds13-03.pdf has changed
--- a/notes/tex/basics.tex	Tue Nov 05 00:02:11 2013 +0100
+++ b/notes/tex/basics.tex	Tue Nov 05 00:02:23 2013 +0100
@@ -576,3 +576,218 @@
     }
 \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}
+}
--- a/notes/tex/preamble.tex	Tue Nov 05 00:02:11 2013 +0100
+++ b/notes/tex/preamble.tex	Tue Nov 05 00:02:23 2013 +0100
@@ -14,6 +14,7 @@
 \usepackage{url}
 \usepackage{listings}
 \usepackage{xcolor}
+\usepackage{tabu}
 \usepackage{tikz}
 \usepackage{pgfplots}
 \pgfplotsset{compat=1.8}
@@ -26,7 +27,8 @@
 \usepackage{amsmath}
 \usepackage{mathdots}
 \usepackage{mathtools}
-\mathtoolsset{showonlyrefs}
+\mathtoolsset{showonlyrefs,showmanualtags}
+\usepackage{mathrsfs}
 \usepackage{csquotes}
 \usepackage{wasysym}
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue03_notes.tex	Tue Nov 05 00:02:23 2013 +0100
@@ -0,0 +1,12 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 3: Aussagenlogik}
+\subtitle{Diskrete Strukturen im Wintersemester 2013/2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{aussagenlogiksyntax}
+\showUnit{aussagenlogiksemantik}
+\end{document}
Binary file notes/ue03_notes.pdf has changed