\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath,amssymb}
\usepackage{german}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{bis zum 27. Juni 2017, in der
Vorlesung}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\N}{\mathbb{N}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Semantik von Programmiersprachen}\hfill SoSe 2017 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Max Willert

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Die Ordnungsrelation $\sqsubseteq$}{10 Punkte}

\begin{enumerate}
\item Seien $g_1, g_2, g_3: \mathbf{State} \rightarrow \mathbf{State}$
gegeben durch:
\begin{enumerate}
\item $g_1(\sigma) = \sigma$, falls $\sigma(\texttt{x})$ gerade ist,
  und $g_1(\sigma) = \perp$, sonst, f\"ur alle $\sigma \in \mathbf{State}$.
\item $g_2(\sigma) = \sigma$, falls $\sigma(\texttt{x})$ Primzahl ist,
  und $g_2(\sigma) = \perp$, sonst, f\"ur alle $\sigma \in \mathbf{State}$.
\item $g_3(\sigma) = \sigma$, f\"ur alle $\sigma \in \mathbf{State}$.
\end{enumerate}
Bestimmen Sie, wie $g_1$, $g_2$ und $g_3$ bez\"uglich $\sqsubseteq$
in Relation stehen. Geben Sie dann eine neue Funktion 
$g_4: \mathbf{State} \rightarrow \mathbf{State}$, so dass
\[
g_4 \sqsubseteq g_1, g_4 \sqsubseteq g_2 \text{ und } 
g_4 \sqsubseteq g_3
\]
gilt, und eine neue Funktion 
$g_5: \mathbf{State} \rightarrow \mathbf{State}$, so dass
\[
g_1 \sqsubseteq g_5, g_2 \sqsubseteq g_5 \text{ und }
g_5 \sqsubseteq g_3
\] 
ist.
\item
Zeigen Sie: F\"ur alle $g_1, g_2: \mathbf{State} \rightarrow \mathbf{State}$
gilt: es ist $g_1 \sqsubseteq g_2$ genau dann, wenn 
$\text{graph}(g_1) \subseteq \text{graph}(g_2)$ gilt.
Dabei ist
\[ 
\text{graph}(g) = \{ (\sigma, g(\sigma)) \mid \sigma \in \mathbf{State},
g(\sigma) \neq \perp\}.
\]
\end{enumerate}

\AUFGABE{Ordnungsrelationen und Minima}{10 Punkte}

\begin{enumerate}
\item Sei $S$ eine Menge
und $\mathcal{P}(S)$ die Potenzmenge von $S$.
Zeigen Sie:
$(\mathcal{P}(S), \supseteq)$ ist eine Halbordnung.
Bestimmen Sie das Minimum, und zeichnen Sie 
das Hasse-Diagramm der Ordnung f\"ur $S = \{1,2,3\}$.
\item 
Sei $S$ eine nichtleere Menge. Definieren Sie
\[
\mathcal{P}_\text{fin}(S) = \{ K \subseteq S \mid K \text{ ist endlich}\}.
\]
Zeigen Sie, dass 
$(\mathcal{P}_\text{fin}(S), \subseteq)$
und
$(\mathcal{P}_\text{fin}(S), \supseteq)$ Halbordnungen sind.
Gibt es in beiden Halbordnungen f\"ur jede Wahl von $S$ ein
Minimum?
\end{enumerate}

\AUFGABE{Suprema}{10 Punkte}

\begin{enumerate}
  \item Konstruieren Sie eine Teilmenge $\mathcal{G}$ von
    Zustands\"uberf\"uhrungsfunktionen, so dass
    $\mathcal{G}$ bez\"uglich $\sqsubseteq$ 
    keine obere Schranke und somit kein Supremum besitzt.
  \item Sei $(g_n)_{n \in \N}$ die Folge von 
  Zustands\"uberf\"uhrungsfunktionen mit 
  $g_n(\sigma) = 
  \sigma[\texttt{y} \mapsto (\sigma(x))!, \texttt{x} \mapsto 1]$, falls
  $\sigma(\texttt{x}) \in \{1, \dots, n\}$, und $g_n(\sigma) = \perp$,
  sonst. Sei $\mathcal{G} = \{g_n \mid n \in \N\}$. Zeigen Sie, dass
  $\mathcal{G}$ eine Kette ist. Charakterisieren Sie die oberen Schranken 
  von $\mathcal{G}$ und
  bestimmen Sie $\sup \mathcal{G}$.
\end{enumerate}
\end{description}
\end{document}
