||和!运算符是否足以构成所有可能的逻辑表达式?

例如，逻辑表达式( a && b ) (__ABC1和b都有布尔值)可以写成!(!a || !b)。这是不是意味着&&是“不必要的”?这是否意味着所有逻辑表达式只能使用||和!?

22068 次浏览
小开

如果可以的话，花点时间阅读dm的法律里。

你可以在阅读材料中找到答案，还有逻辑证明的参考资料。

但本质上，答案是肯定的。

编辑:为了显式，我的观点是，从逻辑上可以从AND表达式推断出OR表达式，反之亦然。关于逻辑等价和推理还有更多的法则，但我认为这一条是最恰当的。

编辑2:这是一个通过真值表证明以下表达式的逻辑等价性的证明。

德摩根定律:!(!A || !B) -> A && B

_____________________________________________________
| A | B | !A  | !B  | !A || !B | !(!A || !B) | A && B |
-------------------------------------------------------
| 0 | 0 |  1  |  1  |    1     |      0      |   0    |
-------------------------------------------------------
| 0 | 1 |  1  |  0  |    1     |      0      |   0    |
-------------------------------------------------------
| 1 | 0 |  0  |  1  |    1     |      0      |   0    |
-------------------------------------------------------
| 1 | 1 |  0  |  0  |    0     |      1      |   1    |
_______________________________________________________
小开

是的。

所有的逻辑门都可以由NOR门制成

由于NOR门可以由一个NOT和一个OR组成，结果如下。

小开

你所描述的是< em > < / em >功能完整性。

这描述了一组足以“表达所有可能的真值表”的逻辑运算符。你的Java操作符集{||， !}是足够的;它对应于集合{∨，¬}，这个集合在“最小函数完备算子集”一节中列出。

所有真值表的集合意味着4个布尔值的所有可能集合，它们可以是2个布尔值之间操作的结果。因为布尔值有2个可能的值，所以有24或16个可能的真值表。

A B | 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
----+------------------------------------------------
T T | T  T  T  T  T  T  T  T  F  F  F  F  F  F  F  F
T F | T  T  T  T  F  F  F  F  T  T  T  T  F  F  F  F
F T | T  T  F  F  T  T  F  F  T  T  F  F  T  T  F  F
F F | T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F

这里有一个真值表数字(0-15)，产生它的||和!组合，以及一个描述。

Table  |  Operation(s)                    | Description
-------+----------------------------------+-------------
0    | A || !A                          | TRUE
1    | A || B                           | OR
2    | A || !B                          | B IMPLIES A
3    | A                                | A
4    | !A || B                          | A IMPLIES B
5    | B                                | B
6    | !(!A || !B) || !(A || B)         | XNOR (equals)
7    | !(!A || !B)                      | AND
8    | !A || !B                         | NAND
9    | !(A || !B) || !(!A || B)         | XOR
10    | !B                               | NOT B
11    | !(!A || B)                       | NOT A IMPLIES B
12    | !A                               | NOT A
13    | !(A || !B)                       | NOT B IMPLIES A
14    | !(A || B)                        | NOR
15    | !(A || !A)                       | FALSE

还有很多其他类似的功能完整集，包括一个元素集{NAND}和{NOR}，它们在Java中没有相应的单个操作符。

小开
最佳答案

是的，正如其他答案指出的那样，由||和!组成的操作符集是功能完整的。下面是一个建设性的证明，展示了如何使用它们来表示布尔变量A和B之间所有16种可能的逻辑连接:

注意，NAND和NOR本身都是功能完备的(可以使用上面相同的方法来证明)，因此，如果您想验证一组操作符是否功能完备，只需证明可以用它来表示NAND或NOR就足够了。

下面的图表显示了上面列出的每个连接词的维恩图:

enter image description here

(源)

小开

是的，根据布尔代数，任何布尔函数都可以表示为minterms的和或maxterms的乘积，即正则范式。这种逻辑没有理由不能应用于计算机科学中使用的相同运算符。

https://en.wikipedia.org/wiki/Canonical_normal_form < a href = " https://en.wikipedia.org/wiki/Canonical_normal_form " > < / >

小开

与非和也不是通用的，它们可以用来在任何地方构建任何逻辑操作;其他运算符在编程语言中可用，使代码易于编写和可读。

此外，所有需要在电路中硬连线的逻辑操作也都是使用NAND或NOR仅ic开发的。


提交答案