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

comparison notes/tex/basics.tex @ 6:4d05c4d352ca

second slides

author	Markus Kaiser <markus.kaiser@in.tum.de>
date	Mon, 28 Oct 2013 22:24:22 +0100
parents	fac222767cda
children	c2d858c9c53e

comparison

equal deleted inserted replaced

-:854a7228871d
+:4d05c4d352ca
 \begin{theorem}[De Morgansche Gesetze]
 Sind $A, B$ Mengen, dann gilt
 \begin{alignat}{2}
 \setnot{A \cup B} &= \setnot{A} \cap \setnot{B} \qquad\qquad& \setnot{A \cap B} &= \setnot{A} \cup \setnot{B}\\
 \intertext{Für Mengen $A_i$ gilt}
 \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} &
 \end{alignat}
 \end{theorem}
 \vfill
 \vfill
 \begin{example}[]
 Für $M = \left\{ a, b, c \right\}$ ist
 \[ \powerset{M} = \left\{
 \emptyset,
 \left\{ a \right\},
 \left\{ b \right\},
 \left\{ c \right\},
 \left\{ a, b \right\},
 \item $\left\{ \alpha, \beta \right\}^2 = \left\{ (\alpha, \alpha), (\alpha, \beta), (\beta, \alpha), (\beta, \beta) \right\}$
 \end{itemize}
 \end{example}
 \end{frame}
 }
+\defineUnit{relationen}{%
+\begin{frame}
+\frametitle{Relation}
+\setbeamercovered{dynamic}
+\begin{definition}[Relation]
+Eine binäre \structure{Relation} $R$ verbindet Elemente zweier Mengen $A$ und $B$.
+\[ R \subseteq A \times B\]
+Ist $(a, b) \in R$, so schreibt man auch \structure{$a\rel{R}b$}.
+\end{definition}
+\begin{itemize}
+\item Eine Relation über $M \times M$ nennt man homogen
+\item Es gibt $\abs{\powerset{A \times B}}$ Relationen über $A, B$
+\end{itemize}
+\begin{example}[]
+\begin{itemize}
+\item Die \alert{Gleichheitsrelation} über $\N \times \N$ \\
+$\left\{ (1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7) \ldots \right\}$
+\medskip
+\item Die \alert{Teilbarkeitsrelation} über $\N$ \\
+$\left\{ (1,1), (1,2), (1,3), \ldots, (2,2), (2,4), \ldots, (3,3), (3,6), \ldots \right\}$
+\end{itemize}
+\end{example}
+\end{frame}
+\begin{frame}
+\frametitle{Grafische Darstellung}
+\setbeamercovered{dynamic}
+\begin{block}{Grafische Darstellung von Relationen}
+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.
+\end{block}
+\begin{example}[]
+Sei $R \subseteq [4] \times [4]$ eine Relation über den natürlichen Zahlen.
+\[ R \defeq \left\{ (1, 1), (1, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 3) \right\}\]
+\end{example}
+\centering
+\begin{tikzpicture}[x=5em, y=2.5em]
+\path   (0, 0) node[pretty] (1) {$1$}
++(1, 0) node[pretty] (2) {$2$}
++(2, 1) node[pretty] (3) {$3$}
++(2, -1) node[pretty] (4) {$4$};
+\path[edge]
+(1) edge[loop left] (1)
+(1) edge (2)
+(2) edge (3)
+(2) edge (4)
+(3) edge[loop above] (3)
+(3) edge[bend left] (4)
+(4) edge[bend left] (3);
+\end{tikzpicture}
+\end{frame}
+\begin{frame}
+\frametitle{Eigenschaften von Relationen}
+\setbeamercovered{dynamic}
+\begin{block}{Eigenschaften homogener Relationen}
+Sei $R \in M \times M$ eine homogene Relation. Man nennt $R$
+\begin{description}[antisymmetrisch]
+\item[reflexiv] $ \forall a\hphantom{, b, c} \in M.\ (a, a) \in R$
+\item[total] $ \forall a, b\hphantom{, c} \in M.\  (a, b) \in R \vee (b, a) \in R$
+\medskip
+\item[symmetrisch] $ \forall a, b\hphantom{, c} \in M.\  (a, b) \in R \hphantom{{}\wedge (b, a) \in R}\Rightarrow (b,a ) \in R$
+\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$
+\item[antisymmetrisch] $ \forall a, b\hphantom{, c} \in M.\  (a, b) \in R \wedge (b, a) \in R \Rightarrow a \equiv b$
+\medskip
+\item[transitiv] $ \forall a, b, c \in M.\  (a, b) \in R \wedge (b, c) \in R \Rightarrow (a, c) \in R$
+\end{description}
+\end{block}
+\vfill
+\begin{itemize}
+\item Jede totale Relation ist reflexiv
+\item Jede asymmetrische Relation ist antisymmetrisch
+\item \structure{Äquivalenzrelationen} sind reflexiv, symmetrisch und transitiv
+\item $R^+$ ist die \structure{transitive Hülle}, $R^*$ die \structure{reflexive transitive Hülle}
+\end{itemize}
+\end{frame}
+}
+\defineUnit{funktionen}{%
+\begin{frame}
+\frametitle{Funktion}
+\setbeamercovered{dynamic}
+\begin{definition}[Funktion]
+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.
+\[ \forall a \in A. \abs{\left\{ (a, b) \mid b \in B \right\}} \alert{=} 1 \]
+Man schreibt
+\begin{align}
+f : A &\to B \\
+a &\mapsto f(a) = b
+\end{align}
+\structure{$A \to B$} bezeichnet die Menge aller Funktionen von $A$ nach $B$.
+\end{definition}
+\vfill
+\centering
+{
+\tikzstyle{set} = [draw, thick, tumgreen, fill=tumgreen!15]
+\tikzstyle{element} = [thick]
+\tikzstyle{arrow} = [thick, tumblue, shorten >=-.4em, shorten <=-.4em]
+\begin{tikzpicture}[x=1.5em, y=1.5em]
+\draw[set] (0, 0) ellipse (1 and 2);
+\draw[set] (5, 0) ellipse (1 and 2);
+\path[element]
+(0,0)
++(0, 1.5) node (a1) {$\times$}
++(0.2, 0.85) node (a2) {$\times$}
++(0.1, -0.6) node (a4) {$\times$}
++(-0.1, -1.5) node (a5) {$\times$};
+\path[element]
+(5,0)
++(0, 1.5) node (b1) {$\times$}
++(0.2, 0.85) node (b2) {$\times$}
++(-0.3, 0.0) node (b3) {$\times$}
++(0.1, -0.6) node (b4) {$\times$}
++(-0.1, -1.5) node (b5) {$\times$};
+\path[arrow]
+(a1) edge (b1)
+(a2) edge (b5)
+(a4) edge (b2)
+(a5) edge (b5);
+\path
+(0, -2.5) node {$A$}
+(5, -2.5) node {$B$}
+(2.5, -2.5) node {$f$};
+\end{tikzpicture}
+}
+\end{frame}
+\begin{frame}
+\frametitle{Bild und Urbild}
+\setbeamercovered{dynamic}
+\begin{definition}[Bild]
+Sei $f : A \to B$ eine Funktion, $X \subseteq A$, $Y \subseteq B$, $b \in B$. Dann ist
+\begin{align}
+f(X) &\defeq \left\{ f(x) \mid x \in X \right\} \\
+\intertext{das \structure{Bild} der Menge $X$ unter $f$. Außerdem ist}
+f^{-1}(b) &\defeq \left\{ a \mid a \in A, f(a) = b \right\} \\
+f^{-1}(Y) &\defeq \bigcup_{y \in Y} \left\{ f^{-1}(y) \right\}
+\end{align}
+das \structure{Urbild} des Elements $b$ und der Menge $Y$ unter $f$.
+\end{definition}
+\vfill
+\begin{itemize}
+\item Man nennt $A = f^{-1}(B)$ \structure{Urbild} oder \structure{Definitionsmenge} von $f$
+\item Man nennt $f(A) \subseteq B$ \structure{Bild} oder \structure{Wertemenge} von $f$
+\end{itemize}
+\end{frame}
+\begin{frame}
+\frametitle{Komposition}
+\setbeamercovered{dynamic}
+\begin{definition}[Funktionskomposition]
+Seien $f : B \to C$ und $g : A \to B$ Funktionen. Dann ist
+\begin{align}
+h : A &\to C \\
+a &\mapsto (f \circ g)(a) = f(g(a))
+\end{align}
+die \structure{Komposition} der Funktionen $f$ und $g$.\\
+Man ließt $f \circ g$ als \enquote{f \structure{nach} g}.
+\end{definition}
+\vfill
+Man definiert die Potenzierung von Funktionen ähnlich der Mengentheorie.
+\begin{align}
+f^0 &\defeq id\\
+f^n &\defeq \underbracket[0.5pt]{f \circ \ldots \circ f}_{\text{n mal}}
+\end{align}
+Dabei bezeichnet $id$ die \structure{Identität} mit $id(x) \defeq x$.
+\end{frame}
+\begin{frame}
+\frametitle{Eigenschaften von Funktionen}
+\setbeamercovered{dynamic}
+\begin{block}{Eigenschaften von Funktionen}
+Sei $f: A \to B$ eine Funktion. Man nennt $f$
+\begin{description}[surjektiv]
+\item[injektiv] $\forall b \in B. \abs{f^{-1}(b)} \leq 1$ \hfill(Kein $b$ wird doppelt getroffen)
+\item[surjektiv] $\forall b \in B. \abs{f^{-1}(b)} \geq 1$\hfill(Jedes $b$ wird getroffen)
+\item[bijektiv] $\forall b \in B. \abs{f^{-1}(b)} = 1$\hfill(Jedes $b$ wird genau einmal getroffen)
+\end{description}
+\end{block}
+\vfill
+\centering
+{
+\tikzstyle{set} = [draw, thick, tumgreen, fill=tumgreen!15]
+\tikzstyle{element} = [thick]
+\tikzstyle{head} = [draw, fill=tumblue!15, thick]
+\tikzstyle{arrow} = [thick, tumblue, shorten >=-.4em, shorten <=-.4em]
+\newcommand{\function}[3]{%
+\draw[set] (0, 0) ellipse (1 and 2);
+\draw[set] (4, 0) ellipse (1 and 2);
+\path[element]
+(0,0)
++(0, 1.5) node (a1) {$\times$}
++(0.2, 0.85) node (a2) {$\times$}
++(0.1, 0.3) node (a3) {$\times$}
++(-0.1, -0.1) node (a4) {$\times$}
++(-0.2, -0.7) node (a5) {#2}
++(-0.1, -1.5) node (a6) {#3};
+\path[element]
+(4,0)
++(0, 1.5) node (b1) {$\times$}
++(0.2, 0.85) node (b2) {$\times$}
++(-0.3, 0.0) node (b3) {$\times$}
++(0.1, -0.6) node (b4) {$\times$}
++(-0.1, -1.5) node (b5) {$\times$};
+\path
+(0, -2.5) node {$A$}
+(4, -2.5) node {$B$}
+(2, -2.5) node {$f$}
+(2, 3) node[head] {#1};
+}
+\begin{tikzpicture}[x=1.5em, y=1.5em]
+\function{Injektiv}{}{}
+\path[arrow]
+(a1) edge (b1)
+(a2) edge (b3)
+(a3) edge (b2)
+(a4) edge (b4);
+\end{tikzpicture}
+\hfill
+\begin{tikzpicture}[x=1.5em, y=1.5em]
+\function{Surjektiv}{$\times$}{$\times$}
+\path[arrow]
+(a1) edge (b1)
+(a2) edge (b3)
+(a3) edge (b2)
+(a4) edge (b4)
+(a5) edge (b5)
+(a6) edge (b5);
+\end{tikzpicture}
+\hfill
+\begin{tikzpicture}[x=1.5em, y=1.5em]
+\function{Bijektiv}{}{$\times$}
+\path[arrow]
+(a1) edge (b1)
+(a2) edge (b3)
+(a3) edge (b2)
+(a4) edge (b4)
+(a6) edge (b5);
+\end{tikzpicture}
+}
+\end{frame}
+}

Mercurial > 13ws.ds

comparison notes/tex/basics.tex @ 6:4d05c4d352ca