\documentclass[11pt]{article} \usepackage{geometry} % See geometry.pdf to learn the layout options. There are lots. \geometry{letterpaper} % ... or a4paper or a5paper or ... \usepackage[utf8]{inputenc} \usepackage{ngerman} %\geometry{landscape} % Activate for for rotated page geometry %\usepackage[parfill]{parskip} % Activate to begin paragraphs with an empty line rather than an indent \usepackage{graphicx} \usepackage{amssymb} \usepackage{amsmath} \usepackage{epstopdf} \usepackage{color} \usepackage{hyperref} \usepackage{qtree} \DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png} \definecolor{darkblue}{rgb}{0,0,.5} \hypersetup{pdftex=true, colorlinks=true, breaklinks=true, linkcolor=darkblue, menucolor=darkblue, pagecolor=darkblue, urlcolor=darkblue} \title{Mafi 1 - Mitschrift} \author{Ludwig Schuster} \date{} % Activate to display a given date or no date \begin{document} \maketitle Diese Mitschrift entsteht im Rahmen der Vorlesung Mafi1 bei Herrn Hoffmann an der FU-Berlin im Wintersemester 09/10 und darf gerne erg\"anzt und optimiert werden. Verbesserungen bitte den Autor (schustel[at]inf.fu-berlin.de) zukommen lassen. \tableofcontents \newpage \section{13.10.2009} \subsection{Organisatorisches} \textbf{Tutorien} Siehe Veranstaltungsseite \\ \url{http://www.inf.fu-berlin.de/lehre/WS09/mafi1/index.html} \\ \textbf{Vorlesungsbegin} \\ - Dienstag 08:30-10:00 \\ - Donnerstag 10:15-12:45 \\ \textbf{Literatur} siehe KVV Veranstaltungsseite \\ \url{https://www.mi.fu-berlin.de/kvv/course.htm?sid=18&cid=8356&iid=1} \\ \textbf{Feedback} \\ - Die Studenten haben ein Recht auf \textbf{vorbereitete} Tutoren und Dozenten \\ - Unstimmigkeiten \"uber Tutoren oder Dozenten d\"urfen und sollen kommuniziert werden. \subsection{Boolsche Aussagenlogik} \subsubsection{Was sind 'Aussagen'?} Eine Aussage ist ein Satz (formalsprachlich Gebilde) von dem es sinnvoll ist zu sagen es sei wahr oder falsch. \\ Grundprinzip: Zweiwertigkeit (wahr $\leftrightarrow$ falsch) \begin{enumerate} \item wie kann man Aussagen zusammensetzen? \item Syntax der Aussagenlogik \item Was ist Wahrheitswert von zusammengesetzten Aussagen? \end{enumerate} Grundprinzip: Extensionalit\"atsprinzip \begin{enumerate} \item 11 ist eine Primzahl $\rightsquigarrow$ Ja \item Jede nat\"urliche Zahl $n \geq 2$ besitzt eindeutige Zerlegung in Primfaktoren. $\rightsquigarrow$ Ja \item $\sqrt{7}$ ist rationale Zahl. $\rightsquigarrow$ Falsch \item Jede gerade nat\"urlich Zahl $>2$ ist Summe zweier Primzahlen \item Wenn es f\"ur eine nat\"urliche Zahl $n>2$ nat\"urliche Zahlen $x,y,z$ gibt, \\ mit $x^{n}+y^{n}=z^{n}$, so ist $x+y+z=0$ $\rightsquigarrow$ Ja \\ \textbf{Beispiel} $n=2 \rightarrow x=3, y=4, z=5 3^{2}+4^{2}=5^{2}$ \end{enumerate} \subsubsection{Wie bildet man zusammengesetzte Aussagen?} \begin{tabular}{lll} &\textbf {Notation} &\textbf {Sprechweise} \\ Negation einer Aussage a & $\neg a$ & nicht a \\ Konjunktion von Aussagen a und b & $a \wedge b$ & a und b \\ Disjunktion von a und b & $a \vee b$ & a oder b \\ Implikation von a und b & $a \Rightarrow b$ & wenn a ..., dann b \\ \"Aquivalenz von a und b & $a \Leftrightarrow b$ & a gilt genau dann, wenn b \\ Antivalenz von a und b & $a \oplus b$ & entweder a oder b \\ \end{tabular} \subsection{Syntax der Aussagenlogik} V eine Menge von Variablen, A eine Menge von konkreten Aussagen mit feststehenden Wahrheitswert. {true,false}ist inhalt von A Def: boolsche Formeln (=Boolsche Terme) f\"ur V und A. \begin{enumerate} \item Jedes $v \in V$ und jedes $a \in A$ ist boolscher Term. \item Wenn $t$ Boolscher Term ist, so ist auch $(\neg t)$ Boolscher Term. \item Wenn $t_{1}$ und $t_{2}$ Boolsche Terme, so auch $(t_{1} \vee t_{2})$ und $(t_{1} \wedge t_{2})$. \item Nur was sich durch endlich oftes anwenden von (1)-(3) erzeugen l\"asst, ist Boolscher Term. \end{enumerate} Anmerkung: 1 diese Menge {nicht, oder, und} hei{\ss}t Standard Signatur f\"ur Boolsche Terme. 2 Klammerung weiderspiegelt Hirachie. \section{15.10.2009} Die Anmeldung wird in den kommenden Tagen zur\"uckgesetzt - es wird gebeten dass sich ausschlie{\ss}lich dass nur wirklich notwendige Anmeldungen get\"atigt werden. Alle Teilnehmer die nicht zwingend die Anmeldung zur \"Ubung ben\"otigen, k\"onnen teilnehmen aber sich bitte nicht anmelden. Bsp: $V=\{x,y,z \} A=\{true,false \}$ zul\"assige B.T. $x,y,z,false$ $(\neg x), ((\neg x)\wedge z), (((\neg x) \wedge z) \vee y)$ $t=(((\neg x)\wedge z) \vee y)$ %\Tree [.$\vee$ [.$\wedge$ [.$\neg$ [.$x$]] [.$z$] ] [.$y$] ] \Tree [.$\vee$ [.$\wedge$ [.$\neg$ [.$x$ ]] [.$z$ ] ] [.$y$ ] ] $\rightarrow$ assozieren mit Boolschen Term bestimmte ``Ma{\ss}zahlen'' z.B. Rang eines boolschen Terms t (``Klammerungstiefe'') Def: rg(t) ist definiert als \begin{enumerate} \item Wenn $t=v$ f\"ur $v \in V$ oder $t=a,a \in A$ so sei $rgt=0$ \item Wenn $t=(\neg t_{1})$ f\"ur einen Term $t_{1}$ ist, so sei $rgt=rgt+1$ \item Wenn $t=(t_{1}\vee t_{2})$ oder $t=(t_{1}\wedge t_{2})$ so sei $rgt=max\{ rg(t_{1}),rg(t_{2}) \} +1$ \end{enumerate} \begin{align} rg\biggl(\Bigl(\bigl(\neg x\bigr)\wedge z\Bigr)\vee y\biggr) &= max\biggl\{ rg\Bigl(\bigl(\neg x\bigr)\wedge z\Bigr), rg y \biggr\}+1 \\ &=rg((\neg x)\wedge z)+1 \\ &=rg(\neg x)+1+1 \\ &=rg x + 1 +1 + 1 \\ &=3 \end{align} \subsection{Rechnen mit Wahrheitswerten, Boolsche Algebra} $\mathbb{B}=\{ 0,1 \} , \mathbb{B}x \mathbb{B}=\{ (0,0),(0,1),(1,0),(1,1) \} $ Definitionen Funktionen: $\neg : \mathbb{B}\rightarrow \mathbb{B}$ definiert durch $\neg (0)-1,\neg (1)=0$ $\wedge ,\vee ,\Rightarrow ,\Leftrightarrow ,\oplus : \mathbb{B}x \mathbb{B}\rightarrow \mathbb{B}$ \begin{tabular}{c|c||c|c|c|c|c} $b_{1}$ & $b_{2} $ & $b_{1} \wedge b_{2}$ & $b_{1} \vee b_{2}$ & $b_{1} \Rightarrow b_{2}$ & $b_{1} \Leftrightarrow b_{2}$ & $b_{1} \oplus b_{2}$ \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ \end{tabular} \subsection{Semantik von Boolschen Termen} $V=\{ v_{1},...,v_{n}\} $ Wenn man die Variablen mit konkreten Aussagen belegt, so liefert dies Zuordnung Variable $\rightsquigarrow $ Wahrheitswert (der Aussage) Belegungsfunktion: $ \beta : V \rightarrow \mathbb{B}$ sei $\beta (v_{i})=b_{i}\in \mathbb{B}$ Dies liefert mittels bottom-up-Auswertung. Wahrheitswert des Terms bei dieser Belegung $\beta $. \begin{tabular}{c|c|c|c} $\beta (x)$ & $\beta (y)$ & $\beta (z)$ & $I_{\beta } (t)$ \\ \hline 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \end{tabular} Definition: Interpretation $I_{\beta } (t)$ von t bez\"uglich Belegung $\beta$ \begin{align*} \text{Falls } t=v\text{, so sei } \quad I_{\beta}(t) = & \beta (v) \\ \text{Falls } t=a, a\in A \quad I_{\beta}(t) = & \text{Wahrheitswert von a}\\ \text{insbesondere } \quad I_{\beta}(true) = &1\\ \quad I_{\beta}(false) = & 0 \end{align*} Def: $V=\{ v_{1},...,v_{n}\}$ Die Zuordnugn von $(b_{1},...,b_{n})$ mit $b_{i}=\beta (v_{i})$ zu $I_{\beta}()t$ liefert eine n-stellige Boolsche Funktion $f_{t}:\mathbb{B}x\mathbb{B}x...x\mathbb{B}\rightarrow \mathbb{B}$ $f_{t} (b_{1},...,b_{n})=I_{\beta}(t)$ mittels $f_{t}(b_{1},...,b_{n})=I_{\beta}(t)$ $\rightarrow$ Diese Funktion $f_{t}$ hei{\ss}t Semantik von Term $t$. Def: \begin{enumerate} \item ein Boolscher Term $t$ hei{\ss}t erf\"ullbar, wenn es wenigstens eine Belegung des Variablen gibt, si dass $f_{t}$ Wert $1$ hat. \item Boolsche Term hei{\ss}t Tautologie, falls jede Belegung der Variablen f\"ur $f_{t}$ den Wert $1$ ergibt. \item Boolsche Term hei{\ss}t Kontradiktion, wenn alle Belegungen zu $0$ ausgewertet werden. \item Zwei Terme $t_{1},t_{2}$ hei{\ss}en semantisch \"aquivalent, falls $f_{t_{1}}=f_{t_{2}}$ Notation: $t_{1}\equiv t_{2}$ \end{enumerate} \end{document}