你如何减少这个 lambda 演算表达式？

Question

如何简化这个 lambda 演算表达式？我正在尝试使用具有给定定义的 lambda 演算将 NOT FALSE 减少为 TRUE：

NOT = (λb.λx.λy.b y x)
FALSE = (λx.λy.y)
TRUE = (λx.λy.x)

Answer 1

  NOT FALSE
= { expand definitions }
  (λb.λx.λy.b y x) (λx.λy.y)
= { beta-reduce, alpha-rename to avoid capture }
  λx.λy.(λa.λb.b) y x 
= { beta-reduce inside lambda, twice }
  λx.λy.x
= { definition of TRUE }
  TRUE

Answer 2

给定-

NOT = (λb.λx.λy.b y x)
FALSE = (λx.λy.y)
TRUE = (λx.λy.x)

评价-

NOT FALSE
---
 \
(λb.λx.λy.b y x) FALSE      β [b := FALSE]
 --       -      -----
          _______/
         /
(λx.λy.FALSE y x)

我们已经可以看到 NOT 只是将参数反转为 FALSE，这实际上与 TRUE 相同。通过减少 lambda 内部，我们可以证明它们的计算结果相同 -

(λx.λy.FALSE y x) 
       -----
         \
(λx.λy.(λx.λy.y) y x)       β [x := y]
        --       -
         
(λx.λy.(λy.y) x)            β [y := x]
        __    _
         ____/
        /
(λx.λy.x)                   = TRUE

你如何减少这个 lambda 演算表达式？

How do you reduce this lambda calculus expression?

lambda

computer-science

lambda-calculus