Mercurial > 13ws.ds

comparison notes/tex/basics.tex @ 16:b83150706135

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
use consistent implication arrow
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 12 Nov 2013 00:34:37 +0100
parents 2c32ba8308c3
children 099613ee2f37
comparison
equal deleted inserted replaced
15:2c32ba8308c3 16:b83150706135
592 \begin{align} 592 \begin{align}
593 \neg A &\in \mathcal{F}\tag{\alert{Negation}}\\ 593 \neg A &\in \mathcal{F}\tag{\alert{Negation}}\\
594 \intertext{\item Sind $A, B \in \mathcal{F}$ aussagenlogische Formeln, dann auch} 594 \intertext{\item Sind $A, B \in \mathcal{F}$ aussagenlogische Formeln, dann auch}
595 (A \wedge B)&\in \mathcal{F}\tag{\alert{Konjunktion}}\\ 595 (A \wedge B)&\in \mathcal{F}\tag{\alert{Konjunktion}}\\
596 (A \vee B)&\in \mathcal{F}\tag{\alert{Disjunktion}}\\ 596 (A \vee B)&\in \mathcal{F}\tag{\alert{Disjunktion}}\\
597 (A \Rightarrow B)&\in \mathcal{F}\tag{\alert{Implikation}} 597 (A \rightarrow B)&\in \mathcal{F}\tag{\alert{Implikation}}
598 \end{align} 598 \end{align}
599 \end{itemize} 599 \end{itemize}
600 Alle Formeln lassen sich so konstruieren. 600 Alle Formeln lassen sich so konstruieren.
601 \end{definition} 601 \end{definition}
602 \end{frame} 602 \end{frame}
605 \frametitle{Operatorenbindung} 605 \frametitle{Operatorenbindung}
606 \setbeamercovered{dynamic} 606 \setbeamercovered{dynamic}
607 607
608 \begin{definition}[Bindungsregeln] 608 \begin{definition}[Bindungsregeln]
609 Die \structure{Bindungsstärke} der Operatoren in absteigender Reihenfolge ist 609 Die \structure{Bindungsstärke} der Operatoren in absteigender Reihenfolge ist
610 \[ \neg \quad \wedge \quad \vee \quad \Rightarrow \quad \Leftrightarrow \] 610 \[ \neg \quad \wedge \quad \vee \quad \rightarrow \quad \leftrightarrow \]
611 Die Implikation ist \structure{rechtsassoziativ} 611 Die Implikation ist \structure{rechtsassoziativ}
612 \[ 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) \] 612 \[ 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) \]
613 \end{definition} 613 \end{definition}
614 \begin{itemize} 614 \begin{itemize}
615 \item Üblicherweise klammert man $\wedge$ und $\vee$ 615 \item Üblicherweise klammert man $\wedge$ und $\vee$
616 \[ (a \wedge b) \vee c \text{\quad statt\quad} a \wedge b \vee c \] 616 \[ (a \wedge b) \vee c \text{\quad statt\quad} a \wedge b \vee c \]
617 \end{itemize} 617 \end{itemize}
618 \begin{example}[] 618 \begin{example}[]
619 \begin{itemize} 619 \begin{itemize}
620 \item $\neg a \wedge b$\quad steht für \quad$ \left( \left( \neg a \right) \wedge b \right)$ 620 \item $\neg a \wedge b$\quad steht für \quad$ \left( \left( \neg a \right) \wedge b \right)$
621 \item $a \wedge b \Rightarrow c \vee \neg d$\quad steht für \quad$((a \wedge b) \Rightarrow (c \vee \left( \neg d \right)))$ 621 \item $a \wedge b \rightarrow c \vee \neg d$\quad steht für \quad$((a \wedge b) \rightarrow (c \vee \left( \neg d \right)))$
622 \end{itemize} 622 \end{itemize}
623 \end{example} 623 \end{example}
624 \end{frame} 624 \end{frame}
625 625
626 \begin{frame} 626 \begin{frame}
629 629
630 \begin{block}{Syntaxbaum} 630 \begin{block}{Syntaxbaum}
631 \structure{Syntaxbäume} visualisieren in welcher Reihenfolge die Regeln zur induktiven Definition angewandt werden müssen, um eine Formel zu erzeugen. 631 \structure{Syntaxbäume} visualisieren in welcher Reihenfolge die Regeln zur induktiven Definition angewandt werden müssen, um eine Formel zu erzeugen.
632 \end{block} 632 \end{block}
633 \begin{example}[] 633 \begin{example}[]
634 Sei $F \defeq a \wedge b \Rightarrow c \vee \neg d$ dann ist der dazu passende Syntaxbaum 634 Sei $F \defeq a \wedge b \rightarrow c \vee \neg d$ dann ist der dazu passende Syntaxbaum
635 \centering 635 \centering
636 \begin{tikzpicture}[grow=down, level distance = 33] 636 \begin{tikzpicture}[grow=down, level distance = 33]
637 \tikzstyle{every node} = [] 637 \tikzstyle{every node} = []
638 \tikzstyle{op} = [pretty] 638 \tikzstyle{op} = [pretty]
639 \tikzstyle{var} = [pretty, rectangle] 639 \tikzstyle{var} = [pretty, rectangle]
640 \tikzstyle{edge from parent} = [edge] 640 \tikzstyle{edge from parent} = [edge]
641 641
642 \tikzstyle{level 1} = [sibling distance = 80] 642 \tikzstyle{level 1} = [sibling distance = 80]
643 \tikzstyle{level 2} = [sibling distance = 40] 643 \tikzstyle{level 2} = [sibling distance = 40]
644 \node[op] {$\Rightarrow$} 644 \node[op] {$\rightarrow$}
645 child { 645 child {
646 node[op] {$\wedge$} 646 node[op] {$\wedge$}
647 edge from parent 647 edge from parent
648 child { 648 child {
649 node[var] {$a$} 649 node[var] {$a$}
712 \item Die Semantik löst eingesetzte Formeln auf 712 \item Die Semantik löst eingesetzte Formeln auf
713 \item Wird anhand der induktiven Syntax definiert 713 \item Wird anhand der induktiven Syntax definiert
714 \item Es gibt \alert{syntaktisch verschiedene} Formeln gleicher \structure{Semantik} 714 \item Es gibt \alert{syntaktisch verschiedene} Formeln gleicher \structure{Semantik}
715 \end{itemize} 715 \end{itemize}
716 \begin{example}[] 716 \begin{example}[]
717 Sei $F \defeq \left( G \Rightarrow H \right)$ mit $G, H$ Formeln. Dann ist 717 Sei $F \defeq \left( G \rightarrow H \right)$ mit $G, H$ Formeln. Dann ist
718 \[ [F](\beta) = \begin{cases} 718 \[ [F](\beta) = \begin{cases}
719 0 & \text{falls } [G](\beta) = 1 \text{ und } [H](\beta) = 0 \\ 719 0 & \text{falls } [G](\beta) = 1 \text{ und } [H](\beta) = 0 \\
720 1 & \text{sonst} 720 1 & \text{sonst}
721 \end{cases}\] 721 \end{cases}\]
722 \end{example} 722 \end{example}
728 728
729 \begin{block}{Wahrheitstabelle} 729 \begin{block}{Wahrheitstabelle}
730 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. 730 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.
731 \end{block} 731 \end{block}
732 \begin{example}[] 732 \begin{example}[]
733 Sei $F \defeq a \vee b \Rightarrow \neg c \wedge b$. Die zu $[F]$ gehörige Wahrheitstabelle ist 733 Sei $F \defeq a \vee b \rightarrow \neg c \wedge b$. Die zu $[F]$ gehörige Wahrheitstabelle ist
734 \begin{center} 734 \begin{center}
735 \begin{tabu} to .5\textwidth {cccX|[1.2pt]Xccccc} 735 \begin{tabu} to .5\textwidth {cccX|[1.2pt]Xccccc}
736 a & b & c & & & $a \vee b$ & $\Rightarrow$ & $\neg c$ & $\wedge$ & $b$ \\ \tabucline[1.2pt]{-} 736 a & b & c & & & $a \vee b$ & $\rightarrow$ & $\neg c$ & $\wedge$ & $b$ \\ \tabucline[1.2pt]{-}
737 0 & 0 & 0 & & & \onslide<2->{0} & \onslide<3->{\structure{1}} & \onslide<2->{1} & \onslide<2->{0} & \\ 737 0 & 0 & 0 & & & \onslide<2->{0} & \onslide<3->{\structure{1}} & \onslide<2->{1} & \onslide<2->{0} & \\
738 0 & 0 & 1 & & & \onslide<2->{0} & \onslide<3->{\structure{1}} & \onslide<2->{0} & \onslide<2->{0} & \\ 738 0 & 0 & 1 & & & \onslide<2->{0} & \onslide<3->{\structure{1}} & \onslide<2->{0} & \onslide<2->{0} & \\
739 0 & 1 & 0 & & & \onslide<2->{1} & \onslide<3->{\structure{1}} & \onslide<2->{1} & \onslide<2->{1} & \\ 739 0 & 1 & 0 & & & \onslide<2->{1} & \onslide<3->{\structure{1}} & \onslide<2->{1} & \onslide<2->{1} & \\
740 0 & 1 & 1 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{0} & \onslide<2->{0} & \\ 740 0 & 1 & 1 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{0} & \onslide<2->{0} & \\
741 1 & 0 & 0 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{1} & \onslide<2->{0} & \\ 741 1 & 0 & 0 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{1} & \onslide<2->{0} & \\
753 753
754 \begin{definition}[Äquivalente Formeln] 754 \begin{definition}[Äquivalente Formeln]
755 Man nennt zwei Formeln \structure{äquivalent}, wenn sie dieselbe Semantik besitzen.\\ 755 Man nennt zwei Formeln \structure{äquivalent}, wenn sie dieselbe Semantik besitzen.\\
756 Seien $F, G$ Formeln mit Belegungen $\mathcal{B} = \mathcal{B}_F = \mathcal{B}_G$. $F$ und $G$ sind äquivalent wenn 756 Seien $F, G$ Formeln mit Belegungen $\mathcal{B} = \mathcal{B}_F = \mathcal{B}_G$. $F$ und $G$ sind äquivalent wenn
757 \[ \forall \beta \in \mathcal{B}. [F](\beta) = [G](\beta) \] 757 \[ \forall \beta \in \mathcal{B}. [F](\beta) = [G](\beta) \]
758 Man schreibt \structure{$F \equiv G$} oder \structure{$F \Leftrightarrow G$}. 758 Man schreibt \structure{$F \equiv G$} oder \structure{$F \leftrightarrow G$}.
759 \end{definition} 759 \end{definition}
760 760
761 \begin{example}[] 761 \begin{example}[]
762 Für $F \defeq a \Rightarrow b$ und $G \defeq \neg a \vee b$ gilt $F \equiv G$. 762 Für $F \defeq a \rightarrow b$ und $G \defeq \neg a \vee b$ gilt $F \equiv G$.
763 \begin{center} 763 \begin{center}
764 \begin{tabu} to .4\textwidth {cc|[1.2pt]XcX||Xccc} 764 \begin{tabu} to .4\textwidth {cc|[1.2pt]XcX||Xccc}
765 a & b & & $a \Rightarrow b$ & & & $\neg a$ & $\vee$ & $b$ \\ \tabucline[1.2pt]{-} 765 a & b & & $a \Rightarrow b$ & & & $\neg a$ & $\vee$ & $b$ \\ \tabucline[1.2pt]{-}
766 0 & 0 & & \structure{1} & & & 1 & \structure{1} \\ 766 0 & 0 & & \structure{1} & & & 1 & \structure{1} \\
767 0 & 1 & & \structure{1} & & & 1 & \structure{1} \\ 767 0 & 1 & & \structure{1} & & & 1 & \structure{1} \\