Lamba Kalkül - Aufgabe 5 WS17/18

Question

---

Comments

wusste nicht genau wie ich die Datei richtig einfüge, hoffe dass alles sichtbar ist.
Ist das so korrekt wie ich die aufgaben bearbeitet habe?

Answer 1

Teil a) würde ich so lösen:

((fun x -> f x) (fun f -> f x)) [(fun x -> x) / f]
= ((fun x -> (fun x -> x) x) (fun f -> f x)) 
= (fun x -> (fun y -> y) x) (fun f -> f x)
= (fun f -> f x) 

Teil b) würde ich folgendermaßen lösen:

((fun x y -> y 7) (fun x -> x*2)) (fun x -> x+2)
= (fun y -> y 7) (fun x -> x+2);;
= (fun x -> x+2) 7
= 7+2 = 9

Comments

Bei Teil a) habe ich mehr gemacht als in der Aufgabe gefragt war. Wenn man nur die Substitution ausführen soll, dann genügen die ersten beiden Zeilen. Wichtig ist dabei, das im Teilausdruck (fun x -> f x) das Symbol f frei vorkommt und daher von der Substitution ersetzt wird, während im zweien Ausdruck (fun f -> f x) die Variable f gebunden ist und nicht ersetzt wird. Dort könnte man auch eine gebundene Umbenennung durchführen und (fun f -> f x) zum Beispiel durch (fun g -> g x) ersetzen.

Aber ich sehe, dass die Aufgabensteller genauer sehen wollen, wie man die einzelnen Schritte begründet. Daher sollte man die Substitution Schritt für Schritt durchführen (und nicht alles in einem Rutsch wie ich das gemacht habe). Die Antwort unten von PeterZeller ist daher besser.

Das Ersetzen von (fun x -> x) durch (fun y -> y) muss man nicht machen. Auch das ist nur eine gebundene Umbenennung mit der ich verdeutlichen wollte, dass das (fun x -> x) x zu x äquivalent ist und dass dies durch eine Funktionsanwendung geschieht. Dabei ist es unerheblich ob man (fun x -> x) x oder (fun y -> y) x betrachtet.

Answer 2

Zu Teil a):

Sie sind zum richtigen Ergebnis gekommen, allerdings fehlen die Zwischenschritte. Es soll hier nach der formalen Definition (siehe Skript 25 Seite 6) vorgegangen werden. Das heißt die Substitution wird Schritt für Schritt nach innen gezogen:

    ((λx→f x) (λf→f x))[(λx→x)/f]
= ((λx→f x)[(λx→x)/f] (λf→f x)[(λx→x)/f])
= (λx→(f x)[(λx→x)/f]) (λf→f x)
= (λx→(f[(λx→x)/f] x[(λx→x)/f])) (λf→f x)
= (λx→(λx→x) x)) (λf→f x)

Zu Teil b):

Hier war Ihr Fehler, dass Sie das erste Argument für den zweiten Parameter eingesetzt haben.

In der Aufgabe haben wir eine Funktion, die zwei Parameter x und y nimmt. Als erster konkreter Parameter beim Aufruf wird "(λx→x*2)" übergeben, als zweiter "(λx→x+2)".

Eventuell hilft es die ausführliche Schreibweise zu verwenden:

((λx→ (λy→y 7)) (λx→x*2)) (λx→x+2)