\documentclass{uebungsblatt}
\usepackage{tkz-graph}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Diskrete Strukturen}
\blatt{4}
\gruppe{11}

\begin{document}

\aufgabe

\teilaufgabe

\begin{tikzpicture}[scale=.75]

\draw[fill] (-1, 0) circle (.05cm) node[right] {$11$};
\draw[fill] (-1, 2) circle (.05cm) node[right] {$22$};
\draw (-1,0) -- (-1,2);

\draw[fill] (1, 0) circle (.05cm) node[right] {$12$};
\draw[fill] (1, 2) circle (.05cm) node[right] {$24$};
\draw (1,0) -- (1,2);

\draw[fill] (3, 0) circle (.05cm) node[right] {$13$};
\draw[fill] (3, 2) circle (.05cm) node[right] {$26$};
\draw (3,0) -- (3,2);

\draw[fill] (5, 0) circle (.05cm) node[right] {$14$};
\draw[fill] (5, 2) circle (.05cm) node[right] {$28$};
\draw (5,0) -- (5,2);

\draw[fill] (7, 0) circle (.05cm) node[right] {$15$};
\draw[fill] (7, 2) circle (.05cm) node[right] {$30$};
\draw (7,0) -- (7,2);
\end{tikzpicture}

\teilaufgabe

Urbild von $H$ ist $\{ 11, 12, 13, 14, 15 \}$, $H$ selbst enthält
laut der Definition eines Hasse-Diagrammes keine reflexiven Elemente,
und jede der Zahlen aus $M$ wird höchstens von einer anderen Zahl 
geteilt (jede Zahl in $H$ hat nur eine Kante). Nun erweitert $\N$ die
Menge $M$, aber jedes Element des Urbildes wird schon in $M$ durch
$H$ nur auf ein Element des Urbildes abgebildet, somit wird jedes
Element aus $\N$ nur von höchstens einer Kante getroffen (die Elemente
mit einer Kante sind 22, 24, 26, 28 und 30, alle anderen haben keine
Kanten).

\aufgabe

\teilaufgabe

\begin{enumerate}
  \item \emph{reflexiv}: ja, da die Bedingung für die Relation $\le$ enthält
    und somit auch gleiche Elemente auf beiden Seiten des Operators
    erlaubt sind.
  \item \emph{symmetrisch}: nein, da zwar $((5, 1), (6, 2)) \in R$ aber
    $((6, 2), (5, 1))$ die Bedingung nicht erfüllt und somit $\not\in R$
  \item \emph{antisymmetrisch}: ja, da $xRy$ und $yRx$ nur dann gleichzeitig
    zutreffen wenn $x=y$ (wird durch $\le$ bedingt).
  \item \emph{transitiv}: ja, da für jedes $((x_1, x_2), (y_1, y_2)) \wedge ((y_1, y_2), (z_1, z_2)) \in R$
    gilt, dass auch $ ((x_1, x_2), (z_1, z_2)) \in R$ ist.
  \item \emph{partielle Ordnung}: ja, da die Ordnung transitiv, reflexiv
    und antisymmetrisch ist.
  \item \emph{total}: nein, da zwar $(5, 2) \wedge (10, 1) \in M$, aber
    weder $((5, 2), (10, 1)) \in R$ noch $((10, 1), (5, 2)) \in R$.
\end{enumerate}

\teilaufgabe

Es gibt für jede nichtleere Menge mindestens ein minimales Element bezüglich einer
Relation. Da $R$ keine totale Ordnung ist kann es auch mehrere geben, im vorliegenden
Fall sind es 5 minimale Elemente, $(5, 1)$, $(4, 3)$, $(3, 5)$, $(2, 7)$ und
$(1, 10)$.

\aufgabe

\teilaufgabe

\begin{enumerate}
  \item \emph{GF}: Goethe ist Freund von Margarethe
  \item \emph{GS}: Goethe war in der Stadt
  \item \emph{GM}: Goethe hat Margarethe ermordet
  \item \emph{SS}: Schiller war in der Stadt
  \item \emph{SM}: Schiller hat Margarethe ermordet
  \item \emph{ShF}: Shakespeare ist Freund von Margarethe
  \item \emph{ShM}: Shakespeare hat Margarethe ermordet
\end{enumerate}

Im folgenden wird angenommen dass ``nicht leiden können'' gleich ``war nicht Freund''
ist und ``mit Margarethe zusammen gesehen'' zwar ``in der Stadt gewesen'' nicht aber
``Freund gewesen'' ist.

\begin{enumerate}[1]
  \item $\neg SM \Rightarrow GF \wedge \neg ShF$
  \item $\neg GM \Rightarrow \neg GF \wedge \neg GS$
  \item $\neg ShM \Rightarrow \neg GS \wedge SS$
\end{enumerate}

$(\neg SM \Rightarrow GF \wedge \neg ShF) \wedge (\neg GM \Rightarrow \neg GF \wedge \neg GS) \wedge (\neg ShM \Rightarrow \neg GS \wedge SS)$
$ \wedge ((GM \wedge \neg SM \wedge \neg ShM) \vee (\neg GM \wedge SM \wedge \neg ShM) \vee (\neg GM \wedge \neg SM \wedge Shm)) $

Nun die drei Möglichkeiten, wer der Mörder ist:

Wenn angenommen wird, dass $SM = 1$, dann sind $GM = 0$ und $ShM = 0$, somit
vereinfacht sich die Formel auf
$(1 \Rightarrow (\neg GF \wedge \neg GS)) \wedge (1 \Rightarrow (GS \wedge SS))$,
wobei aber $\neg GS$ und $GS$ nicht gleichzeitig Wahr sein können. Ist also
unmöglich.

Wenn angenommen wird, dass $ShM = 1$, dann sind $GM = 0$ und $SM = 0$, somit
vereinfacht sich die Formel auf
$(1 \Rightarrow (GF \wedge \neg ShF)) \wedge (1 \Rightarrow (\neg GF \wedge \neg GS))$,
wobei sich aber $GF$ und $\neg GF$ gegenseitig ausschließen.

Wenn angenommen wird dass $GM = 1$, dann sind $SM = 0$ und $ShM = 1$, somit
vereinfacht sich die Formel auf
$(1 \Rightarrow (GF \wedge \neg ShF)) \wedge (1 \Rightarrow (GS \wedge SS))$,
was dazu führt dass dafür eine Belegung gefunden werden kann:

\begin{enumerate}
  \item $GF = 1$
  \item $GS = 1$
  \item $GM = 1$
  \item $SS = 1$
  \item $SM = 0$
  \item $ShF = 0$
  \item $ShM = 0$
\end{enumerate}

\teilaufgabe

Wenn man davon ausgeht, dass es mehrere Mörder geben kann gibt es vier 
Möglichkeiten wer der Mörder ist.

\emph{Schiller und Goethe Mörder}: möglich, da Formel zu 
$1 \Rightarrow (GS \wedge SS) $ vereinfacht wird und dies möglich ist wenn
$GS = 1$ und $SS = 1$.

\emph{Goethe und Shakespeare Mörder}: möglich, da Formel zu 
$1 \Rightarrow (GF \wedge \neg ShF) $ vereinfacht wird und dies möglich 
ist, wenn man $GF = 1$ und $ShF = 0$ setzt.

\emph{Schiller und Shakespeare Mörder}: möglich, da Formel zu
$1 \Rightarrow (\neg GF \wedge \neg GS) $ vereinfacht wird und dies
möglich wäre wenn $GF = 0$ und $GS = 0$.

\emph{Goethe, Schiller und Shakespeare Mörder}: möglich da Formel
zu $ 1 \wedge 1 \wedge 1 = 1$ vereinfacht wird und dies bedingungslos
möglich ist.

\aufgabe

\begin{tabular}{|l|l|l|c|}
 \hline
 $A$ & $B$ & $C$ & $ \neg ((A \Rightarrow B) \wedge (A \Rightarrow C)) \wedge (A \Rightarrow C) $ \\
 \hline
 0 & 0 & 0 & 1\\
 0 & 0 & 1 & 1\\
 0 & 1 & 0 & 1\\
 0 & 1 & 1 & 1\\
 1 & 0 & 0 & 1\\
 1 & 0 & 1 & 1\\
 1 & 1 & 0 & 1\\
 1 & 1 & 1 & 1\\
 \hline
\end{tabular}

Der Ausdruck ist für jede Belegung wahr, also allgemeingültig (eine
Tautologie).

\end{document}