\documentstyle[12pt,german]{article}
\pagestyle{empty}
\setlength{\parindent}{0cm}

\begin{document}

\vfill

\centerline{\Large \bf Theoretische Informatik: Logik WS 96/97}

\vfill

\centerline{\Large "Ubung 1}

\vfill

\begin{enumerate}
	\item "Uberpr"ufen Sie folgende Strukturen daraufhin, ob sie 
	reflexive bzw. irreflexive Halbordnungen bilden!
	\begin{enumerate}
		\item $[\mbox{\bf N}^+ , \mid]$ (die Menge der von Null 
		verschiedenen nat"urlichen Zahlen
		mit der Teilbarkeitsrelation $\mid$ --- es gilt $a \mid b$ genau dann,
		wenn eine nat"urliche Zahl $k$ existiert mit $a \cdot k = b$)
		\item $[\mbox{\bf N}\times \mbox{\bf N}, \sharp]$ (die Menge der geordneten
		Paare nat"urlicher Zahlen mit
		der Relation "`$\sharp$"', die definiert ist durch: \\ $[a,b] \sharp [c,d]$
		genau dann, wenn $a > c$ {\em und} $b \leq d$ ist)
		\item $[\mbox{\bf N} \times \mbox{\bf N}, \Join]$ (die Menge der 
		geordneten Paare nat"urlicher Zahlen mit
		der Relation "`$\Join$"', die definiert ist durch: \\ 
		$[a,b] \Join [c,d]$ genau dann, wenn $a \geq c$ {\em und} $b \leq d$ 
		ist)
		\item $[\{\clubsuit,\spadesuit,\heartsuit,\diamondsuit\},\angle]$,
		wobei die folgenden Elemente in der Relation $\angle$ stehen sollen
		(und keine weiteren): $\clubsuit \angle \spadesuit$, $\spadesuit
		\angle \heartsuit$, $\clubsuit \angle \heartsuit$.
	\end{enumerate}

	\item Weisen Sie nach, da"s $[\mbox{\bf N}^+,ggT,kgV]$ ein {\em Verband} 
		  ist! Gibt es ein Nullelement? Gibt es ein Einselement?\\
		  ($ggT$ -- gr"o"ster gemeinsamer Teiler zweier Zahlen; $kgV$ -- kleinstes
		  gemeinsames Vielfaches zweier Zahlen)
	\item $(\ast)$Ist $[\mbox{\bf N}^+,ggT,kgV]$ ein {\em distributiver} Verband?
	\item Beweisen Sie die folgenden Beziehungen zwischen Mengen $M$,$N$ und $L$
		  erster Stufe. St"utzen Sie sich dabei auf die Definitionen der
		  beteiligten Mengenoperationen und -relationen!
		  \begin{enumerate}
			\item Wenn $M \subseteq N$ gilt, so ist $M \cap L \subseteq N \cap L$
			\item Wenn $L \subseteq M$ gilt, so ist $M \cap (N \cup L) = (M \cap N) \cup L$
			\item $M \subseteq N$ gilt genau dann, wenn $M \cap \overline{N} = \emptyset$ ist
		  \end{enumerate}
\end{enumerate}

\vfill

\vfill

\end{document}
		
