deMorgan rules explained

Question

Could you please explain the deMorgan rules as simply as possible (e.g. to someone with only a secondary school mathematics background) ?

Answer 1

Not sure why I've retained this all these years, but it has proven useful on a number of occasions. Thanks to Mr Bailey, my grade 10 math teacher. He called it deMorgan's Theorem.

!(A || B) <==> (!A && !B)
!(A && B) <==> (!A || !B)

When you move the negation in or out of the brackets, the logical operator (AND, OR) changes.

Answer 2

We have two values: T and F.

We can combine these values in three ways: NOT, AND, and OR.

NOT is the simplest:

• NOT T = F
• NOT F = T

We can write this as a truth table:

when given.. | results in...
============================
           T | F
           F | T

For conciseness

x | NOT x
=========
T | F
F | T

Think of NOT as the complement, that is, it turns one value into the other.

AND works on two values:

x y | x AND y
=============
T T | T
T F | F
F T | F
F F | F

AND is T only when both its arguments (the values of x and y in the truth table) are T — and F otherwise.

OR is T when at least one of its arguments is T:

x y | x OR y
=============
T T | T
T F | T
F T | T
F F | F

We can define more complex combinations. For example, we can write a truth table for x AND (y OR z), and the first row is below.

x y z | x AND (y OR z)
======================
T T T | ?

Once we know how to evaluate x AND (y OR z), we can fill in the rest of the table.

To evaluate the combination, evaluate the pieces and work up from there. The parentheses show which parts to evaluate first. What you know from ordinary arithmetic will help you work it out. Say you have 10 - (3 + 5). First you evaluate the part in parentheses to get

10 - 8

and evaluate that as usual to get the answer, 2.

Evaluating these expressions works similarly. We know how OR works from above, so we can expand our table a little:

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | ?

Now it's almost like we're back to the x AND y table. We simply substitute the value of y OR z and evaluate. In the first row, we have

T AND (T OR T)

which is the same as

T AND T

which is simply T.

We repeat the same process for all 8 possible values of x, y, and z (2 possible values of x times 2 possible values of y times 2 possible values of z) to get

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | T
T T F | T      | T
T F T | T      | T
T F F | F      | F
F T T | T      | F
F T F | T      | F
F F T | T      | F
F F F | F      | F

Some expressions may be more complex than they need to be. For example,

x | NOT (NOT x)
===============
T | T
F | F

In other words, NOT (NOT x) is equivalent to just x.

DeMorgan's rules are handy tricks that let us convert between equivalent expressions that fit certain patterns:

• NOT (x AND y) = (NOT x) OR (NOT y)
• NOT (x OR y) = (NOT x) AND (NOT y)

(You might think of this as how NOT distributes through simple AND and OR expressions.)

Your common sense probably already understands these rules! For example, think of the bit of folk wisdom that "you can't be in two places at once." We could make it fit the first part of the first rule:

NOT (here AND there)

Applying the rule, that's another way of saying "you're not here or you're not there."

Exercise: How might you express the second rule in plain English?

For the first rule, let's look at the truth table for the expression on the left side of the equals sign.

x y | x AND y | NOT (x AND y)
=============================
T T | T       | F
T F | F       | T
F T | F       | T
F F | F       | T

Now the righthand side:

x y | NOT X | NOT Y | (NOT x) or (NOT y)
========================================
T T | F     | F     | F
T F | F     | T     | T
F T | T     | F     | T
F F | T     | T     | T

The final values are the same in both tables. This proves that the expressions are equivalent.

Exercise: Prove that the expressions NOT (x OR y) and (NOT x) AND (NOT y) are equivalent.