2.1 De Morgan’s Law

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\ffrac }[2]{\frac {\text {\footnotesize $#1$}}{\text {\footnotesize $#2$}}} \newcommand {\newrobustcmd }[0]{} \newcommand {\csshow }[1]{\begingroup \expandafter \endgroup \expandafter \show \csname #1\endcsname } \newcommand {\csmeaning }[1]{\ifcsname #1\endcsname \expandafter \meaning \csname #1\endcsname \else \detokenize {undefined}\fi } \newcommand {\ifdefmacro }[0]{} \newcommand {\ifdefparam }[0]{} \newcommand {\ifdefprotected }[0]{} \newcommand {\ifnumequal }[1]{\ifnumcomp {#1}=} \newcommand {\ifnumgreater }[1]{\ifnumcomp {#1}>} \newcommand {\ifnumless }[1]{\ifnumcomp {#1}<} \newcommand {\ifdimequal }[1]{\ifdimcomp {#1}=} \newcommand {\ifdimgreater }[1]{\ifdimcomp {#1}>} \newcommand {\ifdimless }[1]{\ifdimcomp {#1}<} \newcommand {\expandonce }[1]{\unexpanded \expandafter {#1}} \newcommand {\csexpandonce }[1]{\expandafter \expandonce \csname #1\endcsname } \newcommand {\protecting }[0]{} \newcommand {\csdef }[1]{\expandafter \def \csname #1\endcsname } \newcommand {\csedef }[1]{\expandafter \edef \csname #1\endcsname } \newcommand {\csgdef }[1]{\expandafter \gdef \csname #1\endcsname } \newcommand {\csxdef }[1]{\expandafter \xdef \csname #1\endcsname } \newcommand {\cslet }[2]{\expandafter \let \csname #1\endcsname #2} \newcommand {\letcs }[2]{\ifcsdef {#2} {\expandafter \let \expandafter #1\csname #2\endcsname } {\undef #1}} \newcommand {\csletcs }[2]{\ifcsdef {#2} {\expandafter \let \csname #1\expandafter \endcsname \csname #2\endcsname } {\csundef {#1}}} \newcommand {\csuse }[1]{\ifcsname #1\endcsname \csname #1\expandafter \endcsname \fi } \newcommand {\appto }[2]{\ifundef {#1} {\edef #1{\unexpanded {#2}}} {\edef #1{\expandonce #1\unexpanded {#2}}}} \newcommand {\eappto }[2]{\ifundef {#1} {\edef #1{#2}} {\edef #1{\expandonce #1#2}}} \newcommand {\gappto }[2]{\ifundef {#1} {\xdef #1{\unexpanded {#2}}} {\xdef #1{\expandonce #1\unexpanded {#2}}}} \newcommand {\xappto }[2]{\ifundef {#1} {\xdef #1{#2}} {\xdef #1{\expandonce #1#2}}} \newcommand {\preto }[2]{\ifundef {#1} {\edef #1{\unexpanded {#2}}} {\edef #1{\unexpanded {#2}\expandonce #1}}} \newcommand {\epreto }[2]{\ifundef {#1} {\edef #1{#2}} {\edef #1{#2\expandonce #1}}} \newcommand {\gpreto }[2]{\ifundef {#1} {\xdef #1{\unexpanded {#2}}} {\xdef #1{\unexpanded {#2}\expandonce #1}}} \newcommand {\xpreto }[2]{\ifundef {#1} {\xdef #1{#2}} {\xdef #1{#2\expandonce #1}}} \newcommand {\csappto }[1]{\expandafter \appto \csname #1\endcsname } \newcommand {\cseappto }[1]{\expandafter \eappto \csname #1\endcsname } \newcommand {\csgappto }[1]{\expandafter \gappto \csname #1\endcsname } \newcommand {\csxappto }[1]{\expandafter \xappto \csname #1\endcsname } \newcommand {\cspreto }[1]{\expandafter \preto \csname #1\endcsname } \newcommand {\csepreto }[1]{\expandafter \epreto \csname #1\endcsname } \newcommand {\csgpreto }[1]{\expandafter \gpreto \csname #1\endcsname } \newcommand {\csxpreto }[1]{\expandafter \xpreto \csname #1\endcsname } \newcommand {\csnumdef }[1]{\expandafter \numdef \csname #1\endcsname } \newcommand {\csnumgdef }[1]{\expandafter \numgdef \csname #1\endcsname } \newcommand {\csdimdef }[1]{\expandafter \dimdef \csname #1\endcsname } \newcommand {\csdimgdef }[1]{\expandafter \dimgdef \csname #1\endcsname } \newcommand {\csgluedef }[1]{\expandafter \gluedef \csname #1\endcsname } \newcommand {\csgluegdef }[1]{\expandafter \gluegdef \csname #1\endcsname } \newcommand {\mudef }[2]{\ifundef #1{\def #1{0mu}}{}\edef #1{\the \muexpr #2}} \newcommand {\csmudef }[1]{\expandafter \mudef \csname #1\endcsname } \newcommand {\csmugdef }[1]{\expandafter \mugdef \csname #1\endcsname } \newcommand {\listbreak }[0]{} \newcommand {\listadd }[2]{\ifblank {#2}{}{\appto #1{#2|}}} \newcommand {\listgadd }[2]{\ifblank {#2}{}{\gappto #1{#2|}}} \newcommand {\listcsadd }[1]{\expandafter \listadd \csname #1\endcsname } \newcommand {\listcseadd }[1]{\expandafter \listeadd \csname #1\endcsname } \newcommand {\listcsgadd }[1]{\expandafter \listgadd \csname #1\endcsname } \newcommand {\listcsxadd }[1]{\expandafter \listxadd \csname #1\endcsname } \newcommand {\dolistloop }[0]{\forlistloop \do } \newcommand {\dolistcsloop }[0]{\forlistcsloop \do } \newcommand {\AfterPreamble }[0]{\AtBeginDocument } \newcommand {\npnoround }[0]{\nprounddigits {-1}} \newcommand {\npnoroundexp }[0]{\nproundexpdigits {-1}} \newcommand {\npunitcommand }[1]{\ensuremath {\mathrm {#1}}} \newcommand {\RR }[0]{\mathbb R} \newcommand {\R }[0]{\mathbb R} \newcommand {\C }[0]{\mathbb C} \newcommand {\N }[0]{\mathbb N} \newcommand {\Z }[0]{\mathbb Z} \newcommand {\dis }[0]{\displaystyle } \newcommand {\d }[0]{\mathop {}\!d} \newcommand {\l }[0]{\ell } \newcommand {\ddx }[0]{\frac {d}{\d x}} \newcommand {\zeroOverZero }[0]{\ensuremath {\boldsymbol {\tfrac {0}{0}}}} \newcommand {\inftyOverInfty }[0]{\ensuremath {\boldsymbol {\tfrac {\infty }{\infty }}}} \newcommand {\zeroOverInfty }[0]{\ensuremath {\boldsymbol {\tfrac {0}{\infty }}}} \newcommand {\zeroTimesInfty }[0]{\ensuremath {\small \boldsymbol {0\cdot \infty }}} \newcommand {\inftyMinusInfty }[0]{\ensuremath {\small \boldsymbol {\infty -\infty }}} \newcommand {\oneToInfty }[0]{\ensuremath {\boldsymbol {1^\infty }}} \newcommand {\zeroToZero }[0]{\ensuremath {\boldsymbol {0^0}}} \newcommand {\inftyToZero }[0]{\ensuremath {\boldsymbol {\infty ^0}}} \newcommand {\numOverZero }[0]{\ensuremath {\boldsymbol {\tfrac {\#}{0}}}} \newcommand {\dfn }[0]{\textbf } \newcommand {\unit }[0]{\mathop {}\!\mathrm } \newcommand {\eval }[1]{ #1 \bigg |} \newcommand {\seq }[1]{\left ( #1 \right )} \newcommand {\epsilon }[0]{\varepsilon } \newcommand {\iff }[0]{\Leftrightarrow } \DeclareMathOperator {\arccot }{arccot} \DeclareMathOperator {\arcsec }{arcsec} \DeclareMathOperator {\arccsc }{arccsc} \DeclareMathOperator {\si }{Si} \DeclareMathOperator {\proj }{proj} \DeclareMathOperator {\scal }{scal} \DeclareMathOperator {\cis }{cis} \DeclareMathOperator {\Arg }{Arg} \DeclareMathOperator {\Rep }{Re} \DeclareMathOperator {\Imp }{Im} \DeclareMathOperator {\sech }{sech} \DeclareMathOperator {\csch }{csch} \DeclareMathOperator {\Log }{Log} \newcommand {\tightoverset }[2]{\mathop {#2}\limits ^{\vbox to -.5ex{\kern -0.75ex\hbox {$#1$}\vss }}} \newcommand {\arrowvec }[0]{\overrightarrow } \newcommand {\vec }[0]{\mathbf } \newcommand {\veci }[0]{{\boldsymbol {\hat {\imath }}}} \newcommand {\vecj }[0]{{\boldsymbol {\hat {\jmath }}}} \newcommand {\veck }[0]{{\boldsymbol {\hat {k}}}} \newcommand {\vecl }[0]{\boldsymbol {\l }} \newcommand {\utan }[0]{\vec {\hat {t}}} \newcommand {\unormal }[0]{\vec {\hat {n}}} \newcommand {\ubinormal }[0]{\vec {\hat {b}}} \newcommand {\dotp }[0]{\bullet } \newcommand {\cross }[0]{\boldsymbol \times } \newcommand {\grad }[0]{\boldsymbol \nabla } \newcommand {\divergence }[0]{\grad \dotp } \newcommand {\curl }[0]{\grad \cross } \newcommand {\vector }[1]{\left \langle #1\right \rangle } \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument }$

We use De Morgan’s Law to enumerate sets.

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

Union Given a sets $A$ and $B$ , their union is defined as $A \cup B = \{x \,|\, x \in A \text { or } x \in B \}$

Intersection Given a sets $A$ and $B$ , their intersection is defined as $A \cap B = \{x \,|\, x \in A \text { and } x \in B \}$

Inclusion-Exclusion Principle (for two sets) Given sets $A$ and $B$ with finite cardinalities $|A|$ and $|B|$ , we have $|A \cup B| = |A| + |B| - |A \cap B|$

Proof: Let $x \in A \cup B$ . Then $x$ is in $A, B$ or both.
Case 1. ( $x$ is in both) If $x$ is in both $A$ and $B$ , then the right hand side of the formula accounts for $x$ twice, once as an element of $A$ and again as an element of $B$ . But then, since $x$ is in both $A$ and $B$ , $x$ is in their intersection, $A \cap B$ . The coefficient of $|A \cap B|$ being $-1$ , $x$ is “de-accounted” for once in the right hand side of the formula. In total, $x$ is accounted for twice and de-accounted for once, thereby accounting for it just once in total.
Case 2. ( $x$ is in $A$ only) If $x \in A$ but $x \notin B$ , then the right hand side of the formula accounts for such $x$ exactly once, as a member of $A$ . Note that such an $x$ is not a member of $A \cap B$ and so it is not de-accounted for by the right hand side of the formula.
Case 3. ( $x$ is in $B$ only) This is the same as case 2 with the roles of $A$ and $B$ reversed.
Finally, we need to be sure that the right hand side of the formula does not count elements that are not in $A \cup B$ .
Case 4. ( $x$ is in neither $A$ nor $B$ ) In this case, none of the terms on the right hand side of the formula will either account for or de-account for $x$ (since $x \notin A \cap B$ either). $\blacksquare$

In our discussion of partitions, we did not have a subtraction term. This is because for each pair of sets in a partition, $S_i \cap S_j = \emptyset$ and hence $|S_i \cap S_j| = 0$ .

example 1 How many numbers in the set $S = \{1,2,3, \ldots , 1000\}$ are multiples of either 2 or 5?
Let $A$ be the subset of $S$ consisting of the multiples of 2, and $B$ be the subset of $S$ consisting of the multiples of 5. We seek $|A \cup B|$ . According to the proposition, $|A \cup B| = |A| + |B| - |A \cap B|$ We have $|A| =500$ and $|B| = 200$ and $|A \cap B| = 100$ since the set $A \cap B$ consists of the multiples of 10. Using the Inclusion-Exclusion Principle (for two sets), we can conclude that the number of elements of $S$ that are either multiples of 2 or 5 is $|A \cup B| = 500 + 200 - 100 = 600$

(problem 1) How many numbers from the given set $S= \{1,2,3, \ldots , 1000\}$ are multiples of the given numbers $a$ and $b$ ?
a) $\; a = 4, b = 5 \;\; \answer {400}$
b) $\; a = 7, b = 12 \;\; \answer {214}$
c) $\; a = 6, b = 10 \;\; \answer {233}$
d) $\; a = 18, b = 30 \;\; \answer {77}$

Recall set complements from section 1.2:

Complement Given a universal set $U$ and a subset, $A \subset U$ , we define the complement of $A$ , denoted, $A^c$ by $A^c = \{x \in U | x \notin A \}$

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

De Morgan’s Law Given sets $A$ and $B$ in a universal set $U$ , De Morgan’s Law states that $\left (A \cup B\right )^c = A^c \cap B^c$

Proof: First, let $x \in (A \cup B)^c$ . Then $x \notin A \cup B$ which implies that $x \notin A$ and $x \notin B$ . By definition of complement, this means that $x \in A^c$ and $x \in B^c$ . Finally, by definition of intersection, $x \in A^c \cap B^c$ . Thus $(A \cup B)^c \subseteq A^c \cap B^c$ .
Next, let $x \in A^c \cap B^c$ . By definition of intersection, $x \in A^c$ and $x \in B^c$ . Then, $x \notin A$ and $x \notin B$ which implies that $x \notin A \cup B$ . Thus $x \in (A \cup B)^c$ and we have shown that $A^c \cap B^c\subseteq (A \cup B)^c$ .
By virtue of being subsets of each other, the two sets are equal and De Morgan’s Law is proved. $\blacksquare$

There are actually two of De Morgan’s Laws. The second is $\left (A \cap B\right )^c = A^c \cup B^c$ The proof of this second law follows immediately from the first law by replacing $A$ and $B$ with $A^c$ and $B^c$ and using the fact that $(S^c)^c = S$ for any set $S$ .

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

example 2 Computer passwords are eight characters long where a character can be either an upper case letter, lower case letter, digit 0-9, or one of 8 special symbols. How many passwords are possible if a password must contain at least one digit and at least one special symbol?

Let $A$ be the set of passwords that do not contain any digits and let $B$ 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 $|A^c \cap B^c|$ . By De Morgan’s Law, $A^c \cap B^c = (A \cup B)^c$ Then according to the Rule for Complements, $|(A \cup B)^c| = |S| - |A \cup B|,$ where $S$ 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 $|A^c \cap B^c| = |S| - |A| - |B| + |A\cap B|$ 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, $|S| = 70^8, \; |A| = 60^8, \; |B| = 62^8 \; \text { and } \; |A\cap B| = 52^8$ Note that the passwords in the set $A \cap B$ do not contain either digits or special symbols, so there are $70-10-8 = 52$ available characters for them. In conclusion, the number of acceptable passwords is $70^8 - 60^8 - 62^8 + 52^8 \approx 243638122947000$

(problem 2) Computer passwords are eight characters long where a character can be either an upper case letter, lower case letter, digit 0-9, or one of 8 special symbols. How many passwords are possible if a password must contain:
a) at least one digit and at least one upper case letter? $\; \answer {70^8 - 60^8 - 44^8 + 34^8}$
b) at least one special symbol and at least one lower case letter? $\; \answer {70^8 - 62^8 - 44^8 + 36^8}$
c) at least one letter? $\; \answer {70^8 - 18^8}$

example 3 How many permutations are there of the letters in the phrase MATH ROCKS in which neither the word MATH nor the word ROCKS appears?
Such permutations include MRAOTCHKS and SKCORHTAM, but not RKMATHSOC, HROCKSMTA, or ROCKSMATH. Let $A$ be the set of permutations which include the word MATH and let $B$ be the set of permutations which include the word ROCKS. We seek $|A^c \cap B^c|$ . By De Morgan’s Law, this is the same as $|(A \cup B)^c|$ . Let $S$ 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 $A$ is the number of permutations of the symbols MATH, R, O, C, K, S. Since this is 6 distinct symbols, $|A| = 6!$ . The number of elements in $B$ is the number of permutations of the symbols M, A, T, H, ROCKS. Since this is 5 distinct symbols, $|B| = 5!$ . The number of elements in $A \cap B$ is 2 and the number of elements in $S$ is $9!$ . 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 $|A^c \cap B^c| = 9! - 6! - 5! + 2 = 362042$

(problem 3) How many permutations are there of the letters in the phrase DOGS RULE in which neither the word DOGS nor the word RULE appears? $\; \answer {40082}$

example 4 How many permutations are there of the numbers 1-7 such that the 1 is not in the first position and the 2 is not in the second position?
Let $A$ be the permutations with 1 in the first position, $B$ be the permutations with 2 in the second position and $S$ be the set of all permutations. We seek $|A^c \cap B^c|$ . 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*}$

(problem 4) How many permutations are there of the letters in the word ABCDEF in which the letter A is not first and the letter F is not last? $\; \answer {504}$

example 5 How many non-negative integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 20$ if $x_1 \leq 4$ and $x_2 \leq 3$ ?
With no restrictions on the variables (except that they be non-negative integers), the total number of solutions is $C(24, 20)$ by the stars and bars method. Let $A$ be the set of all solutions which have $x_1 > 4$ and let $B$ be the set of all solutions with $x_2 > 3$ . We wish to find $|A^c \cap B^c|$ . 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 $S$ is the set of all non-negative integer solutions. By letting $y_1 = x_1 -5$ , we see that the number of elements in the set $A$ is the number of non-negative integer solutions to the equation: $y_1 + x_2 + x_3 + x_4 + x_5 = 15$ which is $C(19, 15)$ . By letting $y_2 = x_2 -4$ , we see that the number of elements in the set $B$ is the number of non-negative integer solutions to the equation: $x_1 + y_2 + x_3 + x_4 + x_5 = 16$ which is $C(20, 16)$ . Finally, by letting $y_1 = x_1 -5$ and $y_2 = x_2 -4$ we see that the number of elements in the set $A \cap B$ is the number of non-negative integer solutions to the equation: $y_1 + y_2 + x_3 + x_4 + x_5 = 11$ which is $C(15, 11)$ . Thus the total number of non-negative integer solutions to the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 20$ with $x_1 \leq 4$ and $x_2 \leq 3$ is $|A^c \cap B^c| = \binom {24}{20} - \binom {19}{15} - \binom {20}{16} + \binom {15}{11} = 3270$

(problem 5) How many non-negative integer solutions are there to the equation $x + y + z + w = 12$ if $y < 5$ and $w \leq 2 ? \; \answer {150}$