\documentclass[12pt,a4paper]{article}
\usepackage{german}
\usepackage[latin1]{inputenc}
\usepackage[dvips]{epsfig}
\usepackage{fancyhdr}
\usepackage{amstext,amssymb}
\pagestyle{fancy}
\textwidth17cm
\textheight23.7cm
\headwidth17cm
\topmargin-0.8cm
\headheight12pt
\headsep36pt
\oddsidemargin-0.5cm
\footskip1.5cm
\parskip6pt
\parindent0pt

\begin{document}

\lhead{SS 2000 Theoretische Informatik 2}
\chead{Blatt 1}
\rhead{Seite \thepage}

\lfoot{}
\cfoot{}
\rfoot{}

\section*{Aufgabe 1}
\subsection*{a)}
Gegeben: algebraische Strukturen $\langle M_1,\circ_1 \rangle$,
$\langle M_2, \circ_2 \rangle$. Homomorphismus $h: M_1 \to M_2$.
$\langle M_2, \circ_2\rangle$ assoziativ, $h$ injektiv.

Zu zeigen: $\langle M_1, \circ_1\rangle$ ist assoziativ, d.h. $\forall
a_n \in M_1: a_1 \circ_1(a_2\circ_1a_3)=(a_1\circ_1a_2)\circ_1a_3$.

Seien $a_1,a_2,a_3 \in M_1$. Dann gilt:

\begin{eqnarray*}
h(a_1 \circ_1(a_2 \circ_1 a_3))&=&h(a_1)\circ_2 h(a_2 \circ_1 a_3)\\
&=&h(a_1) \circ_2(h(a_2)\circ_2 h(a_3))\\ 
&=&(h(a_1)\circ_2 h(a_2))\circ_2 h(a_3)\\ 
&=&h((a_1 \circ_1 a_2)\circ_1 a_3)\\ 
&=&h((a_1 \circ_1 a_2)\circ_1 a_3)\\
\end{eqnarray*}

Es gilt $h(a_1 \circ_1 (a_2\circ_1 a_3)=h((a_1 \circ_1 a_2)\circ_1
a_3)$. Da $h$ injektiv ist, folgt:

$$a_1\circ_1(a_2 \circ_1 a_3) = (a_1 \circ_1 a_2)\circ_1 a_3~~\Box $$

\subsection*{b)}
Gegeben: algebraische Strukturen $\langle M_1,\circ_1\rangle$,
$\langle M_2,\circ_2\rangle$, Homomorphismus $h: M_1 \to M_2$,
$\langle M_1,\circ_1\rangle$ assoziativ, $h$ surjektiv.

Zu zeigen: $\langle M_2,\circ_2\rangle$ assoziativ, d.h. $\forall
b_{1,2,3} \in M_2: b_1 \circ_2(b_2 \circ_2 b_3)=(b_1 \circ_2
b_2)\circ_2 b_3$.

Seien $b_1,b_2,b_3 \in M_2$. Dann gibt es, da $h$ surjektiv ist, $a_1,
a_2, a_3 \in M_1$, so daß $h(a_1)=b_1$, $h(a_2)=b_2$, $h(a_3)=b_3$.

Es gilt:

\begin{eqnarray*}
b_1 \circ_2 (b_2 \circ_2 b_3)&=&h(a_1) \circ_2 (h(a_2)\circ_2 h(a_3))\\
&=& h(a_1)\circ_2(h(a_2 \circ_1 a_3))\\
&=& h(a_1 \circ_1 (a_2 \circ_1 a_3))\\
&=& h((a_1 \circ_1 a_2)\circ_1 a_3)\\
&=& h(a_1 \circ_1 a_2)\circ_2 h(a_3)\\
&=& (h(a_1)\circ_2 h(a_2))\circ_2 h(a_3)\\
&=& (b_1 \circ_2 b_2)\circ_2 b_3~~\Box
\end{eqnarray*}

\section*{Aufgabe 2}
\subsection*{a), b)}

Gegeben: Abbildung $h: \Sigma \to \Delta^*$. Zu zeigen: Es gibt genau
einen Homomorphismus $\tilde{h}: \Sigma^* \to \Delta^*$ mit
$\tilde{h}(a) =h(a) \forall a \in \Sigma$. Gezeigt werden müssen
Existenz und Eindeutigkeit.

{\bfseries Existenz:} Man definiere $\tilde{h}: \Sigma^* \to \Delta^*$
durch $\tilde{h}(w)=h(a_1)\cdot h(a_2) \cdot \dots \cdot h(a_n)$ für
$v=a_1a_2 \dots a_n$, $a_i \in \Sigma$, $1 \le i \le n$. 

$\Rightarrow \tilde{h}$ ist eine Abbildung $\Sigma^* \to
\Delta^*~~\checkmark$

$\Rightarrow \tilde{h}$ ist ein Homomorphismus. Für alle $u, v \in
\Sigma^*$ gilt $h(uv)=h(u)\cdot h(v), u=a_1 \dots a_m, v = b_1 \dots
b_m, a_i \in \Sigma, 1 \le i \le m, b_i \in \Sigma, 1 \le i \le
m$. $\tilde{h}(uv) =(h(a_1) \dots h(a_n))(h(b_1) \dots h(b_n)) =
\tilde{h}(u)\cdot \tilde{h}(v)~~\Box$

{\bfseries Eindeutigkeit:} Seien $\overline{h},\tilde{h}: \Sigma^* \to
\Delta^*$ Homomorphismen mit $\overline{h}(a)=\tilde{h}(a) = h(a)
\forall a \in \Sigma$. Sei $w = a_1a_2\dots a_n \in \Sigma$ beliebig.

\begin{eqnarray*}
\tilde{h}(w)&=&\tilde{h}(a_1)\cdot \dots \cdot \tilde{h}(a_n)\\
&=&h(a_1)\cdot \dots \cdot h(a_n)\\
&=&\overline{h}(a_1) \cdot \dots \cdot \overline{h}(a_n)\\
&=&\overline{h}(w)\\
&\Rightarrow&\tilde{h}=\overline{h}~~\Box
\end{eqnarray*}

\section*{Aufgabe 3}
Gegeben: Menge $A$, Relation $R \subset A \times A,~R$
transitiv. Beweise oder widerlege:

\subsection*{a)}
$R_1:(a,b)\in R_1 \stackrel{\text{def}}{\Leftrightarrow} (a,b) \in R
\wedge (b,a) \in R$ ist eine Äquivalenzrelation.

Diese Aussage ist \emph{falsch}. Beweis durch Gegenbeispiel:

\begin{eqnarray*}
&& A=\{1,2,3\}\\
&& R=\{(1,2),(2,3),(1,3)\}\\
&& R_1=\emptyset~\rightarrow~\text{nicht reflexiv!}
\end{eqnarray*}

\subsection*{b)}
$R_2:(a,b)\in R_2 \stackrel{\text{def}}{\Leftrightarrow}(((a,b)\in R
  \wedge (b,a)\in R)\vee(a=b))$~ist eine Äquivalenzrelation.

Diese Aussage ist \emph{wahr}. Zu zeigen: $R_2$ ist reflexiv,
transitiv, symmetrisch.

\begin{itemize}
  \item Reflexivität: $\checkmark$
  \item Transitivität: Seien $(a,b) \in R_2$ und $(b,c) \in
    R_2$.\\
    $(a,b) \in R_2 \Leftrightarrow ((a,b)\in R \wedge (b,a)\in R) \vee
    a=b$\\
    $(b,c) \in R_2 \Leftrightarrow ((b,c)\in R \wedge (c,b)\in R) \vee
    b=c$

    {\bfseries Fallunterscheidung:}
    \begin{itemize}
      \item $a=b$

        $(b,c)\in R_2 \Rightarrow (a,c) \in R_2~~\checkmark$
      \item $b=c$

        $(a,b)\in R_2 \Rightarrow (a,c)\in R_2~~\checkmark$
      \item $a\neq b \wedge b \neq 0$
        \begin{eqnarray*}
          (a,b)\in R_2 \wedge (b,c)\in R_2 &\Rightarrow& (a,b)\in R
          \wedge (b,a)\in R \wedge (b,c)\in R \wedge (c,b) \in R\\
          &\Rightarrow& (a,c)\in R \wedge (c,a)\in R \\
          &\Rightarrow& (a,c)\in R_2~~\checkmark\\ \\
          (a,b)\in R_2 &\Leftrightarrow& ((a,b)\in R \wedge (b,a) \in
          R) \vee a=b\\
          &\Leftrightarrow&((b,a)\in R \wedge (a,b)\in R) \vee b=a\\
          &\Leftrightarrow& (b,a)\in R_2~~\checkmark
        \end{eqnarray*}
    \end{itemize}
  \item Symmetrie: $\checkmark$
\end{itemize}

\subsection*{c)}
$R_3:(a,b)\in R_3 \stackrel{\text{def}}{\Leftrightarrow}(a,b)\in R
  \vee (b,a)\in R$~ist eine Äquivalenzrelation.

Diese Aussage ist \emph{falsch}. Beweis durch Gegenbeispiel:

\begin{eqnarray*}
&& A=\{1,2\}\\
&& R=\{(1,2)\}\\
&& R_3=\{(1,2),(2,1)\}~\rightarrow~\text{nicht reflexiv!}
\end{eqnarray*}

\subsection*{d)}
$R_4:(a,b)\in R_4 \stackrel{\text{def}}{\Leftrightarrow}((a,b)\in R
  \vee (b,a)\in R)\vee (a=b)$~ist eine Äquivalenzrelation.

Diese Aussage ist \emph{falsch}. Beweis durch Gegenbeispiel:

\begin{eqnarray*}
&& A=\{1,2,3\}\\
&& R=\{(1,2),(3,2)\}\\
&& R_4=\{(1,2),(2,1),(2,3),(3,2),(1,1),(2,2),(3,3)\}\\
&& (1,2) \in R_4,~(2,3) \in R_4,~\text{aber}~(1,3) \notin R_4
~\rightarrow R_4~\text{nicht transitiv!}
\end{eqnarray*}

\section*{Aufgabe 4}

Gegeben: Monoid $\langle M_1, \circ_1\rangle$, algebraische Struktur
$\langle M_2, \circ_2\rangle$, Homomorphismus $h: M_1 \rightarrow
M_2$.
\subsection*{a)}
Zu zeigen: $\langle h(M_1),\circ_2\rangle$ ist ein Monoid
$\rightarrow$ algebraische Struktur, assoziativ, neutrales Element.

\begin{itemize}
\item {\bfseries algebraische Struktur}

  Sei $b_1, b_2 \in h(M_1) \Rightarrow$ es gibt $a_1, a_2 \in M_1$ mit
  $h(a_1)=b_1,h(a_2)=b_2$. Ferner gilt $b_1 \circ_2 b_2 =
  h(a_1)\circ_2 h(a_2)=h(a_1 \circ_1 a_2)$. Wegen $a_1 \circ_1 a_2 \in
  M_1$ ist $h(a_1 \circ_1 a_2) \in h(M_1)~~\checkmark$

\item {\bfseries Assoziativität}$~~\checkmark$
\item {\bfseries Existenz des neutralen Elementes}
  
  $\langle M_1,\circ_1\rangle$ ist ein Monoid $\Rightarrow$ es gibt
  ein neutrales Element $\varepsilon_1 \in M_1$, so daß $a_1 \circ_1
  \varepsilon_1 = \varepsilon_1 \circ_1 a_1 = a_1$ für alle $a_1 \in M_1$.

  $h(\varepsilon_1)$ ist neutrales Element in $\langle
  h(M_1),\circ_2\rangle$. Sei $b \in h(M_1)$. Dann gibt es ein $a \in
  M_1$ mit $h(a)=b$. $a \circ_1 \varepsilon_1 = \varepsilon_1 \circ_1 a=a,
  h(a) \circ_2 h(\varepsilon_1)=h(\varepsilon_1)\circ_2 h(a) = h(a)~~\checkmark$

\end{itemize}

\subsection*{b)}
Zu zeigen: $R \subseteq M_1 \times M_1: (a,b)\in R
\stackrel{\text{def}}{\Leftrightarrow} h(a)=h(b)$ ist eine
Kongruenzrelation $\rightarrow$ reflexiv, symmetrisch, transitiv,
Kongruenzrelation.

\begin{itemize}
\item {\bfseries Reflexivität}$~~\checkmark$
\item {\bfseries Symmetrie}
  \begin{eqnarray*}
    (a,b) \in R &\Leftrightarrow& h(a)=h(b)\\
    &\Leftrightarrow& h(b)=h(a)\\
    &\Leftrightarrow& (b,a) \in R~~\checkmark
  \end{eqnarray*}
\item {\bfseries Transitivität}
  \begin{eqnarray*}
    (a,b)\in R, (b,c)\in R &\Rightarrow&h(a)=h(b)\wedge h(b)=h(c)\\
    &\Rightarrow& h(a)=h(c)\\
    &\Rightarrow& (a,c) \in R~~\checkmark
  \end{eqnarray*}
\item {\bfseries Kongruenzrelation}

  Zu zeigen: Bei $x\sim y$ gilt für beliebige $z,z' \in M_1: z \circ_1
  x \circ_1 z' \sim z \circ_1 y \circ_1 z'$.
  \begin{eqnarray*}
    h(z \circ_1 x \circ_1 z')&=&h(z)\circ_2 h(x) \circ_2 h(z')\\
    &=& h(z)\circ_2 h(y) \circ_2 h(z')\\
    &=& h(z \circ_1 y \circ_1 z')\\
    &\Rightarrow& z \circ_1 x \circ_1 z' \sim z \circ_1 y \circ_1 z'~~\checkmark
  \end{eqnarray*}
\end{itemize}

\subsection*{c)}
$[a]_R \stackrel{\text{def}}{\Leftrightarrow} \{b \in M_1 | (a \sim b)
\in R\}; M_3 = \{[a]_R | a \in M_1\}; \circ_3: [a]\circ_3 [b]
\stackrel{\text{def}}{\Leftrightarrow} [a \circ_1 b].$

Zu zeigen: $\circ_3$ ist wohldefiniert, $\langle M_3,\circ_3\rangle$
ist isomorph zu $\langle h(M_1), \circ_2\rangle$.

Seien $a_1,a_2,b_1,b_2 \in M_1$ mit $ a_1 \sim_R a_2, b_1 \sim_R b_2$.
\begin{eqnarray*}
  [a_1]\circ_3[b_1]&=&[a_1 \circ_1 b_1]\\
  &=& [a_1 \circ_1 b_2]\\
  &=& [a_2 \circ_1 b_2]\\
  &=& [a_2] \circ_3 [b_2]
\end{eqnarray*}
\end{document}