lambda - Lambda 表达式简化为 NF

Question

我需要使用 Normal Order 将以下 Lambda 表达式简化为 Normal Form。这些是我的减少，但对我来说没有意义：

//First expression
(λf.λx.f(fx))(λy.+y1)(+ 2 3)
(λx.fx)(λy.+y1)(+ 2 3)
f(λy.+y1)(+ 2 3)
f(+(+ 2 3) 1)
f(+ 5 1)
f 6

//Second expression
λx. + ((λy.((λx.∗ xy) 2)) x) y)
+((λy.((λw.* wy) 2) w)
+((λw.* ww) 2)
+(* 2 2)
+ 4

我得到的两个NF都没有意义。第二个是 + 函数，它需要 2 个变量，但最终只有一个。

我将不胜感激任何建议和更正。

标签： lambdalambda-calculuschomsky-normal-form

Answer 1

1.

//First expression
(λf.λx.f(fx))(λy.+y1)(+ 2 3)

我认为您在这里的错误是认为可以减少第一项。我不认为它可以，所以立即开始将其应用于其他术语。

2.

//Second expression
λx. (+ ((λy.((λx.∗ xy) 2)) x) y)  

为了减少这个开始，通过应用最里面的术语并重命名最后一个y，你得到：

λx. (+ ((λy.(∗ 2y)) x) w)

然后继续:)