Mercurial > 13ws.ds
annotate notes/tex/basics.tex @ 16:b83150706135
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 |
rev | line source |
---|---|
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
1 \defineUnit{mengen}{% |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
2 \begin{frame} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
3 \frametitle{Mengen} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
4 \setbeamercovered{dynamic} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
5 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
6 \begin{definition}[Menge] |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
7 Eine \structure{Menge} ist eine \alert{ungeordnete} Sammlung \alert{unterscheidbarer} Objekte.\\ |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
8 Mit \structure{Mengenklammern} werden Objekte zusammengefasst. |
3 | 9 \[ A \defeq \left\{ a, b, \ldots, z \right\} \] |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
10 Man nennt $a$ ein \structure{Element} von $A$, es gilt $a \in A$. |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
11 \end{definition} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
12 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
13 \begin{itemize} |
3 | 14 \item Reihenfolge ist \alert{egal} |
15 \item Elemente kommen \alert{nicht} mehrfach vor | |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
16 \end{itemize} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
17 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
18 \vfill |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
19 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
20 \begin{example}[] |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
21 \begin{itemize} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
22 \item $\left\{ a, b, c, a, c \right\} = \left\{ a, b, c \right\} = \left\{ c, a, b \right\}$ |
3 | 23 \item $\N \defeq \left\{ 1, 2, 3, \ldots \right\}$ |
24 \item $\emptyset \defeq \left\{ \right\}$ | |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
25 \end{itemize} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
26 \end{example} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
27 \end{frame} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
28 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
29 \begin{frame} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
30 \frametitle{Schreibweisen} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
31 \setbeamercovered{dynamic} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
32 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
33 \begin{definition}[Extensionale Schreibweise] |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
34 Die \structure{extensionale Schreibweise} einer Menge zählt ihre Elemente auf. |
3 | 35 \[ M \defeq \left\{ x_1, x_2, x_3, \ldots \right\} \] |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
36 \end{definition} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
37 \vfill |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
38 \begin{example}[] |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
39 \begin{itemize} |
3 | 40 \item $A \defeq \left\{ 2, 4, 6, \ldots \right\}$ |
41 \item $B \defeq \left\{ 1, 2, 3, 4 \right\}$ = [4] | |
42 \item $C \defeq \left\{ 2, 3, 5, 7, 11, \ldots \right\}$ | |
43 \item $D \defeq \left\{ \alpha, a, \smiley, 8, \left\{ 1, 2 \right\}, \N \right\}$ | |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
44 \end{itemize} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
45 \end{example} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
46 \end{frame} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
47 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
48 \begin{frame} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
49 \frametitle{Schreibweisen} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
50 \setbeamercovered{dynamic} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
51 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
52 \begin{definition}[Intensionale Schreibweise] |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
53 Die \structure{intensionale Schreibweise} beschreibt eine Menge durch charakteristische Eigenschaften. |
3 | 54 \[ M \defeq \left\{ x \in \Omega \mid P(x) \right\} \] |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
55 $M$ enthält alle Elemente im \structure{Universum} $\Omega$ mit der Eigenschaft $P$. |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
56 \end{definition} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
57 \vfill |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
58 \begin{example}[] |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
59 \begin{itemize} |
3 | 60 \item $A \defeq \left\{ 2, 4, 6, \ldots \right\} = \left\{ x \in \N \mid x\ \text{gerade} \right\} = \left\{ 2x : x \in \N \right\}$ |
61 \item $B \defeq \left\{ 1, 2, 3, 4 \right\} = \left\{ x \in \N \mid x \leq 4 \right\}$ | |
62 \item $C \defeq \left\{ 2, 3, 5, 7, 11, \ldots \right\} = \left\{ x \in \N \mid x\ \text{prim} \right\}$ | |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
63 \end{itemize} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
64 \end{example} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
65 \end{frame} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
66 } |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
67 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
68 \defineUnit{mengenoperationen}{% |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
69 \begin{frame} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
70 \frametitle{Mengenoperationen} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
71 \setbeamercovered{dynamic} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
72 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
73 \begin{block}{Bezeichnungen} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
74 \begin{itemize} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
75 \item Objekte in Mengen |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
76 \begin{description}[\qquad\qquad] |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
77 \item[$a \in A$] $a$ ist Element von $A$ |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
78 \item[$b \not\in A$] $b$ ist kein Element von $A$ |
3 | 79 \item[$\abs{A}$] Anzahl der Elemente in $A$, Kardinalität |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
80 \end{description} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
81 \item Relationen zwischen Mengen |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
82 \begin{description}[\qquad\qquad] |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
83 \item[$B \subseteq A$] $B$ ist Teilmenge von $A$, \quad $x \in B \Rightarrow x \in A$ |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
84 \item[$B \subset A$] $B$ ist echte Teilmenge von $A$ |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
85 \item[$B = A$] $B \subseteq A$ und $A \subseteq B$ |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
86 \end{description} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
87 \end{itemize} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
88 \end{block} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
89 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
90 \begin{example}[] |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
91 \begin{itemize} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
92 \item $1 \in \left\{ 1, 2, 3, 4 \right\}$, aber $9 \not\in \left\{ 1, 2, 3, 4 \right\}$ |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
93 \item $\left\{ 1, 2 \right\} \subseteq \left\{ 1, 2, 3, 4 \right\}$, aber $\left\{ 1, 5 \right\} \not\subseteq \left\{ 1, 2 \right\}$ |
3 | 94 \item $\emptyset \subseteq [5] \subseteq \N \subseteq \N_0 \subseteq \Z \subseteq \Q \subseteq \R \subseteq \C$ |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
95 \end{itemize} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
96 \end{example} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
97 \end{frame} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
98 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
99 \begin{frame} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
100 \frametitle{Mengenoperationen} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
101 \setbeamercovered{dynamic} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
102 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
103 \begin{block}{Operationen} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
104 \begin{description}[\qquad\qquad] |
3 | 105 \item[$\setnot{A}$] $\defeq \left\{ x \mid x \not\in A \right\}$\hfill\alert{Komplement} |
106 \item[$A \cup B$] $\defeq \left\{ x \mid x \in A\ \text{oder}\ x \in B \right\}$\hfill\alert{Vereinigung} | |
107 \item[$A \cap B$] $\defeq \left\{ x \mid x \in A\ \text{und}\ x \in B \right\}$\hfill\alert{Schnitt} | |
108 \item[$A \setminus B$] $\defeq A \cap \setnot{B}$\hfill\alert{Differenz} | |
109 \item[$A \setsymdiff B$] $\defeq \left( A \setminus B \right) \cup \left( B \setminus A \right)$\hfill\alert{Symmetrische Differenz} | |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
110 \end{description} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
111 \end{block} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
112 \vill |
3 | 113 Für mehrere Mengen schreibt man |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
114 \begin{align} |
3 | 115 \bigcap_{i=1}^n A_i &\defeq A_1 \cap A_2 \cap \ldots \cap A_n\\ |
116 \bigcup_{i=1}^n A_i &\defeq A_1 \cup A_2 \cup \ldots \cup A_n | |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
117 \end{align} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
118 \end{frame} |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
119 } |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
120 |
3 | 121 \defineUnit{venn}{% |
122 \begin{frame} | |
123 \frametitle{Venn-Diagramme} | |
124 \setbeamercovered{dynamic} | |
125 | |
126 \structure{Venn-Diagramme} visualisieren Mengen $A, B, \ldots$ im Universum $\Omega$. | |
127 | |
128 { | |
129 \def\universe{(-1.5, -1.25) rectangle (2.5, 1.25) node[anchor=north east, black] {$\Omega$}} | |
130 \def\first{(0, 0) circle (1)} | |
131 \def\second{(1, 0) circle (1)} | |
132 \tikzstyle{universe} = [draw, thick, tumblue, fill=tumlightblue!15] | |
133 \tikzstyle{inset} = [fill=tumred!35] | |
134 \tikzstyle{outline} = [draw, thick, black] | |
135 \begin{columns} | |
136 \begin{column}{.5\textwidth} | |
137 \begin{itemize} | |
138 \item $A \cup B$ | |
139 \begin{figure} | |
140 \begin{tikzpicture} | |
141 \draw[universe] \universe; | |
142 \fill[inset] \first; | |
143 \fill[inset] \second; | |
144 \draw[outline] \first node[left=1em] {$A$}; | |
145 \draw[outline] \second node[right=1em] {$B$}; | |
146 \end{tikzpicture} | |
147 \end{figure} | |
148 \item $A \setminus B$ | |
149 \begin{figure} | |
150 \begin{tikzpicture} | |
151 \draw[universe] \universe; | |
152 \begin{scope} | |
153 \clip \first; | |
154 \fill[inset, even odd rule] \first \second; | |
155 \end{scope} | |
156 \draw[outline] \first node[left=1em] {$A$}; | |
157 \draw[outline] \second node[right=1em] {$B$}; | |
158 \end{tikzpicture} | |
159 \end{figure} | |
160 \end{itemize} | |
161 \end{column} | |
162 \begin{column}{.5\textwidth} | |
163 \begin{itemize} | |
164 \item $A \cap B$ | |
165 \begin{figure} | |
166 \begin{tikzpicture} | |
167 \draw[universe] \universe; | |
168 \begin{scope} | |
169 \clip \first; | |
170 \fill[inset] \second; | |
171 \end{scope} | |
172 \draw[outline] \first node[left=1em] {$A$}; | |
173 \draw[outline] \second node[right=1em] {$B$}; | |
174 \end{tikzpicture} | |
175 \end{figure} | |
176 \item $A \setsymdiff B = (A \setminus B) \cup (B \setminus A)$ | |
177 \begin{figure} | |
178 \begin{tikzpicture} | |
179 \draw[universe] \universe; | |
180 \fill[inset, even odd rule] \first \second; | |
181 \draw[outline] \first node[left=1em] {$A$}; | |
182 \draw[outline] \second node[right=1em] {$B$}; | |
183 \end{tikzpicture} | |
184 \end{figure} | |
185 \end{itemize} | |
186 \end{column} | |
187 \end{columns} | |
188 } | |
189 \end{frame} | |
190 } | |
191 | |
192 \defineUnit{mengenrechenregeln}{% | |
193 \begin{frame} | |
194 \frametitle{Rechnen mit Mengen} | |
195 \setbeamercovered{dynamic} | |
196 | |
197 \begin{theorem}[De Morgansche Gesetze] | |
198 Sind $A, B$ Mengen, dann gilt | |
199 \begin{alignat}{2} | |
200 \setnot{A \cup B} &= \setnot{A} \cap \setnot{B} \qquad\qquad& \setnot{A \cap B} &= \setnot{A} \cup \setnot{B}\\ | |
201 \intertext{Für Mengen $A_i$ gilt} | |
6 | 202 \setnot{\bigcup_{i=1}^nA_i} &= \bigcap_{i=1}^n\setnot{A_i} & \setnot{\bigcap_{i=1}^nA_i} &= \bigcup_{i=1}^n\setnot{A_i} & |
3 | 203 \end{alignat} |
204 \end{theorem} | |
205 | |
206 \vfill | |
207 | |
208 \begin{itemize} | |
209 \item Zusammen mit $\setnot{\setnot{A}} = A$ wichtigste Regel | |
210 \item Gilt auch in der Aussagenlogik | |
211 \end{itemize} | |
212 \end{frame} | |
213 } | |
214 | |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
215 \defineUnit{potenzmenge}{% |
3 | 216 \begin{frame} |
217 \frametitle{Potenzmenge} | |
218 \setbeamercovered{dynamic} | |
219 | |
220 \begin{definition}[Potenzmenge] | |
221 Die \structure{Potenzmenge} $\powerset{M}$ zu einer Menge $M$ ist die Menge all ihrer Teilmengen. | |
222 \[ \powerset{M} \defeq \left\{ X \mid X \subseteq M \right\} \] | |
223 \end{definition} | |
224 | |
225 \begin{itemize} | |
226 \item $\powerset{M}$ enthält für endliche Mengen genau $2^{\abs{M}}$ Elemente | |
227 \item Man schreibt deshalb auch $2^M$ | |
228 \item Es ist $M \in \powerset{M}$ und $\emptyset \in \powerset{M}$ | |
229 \end{itemize} | |
230 | |
231 \vfill | |
232 | |
233 \begin{example}[] | |
234 Für $M = \left\{ a, b, c \right\}$ ist | |
6 | 235 \[ \powerset{M} = \left\{ |
3 | 236 \emptyset, |
237 \left\{ a \right\}, | |
238 \left\{ b \right\}, | |
239 \left\{ c \right\}, | |
240 \left\{ a, b \right\}, | |
241 \left\{ a, c \right\}, | |
242 \left\{ b, c \right\}, | |
243 \left\{ a, b, c \right\} | |
244 \right\} \] | |
245 mit $\abs{\powerset{M}} = 2^3 = 8$ | |
246 \end{example} | |
247 \end{frame} | |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
248 } |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
249 |
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
250 \defineUnit{tupel}{% |
3 | 251 \begin{frame} |
252 \frametitle{Tupel} | |
253 \setbeamercovered{dynamic} | |
254 | |
255 \begin{definition}[Tupel] | |
256 Ein \structure{$n$-Tupel} ist eine \alert{geordnete} Sammlung $n$ \alert{beliebiger} Objekte.\\ | |
257 Mit \structure{Tupelklammern} werden Objekte zusammengefasst. | |
258 \[ T \defeq \left( t_1, t_2, \ldots, t_n \right)\] | |
259 \end{definition} | |
260 | |
261 \begin{itemize} | |
262 \item Reihenfolge \alert{nicht} egal | |
263 \item Elemente \alert{dürfen} mehrmals vorkommen | |
264 \end{itemize} | |
265 | |
266 \vfill | |
267 | |
268 \begin{example}[] | |
269 \begin{itemize} | |
4
fac222767cda
add missing math context
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
3
diff
changeset
|
270 \item $\left( a, b, c \right) \neq \left( c, a, b \right) \neq \left( a, b, c, a, c \right)$ |
3 | 271 \item $\left( 1, 2, 3 \right) \neq \left\{ 3, 2, 1 \right\} = \left\{ 1, 2, 3 \right\}$ |
272 \item $\left( \left\{ \alpha, \beta \right\}, \emptyset, \N \right)$ | |
273 \end{itemize} | |
274 \end{example} | |
275 \end{frame} | |
276 | |
277 \begin{frame} | |
278 \frametitle{Kreuzprodukt} | |
279 \setbeamercovered{dynamic} | |
280 | |
281 \begin{definition}[Kreuzprodukt] | |
282 Sind $A, B$ Mengen, dann ist ihr \structure{kartesisches Produkt} (Kreuzprodukt) | |
283 \begin{align} | |
284 A \times B &\defeq \left\{ \left( a, b \right) \mid a \in A, b \in B \right\}\\ | |
285 \intertext{Für Mengen $A_i$ ist} | |
286 A_1 \times \ldots \times A_n &\defeq \left\{ \left(a_1, \ldots, a_n\right) \mid a_1 \in A_1, \ldots, a_n \in A_n \right\} | |
287 \end{align} | |
288 \end{definition} | |
289 | |
290 \begin{itemize} | |
291 \item Für endliche $A_i$ ist $\abs{A_1 \times \ldots \times A_n} = \abs{A_1} \cdot \ldots \cdot \abs{A_n}$ | |
292 \item Man schreibt \structure{$A^n \defeq \underbracket[0.5pt]{A \times \ldots \times A}_{\text{n mal}}$} mit $A^0 = \left\{ \emptyset \right\}$ | |
293 \end{itemize} | |
294 | |
295 \vfill | |
296 | |
297 \begin{example}[] | |
298 \begin{itemize} | |
299 \item $\left\{ 1, 2 \right\} \times \left\{ a, b \right\} = \left\{ (1, a), (2, a), (1, b), (2, b) \right\}$ | |
300 \item $\left\{ \alpha, \beta \right\}^2 = \left\{ (\alpha, \alpha), (\alpha, \beta), (\beta, \alpha), (\beta, \beta) \right\}$ | |
301 \end{itemize} | |
302 \end{example} | |
303 \end{frame} | |
1
ae52d9ffef38
add basic theme; first slides
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
diff
changeset
|
304 } |
6 | 305 |
306 \defineUnit{relationen}{% | |
307 \begin{frame} | |
308 \frametitle{Relation} | |
309 \setbeamercovered{dynamic} | |
310 | |
311 \begin{definition}[Relation] | |
312 Eine binäre \structure{Relation} $R$ verbindet Elemente zweier Mengen $A$ und $B$. | |
313 \[ R \subseteq A \times B\] | |
314 Ist $(a, b) \in R$, so schreibt man auch \structure{$a\rel{R}b$}. | |
315 \end{definition} | |
316 | |
317 \begin{itemize} | |
318 \item Eine Relation über $M \times M$ nennt man homogen | |
319 \item Es gibt $\abs{\powerset{A \times B}}$ Relationen über $A, B$ | |
320 \end{itemize} | |
321 | |
322 \begin{example}[] | |
323 \begin{itemize} | |
324 \item Die \alert{Gleichheitsrelation} über $\N \times \N$ \\ | |
325 $\left\{ (1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7) \ldots \right\}$ | |
326 \medskip | |
327 \item Die \alert{Teilbarkeitsrelation} über $\N$ \\ | |
328 $\left\{ (1,1), (1,2), (1,3), \ldots, (2,2), (2,4), \ldots, (3,3), (3,6), \ldots \right\}$ | |
329 \end{itemize} | |
330 \end{example} | |
331 \end{frame} | |
332 | |
333 \begin{frame} | |
334 \frametitle{Grafische Darstellung} | |
335 \setbeamercovered{dynamic} | |
336 | |
337 \begin{block}{Grafische Darstellung von Relationen} | |
338 Jede Relation $R \subseteq M \times M$ kann als \structure{Graph} dargestellt werden. Die Elemente aus M werden zu \structure{Knoten} und für jedes Tupel $(a, b) \in R$ wird ein \structure{Pfeil} von $a$ nach $b$ eingefügt. | |
339 \end{block} | |
340 | |
341 \begin{example}[] | |
342 Sei $R \subseteq [4] \times [4]$ eine Relation über den natürlichen Zahlen. | |
343 \[ R \defeq \left\{ (1, 1), (1, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 3) \right\}\] | |
344 | |
11
c2d858c9c53e
move example graph into example block
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
345 \centering |
c2d858c9c53e
move example graph into example block
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
346 \begin{tikzpicture}[x=5em, y=2.5em] |
c2d858c9c53e
move example graph into example block
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
347 \path (0, 0) node[pretty] (1) {$1$} |
c2d858c9c53e
move example graph into example block
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
348 +(1, 0) node[pretty] (2) {$2$} |
c2d858c9c53e
move example graph into example block
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
349 +(2, 1) node[pretty] (3) {$3$} |
c2d858c9c53e
move example graph into example block
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
350 +(2, -1) node[pretty] (4) {$4$}; |
6 | 351 |
11
c2d858c9c53e
move example graph into example block
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
352 \path[edge] |
6 | 353 (1) edge[loop left] (1) |
354 (1) edge (2) | |
355 (2) edge (3) | |
356 (2) edge (4) | |
357 (3) edge[loop above] (3) | |
358 (3) edge[bend left] (4) | |
359 (4) edge[bend left] (3); | |
11
c2d858c9c53e
move example graph into example block
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
360 \end{tikzpicture} |
c2d858c9c53e
move example graph into example block
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
6
diff
changeset
|
361 \end{example} |
6 | 362 \end{frame} |
363 | |
364 \begin{frame} | |
365 \frametitle{Eigenschaften von Relationen} | |
366 \setbeamercovered{dynamic} | |
367 | |
368 | |
369 \begin{block}{Eigenschaften homogener Relationen} | |
370 Sei $R \in M \times M$ eine homogene Relation. Man nennt $R$ | |
371 \begin{description}[antisymmetrisch] | |
372 \item[reflexiv] $ \forall a\hphantom{, b, c} \in M.\ (a, a) \in R$ | |
373 \item[total] $ \forall a, b\hphantom{, c} \in M.\ (a, b) \in R \vee (b, a) \in R$ | |
374 \medskip | |
375 \item[symmetrisch] $ \forall a, b\hphantom{, c} \in M.\ (a, b) \in R \hphantom{{}\wedge (b, a) \in R}\Rightarrow (b,a ) \in R$ | |
376 \item[asymmetrisch] $ \forall a, b\hphantom{, c} \in M.\ (a, b) \in R \hphantom{{}\wedge (b, a) \in R}\Rightarrow (b,a ) \not\in R$ | |
377 \item[antisymmetrisch] $ \forall a, b\hphantom{, c} \in M.\ (a, b) \in R \wedge (b, a) \in R \Rightarrow a \equiv b$ | |
378 \medskip | |
379 \item[transitiv] $ \forall a, b, c \in M.\ (a, b) \in R \wedge (b, c) \in R \Rightarrow (a, c) \in R$ | |
380 \end{description} | |
381 \end{block} | |
382 | |
383 \vfill | |
384 | |
385 \begin{itemize} | |
386 \item Jede totale Relation ist reflexiv | |
387 \item Jede asymmetrische Relation ist antisymmetrisch | |
388 \item \structure{Äquivalenzrelationen} sind reflexiv, symmetrisch und transitiv | |
389 \item $R^+$ ist die \structure{transitive Hülle}, $R^*$ die \structure{reflexive transitive Hülle} | |
390 \end{itemize} | |
391 \end{frame} | |
392 } | |
393 | |
394 \defineUnit{funktionen}{% | |
395 \begin{frame} | |
396 \frametitle{Funktion} | |
397 \setbeamercovered{dynamic} | |
398 | |
399 \begin{definition}[Funktion] | |
400 Eine Relation $f \subseteq A \times B$ ist eine \structure{Funktion von A nach B} wenn es für alle $a \in A$ genau ein Element $b \in B$ mit $a \rel{f} b$ gibt. | |
401 \[ \forall a \in A. \abs{\left\{ (a, b) \mid b \in B \right\}} \alert{=} 1 \] | |
402 Man schreibt | |
403 \begin{align} | |
404 f : A &\to B \\ | |
405 a &\mapsto f(a) = b | |
406 \end{align} | |
407 \structure{$A \to B$} bezeichnet die Menge aller Funktionen von $A$ nach $B$. | |
408 \end{definition} | |
409 | |
410 \vfill | |
411 \centering | |
412 { | |
413 \tikzstyle{set} = [draw, thick, tumgreen, fill=tumgreen!15] | |
414 \tikzstyle{element} = [thick] | |
415 \tikzstyle{arrow} = [thick, tumblue, shorten >=-.4em, shorten <=-.4em] | |
416 \begin{tikzpicture}[x=1.5em, y=1.5em] | |
417 \draw[set] (0, 0) ellipse (1 and 2); | |
418 \draw[set] (5, 0) ellipse (1 and 2); | |
419 | |
420 \path[element] | |
421 (0,0) | |
422 +(0, 1.5) node (a1) {$\times$} | |
423 +(0.2, 0.85) node (a2) {$\times$} | |
424 +(0.1, -0.6) node (a4) {$\times$} | |
425 +(-0.1, -1.5) node (a5) {$\times$}; | |
426 | |
427 \path[element] | |
428 (5,0) | |
429 +(0, 1.5) node (b1) {$\times$} | |
430 +(0.2, 0.85) node (b2) {$\times$} | |
431 +(-0.3, 0.0) node (b3) {$\times$} | |
432 +(0.1, -0.6) node (b4) {$\times$} | |
433 +(-0.1, -1.5) node (b5) {$\times$}; | |
434 | |
435 \path[arrow] | |
436 (a1) edge (b1) | |
437 (a2) edge (b5) | |
438 (a4) edge (b2) | |
439 (a5) edge (b5); | |
440 | |
441 \path | |
442 (0, -2.5) node {$A$} | |
443 (5, -2.5) node {$B$} | |
444 (2.5, -2.5) node {$f$}; | |
445 \end{tikzpicture} | |
446 } | |
447 \end{frame} | |
448 | |
449 \begin{frame} | |
450 \frametitle{Bild und Urbild} | |
451 \setbeamercovered{dynamic} | |
452 | |
453 \begin{definition}[Bild] | |
454 Sei $f : A \to B$ eine Funktion, $X \subseteq A$, $Y \subseteq B$, $b \in B$. Dann ist | |
455 \begin{align} | |
456 f(X) &\defeq \left\{ f(x) \mid x \in X \right\} \\ | |
457 \intertext{das \structure{Bild} der Menge $X$ unter $f$. Außerdem ist} | |
458 f^{-1}(b) &\defeq \left\{ a \mid a \in A, f(a) = b \right\} \\ | |
459 f^{-1}(Y) &\defeq \bigcup_{y \in Y} \left\{ f^{-1}(y) \right\} | |
460 \end{align} | |
461 das \structure{Urbild} des Elements $b$ und der Menge $Y$ unter $f$. | |
462 \end{definition} | |
463 | |
464 \vfill | |
465 | |
466 \begin{itemize} | |
467 \item Man nennt $A = f^{-1}(B)$ \structure{Urbild} oder \structure{Definitionsmenge} von $f$ | |
468 \item Man nennt $f(A) \subseteq B$ \structure{Bild} oder \structure{Wertemenge} von $f$ | |
469 \end{itemize} | |
470 \end{frame} | |
471 | |
472 \begin{frame} | |
473 \frametitle{Komposition} | |
474 \setbeamercovered{dynamic} | |
475 | |
476 \begin{definition}[Funktionskomposition] | |
477 Seien $f : B \to C$ und $g : A \to B$ Funktionen. Dann ist | |
478 \begin{align} | |
479 h : A &\to C \\ | |
480 a &\mapsto (f \circ g)(a) = f(g(a)) | |
481 \end{align} | |
482 die \structure{Komposition} der Funktionen $f$ und $g$.\\ | |
483 Man ließt $f \circ g$ als \enquote{f \structure{nach} g}. | |
484 \end{definition} | |
485 | |
486 \vfill | |
487 | |
488 Man definiert die Potenzierung von Funktionen ähnlich der Mengentheorie. | |
489 \begin{align} | |
490 f^0 &\defeq id\\ | |
491 f^n &\defeq \underbracket[0.5pt]{f \circ \ldots \circ f}_{\text{n mal}} | |
492 \end{align} | |
493 Dabei bezeichnet $id$ die \structure{Identität} mit $id(x) \defeq x$. | |
494 \end{frame} | |
495 | |
15
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
496 { |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
497 \tikzstyle{set} = [draw, thick, tumgreen, fill=tumgreen!15] |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
498 \tikzstyle{element} = [thick] |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
499 \tikzstyle{head} = [draw, fill=tumblue!15, thick] |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
500 \tikzstyle{arrow} = [thick, tumblue, shorten >=-.4em, shorten <=-.4em] |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
501 \newcommand{\function}[3]{% |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
502 \draw[set] (0, 0) ellipse (1 and 2); |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
503 \draw[set] (4, 0) ellipse (1 and 2); |
6 | 504 |
15
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
505 \path[element] |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
506 (0,0) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
507 +(0, 1.5) node (a1) {$\times$} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
508 +(0.2, 0.85) node (a2) {$\times$} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
509 +(0.1, 0.3) node (a3) {$\times$} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
510 +(-0.1, -0.1) node (a4) {$\times$} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
511 +(-0.2, -0.7) node (a5) {##2} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
512 +(-0.1, -1.5) node (a6) {##3}; |
6 | 513 |
15
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
514 \path[element] |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
515 (4,0) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
516 +(0, 1.5) node (b1) {$\times$} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
517 +(0.2, 0.85) node (b2) {$\times$} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
518 +(-0.3, 0.0) node (b3) {$\times$} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
519 +(0.1, -0.6) node (b4) {$\times$} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
520 +(-0.1, -1.5) node (b5) {$\times$}; |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
521 |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
522 \path |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
523 (0, -2.5) node {$A$} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
524 (4, -2.5) node {$B$} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
525 (2, -2.5) node {$f$} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
526 (2, 3) node[head] {##1}; |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
527 } |
6 | 528 |
15
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
529 \begin{frame} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
530 \frametitle{Eigenschaften von Funktionen} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
531 \setbeamercovered{dynamic} |
6 | 532 |
15
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
533 \begin{block}{Eigenschaften von Funktionen} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
534 Sei $f: A \to B$ eine Funktion. Man nennt $f$ |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
535 \begin{description}[surjektiv] |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
536 \item[injektiv] $\forall b \in B. \abs{f^{-1}(b)} \leq 1$ \hfill(Kein $b$ wird doppelt getroffen) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
537 \item[surjektiv] $\forall b \in B. \abs{f^{-1}(b)} \geq 1$\hfill(Jedes $b$ wird getroffen) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
538 \item[bijektiv] $\forall b \in B. \abs{f^{-1}(b)} = 1$\hfill(Jedes $b$ wird genau einmal getroffen) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
539 \end{description} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
540 \end{block} |
6 | 541 |
15
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
542 \vfill |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
543 \centering |
6 | 544 \begin{tikzpicture}[x=1.5em, y=1.5em] |
545 \function{Injektiv}{}{} | |
546 | |
547 \path[arrow] | |
15
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
548 (a1) edge (b1) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
549 (a2) edge (b3) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
550 (a3) edge (b2) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
551 (a4) edge (b4); |
6 | 552 \end{tikzpicture} |
553 \hfill | |
554 \begin{tikzpicture}[x=1.5em, y=1.5em] | |
555 \function{Surjektiv}{$\times$}{$\times$} | |
556 | |
557 \path[arrow] | |
15
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
558 (a1) edge (b1) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
559 (a2) edge (b3) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
560 (a3) edge (b2) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
561 (a4) edge (b4) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
562 (a5) edge (b5) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
563 (a6) edge (b5); |
6 | 564 \end{tikzpicture} |
565 \hfill | |
566 \begin{tikzpicture}[x=1.5em, y=1.5em] | |
567 \function{Bijektiv}{}{$\times$} | |
568 | |
569 \path[arrow] | |
15
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
570 (a1) edge (b1) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
571 (a2) edge (b3) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
572 (a3) edge (b2) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
573 (a4) edge (b4) |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
574 (a6) edge (b5); |
6 | 575 \end{tikzpicture} |
15
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
576 \end{frame} |
2c32ba8308c3
hopefully fix compilation error in funktionen unit
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
12
diff
changeset
|
577 } |
6 | 578 } |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
579 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
580 \defineUnit{aussagenlogiksyntax}{% |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
581 \begin{frame}[c] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
582 \frametitle{Syntax der Aussagenlogik} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
583 \setbeamercovered{dynamic} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
584 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
585 \begin{definition}[Syntax der Aussagenlogik] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
586 Aussagenlogische \structure{Formeln} bestehen aus Konstanten, Variablen und Operatoren. Die Menge \structure{$\mathcal{F}$} aller Formeln ist induktiv definiert. |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
587 \begin{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
588 \item $\mathrm{false} = 0 \in \mathcal{F},\quad \mathrm{true} = 1 \in \mathcal{F}$\hfill(\alert{Konstanten}) |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
589 \item $V = \left\{ a, b, c,\ldots \right\} \subseteq \mathcal{F}$\hfill(\alert{Variablen})\\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
590 \medskip |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
591 \item Ist $A \in \mathcal{F}$ eine aussagenlogische Formel, dann auch |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
592 \begin{align} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
593 \neg A &\in \mathcal{F}\tag{\alert{Negation}}\\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
594 \intertext{\item Sind $A, B \in \mathcal{F}$ aussagenlogische Formeln, dann auch} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
595 (A \wedge B)&\in \mathcal{F}\tag{\alert{Konjunktion}}\\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
596 (A \vee B)&\in \mathcal{F}\tag{\alert{Disjunktion}}\\ |
16
b83150706135
use consistent implication arrow
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
597 (A \rightarrow B)&\in \mathcal{F}\tag{\alert{Implikation}} |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
598 \end{align} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
599 \end{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
600 Alle Formeln lassen sich so konstruieren. |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
601 \end{definition} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
602 \end{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
603 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
604 \begin{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
605 \frametitle{Operatorenbindung} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
606 \setbeamercovered{dynamic} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
607 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
608 \begin{definition}[Bindungsregeln] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
609 Die \structure{Bindungsstärke} der Operatoren in absteigender Reihenfolge ist |
16
b83150706135
use consistent implication arrow
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
610 \[ \neg \quad \wedge \quad \vee \quad \rightarrow \quad \leftrightarrow \] |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
611 Die Implikation ist \structure{rechtsassoziativ} |
16
b83150706135
use consistent implication arrow
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
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) \] |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
613 \end{definition} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
614 \begin{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
615 \item Üblicherweise klammert man $\wedge$ und $\vee$ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
616 \[ (a \wedge b) \vee c \text{\quad statt\quad} a \wedge b \vee c \] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
617 \end{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
618 \begin{example}[] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
619 \begin{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
620 \item $\neg a \wedge b$\quad steht für \quad$ \left( \left( \neg a \right) \wedge b \right)$ |
16
b83150706135
use consistent implication arrow
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
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)))$ |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
622 \end{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
623 \end{example} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
624 \end{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
625 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
626 \begin{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
627 \frametitle{Syntaxbaum} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
628 \setbeamercovered{dynamic} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
629 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
630 \begin{block}{Syntaxbaum} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
631 \structure{Syntaxbäume} visualisieren in welcher Reihenfolge die Regeln zur induktiven Definition angewandt werden müssen, um eine Formel zu erzeugen. |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
632 \end{block} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
633 \begin{example}[] |
16
b83150706135
use consistent implication arrow
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
634 Sei $F \defeq a \wedge b \rightarrow c \vee \neg d$ dann ist der dazu passende Syntaxbaum |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
635 \centering |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
636 \begin{tikzpicture}[grow=down, level distance = 33] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
637 \tikzstyle{every node} = [] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
638 \tikzstyle{op} = [pretty] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
639 \tikzstyle{var} = [pretty, rectangle] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
640 \tikzstyle{edge from parent} = [edge] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
641 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
642 \tikzstyle{level 1} = [sibling distance = 80] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
643 \tikzstyle{level 2} = [sibling distance = 40] |
16
b83150706135
use consistent implication arrow
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
644 \node[op] {$\rightarrow$} |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
645 child { |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
646 node[op] {$\wedge$} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
647 edge from parent |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
648 child { |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
649 node[var] {$a$} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
650 edge from parent |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
651 } |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
652 child { |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
653 node[var] {$b$} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
654 edge from parent |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
655 } |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
656 } |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
657 child { |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
658 node[op] {$\vee$} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
659 edge from parent |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
660 child { |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
661 node[var] {$c$} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
662 edge from parent |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
663 } |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
664 child { |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
665 node[op] {$\neg$} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
666 edge from parent |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
667 child { |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
668 node[var] {$d$} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
669 edge from parent |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
670 } |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
671 } |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
672 }; |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
673 \end{tikzpicture} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
674 \end{example} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
675 \end{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
676 } |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
677 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
678 \defineUnit{aussagenlogiksemantik}{% |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
679 \begin{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
680 \frametitle{Belegung} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
681 \setbeamercovered{dynamic} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
682 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
683 \begin{definition}[Belegung] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
684 Eine passende \structure{Belegung} $\beta$ zu einer Formel $F$ ordnet jeder Variable in $V$ einen Wahrheitswert aus $\left\{ 0, 1 \right\}$ zu. Es ist |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
685 \[ \beta : V \to \left\{ 0, 1 \right\} \] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
686 \end{definition} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
687 \begin{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
688 \item Belegungen formalisieren Einsetzen |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
689 \item Für $n$ Variablen existieren $2^n$ Belegungen |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
690 \end{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
691 \begin{example}[] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
692 Sei $F \defeq \neg \left( a \wedge b \right)$ mit $V = \left\{ a, b \right\}$ und |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
693 \begin{align} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
694 \beta : \left\{ a, b \right\} &\to \left\{ 0, 1 \right\}\\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
695 a &\mapsto 1\\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
696 b &\mapsto 0 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
697 \end{align} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
698 Dann ist $\beta$ eine zu $F$ passende \structure{Belegung}. |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
699 \end{example} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
700 \end{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
701 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
702 \begin{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
703 \frametitle{Semantik der Aussagenlogik} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
704 \setbeamercovered{dynamic} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
705 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
706 \begin{definition}[Semantik einer Formel] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
707 Die \structure{Semantik} $[F]$ einer aussagenlogischen Formel $F$ ist eine Funktion, die jeder passenden Belegung $\beta$ einen Wahrheitswert zuordnet.\\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
708 Sei $\mathcal{B} = \left\{ \beta_0, \beta_1, \ldots \right\}$ die Menge aller Belegungen zu $F$. Dann ist |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
709 \[[F] : \mathcal{B} \to \left\{ 0, 1 \right\}\] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
710 \end{definition} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
711 \begin{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
712 \item Die Semantik löst eingesetzte Formeln auf |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
713 \item Wird anhand der induktiven Syntax definiert |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
714 \item Es gibt \alert{syntaktisch verschiedene} Formeln gleicher \structure{Semantik} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
715 \end{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
716 \begin{example}[] |
16
b83150706135
use consistent implication arrow
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
717 Sei $F \defeq \left( G \rightarrow H \right)$ mit $G, H$ Formeln. Dann ist |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
718 \[ [F](\beta) = \begin{cases} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
719 0 & \text{falls } [G](\beta) = 1 \text{ und } [H](\beta) = 0 \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
720 1 & \text{sonst} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
721 \end{cases}\] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
722 \end{example} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
723 \end{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
724 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
725 \begin{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
726 \frametitle{Wahrheitstabelle} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
727 \setbeamercovered{dynamic} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
728 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
729 \begin{block}{Wahrheitstabelle} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
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. |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
731 \end{block} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
732 \begin{example}[] |
16
b83150706135
use consistent implication arrow
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
733 Sei $F \defeq a \vee b \rightarrow \neg c \wedge b$. Die zu $[F]$ gehörige Wahrheitstabelle ist |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
734 \begin{center} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
735 \begin{tabu} to .5\textwidth {cccX|[1.2pt]Xccccc} |
16
b83150706135
use consistent implication arrow
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
736 a & b & c & & & $a \vee b$ & $\rightarrow$ & $\neg c$ & $\wedge$ & $b$ \\ \tabucline[1.2pt]{-} |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
737 0 & 0 & 0 & & & \onslide<2->{0} & \onslide<3->{\structure{1}} & \onslide<2->{1} & \onslide<2->{0} & \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
738 0 & 0 & 1 & & & \onslide<2->{0} & \onslide<3->{\structure{1}} & \onslide<2->{0} & \onslide<2->{0} & \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
739 0 & 1 & 0 & & & \onslide<2->{1} & \onslide<3->{\structure{1}} & \onslide<2->{1} & \onslide<2->{1} & \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
740 0 & 1 & 1 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{0} & \onslide<2->{0} & \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
741 1 & 0 & 0 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{1} & \onslide<2->{0} & \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
742 1 & 0 & 1 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{0} & \onslide<2->{0} & \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
743 1 & 1 & 0 & & & \onslide<2->{1} & \onslide<3->{\structure{1}} & \onslide<2->{1} & \onslide<2->{1} & \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
744 1 & 1 & 1 & & & \onslide<2->{1} & \onslide<3->{\structure{0}} & \onslide<2->{0} & \onslide<2->{0} & \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
745 \end{tabu} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
746 \end{center} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
747 \end{example} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
748 \end{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
749 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
750 \begin{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
751 \frametitle{Äquivalente Formeln} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
752 \setbeamercovered{dynamic} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
753 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
754 \begin{definition}[Äquivalente Formeln] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
755 Man nennt zwei Formeln \structure{äquivalent}, wenn sie dieselbe Semantik besitzen.\\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
756 Seien $F, G$ Formeln mit Belegungen $\mathcal{B} = \mathcal{B}_F = \mathcal{B}_G$. $F$ und $G$ sind äquivalent wenn |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
757 \[ \forall \beta \in \mathcal{B}. [F](\beta) = [G](\beta) \] |
16
b83150706135
use consistent implication arrow
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
758 Man schreibt \structure{$F \equiv G$} oder \structure{$F \leftrightarrow G$}. |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
759 \end{definition} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
760 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
761 \begin{example}[] |
16
b83150706135
use consistent implication arrow
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
15
diff
changeset
|
762 Für $F \defeq a \rightarrow b$ und $G \defeq \neg a \vee b$ gilt $F \equiv G$. |
12
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
763 \begin{center} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
764 \begin{tabu} to .4\textwidth {cc|[1.2pt]XcX||Xccc} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
765 a & b & & $a \Rightarrow b$ & & & $\neg a$ & $\vee$ & $b$ \\ \tabucline[1.2pt]{-} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
766 0 & 0 & & \structure{1} & & & 1 & \structure{1} \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
767 0 & 1 & & \structure{1} & & & 1 & \structure{1} \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
768 1 & 0 & & \structure{0} & & & 0 & \structure{0} \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
769 1 & 1 & & \structure{1} & & & 0 & \structure{1} \\ |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
770 \end{tabu} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
771 \end{center} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
772 \end{example} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
773 \end{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
774 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
775 \begin{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
776 \frametitle{Eigenschaften von Formeln} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
777 \setbeamercovered{dynamic} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
778 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
779 \begin{block}{Eigenschaften aussagenlogischer Formeln} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
780 Sei $F$ eine aussagenlogische Formel mit Variablen $V$ und der Menge der passenden Belegungen $\mathcal{B}$. Man nennt F |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
781 \begin{description}[\quad unerfüllbar] |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
782 \item[erfüllbar] $\exists \beta \in \mathcal{B}. [F](\beta) = 1$\hfill($F$ kann wahr sein) |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
783 \item[unerfüllbar] $\forall \beta \in \mathcal{B}. [F](\beta) = 0$\hfill($F$ ist nie wahr) |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
784 \item[gültig] $\forall \beta \in \mathcal{B}. [F](\beta) = 1$\hfill($F$ ist immer wahr) |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
785 \end{description} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
786 \end{block} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
787 \begin{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
788 \item Eine unerfüllbare Formel nennt man \structure{Widerspruch} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
789 \item Eine gültige Formel nennt man \structure{Tautologie} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
790 \end{itemize} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
791 |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
792 \end{frame} |
c903f55b68de
third slides and sheet
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
793 } |