CODEWITHSUNDEEP
boolean-expressiondemorgans-law
user3096748
user3096748

Reputation: 43

De Morgan's law on a boolean expression

I was given a test question:

Assume that p, q and r are boolean variables. Consider the following expression:

!(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

My answer was D, but the correct answer is C. Why? How does associativity work for these operators?

Upvotes: 1

Views: 2259

Answers (3)

Chris Drake
Chris Drake

Reputation: 393

I'm going to answer using 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

Upvotes: 0

user2864740
user2864740

Reputation: 61865

See De Morgan's law and note that it is only directly defined over (P && Q) and (P || Q).

The binary operators are left-associative and precedence is: (), !, &&, ||.

Thus:

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

This arrives at C, but we can't get do D because that would require distributing over && or adjusting the parenthesis such that the precedence is changed.

Upvotes: 1

Marc B
Marc B

Reputation: 360572

Boolean algebra uses this operator precedence: NOT, AND, OR

So the original expression can be rewritten as:

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

without changing meaning. To preserve that order of operations after the negation:

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

which is your C) answer

Upvotes: 3

Related Questions