13ws.ds: notes/tex/basics.tex comparison

comparison notes/tex/basics.tex @ 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	2c32ba8308c3

comparison

equal deleted inserted replaced

-:c2d858c9c53e
+:c903f55b68de
 (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}
+}

Mercurial > 13ws.ds

comparison notes/tex/basics.tex @ 12:c903f55b68de