How to Prove De Morgan's Laws

math proof on board
Getty Images

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 AB.
  • 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 AC.

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

  1. (A ∩ B)C = AC U BC.
  2. (A U B)C = AC ∩ BC.

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 AC U BC.

    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 AC or BC.
    5. By definition this means that x is an element of AC U BC
    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 AC U BC is a subset of (A ∩ B)C.

    1. We begin with an element x in the set AC U BC.
    2. This means that x is an element of AC or that x is an element of BC.
    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.

    Format
    mla apa chicago
    Your Citation
    Taylor, Courtney. "How to Prove De Morgan's Laws." ThoughtCo, May. 24, 2017, thoughtco.com/how-to-prove-de-morgans-laws-3895999. Taylor, Courtney. (2017, May 24). How to Prove De Morgan's Laws. Retrieved from https://www.thoughtco.com/how-to-prove-de-morgans-laws-3895999 Taylor, Courtney. "How to Prove De Morgan's Laws." ThoughtCo. https://www.thoughtco.com/how-to-prove-de-morgans-laws-3895999 (accessed May 23, 2018).