# HG changeset patch # User Markus Kaiser # Date 1383606143 -3600 # Node ID c903f55b68de860425ed82dfdec86fc933e19a78 # Parent c2d858c9c53e6cc720aba54bd23e9c97d77a6833 third slides and sheet diff -r c2d858c9c53e -r c903f55b68de ds13-03.pdf Binary file ds13-03.pdf has changed diff -r c2d858c9c53e -r c903f55b68de notes/tex/basics.tex --- 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} +} diff -r c2d858c9c53e -r c903f55b68de notes/tex/preamble.tex --- 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} diff -r c2d858c9c53e -r c903f55b68de notes/tex/ue03_notes.tex --- /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} diff -r c2d858c9c53e -r c903f55b68de notes/ue03_notes.pdf Binary file notes/ue03_notes.pdf has changed