Закон Де Моргана о булевом выражении

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, OR

Таким образом, исходное выражение можно переписать в виде:

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

без изменения смысла. Чтобы сохранить этот порядок действий после отрицания:

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

который является вашим C) ответ

Answer 2

См De Morgan's law и обратите внимание, что только непосредственно определена над (P && Q) и (P || Q).

Бинарные операторы: left-associative и precedence is: (), !, &&, ||.

Таким образом:

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

Это прибывает в C, но мы не можем получить сделать D, потому что это потребует distributing over && или регулировки скобку таким образом, что приоритет изменяется.

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