\documentclass{uebungsblatt}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Diskrete Strukturen}
\blatt{3}
\gruppe{11}

\begin{document}

\aufgabe

\teilaufgabe

\begin{flalign*}
G & = F \cap (A \cup B) & \text{Angabe} \\
G & = (E \cup (A \setminus C)) \cap (A \cup B) & \text{F einsetzen} \\
G & = ((D \cap (A \cup B)) \cup (A \setminus C)) \cap (A \cup B) & \text{E einsetzen} \\
G & = (((B \cap (A \cup C)) \cap (A \cap B)) \cup (A \setminus C)) \cap (A \cup B) & \text{D einsetzen} \\
G & = ((B \cap B \cap A \cap (A \cup C)) \cup (A \setminus C)) \cap (A \cup B) & \text{Assoziativität, Kommutivität} \\
G & = ((B \cap A \cap (A \cup C)) \cup (A \setminus C)) \cap (A \cup B) & \text{Idempotenz von } B \cap B \\
G & = ((B \cap A) \cup (A \setminus C)) \cap (A \cup B) & \text{Absorption} \\
G & = (A \cap B) \cup (A \setminus C) \cap (A \cup B) & \text{Kommutivität} \\
G & = (A \cap B) \cap (A \cup B) \cup (A \setminus C) & \text{Kommutivität} \\
G & = (A \cup B) \cap (A \setminus C)
\end{flalign*}

\teilaufgabe

\begin{flalign*}
A & = \{x, b, 35, x\} = \{x, b, 35\} & \\
B & = \{x, b, 2, 3, \delta, x\} = \{x, b, 2, 3, \delta\} \\
C & = \{\alpha, 2, 3, \epsilon\} \\
D & = B \cap (A \cup C) = \{x, b, 2, 3, \delta\} \cap (\{x, b, 35\} \cup \{\alpha, 2, 3, \epsilon\} =\\
 & = \{x, b, 2, 3, \delta\} \cap \{x, b, 35, \alpha, 2, 3, \epsilon\} = \{x, b, 2, 3\} \\
E & = D \cap (A \cap B) = \{x, b, 2, 3\} \cap (\{x, b, 35\} \cap \{x, b, 2, 3, \delta\}) =\\
 & = \{x, b, 2, 3\} \cap \{x, b\} \\
F & = F \cup (A \setminus C) = \{x, b\} \cup (\{x, b, 35\} \setminus \{\alpha, 2, 3, \epsilon\}) =\\
 & = \{x, b\} \cup \{x, b, 35\} = \{x, b, 35\} \\
G & = F \cap (A \cup B) = \{x, b, 35\} \cap (\{x, b, 35\} \cup \{x, b, 2, 3, \delta\}) =\\
 & = \{x, b, 35\} \cap \{x, b, 35, 2, 3, \delta\} = \{x, b, 35\}
\end{flalign*}

\aufgabe

\teilaufgabe

\begin{multline*}
P(A) = \{ \emptyset, \{y\}, \{x\}, \{x, y\}, \{w\} \{x, y\}, \{w, x\}, \{w, x, y\}, \{v\}, \{v, y\}, \{v, x\}, \{v, x, y\}, \{v, w\},\\
\{v, w, y\}, \{v, w, x\}, \{v, w, x, y\}, \{u\}, \{u, y\}, \{u, x\}, \{u, x, y\}, \{u, w\} \{u, w, y\}, \{u, w, x\}, \{u, w, x, y\},\\
\{u, v\}, \{u, v, y\}, \{u, v, x\}, \{u, v, x, y\}, \{u, v, w\}, \{u, v, w, y\}, \{u, v, w, x\}, \{u, v, w, x, y\} \}
\end{multline*}

$ |P(A)| = 2^{|A|} = 2^5 = 32 $

Der Zusammenhang besteht darin, dass die Menge $ \{ u, v, w, x, y \} $ jeweils durch 0 und 1 repräsentiert werden können, wobei
1 für ``Im Element der Potenzmenge vorhanden'' angesehen werden kann und 0 ``nicht im Element der Potenzmenge vorhanden''
repräsentiert. Somit hat jedes dieser Elemente zwei Möglichkeiten und es existieren fünf Elemente, also $2^5$. Dies bildet die
Zustände $00000_2$ ($\emptyset$) bis $11111_2$ ($ \{u, v, w, x, y \}$) ab.

\teilaufgabe

\begin{multline*}
P(A) = \{ \emptyset, \{c\}, \{\{a, b\}\}, \{\{a, b\}, c\}, \{a\}, \{a, c\}, \{a, \{a, b\}\}, \{a, \{a, b\}, c\}, \{1\}, \{1, c\},\\
\{1, \{a, b\}\}, \{1, \{a, b\}, c\}, \{1, a\}, \{1, a, c\}, \{1, a, \{a, b\}\}, \{1, a, \{a, b\}, c\} \}
\end{multline*}

$ |P(P(A))| = 2^{|P(A)|} = 2^{16} = 65536 $

\aufgabe

\teilaufgabe

\begin{flalign*}
A & = \{1, 2, 3\} &\\
B & = \{a, b, c, d\} \\
A \times B & = \{ (1, a), (1, b), (1, c), (1, d), (2, a), (2, b), (2, c), (2, d), (3, a), (3, b), (3, c), (3, d) \}
\end{flalign*}

\teilaufgabe

\begin{flalign*}
|A \times B| & = 12\\
|B \times A| & = 12\\
|(A \times B) \times (B \times A)| & = 12 \times 12 = 144
\end{flalign*}

\aufgabe

$ M = \{1, 2, 3\} $

\teilaufgabe

\begin{flalign}
R_1 & = \{ (2, 3), (3, 2), (1, 1) \}\\
R_2 & = \{ (1, 2), (2, 3), (3, 3), (3, 2) \}\\
R_3 & = \{ (1, 3), (2, 3), (1, 1), (2, 2), (3, 3) \}
\end{flalign}

\begin{enumerate}[1]
  \item 
    \begin{itemize}
      \item nichtreflexiv, da $ (2, 2) \not\in R_1 $
      \item symmetrisch, da für jedes $ x, y \in R_1 (x, y) \wedge (y, x) \in R_1 $
      \item nichtantisymmetrisch, da obwohl $ (2, 3) \in R_1 \wedge (3, 2) \in R_1 $
        $ 2 \neq 3 $
      \item nichttransitiv da $ (1, 1) \wedge (2, 3) $ nicht transitiv
    \end{itemize}
    $ R_1 $ ist eine Abbildung, da das Urbild $ \{ 1, 2, 3 \} $ ist und jedes
    $ x \in $ Urbild einem Element aus $ y \in \{ 1, 2, 3 \} $, dem Bild zugeordnet
    wird.
  \item
    \begin{itemize}
      \item nichtreflexiv, da $ (1, 1) \not\in R_2 $
      \item nichtsymmetrisch, da $ (1, 2) \in R_2 $ aber $ (2, 1) \not\in R_2 $
      \item nichtantisymmetrisch, da $ (2, 3) \in R_2 \wedge (3, 2) \in R_2 $ aber
        $ 2 \neq 3 $
      \item transitiv, da für jedes $ x, y, z $ gilt, dass wenn $ (x, y) \in R_2 $ 
        dann auch $ (y, z) \in R_2 $
    \end{itemize}
    $ R_2 $ ist keine Abbildung, da das Element 3 des Urbildes $ \{ 1, 2, 3 \} $
    auf die Elemente 2 und 3 des Bildes $ \{ 2, 3 \} $ abgebildet wird.
  \item 
    \begin{itemize}
      \item reflexiv, da für jedes $ x \in $ Urbild gilt, dass $ (x, x) \in R_3 $
      \item nichtsymmetrisch, da $ (2, 3) \in R_3 $ aber $ (3, 2) \not\in R_3 $
      \item antisymmetrisch, da nicht gilt, dass für beliebige Elemente $ x, y \in M $
       gilt dass $ (x, y) \in R_3 \wedge (y, x) \in R_3 $ mit der Ausnahme dass
       $ x = y $ wie etwa in $ (1, 1) \in R_3 $
      \item transitiv, da für jedes $ x, y, z $ gilt, dass wenn $ (x, y) \in R_3 $ 
        dann auch $ (y, z) \in R_3 $
    \end{itemize}
    $ R_3 $ ist keine Abbildung, da das Element 1 des Urbildes $ \{ 1, 2, 3 \} $
    auf die Elemente 1 und 3 des Bildes $ \{1, 2, 3 \} $ abgebildet wird.
\end{enumerate}

\teilaufgabe

\begin{flalign*}
R_1 \circ R_2 & = \{ (2, 3), (2, 2), (3, 3), (1, 2) \}\\
R_2^* & = \{ (1, 2), (2, 3), (3, 3), (3, 2), (1, 1), (2, 2) \}\\
R_3^* &=  \{ (1, 3), (2, 3), (1, 1), (2, 2), (3, 3), (3, 2), (1, 2) \}
\end{flalign*}

\end{document}