# HG changeset patch # User Markus Kaiser # Date 1382995462 -3600 # Node ID 4d05c4d352cadcc811588cd98bf77d7021acb6be # Parent 854a7228871da9c47498a8143395ed13bff8aa97 second slides diff -r 854a7228871d -r 4d05c4d352ca notes/tex/basics.tex --- a/notes/tex/basics.tex Tue Oct 22 00:24:27 2013 +0200 +++ b/notes/tex/basics.tex Mon Oct 28 22:24:22 2013 +0100 @@ -199,7 +199,7 @@ \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} & + \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} @@ -232,7 +232,7 @@ \begin{example}[] Für $M = \left\{ a, b, c \right\}$ ist - \[ \powerset{M} = \left\{ + \[ \powerset{M} = \left\{ \emptyset, \left\{ a \right\}, \left\{ b \right\}, @@ -302,3 +302,277 @@ \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} +} diff -r 854a7228871d -r 4d05c4d352ca notes/tex/preamble.tex --- a/notes/tex/preamble.tex Tue Oct 22 00:24:27 2013 +0200 +++ b/notes/tex/preamble.tex Mon Oct 28 22:24:22 2013 +0100 @@ -7,6 +7,7 @@ \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} +\usepackage{mathpazo} \usepackage{helvet} \usepackage{microtype} @@ -15,12 +16,14 @@ \usepackage{xcolor} \usepackage{tikz} \usepackage{pgfplots} +\pgfplotsset{compat=1.8} \usetikzlibrary{automata} \usetikzlibrary{calc} \usetikzlibrary{shapes} \usetikzlibrary{positioning} \usetikzlibrary{chains} +\usepackage{amsmath} \usepackage{mathdots} \usepackage{mathtools} \mathtoolsset{showonlyrefs} @@ -41,4 +44,14 @@ \newcommand{\powerset}[1]{\mathcal{P}\left( #1 \right)} \newcommand{\setnot}[1]{\overline{#1}} \newcommand{\setsymdiff}{\,\triangle\,} + +\newcommand{\rel}[1]{\,\mathrm{#1}\,} + \newcommand{\defeq}{\mathrel{\vcenter{\baselineskip0.5ex\lineskiplimit0pt\hbox{\scriptsize.}\hbox{\scriptsize.}}}=} + +\tikzstyle{edge} = [draw,very thick,->,>=latex] +\tikzstyle{pretty} = [circle,thick,draw,fill=tumblue!10] +\tikzstyle{every edge} = [edge] +\tikzstyle{every state} = [pretty] +\tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] +\tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE] diff -r 854a7228871d -r 4d05c4d352ca notes/tex/ue02_notes.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue02_notes.tex Mon Oct 28 22:24:22 2013 +0100 @@ -0,0 +1,12 @@ +\input{preamble.tex} +\input{frames.tex} + +\title{Übung 2: Relationen und Abbildungen} +\subtitle{Diskrete Strukturen im Wintersemester 2013/2014} +\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} + +\begin{document} +\showUnit{titel} +\showUnit{relationen} +\showUnit{funktionen} +\end{document}