De Morgan's Laws
De Morgan's Laws describe how mathematical statements and concepts are related through their opposites. In set theory, De Morgan's Laws relate the intersection and union of sets through complements. In propositional logic, De Morgan's Laws relate conjunctions and disjunctions of propositions through negation. De Morgan's Laws are also applicable in computer engineering for developing logic gates.
Interestingly, regardless of whether De Morgan's Laws apply to sets, propositions, or logic gates, the structure is always the same.
De Morgan's Laws
Not (A and B) is the same as Not A or Not B.
Not (A or B) is the same as Not A and Not B.
This same structure can be used to make observations in cardinality of sets, to calculate certain probabilities, and to write equivalent propositions.
Contents
De Morgan's Laws for Sets
For sets, De Morgan's Laws are simply observations about the relation between sets and their complements. An easy way to visualize these rules is through Venn Diagrams.
Observe the union of the complements of two sets. On a Venn Diagram, this union covers all space in the Venn Diagram except for the intersection of the two sets. Hence, De Morgan's Law for the complement of an intersection of two sets.
Complement of an Intersection of Two Sets
The complement of the intersection of sets \(A\) and \(B\) is equal to the union of \(A^c\) and \(B^c\).
A recent survey asked high school students whether or not they planned to go to the upcoming basketball game or the upcoming football game.
200 total students were surveyed.
58 students stated that they would miss at least one of the games (this includes the students that plan to miss both games).
How many students plan to attend both games?
Observe the intersection of the complements of two sets. On a Venn Diagram, this intersection covers all space in the Venn Diagram except for the union of the two sets. Hence, De Morgan's Law for the complement of a union of two sets.
Complement of a Union of Two Sets
The complement of the union of sets \(A\) and \(B\) is equal to the intersection of \(A^c\) and \(B^c\).
How many integers between 1 and 1000 (inclusive) are neither multiples of 2 nor multiples of 5?
De Morgan's Laws can be generalized to any number of sets.
Generalization of the Complement of an Intersection of Sets
Let \(\{A_1,\ A_2,\ \ldots ,\ A_{n-1},\ A_n\}\) be a set of \(n\) sets. The complement of the intersection of these sets is:
\[\left(\bigcap\limits_{k=1}^n{A_k}\right)^c=\bigcup\limits_{k=1}^n{A_k^c}\]
The \(\displaystyle\bigcap\) and \(\displaystyle\bigcup\) symbols above are used to represent an intersection or union of many sets. For example, suppose there are four sets: \(B_1\), \(B_2\), \(B_3\), and \(B_4\). The union of these sets could be represented by \((B_1\cup B_2\cup B_3\cup B_4)\). However, it could be represented more concisely with \(\displaystyle\bigcup\limits_{k=1}^4{B_k}\).
Generalization of the Complement of a Union of Sets
Let \(\{A_1,\ A_2,\ \ldots ,\ A_{n-1},\ A_n\}\) be a set of \(n\) sets. The complement of the union of these sets is:
\[\left(\bigcup\limits_{k=1}^n{A_k}\right)^c=\bigcap\limits_{k=1}^n{A_k^c}\]
Because these generalizations require finding the unions and intersections of many sets, it is important to consider the principle of inclusion and exclusion when calculating the cardinality of sets with De Morgan's Laws.
Let a tough-to-test composite be a positive integer that is composite, but not divisible by 2, nor 3, nor 5.
Given that there are 168 prime numbers between 1 and 1000, how many tough-to-test composite numbers are there between 1 and 1000?
Notes: 1 is neither prime nor composite. There are some tough-to-test composite numbers that many would recognize as composite. For example, 49 and 77.
De Morgan's Laws for Logical Propositions
De Morgan's Laws follow a similar structure for logical propositions. The language of these concepts can seem intimidating, but the concepts themselves are fairly straightforward.
Negation of the Conjunction of Propositions
The negation of the conjunction of two propositions \(p\) and \(q\) is equivalent to the disjunction of the negations of those propositions.
\[\neg(p\wedge q)\iff \neg p \vee \neg q\]
This can be confirmed with a truth table of the propositions \(p\) and \(q\):
\[\begin{array}{|c|c|c|c|c|c|c|} \hline p & q & \neg p & \neg q & p\wedge q & \neg(p\wedge q) & \neg p \vee \neg q \\ \hline \text{T} & \text{T} & \text{F} & \text{F} & \text{T} & \text{F} & \text{F} \\ \text{T} & \text{F} & \text{F} & \text{T} & \text{F} & \text{T} & \text{T} \\ \text{F} & \text{T} & \text{T} & \text{F} & \text{F} & \text{T} & \text{T} \\ \text{F} & \text{F} & \text{T} & \text{T} & \text{F} & \text{T} & \text{T} \\ \hline \end{array}\]
What is an equivalent statement to "The lawn needs mowed and the car needs washed, but I will not do both."?
The two propositions are "I will mow the lawn" and "I will wash the car." Simply change the statement to an "or" statement and negate each of these propositions:
"Either I will not mow the lawn or I will not wash the car."
Note that this statement leaves open the possibility that one of the chores is completed, and it is also possible that neither chores are completed.
Negation of the Disjunction of Propositions
The negation of the disjunction of two propositions \(p\) and \(q\) is equivalent to the conjunction of the negations of those propositions.
\[\neg(p\vee q)\iff \neg p \wedge \neg q\]
This can be confirmed with a truth table of the propositions \(p\) and \(q\):
\[\begin{array}{|c|c|c|c|c|c|c|} \hline p & q & \neg p & \neg q & p\vee q & \neg(p\vee q) & \neg p \wedge \neg q \\ \hline \text{T} & \text{T} & \text{F} & \text{F} & \text{T} & \text{F} & \text{F} \\ \text{T} & \text{F} & \text{F} & \text{T} & \text{T} & \text{F} & \text{F} \\ \text{F} & \text{T} & \text{T} & \text{F} & \text{T} & \text{F} & \text{F} \\ \text{F} & \text{F} & \text{T} & \text{T} & \text{F} & \text{T} & \text{T} \\ \hline \end{array}\]
What is an equivalent statement to, "It is not the case that the dog is brown or black."?
The two propositions are "The dog is brown" and "The dog is black." Simply change the statement to an "and" statement and negate each of these propositions:
"The dog is not brown and it is not black."
Alternatively, an equivalent statement can be constructed with "neither" and "nor":
"The dog is neither brown nor black."
De Morgan's Laws can be generalized to any number of propositions.
Generalization of the Negation of a Conjunction
Let \(\{p_1,\ p_2, \ldots,\ p_{n-1},\ p_n\}\) be a set of \(n\) propositions. The negation of the conjunction of these propositions is equivalent to the disjunction of their negations:
\[\neg\left(\bigwedge\limits_{k=1}^n{p_k}\right)\iff \bigvee\limits_{k=1}^n{\neg p_k}\]
Generalization of the Negation of a Disjunction
Let \(\{p_1,\ p_2, \ldots,\ p_{n-1},\ p_n\}\) be a set of \(n\) propositions. The negation of the disjunction of these propositions is equivalent to the conjunction of their negations:
\[\neg\left(\bigvee\limits_{k=1}^n{p_k}\right)\iff \bigwedge\limits_{k=1}^n{\neg p_k}\]
Application to Logic Gates
In computer engineering, a NAND logic gate is considered to be universal, meaning that any logic gate can be constructed solely from NAND gates. Having an understanding of De Morgan's Laws can help one understand how to make these constructions.
A NAND gate has two inputs, \(\text{A}\) and \(\text{B}\). Each of these inputs can have a value of \(1\) (for high) or \(0\) (for low).
The output, \(\text{Q}\), of a NAND gate is \(0\) only if both inputs are \(1\). Otherwise, the output is \(1\).
\[\begin{array}{cc|c} \text{A} & \text{B} & \text{Q} \\ \hline 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{array}\]
Construction of a NOT gate
A NOT gate negates a signal. If the input is \(1\), then the output will be \(0\), and vice versa.
Consider how a NOT gate can be constructed from a NAND gate. If the same signal, \(\text{A}\), is routed to both inputs of a NAND gate, then the inputs will look like either the top or bottom row of the truth table for NAND above. Thus, the NAND gate will produce the negated signal.
\[\begin{array}{c|c} \text{A} & \text{Q} \\ \hline 1 & 0 \\ 0 & 1 \\ \end{array}\]
Construction of an AND gate
An AND gate works just like a logical conjunction. If both input signals are \(1\), then the output signal is \(1\). Otherwise, the output signal is \(0\).
Consider how an AND gate can be constructed from NAND gates. Since a NAND gate produces the negation of an AND gate, it suffices to negate the signal again. This can be accomplished with the NOT construction above.
\[\begin{array}{cc|c} \text{A} & \text{B} & \text{Q} \\ \hline 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ \end{array}\]
Construction of an OR gate
An OR gate works just like a logical disjunction. If both input signals are \(0\), then the output signal is \(0\). Otherwise, the output signal is \(1\).
Consider how an OR gate can be constructed from NAND gates. In particular, consider how De Morgan's Laws can be applied. By De Morgan's Laws, A NAND B is equivalent to A̅ OR B̅ (The overline represents the negation of a signal). Thus, an OR gate can be constructed by negating each input of a NAND gate.
\[\begin{array}{cc|c} \text{A} & \text{B} & \text{Q} \\ \hline 1 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ \end{array}\]
Similarly, the NOT, AND, and OR gates can be constructed purely from NOR (negated OR) gates. NAND and NOR gates can also be used to construct the derived logic gates, XOR and XNOR. In fact, any truth table consisting of any number of inputs and outputs can be constructed solely from NAND gates or NOR gates.