Übungen: Der Lambda-Kalkül
Aufgabe 1: Auswertung mit Beta-Reduktion
(a)-(e) Reduziere die folgenden Lambda-Kalkül-Ausdrücke durch die Beta-Reduktion.
(a) $\ (\lambda a.a*4)\ 5$
(b) $\ (\lambda x.(x\ x))\ (\lambda z.z)$
(c) $\ ((((\lambda abcf.(f\ (a*b+a*c)))\ 2)\ 7)\ 12)\ (\lambda x.x-8)$
(d) $\ (\lambda x.(x\ ((\lambda y.(y*y))\ 3)))\ (\lambda z.z+z)$
(e) $\ ((\lambda fx.f(f\ x))\ (\lambda y.y+1))\ 2$
Aufgabe 2: Boolesche Logik im Lambda-Kalkül
Genau wie mathematische Rechnungen lässt sich auch die Boolesche Logik durch Ausdrücke des Lambda-Kalküls darstellen. Betrachten wir beispielsweise die beiden Racket-Ausdrücke:
(if #t 1 0)
; Gibt zurück -> 1
(if #f 1 0)
; Gibt zurück -> 0
Um diese äquivalent im Lambda-Kalkül darzustellen, nutzen wir die folgenden Lambda-Kalkül-Ausdrücke:
| Racket | Lambda-Kalkül-Ausdruck |
|---|---|
#t |
$\lambda ab. a$ |
#f |
$\lambda ab. b$ |
if |
$\lambda xyz. ((x\ y)\ z)$ |
(a) Zeige, dass die obigen beiden Racket-Ausdrücke im Lambda-Kalkül darstellbar sind und bei Auswertung jeweils die gleichen Ergebnisse wie in Racket liefern.
Die Repräsentation des Racket-Ausdrucks:
(if #t 1 0)
