是|| 而且!运营商是否有足够的逻辑表达式？
Jak*_*ake 294 logic logical-operators
逻辑表达式( a && b ) (包括a和b具有布尔值)可以写成像!(!a || !b),例如.这是不是意味着&&"不必要"？这是否意味着所有逻辑表达式只能使用||和!？
Pet*_*son 425
是的,正如其他答案所指出的那样,运营商包括||并且!在功能上是完整的.下面是一个建设性的证据,显示如何使用它们来表达布尔变量之间的所有十六个可能的逻辑连接词A和B:
- 真的:
A || !A - 一个NAND B:
!A || !B - B暗示A:
!B || A - A意味着B:
!A || B - A或B:
A || B - 不是B:
!B - 不是A:
!A - 一个XOR B:
!(!A || B) || !(A || !B) - A XNOR B:
!(!A || !B) || !(A || B) - 答:
A - B:
B - 一个NOR B:
!(A || B) - A并不意味着B:
!(!A || B) - B并不意味着A:
!(!B || A) - A和B:
!(!A || !B) - 错:
!(A || !A)
请注意,NAND和NOR本身在功能上都是完整的(可以使用上面相同的方法证明),因此如果您想验证一组运算符是否在功能上完整,那么足以表明您可以表达NAND或NOR用它.
这是一个图表,显示了上面列出的每个连接词的维恩图:
[ 来源 ]
- 很难说这个问题是否意味着这个问题,但这个答案并没有解决短路行为(相关问题,因为问题是关于`||`而不是`|`)或副作用(相关因为真实的扩展) ,false,XOR和XNOR比原始常量或运算符更多次评估它们的参数. (20认同)
- 包含圆圈和过渡的圆圈形成Hasse Diagram(https://en.wikipedia.org/wiki/Hasse_diagram).(是的,我今天学到了新东西!) (5认同)
- @DavidRicherby那是真的.除了XOR,XNOR,true和false之外,据我所知,副作用和评估次数应该与内置等价物相同(例如`!(!A ||!B)`相同的短路和评估计数为"A && B`".我不认为你可以在没有额外结构的情况下为XOR和XNOR做这个(例如`a？!b:b`),如果可以保存值,则true或false不是问题,因为你可以通过以下方式启动你的程序使用一些虚拟布尔变量定义`true`和`false`. (5认同)
rge*_*man 125
你所描述的是功能完整性.
这描述了一组足以"表达所有可能的真值表"的逻辑运算符.您的Java运算符集{ ||,!}就足够了; 它对应于集合{∨,¬},它列在"最小功能完整的运算符集"部分下面.
所有真值表的集合表示所有可能的4个布尔值集合,这些值可以是2个布尔值之间的操作的结果.因为布尔值有2个可能的值,所以有2 4或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中没有相应的单个运算符.
- 编辑+1.尽管投票数有所不同,但我认为你的答案实际上比我现在更详细. (4认同)
Pau*_*ton 80
是.
由于NOR门可以由NOT和OR构成,因此结果如下.
- @PaulDraper***或***与非门 (64认同)
- 它需要4100个NOR门才能让两个人登陆月球. (25认同)
- 是的,对不起,[阿波罗指导计算机](https://en.wikipedia.org/wiki/Apollo_Guidance_Computer#Design). (11认同)
- @HansPassant和一些字符串.很多字符串.(核心绳记忆,而不是锡罐的种类.) (4认同)
- @HansPassant有时我希望Stack Exchange是维基百科,然后我会在那里插入一个`[citation-needed]'标记. (3认同)
ryu*_*187 64
如果可以,请花点时间阅读DeMorgan的法律.
您可以在阅读中找到答案,并参考逻辑证明.
但基本上,答案是肯定的.
编辑:为了明确,我的观点是,可以从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 | _______________________________________________________
- 有些人不得不投票,作为他们"功能完整性"的一部分 (19认同)
- 在+ 27/-2时,我不会担心过度投票. (3认同)
- 一般来说,依赖于链接的答案不太受欢迎(因为链接死亡),但在这种情况下,任何对DeMorgan法律的替代解释都是如此之多,我没有看到问题 - 仍然,这是我对于DV的 (3认同)
- @MichaelKjörling我只是好奇为什么有些人认为我的回答没有帮助/有害. (2认同)
Mic*_*ski 10
是的,根据布尔代数,任何布尔函数都可以表示为minterms的总和或maxterms的乘积,称为规范正规形式.没有理由将这种逻辑应用于计算机科学中使用的相同运算符.
https://en.wikipedia.org/wiki/Canonical_normal_form
| 归档时间： |
|
| 查看次数： |
20799 次 |
| 最近记录： |