Lambda Kalkül Normalform?

1 Antwort

Gegeben:

(λa b c. a (b b) c) (λx y. x y a) (λa. a)
Schritt 1: Verstehe die Struktur

Wir haben:

λa b c. a (b b) c

Das ist eine Funktion mit drei Parametern:

a

,

b

,

c

.

Der Funktionskörper ist:

a (b b) c

→ Bedeutet:

b

wird auf sich selbst angewendet, dann wird

a

auf das Ergebnis und auf

c

angewendet.

Wir wenden diese Funktion auf zwei Argumente an:

  1. λx y. x y a
  2. λa. a
Schritt 2: Beta-Reduktion – Setze Argumente ein

Wir ersetzen:

  • a
  • durch
  • λx y. x y a
  • b
  • durch
  • λa. a

Der Körper war:

a (b b) c

Daraus wird:

(λx y. x y a) ((λa. a) (λa. a)) c

Jetzt definieren wir eine neue Funktion über

c

:

λc. (λx y. x y a) ((λa. a) (λa. a)) c
Schritt 3: Reduziere
(λa. a)(λa. a)

Das ist die Identitätsfunktion auf sich selbst angewendet:

Ergibt einfach:

λa. a

Also:

λc. (λx y. x y a) (λa. a) c
Schritt 4: Wende
(λx y. x y a)
auf
(λa. a)
an

Jetzt wenden wir:

(λx y. x y a)

auf:

λa. a

an.

Ergebnis: Ersetze

x

durch

λa. a

.

Dann bleibt:

λy. (λa. a) y a

Nun:

(λa. a) y

ergibt

y

, also bleibt:

λy. y a
Schritt 5: Wende das auf
c
an

Jetzt haben wir:

λc. (λy. y a) c

Wende

(λy. y a)

auf

c

an:

→ ergibt:

c a

Fertig! Das ist die Normalform:
λc. c a