真假的lambda演算异或表达式

Question

我试图在 lambda 演算的上下文中理解 xor。我将 xor（异或）理解为 https://en.wikipedia.org/wiki/Exclusive_or 中的布尔逻辑运算和 xor 的真值 table。

但是为什么异或 b=(a)((b)(false)(true))(b) 来自 http://safalra.com/lambda-calculus/boolean-logic/ 这确实是 lambda 演算中所期望的。当我看到真=λab.a 假=λab.b 我有点必须将 true 和 false 视为 lambda calc true 和 false，因为它 returns 在 true 的情况下是第一个元素。但是这里的xor也是一个名字但是和boolean逻辑中的xor不一样的理解正确吗？

Answer 1

直观上，我们可以把A XOR B想成

如果A，那么不是B
否则，B

.. 或者在一些伪代码中：

func xor (a,b)
  if a then
    return not b
  else
    return b

让我们开始计算 lambda

true := λa.λb.a
false := λa.λb.b

true a b
// a

false a b
// b

接下来我们会做not

not := λp.p false true

not true a b
// b

not false a b
// a

接下来我们可以做 if（注意，这有点傻，因为 true 和 false 已经表现得像 if）

if := λp.λa.λb.p a b

if true a b
// a

if false a b
// b

好的，最后写xor

xor := λa.λb.if a (not b) b

(xor true true) a b
// b

(xor true false) a b
// a

(xor false true) a b
// a

(xor false false) a b
// b

记住 if 在这里有点笨，我们可以删除它

xor := λa.λb.a (not b) b

现在，如果我们想用纯 lambda 编写所有内容，只需将 not 替换为其定义

xor := λa.λb.a (not b) b
->β [ not := λp.p false true ]

xor := λa.λb.a ((λp.p false true) b) b
->β [ p := b ]

xor := λa.λb.a (b false true) b

在这个点，你可以看到我们有你问题的定义

a xor b = (a)((b)(false)(true))(b)

但当然这引入了额外的自由变量 false 和 true – 您可以用一些额外的 beta 减少来替换它们

xor := λa.λb.a (b false true) b
->β [ false := (λa.λb.b) ]

xor := λa.λb.a (b (λa.λb.b) true) b
->β [ true := (λa.λb.a) ]

// pure lambda definition
xor := λa.λb.a (b (λa.λb.b) (λa.λb.a)) b

Answer 2

考虑 a(b F T)b，中间表达式本质上是 (not b)，所以 a(not b)b 只有当 a 和 b 不同时才为真。

真假的lambda演算异或表达式

lambda calculus xor expression by true false

functional-programming

xor

church-encoding