How to Prove De Morgan's Laws

In mathematical statistics and probability it is important to be familiar with set theory. The elementary operations of set theory have connections with certain rules in the calculation of probabilities. The interactions of these elementary set operations of union, intersection and the complement are explain by two statements known as De Morgan’s Laws. After stating these laws, we will see how to prove them.

Statement of De Morgan’s Laws

De Morgan’s Laws relate to the interaction of the union, intersection and complement. Recall that:

• The intersection of the sets A and B consists of all elements that are common to both A and B. The intersection is denoted by A ∩ B.
• The union of the sets A and B consists of all elements that in either A or B, including the elements in both sets. The intersection is denoted by A U B.
• The complement of the set A consists of all elements that are not elements of A. This complement is denoted by A^C.

Now that we have recalled these elementary operations, we will see the statement of De Morgan’s Laws. For every pair of sets A and B

Read More

What Are De Morgan's Laws?

By Courtney Taylor

1. (A ∩ B)^C = A^C U B^C.
2. (A U B)^C = A^C ∩ B^C.

Outline of Proof Strategy

Before jumping into the proof we will think about how to prove the statements above. We are trying to demonstrate that two sets are equal to one another. The way that this is done in a mathematical proof is by the procedure of double inclusion. The outline of this method of proof is:

1. Show that the set on the left side of our equals sign is a subset of the set on the right.
2. Repeat the process in the opposite direction, showing that the set on the right is a subset of the set on the left.
3. These two steps allow us to say that the sets are in fact equal to one another. They consist of all of the same elements.

Proof of One of Laws

We will see how to prove the first of De Morgan’s Laws above. We begin by showing that (A ∩ B)^C is a subset of A^C U B^C.

1. First suppose that x is an element of (A ∩ B)^C.
2. This means that x is not an element of (A ∩ B).
3. Since the intersection is the set of all elements common to both A and B, the previous step means that x cannot be an element of both A and B.
4. This means that x is must be an element of at least one of the sets A^C or B^C.
5. By definition this means that x is an element of A^C U B^C
6. We have shown the desired subset inclusion.

Our proof is now halfway done. To complete it we show the opposite subset inclusion. More specifically we must show A^C U B^C is a subset of (A ∩ B)^C.

1. We begin with an element x in the set A^C U B^C.
2. This means that x is an element of A^C or that x is an element of B^C.
3. Thus x is not an element of at least one of the sets A or B.
4. So x cannot be an element of both A and B. This means that x is an element of (A ∩ B)^C.
5. We have shown the desired subset inclusion.

Proof of the Other Law

The proof of the other statement is very similar to the proof that we have outlined above. All that must be done is to show a subset inclusion of sets on both sides of the equals sign.