Re: Using De Morgans to reduce a boolean expression

Posted by ouverson on Jul 29, 2021; 6:39pm
URL: http://nand2tetris-questions-and-answers-forum.52.s1.nabble.com/Using-De-Morgans-to-reduce-a-boolean-expression-tp4036177p4036229.html

Thank you for your help, Bill. Not that you need to respond, but here was what I wrote out to help myself better understand the problem:

---

Algebraic laws:

Commutative laws:
x And y = y And x

Associative laws:
x And (y And z) = (x And y) And z
x Or (y Or z) = (x Or y) Or z

Distributive laws:
x And (y Or z) = (x And y) Or (x And z)
x Or (y And z) = (x Or y) And (x Or z)

De Morgans laws:
Not(x And y) = Not(x) Or Not(y)
Not(x Or y) = Not(x) And Not(y)

Idempotent laws:
x And x = x
x Or x = x

Example in the appendices of the 2nd edition and in a Coursera video:

"These algebraic laws can be used to simplify Boolean functions. For example, consider the function Not (Not (x) And Not (x Or y)).

Not(Not(x) And Note(x Or y)) = // by De Morgans:
Not(Not(x) And (Not(x) And Not(y))) = // by the associative law:
Not((Not(x) And Not(x)) And Not(y)) = // by the idempotent law:
Not(Not(x) And Not(y)) = // by De Morgans:
Not(Not(x)) Or Not(Not(y)) = by double negation:
x Or y"

I want to use algebraic laws to reduce the Or function so that only Not and And operators are present:

(DNF) of the Or function: (Not(a) And b) Or (a And (Not(b)) Or (a And b)

---

From the book:

"Reducing a Boolean expression into a simpler one is an art requiring experience and insight. Various reduction tools and techniques are available, but the problem remains challenging. In general, reducing a Boolean expression into its simplest form is an NP-hard problem."

So, maybe I just need to spend time playing around with various options.

Thanks again for taking the time!