How to Prove and Apply De Morgan's Laws

De Morgan's Laws Proof and real world application.

De Morgan's Laws are transformational Rules for 2 Sets

1) Complement of the Union Equals the Intersection of the Complements

not (A or B) = not A and not B

2) Complement of the Intersection Equals the Union of the Complements

not (A and B) = not A or not B

Take 2 Sets A and B

Union = A U B ← Everything in A or B

Intersection = A ∩ B ← Everything in A and B

U = Universal Set (All possible elements in your defined universe)

Complement = A’ Everything not in A, but in the Universal Set

1. DeMorgan’s Laws Transformational Rules for 2 Sets Complement of the Union Equals the Intersection of the Complements not (A or B) = not A and not B Complement of the Intersection Equals the Union of the Complements not (A and B) = not A or not B ‹#›

2. DeMorgan’s Laws Visual ‹#›

3. Set Notation Refresher Take 2 Sets A and B Union = A U B ← Everything in A or B Intersection = A ∩ B ← Everything in A and B U = Universal Set (All possible elements in your defined universe) Complement = A’ Everything not in A, but in the Universal Set ‹#›

4. Prove DeMorgan’s Law #1 Complement of the Union Equals the Intersection of the Complements Let P = (A U B)' and Q = A' ∩ B' Let x be an arbitrary element of P then x ∈ P ⇒ x ∈ (A U B)' ⇒ x ∉ (A U B) ⇒ x ∉ A and x ∉ B ⇒ x ∈ A' and x ∈ B' ⇒ x ∈ A' ∩ B' ⇒ x ∈ Q ‹#›

5. Test Problem for DeMorgan’s Law #1 Complement of the Union Equals the Intersection of the Complements Take 2 sets A and B. (A U B)’ = A’ ∩ B’ U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = { 1, 2, 3, 4, 5 }, B = { 2, 4, 6 } A U B = { 1 , 2 , 3 , 4 , 5 , 6 }, (A U B)’ = {7, 8, 9, 10} A’ = {6, 7, 8, 9, 10}, B’ = {1, 3, 5, 7, 8, 9, 10} A’ ∩ B’ = {7, 8, 9, 10} ‹#›

6. Prove DeMorgan’s Law #2 Complement of the Intersection Equals the Union of the Complements Let P = (A ∩ B)' and Q = A' U B' Let x be an arbitrary element of P then x ∈ P ⇒ x ∈ (A ∩ B)' ⇒ x ∉ (A ∩ B) ⇒ x ∉ A or x ∉ B ⇒ x ∈ A' or x ∈ B' ⇒ x ∈ A' U B' ⇒ x ∈ Q ‹#›

7. Test Problem for DeMorgan’s Law #2 Complement of the Intersection Equals the Union of the Complements Take 2 sets A and B. (A ∩ B)’ = A’ U B’ U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} A = { 1, 2, 3, 4, 5 }, B = { 2, 4, 6 } A ∩ B = { 2, 4 }, (A ∩ B)’ = {1, 3, 5, 6, 7, 8, 9, 10} A’ = {6, 7, 8, 9, 10}, B’ = {1, 3, 5, 7, 8, 9, 10} A’ U B’ = {1, 3, 5, 6, 7, 8, 9, 10} ‹#›