~DeMorgan's laws basically say that the negation of an "OR" statement is an "AND" statement in both directions. Just be careful to use the complements of the statements correctly.

i.e., In symbols, the negation of  P OR Q  is (not P) AND (not Q)
       Also,  the negation of P AND Q is (not P) OR (not Q)
Also, the negation of   (not P) AND Q would be P OR (not Q)
Also, the negation of   P AND (not Q) would be (not P) OR Q
Also, the negation of   (not P) OR Q would be P AND (not Q)
Also, the negation of   P OR (not Q) would be (not P) AND Q

 

Example:  Take the statement: "I will go to the movies and eat popcorn".  The negation of this statement would be "I will not go to the movies or I will not eat popcorn".

 

Example:  Take the statement:  "The moon is made out of green cheese or I'm a monkey's uncle".  The negation would be:  "The moon is not made out of green cheese and I'm not a monkey's uncle".

 

Note:  Since an "if p, then q" statement is logically equivalent to a "(not p) or q" statement, DeMorgan gives us a way to find the negative of an implicitive statement as well.

 

Example:  Take the statement:  "If I take $100 to the mall, then I will spend it all".  The equivalent or statement would be:  "I do not take $100 to the mall or I will spend it all".

The negation would be:  "I take $100 to the mall and I do not spend it all".

Method used in proofs:  Show each side is a subset of the other

 

Prove:  (A union B)' = A' interesect B'. 

If x is a member of (A union B)', then x is not a member of (A union B)

So, x is not a member of A and x is not a member of B, so,

x is a member of A' and x is a member of B',  hence, x is a member of (A' intersect B' )

 

If x is a member of A' intersect B', then x is a member of A' and x is a member of B'.

So, x is not a member of A and x is not a member of B.

Hence, x is not a member of (A union B), so, x is a member of (A union B)'.

 

Since each side is a subset of the other, the sets contain the same elements,

therefore are =.

 

Prove:  ( A  intersect  B)'  =  A'  union  B'

If x is a member of  (A intersect B)', then x is not a member of (A intersect B)

So, one of the following must hold:

 

a) x is not a member of A and x is not a member of B

So, x is a member of A', thus x is a member of (A' union  B' )

 

b) x is a member of A and x is a member of B', so x is a member of (A' union B' )

 

c) x is a member of A' and x is a member of B', so x is a member of (A' union B' )

 

The result is the same in all cases.

 

Let x be a member of (A' union B' ). One of the following must hold:

 

a) x is a member of A' and x is a member of B'.

Then x is not a member of A and x is not a member of B.

so, x is not a member of (A intersect B). So, x is a member of (A intersect B)'.

 

b) x is a member of A' and x is a member of B.

Then x is not a member of A and x is a member of B.

so, x is not a member of ( A intersect B). So, x is a member of (A intersect B)'.

 

c) x is a member of A and x is a member of B'.

So, x is a member of A and x is not a member of B.

so, x is not a member of ( A intersect B). So, x is a member of  (A intersect B)'.

 

Therefore, we get the same result in each case.