De Morgan's rules explained

Question

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

Solution 1

Overview of boolean algebra

We have two values: T and F.

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

NOT

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

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

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

Combining

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

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.

Solution 2

Looking over some of the answers, I think I can explain it better by using conditions that are actually related to each other.

DeMorgan's Law refers to the fact that there are two identical ways to write any combination of two conditions - specifically, the AND combination (both conditions must be true), and the OR combination (either one can be true). Examples are:

Part 1 of DeMorgan's Law

Statement: Alice has a sibling.
Conditions: Alice has a brother OR Alice has a sister.
Opposite: Alice is an only child (does NOT have a sibling).
Conditions: Alice does NOT have a brother, AND she does NOT have a sister.

In other words: NOT [A OR B] = [NOT A] AND [NOT B]

Part 2 of DeMorgan's Law

Statement: Bob is a car driver.
Conditions: Bob has a car AND Bob has a license.
Opposite: Bob is NOT a car driver.
Conditions: Bob does NOT have a car, OR Bob does NOT have a license.

In other words: NOT [A AND B] = [NOT A] OR [NOT B].

I think this would be a little less confusing to a 12-year-old. It's certainly less confusing than all this nonsense about truth tables (even I'm getting confused looking at all of those).

Solution 3

It is just a way to restate truth statements, which can provide simpler ways of writing conditionals to do the same thing.

In plain English:
When something is not This or That, it is also not this and not that.
When something is not this and that, it is also not this or not that.

Note: Given the imprecision of the English language on the word 'or' I am using it to mean a non-exclusive or in the preceding example.

For example the following pseudo-code is equivalent:
If NOT(A OR B)...
IF (NOT A) AND (NOT B)....

IF NOT(A AND B)...
IF NOT(A) OR NOT(B)...

Solution 4

"He doesn't have either a car or a bus." means the same thing as "He doesn't have a car, and he doesn't have a bus."

"He doesn't have a car and a bus." means the same thing as "He either doesn't have a car, or doesn't have a bus, I'm not sure which, maybe he has neither."

Of course, in plain english "He doesn't have a car and a bus." has a strong implication that he has at least one of those two things. But, strictly speaking, from a logic standpoint the statement is also true if he doesn't have either of them.

Formally:

• not (car or bus) = (not car) and (not bus)
• not (car and bus) = (not car) or (not bus)

In english, 'or' tends to mean a choice, that you don't have both things. In logic, 'or' always means the same as 'and/or' in English.

Here's a truth table that shows how this works:

First case: not (cor or bus) = (not car) and (not bus)

 c | b || c or b | not (c or b) || (not c) | (not b) | (not c) and (not b)
---+---++--------+--------------++---------+---------+--------------------
 T | T ||    T   |      F       ||    F    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 T | F ||    T   |      F       ||    F    |    T    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | T ||    T   |      F       ||    T    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | F ||    F   |      T       ||    T    |    T    |        T
---+---++--------+--------------++---------+---------+--------------------

Second case: not (car and bus) = (not car) or (not bus)

 c | b || c and b | not (c and b) || (not c) | (not b) | (not c) or (not b)
---+---++---------+---------------++---------+---------+--------------------
 T | T ||    T    |       F       ||    F    |    F    |        F
---+---++---------+---------------++---------+---------+--------------------
 T | F ||    F    |       T       ||    F    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | T ||    F    |       T       ||    T    |    F    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | F ||    F    |       T       ||    T    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------

Solution 5

Draw a simple Venn diagram, two intersecting circles. Put A in the left and B in the right. Now (A and B) is obviously the intersecting bit. So NOT(A and B) is everything that's not in the intersecting bit, the rest of both circles. Colour that in.

Draw another two circles like before, A and B, intersecting. Now NOT(A) is everything that's in the right circle (B), but not the intersection, because that's obviously A as well as B. Colour this in. Similarly NOT(B) is everything in the left circle but not the intersection, because that's B as well as A. Colour this in.

Two drawings look the same. You've proved that NOT(A and B) = NOT(A) or NOT(B). T'other case is left as an exercise for the student.

View more solutions

Comments

[Anonymous]

I would rather phrase logical or as "either not this, (or) not that, or both" or "not this, not that, or neither". Though, it might be simpler and more productive at this level to concretely explain parenthetical grouping and use your second example!

[Stefano Borini]

Your answer walks you through logic algebra. Occasionally it gets a bit complex but it's very complete. It's almost ok, probably with some sectioning it would be even better. I don't know if it would pass the 15yo test, but for a smart 15yo I guess it's very fine.

[wjandrea]

@Stefano I added section headers