是||和 ！足以使每个可能的逻辑表达式的运算符？
Are || and ! operators sufficient to make every possible logical expression?
逻辑表达式( a && b ) (a和b都有布尔值)可以写成!(!a || !b),例如。这不是说 && 是 "unneccesary" 吗？这是否意味着 所有 逻辑表达式只能使用 || 和 !？
如果可以，花点时间阅读 DeMorgan's Laws。
你会在那儿的阅读中找到答案，以及对逻辑证明的引用。
但本质上，答案是肯定的。
编辑：为了明确起见，我的观点是可以从逻辑上从 AND 表达式推断出 OR 表达式，反之亦然。逻辑等价和推理的规律还有很多，但我觉得这条最合适。
编辑 2：这是通过 truth-table 的证明，显示了以下表达式的逻辑等价性。
德摩根定律：!(!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 |
_______________________________________________________
是的。
All logic gates can be made from NOR gates.
由于 NOR 门可以由 NOT 和 OR 构成，结果如下。
您所描述的是functional completeness。
这描述了一组足以"express all possible truth tables"的逻辑运算符。您的 Java 运算符集 {||, !} 就足够了；它对应于 "Minimal functionally complete operator sets".
部分下列出的集合 {∨, ¬}
全真集合table表示所有可能的4个布尔值集合，可以是2个布尔值之间运算的结果。因为布尔值有 2 个可能值，所以有 24，或 16 个可能的真值 tables.
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
这是 table 的真值 table 数字 (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 中没有对应的单个运算符。
是的，正如其他答案所指出的，由 || 和 ! 组成的运算符集是 functionally complete。这是一个建设性的证明，展示了如何使用它们来表达布尔变量 A 和 B:
之间所有十六种可能的逻辑连接词
- True:
A || !A
- A NAND B:
!A || !B
- B implies A:
!B || A
- A implies B:
!A || B
- A OR B:
A || B
- Not B:
!B
- Not A:
!A
- A XOR B:
!(!A || B) || !(A || !B)
- A XNOR B:
!(!A || !B) || !(A || B)
- A:
A
- B:
B
- A NOR B:
!(A || B)
- A does not imply B:
!(!A || B)
- B does not imply A:
!(!B || A)
- A AND B:
!(!A || !B)
- False:
!(A || !A)
请注意，NAND 和 NOR 本身都是功能完整的（可以使用上面相同的方法证明），因此如果要验证一组运算符功能完整，足以证明您可以用它表达 NAND 或 NOR。
这是一张图表，显示了上面列出的每个连接词的 Venn diagrams：
[source]
是的，根据布尔代数，任何布尔函数都可以表示为最小项之和或最大项之积，称为规范范式。没有理由不能将这种逻辑应用于计算机科学中使用的相同运算符。
NAND and NOR 是通用的，它们可用于在任何地方构建您想要的任何逻辑操作；其他运算符以编程语言提供，以便于编写和制作可读代码。
此外，所有需要在电路中硬连线的逻辑操作也都是使用 NAND 或 NOR 专用 IC 开发的。
逻辑表达式( a && b ) (a和b都有布尔值)可以写成!(!a || !b),例如。这不是说 && 是 "unneccesary" 吗？这是否意味着 所有 逻辑表达式只能使用 || 和 !？
如果可以，花点时间阅读 DeMorgan's Laws。
你会在那儿的阅读中找到答案，以及对逻辑证明的引用。
但本质上，答案是肯定的。
编辑：为了明确起见，我的观点是可以从逻辑上从 AND 表达式推断出 OR 表达式，反之亦然。逻辑等价和推理的规律还有很多，但我觉得这条最合适。
编辑 2：这是通过 truth-table 的证明，显示了以下表达式的逻辑等价性。
德摩根定律：!(!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 | _______________________________________________________
是的。
All logic gates can be made from NOR gates.
由于 NOR 门可以由 NOT 和 OR 构成，结果如下。
您所描述的是functional completeness。
这描述了一组足以"express all possible truth tables"的逻辑运算符。您的 Java 运算符集 {||, !} 就足够了；它对应于 "Minimal functionally complete operator sets".
全真集合table表示所有可能的4个布尔值集合，可以是2个布尔值之间运算的结果。因为布尔值有 2 个可能值，所以有 24，或 16 个可能的真值 tables.
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
这是 table 的真值 table 数字 (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 中没有对应的单个运算符。
是的，正如其他答案所指出的，由 || 和 ! 组成的运算符集是 functionally complete。这是一个建设性的证明，展示了如何使用它们来表达布尔变量 A 和 B:
- True:
A || !A - A NAND B:
!A || !B - B implies A:
!B || A - A implies B:
!A || B - A OR B:
A || B - Not B:
!B - Not A:
!A - A XOR B:
!(!A || B) || !(A || !B) - A XNOR B:
!(!A || !B) || !(A || B) - A:
A - B:
B - A NOR B:
!(A || B) - A does not imply B:
!(!A || B) - B does not imply A:
!(!B || A) - A AND B:
!(!A || !B) - False:
!(A || !A)
请注意，NAND 和 NOR 本身都是功能完整的（可以使用上面相同的方法证明），因此如果要验证一组运算符功能完整，足以证明您可以用它表达 NAND 或 NOR。
这是一张图表，显示了上面列出的每个连接词的 Venn diagrams：
[source]
是的，根据布尔代数，任何布尔函数都可以表示为最小项之和或最大项之积，称为规范范式。没有理由不能将这种逻辑应用于计算机科学中使用的相同运算符。
NAND and NOR 是通用的，它们可用于在任何地方构建您想要的任何逻辑操作；其他运算符以编程语言提供，以便于编写和制作可读代码。
此外，所有需要在电路中硬连线的逻辑操作也都是使用 NAND 或 NOR 专用 IC 开发的。