纯Lambda微积分 - 和功能

Question

我目前正在学习Haskell,还参加了一个关于大学函数式编程的理论讲座.

我知道这纯粹是理论/学术问题,但我感兴趣的是如何简单地用纯lambda演算来表达不同的简单函数(即没有定义任何常量).

我的一些讲义材料定义了布尔值,例如:

True =\xy.x
False =\xy.y

(\表示lambda符号)

如果它们被定义为这些选择器函数,则if条件可以很容易地定义为:

如果 =\xx

现在,我正在尝试为逻辑"和"函数提供一些简短形式.我的第一个猜测是:

和 =\XY {(如果 x)的[(如果 Y)真 假 ] 假 }

所以基本上这个lambda函数会接收2个参数uv,其中两个都必须输入类似True/False.如果我使用逻辑表的所有4种组合进行各种beta减少,我会收到正确的结果.

不过这个功能看起来有点难看,我正在考虑让它更优雅.这里有什么建议？

Answer 1

我们可以减少你的答案,以获得一个更精简的答案.

首先是一些热身.显然IF x ==> x,as TRUE TRUE FALSE ==> TRUE和FALSE TRUE FALSE ==> FALSEif x是一个布尔然后x TRUE FALSE ==> x.

现在我们减少

\x y . (IF x) ( (IF y) TRUE FALSE ) FALSE
\x y .     x  (     y  TRUE FALSE ) FALSE  -- using IF x         ==> x
\x y .     x  (     y             ) FALSE  -- using y TRUE FALSE ==> y
\x y . x y FALSE                           -- clean up

这个表达式仍适用于真值表

AND TRUE  TRUE  = TRUE  TRUE  FALSE = TRUE
AND FALSE TRUE  = FALSE TRUE  FALSE = FALSE
AND TRUE  FALSE = TRUE  FALSE FALSE = FALSE
AND FALSE FALSE = FALSE FALSE FALSE = FALSE