We use De Morgan’s Law to enumerate sets.

We begin by counting the number of elements in the union of two sets.

- Proof
- Let . Then is in or both.

Case 1. ( is in both) If is in both and , then the right hand side of the formula accounts for twice, once as an element of and again as an element of . But then, since is in both and , is in their intersection, . The coefficient of being , is “de-accounted” for once in the right hand side of the formula. In total, is accounted for twice and de-accounted for once, thereby accounting for it just once in total.

Case 2. ( is in only) If but , then the right hand side of the formula accounts for such exactly once, as a member of . Note that such an is not a member of and so it is not de-accounted for by the right hand side of the formula.

Case 3. ( is in only) This is the same as case 2 with the roles of and reversed.

Finally, we need to be sure that the right hand side of the formula does not count elements that are not in .

Case 4. ( is in neither nor ) In this case, none of the terms on the right hand side of the formula will either account for or de-account for (since either).

Let be the subset of consisting of the multiples of 2, and be the subset of consisting of the multiples of 5. We seek . According to the proposition, We have and and since the set consists of the multiples of 10. Using the Inclusion-Exclusion Principle (for two sets), we can conclude that the number of elements of that are either multiples of 2 or 5 is

Recall set complements from section 1.2:

De Morgan’s Law gives us a formula for the complement of a union in terms of the intersection of their complements.

- Proof
- First, let . Then which implies that and . By definition of complement,
this means that and . Finally, by definition of intersection, . Thus .

Next, let . By definition of intersection, and . Then, and which implies that . Thus and we have shown that .

By virtue of being subsets of each other, the two sets are equal and De Morgan’s Law is proved.

The next example uses De Morgan’s Law in conjunction with the Rule for Complements and the Inclusion-Exclusion Principle (for two sets).

Let be the set of passwords that do not contain any digits and let be the set of passwords that do not contain any special symbols. Since our passwords must contain a digit and a special symbol, we seek . By De Morgan’s Law, Then according to the Rule for Complements, where is the set of all possible passwords with no restrictions. Combining the two equations above with the Inclusion-Exclusion Principle (for two sets), we have Each of the terms on the right hand side can be computed using the Fundamental Principle of Counting. Since there are 70 different characters in total with 10 digits and 8 special symbols, Note that the passwords in the set do not contain either digits or special symbols, so there are available characters for them. In conclusion, the number of acceptable passwords is

a) at least one digit and at least one upper case letter?

b) at least one special symbol and at least one lower case letter?

c) at least one letter?

Such permutations include MRAOTCHKS and SKCORHTAM, but not RKMATHSOC, HROCKSMTA, or ROCKSMATH. Let be the set of permutations which include the word MATH and let be the set of permutations which include the word ROCKS. We seek . By De Morgan’s Law, this is the same as . Let be the set of all permutations of the letters in the phrase. Then, applying the Rule for Complements, and the Inclusion-Exclusion Principle (for two sets), we have \begin{align*} |A^c \cap B^c| &= |(A \cup B)^c|\\ &= |S| - |A\cup B|\\ &= |S| - \Big (|A| + |B| -|A\cap B|\Big )\\ &= |S| - |A| - |B| + |A\cap B| \end{align*}

The number of elements in is the number of permutations of the symbols MATH, R, O, C, K, S. Since this is 6 distinct symbols, . The number of elements in is the number of permutations of the symbols M, A, T, H, ROCKS. Since this is 5 distinct symbols, . The number of elements in is 2 and the number of elements in is . Hence, the total number of ways to permute the letters in the phrase MATH ROCKS which do not include either of the words MATH or ROCKS is

Let be the permutations with 1 in the first position, be the permutations with 2 in the second position and be the set of all permutations. We seek . De Morgan’s Law, the Rule for Complements and the Inclusion-Exclusion Principle (for two sets) gives: \begin{align*} |A^c \cap B^c| &= |(A \cup B)^c|\\ &= |S| - |A\cup B|\\ &= |S| - \Big (|A| + |B| - |A\cap B|\Big )\\ &= |S| - |A| - |B| + |A\cap B|\\ &= 7! - 6! - 6! + 5!\\ &= 3720 \end{align*}

With no restrictions on the variables (except that they be non-negative integers), the total number of solutions is by the stars and bars method. Let be the set of all solutions which have and let be the set of all solutions with . We wish to find . De Morgan’s Law, the Rule for Complements and the Inclusion-Exclusion Principle (for two sets) gives: \begin{align*} |A^c \cap B^c| &= |(A \cup B)^c|\\ &= |S| - |A\cup B|\\ &= |S| - \Big (|A| + |B| - |A\cap B|\Big )\\ &= |S| - |A| - |B| + |A\cap B|\\ \end{align*}

where is the set of all non-negative integer solutions. By letting , we see that the number of elements in the set is the number of non-negative integer solutions to the equation: which is . By letting , we see that the number of elements in the set is the number of non-negative integer solutions to the equation: which is . Finally, by letting and we see that the number of elements in the set is the number of non-negative integer solutions to the equation: which is . Thus the total number of non-negative integer solutions to the equation with and is