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

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.

Answer 2

"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
---+---++---------+---------------++---------+---------+--------------------

Answer 3

If you're a police officer looking for underage drinkers, you can do one of the following, and De Morgan's law says they amount to the same thing:

FORMULATION 1 (A AND B)

If they're under the age limit AND drinking an alcoholic beverage, arrest them.

FORMULATION 2 (NOT(NOT A OR NOT B))

If they're over the age limit OR drinking a non-alcoholic beverage, let them go.

This, by the way, isn't my example. As far as I know, it was part of a scientific experiment where the same rule was expressed in different ways to find out how much of a difference it made in peoples' ability to understand them.

Answer 4

DeMorgan's Law allows you to state a string of logical operations in different ways. It applies to logic and set theory, where in set theory you use complement for not, intersection for and, and union for or.

DeMorgan's Law allows you to simplify a logical expression, performing an operation that is rather similar to the distributive property of multiplication.

So, if you have the following in a C-like language

if !(x || y || z) { /* do something */ }

It is logically equivalent to:

if (!x && !y && !z)

It also works like so:

if !(x && !y && z)

turns into

if (!x || y || !z)

And you can, of course, go in reverse.

The equivalence of these statements is easy to see using something called a truth table. In a truth table, you simply lay out your variables (x, y, z) and list all the combinations of inputs for these variables. You then have columns for each predicate, or logical expression, and you determine for the given inputs, the value of the expression. Any university curriculum for computer science, computer engineering, or electrical engineering will likely drive you bonkers with the number and size of truth tables you must construct.

So why learn them? I think the biggest reason in computing is that it can improve readability of larger logical expressions. Some people don't like using logical not ! in front of expressions, as they think it can confuse someone if they miss it. The impact of using DeMorgan's Law on the gate level of chips is useful, however, because certain gate types are faster, cheaper, or you're already using a whole integrated circuit for them so you can reduce the number of chip packages required for the outcome.

Answer 5

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)...

Answer 6

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).