布尔表达式上的德摩根定律

Question

问题是：假设p、q和r是布尔变量。考虑以下表达式：

!(p && !q || r)
Which of the following expressions is equivalent to the given expression?
A. (p && r) || (!q && r)
B. (!p && !q) || (!p && r)
C. (!p || q ) && !r
D. (!p || q && !r)
E. (!p || q) || r

我把它解为D。但答案是C。布尔运算符的结合性定律是什么？有人能解释为什么它应该是C吗？

谢谢，Mita

Answer 1

布尔代数使用此运算符优先级：NOT、AND或

因此，原始表达式可以重写为：

!((p && !q) || r)
  ^--     ^-- new

而不改变意义。在否定后保留操作顺序：

!(p && !q) && !r
(!p || q) && !r

哪个是你的C）答案

Answer 2

请参阅德摩根定律，注意它仅在(P && Q)和(P || Q)上直接定义。

二进制运算符是左关联的，优先级为：(), !, &&, ||。

因此：

!(p && !q || r)      // start
!((p && !q) || r)    // explicitly grouping by precedence
(!(p && !q) && !r)   // by DM
(!p || q) && !r      // by DM

这到达了C，但我们无法执行D，因为这需要在&&上进行分配或调整括号以更改优先级。

Answer 3

我将使用PyEDA 回答

>>> from pyeda.inter import *
>>> f = Not(Or(And('p', '-q'), 'r'))
>>> ga = Or(And('p', 'r'), And('-q', 'r'))
>>> gb = Or(And('-p', '-q'), And('-p', 'r'))
>>> gc = And(Or('-p', 'q'), '-r')
>>> gd = Or('-p', And('q', '-r'))
>>> ge = Or(Or('-p', 'q'), 'r')
>>> for g in [ga, gb, gc, gd, ge]:
...     print(f.equivalent(g))
False
False
True
False
False
>>> expr2truthtable(f)
inputs: r q p
000 1
001 0
010 1
011 1
100 0
101 0
110 0
111 0
>>> expr2truthtable(gc)
inputs: r q p
000 1
001 0
010 1
011 1
100 0
101 0
110 0
111 0