函数式编程-为了证明SKK和II是等效的，使用lambda演算

Question

我是lambda微积分的新手，正在努力证明以下内容。

SKK和II是等效的。

,

S = lambda xyz.xz(yz)K = xyI = lambda x.x

我试图通过打开它来减少SKK，但是没有得到任何结果，它变得很乱。

Answer 1

  SKK
= (λxyz.xz(yz))KK
→ λz.Kz(Kz)        (in two steps actually, for the two parameters)
  Kz
= (λxy.x)z
→ λy.z
  λz.Kz(Kz)
→ λz.(λy.z)(λy.z)  (again, several steps)
→ λz.z
= I

(你应该能够证明II → I)

Answer 2

;另一种步骤更少的方法，首先将SK约简为λyz.z;

SKK
= (λxyz.xz(yz))KK
→ λyz.Kz(yz) K
→ λyz.(λxy.x)z(yz) K
→ λyz.(λy.z)(yz) K
→ λyz.z K
→ λz.z
= I