javascript - 与非门是如何实现的？ (概念上)

Question

我正在尝试找到您无法实现的最低级别的东西，因为它们级别太低。所以似乎所有的计算都可以从 NAND gate 构造出来。 .

从真值表很容易在 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 statements implemented 怎么样？ ？我不太清楚如何在代码中表示 if 语句链接，因为我不确定是否熟悉逻辑门/电路，但我很确定 IF 语句本身可以表示为 NAND 门的组合。

然后就是乌龟了!用更多的 NAND 门(用于 if 语句)等实现 NAND 门。

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

换句话说，我问的原因是因为我注意到每个函数都可以作为其他函数实现，甚至是 IF 语句等。一切都可以一直实现到 NAND 门。但后来我摇摆不定，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