Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

De Morgan's rules explained

Tags:

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

like image 745
Stefano Borini Avatar asked Jan 30 '10 16:01

Stefano Borini


People also ask

What are De Morgan's Law explain?

De Morgans law : The complement of the union of two sets is the intersection of their complements and the complement of the intersection of two sets is the union of their complements. These are called De Morgans laws. These are named after the mathematician De Morgan.

What is De Morgan law formula?

De Morgan's first law can be expressed as (AUB)' = A'∩B'. In set theory, these laws relate the intersection and union of sets by complements. In this article, we will learn De Morgan's first law statement and proof with many solved examples in detail.

What is DeMorgan's rule in logic?

It's called De Morgan's Law, after a famous logician, Augustus de Morgan. De Morgan's Law says that '(P and Q)' is logically equivalent to 'not (not P or not Q)'. If it's logically equivalent, then it should be that '(P and Q)' entails 'not (not P or not Q)' and that 'not (not P or not Q) entails '(P and Q)'.

What are the two laws of De Morgan theorem?

DeMorgan's first theorem states that two (or more) variables NOR´ed together is the same as the two variables inverted (Complement) and AND´ed, while the second theorem states that two (or more) variables NAND´ed together is the same as the two terms inverted (Complement) and OR´ed.


2 Answers

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.

like image 193
Greg Bacon Avatar answered Oct 03 '22 04:10

Greg Bacon


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

like image 43
Aaronaught Avatar answered Oct 03 '22 04:10

Aaronaught