逻辑表达式 ( a && b ) (表示a和b都是布尔值) 可以像 !(!a || !b) 一样书写。这是否意味着 && 是“不必要的”？这是否意味着所有逻辑表达式都可以仅使用||和!来表示？
逻辑运算符 || 和 ! 能够组合出所有可能的逻辑表达式吗？
295
- JakeTheSnake
16
6个回答
429
是的，正如其他答案指出的那样，包括||和!运算符的集合是功能完备的。以下是一个具体的证明，展示了如何使用它们来表示布尔变量A和B之间的所有十六种可能的逻辑连接：
- 真：
A || !A - 与非：
!A || !B - 蕴含：
!B || A - 条件：
!A || B - 或：
A || B - 非B：
!B - 非A：
!A - 异或：
!(!A || B) || !(A || !B) - 等价：
!(!A || !B) || !(A || B) - A：
A - B：
B
!(A || B)!(!A || B)!(!B || A)!(!A || !B)!(A || !A)请注意，NAND 和 NOR 都本身是功能完备的（可以使用上述相同的方法证明），因此，如果您想要验证一组操作符是否功能完备，则只需说明您可以使用其中之一表示 NAND 或 NOR。
以下是显示上述连通性的Venn 图表：
[来源]
- Peter Olson
6
21很难判断问题的意图，但这个答案没有涉及到短路行为（相关，因为问题涉及“||”而不是“|”），也没有涉及副作用（相关，因为true、false、XOR和XNOR的扩展比原始常量或运算符对其参数进行更多次求值）。 - David Richerby
5包含圆圈和转换的圆圈形成了一个 Hasse 图（https://zh.wikipedia.org/wiki/哈斯图）。（耶，今天我学到了新东西！） - Kasper van den Berg
5@DavidRicherby 的说法是正确的。除了 XOR、XNOR、true 和 false 这几个运算符之外，据我所知，自定义的逻辑运算符在副作用和计算次数上应该与内置的等价物相同（例如，
!(!A || !B) 与 A && B 在短路和计算次数上是相同的）。我认为如果没有额外的结构（比如 a ? !b : b），你无法使用 XOR 和 XNOR 定义新的运算符；如果能够保存值，true 或 false 并不是问题，因为你可以通过一些虚拟布尔变量来定义它们。 - Peter Olson有趣的是注意到上面的列表包括16个操作。这与当您有2个输入和1个输出时有16个可能的真值表的事实相一致。 - Paul R
值得注意的是，您还使用括号（即优先级），但这并不是根本性的，因为相同的操作可以通过时间顺序（通过波兰符号表示法）来表达。 - Sklivvz
1只是想为大家提供另一种可视化方式，作为表格的形式，链接如下：https://upload.wikimedia.org/wikipedia/commons/9/91/Logical_connectives_table.svg。与上面的来源相同。 - aug
126
您所描述的是功能完备性。
这描述了一组逻辑运算符，足以“表达所有可能的真值表”。 您的Java运算符集{
所有真值表的集合意味着可以成为两个布尔值之间操作结果的4个布尔值集合的所有可能集合。 因为布尔值有2个可能的值，所以有24个或16个可能的真值表。
这里是真值表数字（0-15）、
这描述了一组逻辑运算符，足以“表达所有可能的真值表”。 您的Java运算符集{
||，!}是足够的； 它对应于集合{∨，¬}，该集合列在“最小功能完备运算符集”部分下。所有真值表的集合意味着可以成为两个布尔值之间操作结果的4个布尔值集合的所有可能集合。 因为布尔值有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中没有相应的单个运算符。
- rgettman
2
4编辑得不错，给你点赞。尽管在投票数量上有差异，但我认为你的回答现在比我的更详细了。 - Peter Olson
真值表，我以为在大学一年级之后就把它们抛在了身后。 - Barkermn01
80
- Paul Boddington
6
64@PaulDraper 或者 NAND 门 - slebetman
25将两个人送上月球需要4100个 NOR 门。 - Hans Passant
4@HansPassant 和一些字符串。很多字符串。（核心绳记忆，而不是锡罐类型的。） - user
3有时候我希望 Stack Exchange 能像维基百科一样，这样我就可以在那里插入一个"[需要引用]"标记了。 - Simon Forsberg
11好的，抱歉。阿波罗制导计算机。 - Hans Passant
为了使你的答案更完整，展示如何通过 NOT 和 OR 门制作 NOR 门会更好。 - rogerdpack
64
如果可以，请花时间阅读 德摩根定律。在那里的阅读中，您将找到答案，以及有关逻辑证明的参考资料。但基本上，答案是肯定的。编辑：为了明确，我的观点是一个AND表示式可以从OR表示式中逻辑地推导出来，反之亦然。还有更多关于逻辑等价和推理的法则，但我认为这个最合适。编辑2：这里通过真值表证明以下表达式的逻辑等价性。德摩根定律：
!(!A ||!B) -> A && B- ryuu9187
5
19有些人必须进行负面评价以满足其“功能完整性”的要求。 - Jesse
3在+27/-2的情况下，我不会太担心一个无关紧要的负评。 - user
2@MichaelKjörling 我只是好奇为什么有些人认为我的回答不够有帮助/有害。 - ryuu9187
3通常，回答需要依赖链接的情况不太受欢迎（因为链接可能失效）。但在这种情况下，有很多对德摩根定律的替代解释，我认为这并不是问题——尽管这只是我的猜测。 - user2813274
@user2813274 感谢您的解释。希望我的编辑能够缩小个人研究和得到答案之间的差距。 - ryuu9187
10
根据布尔代数，任何布尔函数都可以表示为最小项之和或最大项之积的形式，这称为规范标准型。这种逻辑在计算机科学中使用的运算符上同样适用。
- Michał Szydłowski
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
A和B == !A nor !B == !(!A or !B)。 同样，A或B == !A nand !B == !(!A and !B)。 很明显，将相同的值传递到NAND或NOR的两个输入中将得到与简单的NOT相同的结果。 XOR和XNOR也是可能的，但更为复杂。 请参阅德摩根定理。 - Basic