Using De Morgans to reduce a boolean expression

[ouverson]

From the 2nd edition:

"Proof: According to De Morgan law, the Or operator can be expressed using the Not and And operators."

The disjunctive normal form (DNF) of the Or function:

(Not(a) And b) Or (a And (Not(b)) Or (a And b)

De Morgans:

Not(a Or b) = Not(a) And Not(b)

How would I apply De Morgans to reduce this expression using Not and And operators only?

P.S. If I could have asked this question in more accurate terms (or phrases) please let me know.

[WBahn]

Not completely sure of what you are trying to do.

What expression are you trying to reduce (i.e., what's your starting point) and what expression are you trying to reduce it to (i.e., what's your intended destination)?

Are you trying to prove de Morgan's theorem? By applying de Morgan's theorem, you are intrinsically accepting it as valid, so to prove that it is true, the one thing you can't do is apply it.

[WBahn]

Here's an intuitive "proof" of (this form) of de Morgan's that might help you out.

The definition of the Or operator is that it is True if ANY of the inputs is True.

This means that the only way for it to be false is for ALL of the inputs to be False.

Therefore, for two inputs a and b:

Not(a Or b) = Not(a) And Not(b)

[ouverson]

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!

[WBahn]

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.

[ouverson]

Thank you so much Bill for your expert help.

You have a gift for sharing just enough information so as to allow me the satisfaction of discovering the answer.

Have a good one!

[ouverson]

I'm able to eliminate the Or operators, but now I'm left with an expression that is quite long and (for me) quite difficult to solve.

// DNF of the Or function:
(Not(x) And y) Or (x And (Not(y)) Or (x And y)

// Assign variables to
a = Not(x) And y
b = x And Not(y)
c = x And y

// Solve a Or b using de Morgans
a Or b = Not(Not(a) And Not(b))

// Eliminate the final c using de Morgans
d = Not(Not(a) And Not(b))
d Or c = Not(Not(d) And Not(c))

// Now plug in d
Not(Not(Not(Not(a) And Not(b))) And Not(c))

// Now plug in a, b, and c
Not(Not(Not(Not(Not(x) And y) And Not(x And Not(y)))) And Not(x And y))

// Now start reducing
...

This is as far as I got.