仅使用增量，循环，分配，零的关系运算 [英] Relational operations using only increment, loop, assign, zero

问题描述

这是针对以下问题的后续问题:仅使用增量，循环，赋值，零的减法运算

This is a follow up question for: Subtraction operation using only increment, loop, assign, zero

我们只允许使用以下操作:

We're only allowed to use the following operations:

1. incr(x)-调用此函数后，会将x +1分配给x
2. assign(x，y)-此函数会将y的值分配给x(x = y)
3. zero(x)-此函数会将0分配给x(x = 0)
4. 循环X {}-用括号括起来的操作将执行X次

例如，加法可以如下实现:

For example, addition can be implemented as follows:

add(x, y) {
    loop x
        { y = incr(y) }
    return y
}

如何使用这四个操作实现关系运算符?关系操作为:

How do I implement the relational operators using these four operations? The relational operations are:

1. eq(x，y)-x是否等于y?
2. lt(x，y)-x是否小于y?
3. gt(x，y)-x是否大于y?

我们也有相反的看法:

1. ne(x，y)-x不等于y吗?
2. gte(x，y)-x是否大于或等于y?
3. lte(x，y)-x是否小于或等于y?

任何帮助将不胜感激.

推荐答案

自然数集N在加法和减法下是封闭的:

The set of natural numbers N is closed under addition and subtraction:

N + N = N
N - N = N

这意味着两个自然数的加法或减法也是自然数(考虑到0 - 1是0而不是-1，我们不能有负自然数).

This means that the addition or subtraction of two natural numbers is also a natural number (considering 0 - 1 is 0 and not -1, we can't have negative natural numbers).

但是，自然数N的集合在关系运算下不会关闭:

However, the set of natural numbers N is not closed under relational operations:

N < N = {0, 1}
N > N = {0, 1}

这意味着比较两个自然数的结果是真实性(即1)还是虚假(即0).

This means that the result of comparing two natural numbers is either truthfulness (i.e. 1) or falsehood (i.e. 0).

因此，我们将布尔值集(即{0, 1})视为自然数的受限集(即N).

So, we treat the set of booleans (i.e. {0, 1}) as a restricted set of the natural numbers (i.e. N).

false = 0
true  = incr(false)

我们必须回答的第一个问题是我们如何编码if语句，以便我们可以基于真实性或虚假性进行分支?"答案很简单，我们使用loop操作:

The first question we must answer is “how do we encode if statements so that we may branch based on either truthfulness or falsehood?” The answer is simple, we use the loop operation:

isZero(x) {
    y = true
    loop x { y = false }
    return y
}

如果循环条件为true(即1)，则循环仅执行一次.如果循环条件为false(即0)，则循环不会执行.我们可以用它来编写分支代码.

If the loop condition is true (i.e. 1) then the loop executes exactly once. If the loop condition is false (i.e. 0) then the loop doesn't execute. We can use this to write branching code.

那么，我们如何定义关系操作?事实证明，一切都可以用lte定义:

So, how do we define the relational operations? Turns out, everything can be defined in terms of lte:

lte(x, y) {
    z = sub(x, y)
    z = isZero(z)
    return z
}

我们知道x ≥ y与y ≤ x相同.因此:

We know that x ≥ y is the same as y ≤ x. Therefore:

gte(x, y) {
    z = lte(y, x)
    return z
}

我们知道，如果x > y为true，则x ≤ y为false.因此:

We know that if x > y is true then x ≤ y is false. Therefore:

gt(x, y) {
    z = lte(x, y)
    z = not(z)
    return z
}

我们知道x < y与y > x相同.因此:

We know that x < y is the same as y > x. Therefore:

lt(x, y) {
    z = gt(y, x)
    return z
}

我们知道，如果x ≤ y和y ≤ x，则x = y.因此:

We know that if x ≤ y and y ≤ x then x = y. Therefore:

eq(x, y) {
    l = lte(x, y)
    r = lte(y, x)
    z = and(l, r)
    return z
}

最后，我们知道如果x = y为true，则x ≠ y为false.因此:

Finally, we know that if x = y is true then x ≠ y is false. Therefore:

ne(x, y) {
    z = eq(x, y)
    z = not(z)
    return z
}

现在，我们需要做的就是定义以下函数:

Now, all we need to do is define the following functions:

1. sub函数的定义如下:

sub(x, y) {
    loop y
        { x = decr(x) }
    return x
}

decr(x) {
    y = 0
    z = 0

    loop x {
        y = z
        z = incr(z)
    }

    return y
}

not函数与isZero函数相同:

The not function is the same as the isZero function:

not(x) {
    y = isZero(x)
    return y
}

and函数与mul函数相同:

The and function is the same as the mul function:

and(x, y) {
    z = mul(x, y)
    return z
}

mul(x, y) {
    z = 0
    loop x { z = add(y, z) }
    return z
}

add(x, y) {
    loop x
        { y = incr(y) }
    return y
}

这就是您所需要的.希望有帮助.

That's all you need. Hope that helps.

这篇关于仅使用增量，循环，分配，零的关系运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！