评估 lambda 演算- OR FALSE TRUE

Question

真=λxy。 x

假 = λxy。 y

IF = λbtf。 b t f

AND = λxy。如果 x y 为假

OR = λxy。如果 x 真 y

不=λx。如果 x 假真

如何使用 lambda 演算来减少表达式 OR FALSE TRUE？我不知道从哪里开始。我的讲师没有经历过。这是我的尝试

(\xy.IF x TRUE y)(\xy.y)(\xy.x)
= (\xy.IF x TRUE y)[x := (\xy.y))(\xy.x)
= (\y. IF (\xy.y) TRUE y)(\xy.x)
= (IF (\xy.y) TRUE y)[y := (\xy.x))
= IF (\xy.y) TRUE (\xy.x)

Answer 1

当你使用 Church-encodings 时，我认为最好尽可能保持抽象，即你不应该展开 TRUE、FALSE、IF 和 NOT 热切但只在需要的时候。

相反，您首先要证明关于他们行为的基本结果，这也将有助于完整性检查。对于 IF，您要检查 IF TRUE t f = t 和 IF FALSE t f = f。

IF TRUE t f = TRUE t f   (IF returns its arguments directly)
            = t          (TRUE returns its first argument)

与 IF FALSE 相同。

现在

OR FALSE TRUE = IF FALSE TRUE TRUE

通过应用您已经证明的身份，您应该能够得出结论。

评估 lambda 演算- OR FALSE TRUE

evaluate lambda calculus- OR FALSE TRUE

lambda-calculus