时间戳

首页 > 解决方案 > 大于“>”的 Lambda 微积分函数

logical-operators - 大于“>”的 Lambda 微积分函数

问题描述

我最近开始学习 Lambda 微积分作为作业的一部分，我的任务是为逻辑运算符编写一个函数，我们使用的语法与本视频>中所示的相同。我们可以像这样显式地使用基本的数学运算（+、-、/、*）和等号运算符（=）：

λx.λy.(x - y)
λx.λy.(x = y) TRUE FALSE

我发现这个网站使用小于或等于来解释它并将其与零进行比较，问题在于负数也不同于零。

有没有办法编写一个像这样的 GT 运算符一样工作的 Lambda 微积分函数？

我尝试从第二个数字中减去第一个数字，然后以某种方式将结果除以自身，这样我就可以得到1if>或-1if<但我总是以两个数字对的负数或正<数结束>。

标签： logical-operatorslambda-calculus

解决方案

前言

我能想到的最好的办法是要么只使用非负整数，要么允许平方根运算符。

没有负整数

如果您不必使用负数，则可以使用递归（使用 Y 组合器）对以下函数建模（使用 Python 语法）：

def lt(x, y):
  if y == 0:
    return False
  elif x == 0:
    return y != 0
  else:
    return lt(x - 1, y - 1)

既然这还不错，我会让你自己弄清楚 Y-combinator 的应用。如果您遇到问题，请随时发表评论。

使用负整数和平方根运算符

定义

如果你有负数，我能想到的最好的就是这个。我不会使用 lambda 演算符号，因此您可以自己转换这些符号：

ABS(x) = if (x == 0) then 0 else sqrt(x * x)
SIGN(x) = ABS(x) / (x + (x == 0))
LT(x, y) = (-1 == SIGN(x - y))

注意：我冒昧地让布尔表达式返回整数1or0而不是函数TRUEor FALSE，如您发布的Collected Lambdas链接中所示。如果这是一个问题，您可以编写一个映射TRUE到1和FALSE的函数0。

解释

如果您只看 的最后一个等式LT，就很清楚它为什么有效。你首先计算x - y. 然后，你拿那个表情的符号。x - yif -1iff的符号x < y为真。

的解释SIGN是，当 时x == 0，我们将有表达式0/1，这是正确的。如果x != 0，那么我们将有|x|/x，这将是-1或1取决于 的符号x。

推荐阅读