与非门是如何实现的？（概念上）

Question

我试图找到你无法实现的最低级别的事情，因为它们的级别太低了。如此看来，所有的计算都可以由与非门来构建。

从真值表可以很容易地用 JavaScript 来“实现”：

function nand(a, b) {
  if (a == 0 && b == 0) return 1
  if (a == 0 && b == 1) return 1
  if (a == 1 && b == 0) return 1
  if (a == 1 && b == 1) return 0
}

但这是作弊。因为IF 语句是如何实现的？我不太知道如何在代码中表示 if 语句链接，因为我不确定是否熟悉逻辑门/电路，但我很确定 IF 语句本身可以表示为 NAND 门的组合。

那么接下来就是海龟了！与非门由更多与非门（用于 if 语句）等实现。

那么我们如何避免这种情况呢？我们是否简单地说“与非”门是一个公理？我想知道，因为我想知道形式验证的基础在哪里。

换句话说，我问的原因是因为我注意到每个函数都可以实现为其他函数，甚至是 IF 语句等。一切都可以一直实现到与非门。但后来我就左转了，NAND 也是一个功能，但它的实现是什么？！？我很困惑/困惑，需要一些关于如何思考这个问题的指导。

Answer 1

由于 NAND 不是 AND，因此您可以使用 AND 来声明它，这意味着 NAND 不是公理：

function nand(a, b) {
  return !(a && b)
}

console.log(nand(false, false)) // true
console.log(nand(true, false)) // true
console.log(nand(false, true)) // true
console.log(nand(true, true)) // false

使用乘法，您可以用 0 和 1 声明 NAND。由于 AND 是a * b（如果两者都是 1，则得到 1），所以 NAND 是1 - a * b：

function nand(a, b) {
  return 1 - a * b
}

console.log(nand(0, 0)) // 1
console.log(nand(1, 0)) // 1
console.log(nand(0, 1)) // 1
console.log(nand(1, 1)) // 0