Re: Using De Morgans to reduce a boolean expression

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

One problem that I have with the authors' statement (that you have in bold) is that it isn't even defined what it means for a Boolean expression to be in "simplest form". What is the metric by which "simple" is evaluated?

If you are willing to accept de Morgan's theorems (they are theorems, not laws -- they can be proven using more fundamental identities), then the process is quite algorithmic.

Your DNF expression of the Or definition is of the form:

z = a Or b Or c

where a, b, and c are expressions that already involve only the Not and the And operators.

Write is as

z = (a Or b) or c

Now apply de Morgan's to (a Or b)

z = (Not( Not(a) And Not(b) )] Or c

Now apply de Morgan's again to eliminate the remaining Or operator.