Mercurial > 13ws.ds
comparison notes/tex/logic.tex @ 37:3de775b67d8c
eigth sheet and notes
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Tue, 10 Dec 2013 01:58:46 +0100 |
| parents | 010d8f7fa899 |
| children | e65f4b1a6e32 |
comparison
equal
deleted
inserted
replaced
| 36:f386dfdaeade | 37:3de775b67d8c |
|---|---|
| 955 \item Kann verallgemeinert werden, z.B. auf $\Z$ | 955 \item Kann verallgemeinert werden, z.B. auf $\Z$ |
| 956 \item Aber nicht auf $\R$ (Warum?) | 956 \item Aber nicht auf $\R$ (Warum?) |
| 957 \end{itemize} | 957 \end{itemize} |
| 958 \end{frame} | 958 \end{frame} |
| 959 } | 959 } |
| 960 | |
| 961 \defineUnit{wohlfundierteinduktion}{% | |
| 962 \begin{frame} | |
| 963 \frametitle{Wohlfundierte Relation} | |
| 964 \setbeamercovered{dynamic} | |
| 965 | |
| 966 \begin{definition}[Wohlfundierte Relation] | |
| 967 Eine Relation $\prec \subseteq A \times A$ heißt \structure{wohlfundiert}, wenn keine \alert{unendlichen Folgen} von Elementen $a_1, a_2, a_3, \dots \in A$ existieren, sodass | |
| 968 \[a_1 \succ a_2 \succ a_3 \succ \dots\] | |
| 969 Jede Kette hat ein \structure{unteres Ende}. | |
| 970 \end{definition} | |
| 971 | |
| 972 \vfill | |
| 973 | |
| 974 \begin{example}[] | |
| 975 \begin{itemize} | |
| 976 \item $\prec_1 \defeq \left\{ (a, b) \in \N^2 \mid a < b \right\}$ ist wohlfundiert. | |
| 977 \item $\prec_2 \defeq \left\{ (a, b) \in \N^2 \mid a > b \right\}$ ist \alert{nicht} wohlfundiert. | |
| 978 \item $\prec_3 \defeq \left\{ (a, b) \in \Z^2 \mid a < b \right\}$ ist \alert{nicht} wohlfundiert. | |
| 979 \item $\prec_4 \defeq \left\{ (a, b) \in \N^2 \mid \exists x . x \text{ teilt } a \wedge x \text{ teilt } b \right\}$ ist \alert{nicht} wohlfundiert. | |
| 980 \smallskip | |
| 981 \item $\prec_5 \defeq \emptyset$ ist wohlfundiert. | |
| 982 \end{itemize} | |
| 983 \end{example} | |
| 984 \end{frame} | |
| 985 | |
| 986 \begin{frame} | |
| 987 \frametitle{Wohlfundierte Induktion} | |
| 988 \setbeamercovered{dynamic} | |
| 989 | |
| 990 \begin{block}{Wohlfundierte Induktion} | |
| 991 Die \structure{wohlfundierte Induktion} verallgemeinert die vollständige Induktion.\\ | |
| 992 Um für eine Menge $A$ mit wohlfundierter Relation $\prec$ ein Prädikat | |
| 993 \[ \alert{\forall a \in A.\; P(a)} \] | |
| 994 zu zeigen, beweist man | |
| 995 \begin{description}[Induktionsanfang\quad] | |
| 996 \item[Induktionsanfang] Man zeigt, dass für alle bezüglich $\prec$ \structure{minimalen} Elemente $m_i$ das Prädikat gilt. | |
| 997 \item[Induktionsschritt] Man zeigt, dass wenn \structure{alle kleineren} Elemente als $n$ das Prädikat erfüllen, so auch $n$. | |
| 998 \end{description} | |
| 999 \vspace{1em} | |
| 1000 In Prädikatenlogik formuliert gilt | |
| 1001 \begin{align} | |
| 1002 \structure{\forall a \in A. \left( \forall b \prec a.\; P(b) \rightarrow P(a) \right)} \quad\text{gdw.}\quad \alert{\forall a \in A.\; P(a)} | |
| 1003 \end{align} | |
| 1004 \end{block} | |
| 1005 | |
| 1006 \vfill | |
| 1007 | |
| 1008 \begin{itemize} | |
| 1009 \item Wo ist der Induktionsanfang? | |
| 1010 \end{itemize} | |
| 1011 \end{frame} | |
| 1012 } |