decision-tree - ITE 算法的布尔运算

Question

我有点困惑。我需要举例说明在每个布尔运算中使用 ITE 算法。但我其实不知道有多少？例如，我的意思是 AND、OR、XOR、XNOR、NOR、NAND、NOT。我不知道其他的......我至少错过了一个，因为它不可能是七次手术。(2^n)

Answer 1

我需要举例说明在每个布尔运算中使用 ITE 算法。

这是Knuth 的计算机编程艺术第 4 卷分册 1B中的练习 1 。

答案如下。

---

但我其实不知道有多少？

正好有 16 个两个变量的布尔函数（和2 个^2ⁿ</sup>的n 个变量的函数）。只需置换函数真值表中的行。

| F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | FA | FB | FC | FD | FE | FH |
|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|----|
|  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |  1 |
|  0 |  0 |  0 |  0 |  1 |  1 |  1 |  1 |  0 |  0 |  0 |  0 |  1 |  1 |  1 |  1 |
|  0 |  0 |  1 |  1 |  0 |  0 |  1 |  1 |  0 |  0 |  1 |  1 |  0 |  0 |  1 |  1 |
|  0 |  1 |  0 |  1 |  0 |  1 |  0 |  1 |  0 |  1 |  0 |  1 |  0 |  1 |  0 |  1 |

F0 和 FH 不依赖于两个变量的值。
F3、F5、FA、FC 仅取决于一个变量的值。

下表列出了这些函数的常用名称。

上表来自第 4 卷的分册 0B。

我要补充一点，F8 和 FE 也分别称为皮尔斯箭和谢弗箭。