Lambdakalkuel_Aufgaben.tex

\documentclass{scrartcl}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}
\usepackage{amsmath,amssymb}
\usepackage{enumerate}
\usepackage{graphicx}

\newcommand{\same}{$\stackrel{\eta,\beta}{=}$}
\renewcommand{\l}{$\lambda$}

\begin{document}
\shorthandoff{"}
\section*{Aufgaben zum Lambdakalkül}
\subsection*{Aufgabe 1}
Das SKI-Kalkül verwendet die Kombinatoren S = \l x. \l y. \l z. x z (y z), K = \l x. \l y. x und I = \l x. x. Zusätzlich lassen sich die Kombinatoren C = \l f. \l x. \l y. f y x und\\ B = \l f. \l g. \l x. f (g x) definieren.
\begin{enumerate}[1.]
\item Zeigen Sie S K \same{} K I, indem Sie zeigen:\\
S K x y $\Rightarrow^*$ Z und K I x y $\Rightarrow^*$ Z für den gleichen Term Z.
\item Der Kombinator $\Psi$ ist wie folgt definiert: $\Psi$ = \l f. \l g. \l x. \l y. f (g x) (g y).
\begin{enumerate}[(a)]
\item Geben Sie den allgemeinsten Typ von $\Psi$ an.
\item Zeigen Sie C I x y $\Rightarrow^*$ y x.
\item Der Kombinator C' sei definiert durch C' = B (B C) C.\\
Zeigen Sie: C' f x y z $\Rightarrow^*$ f z x y.
\item Der Kombinator S kann dargestellt werden als C' (B ($\Psi$ I) (C I)).\\ Zeigen Sie, dass tatsächlich C' (B ($\Psi$ I) (C I)) x y z $\Rightarrow^*$ x z (y z).
\end{enumerate} 
\end{enumerate}

\subsection*{Aufgabe 2}
Die Church-Booleans waren wie folgt definiert: $c_{true}$=(\l t. \l f. t) und $c_{false}$=(\l t. \l f. f), die Church-Integer als $c_n$=(\l s. \l z. s$^n$ z).
\begin{enumerate}
\item Geben Sie einen Lambdaterm "not" an, der die Negation eines gegebenen Church-Booleans berechnet.
\item Geben Sie nun (z.B. mithilfe von "not") einen Lambdaterm "even" an, der zurückgibt, ob ein gegebener Church-Integer gerade ist.
\item Schreiben Sie einen Lambdaterm "max", der das Maximum von zwei gegebenen Church-Integern berechnet. Sie dürfen die Funktion "less\_eq" verwenden, wobei "less\_eq n m" angibt, ob $n\leq m$ gilt.
\item Der Kombinator B sei definiert durch B = (\l f. \l g. \l x. f (g x)). Zeigen Sie, dass (\l a. \l b. \l c. B B B max max a b c) das Maximum von 3 Zahlen berechnet. Sie dürfen dazu verwenden, dass $\max(a,b,c)=\max(\max(a,b),c)$.
\end{enumerate}

\end{document}