**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(AandB) is the same asNotAorNotB.

Not(AorB) is the same asNotAandNotB.

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
- De Morgan's Laws for Logical Propositions
- Application to Logic Gates

## 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 SetsThe 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 SetsThe complement of the union of sets \(A\) and \(B\) is equal to the intersection of \(A^c\) and \(B^c\).

300 400 600 900

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 SetsLet \(\{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 SetsLet \(\{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 PropositionsThe 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|}\hlinep & 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 PropositionsThe 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|}\hlinep & 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 ConjunctionLet \(\{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 DisjunctionLet \(\{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 gatehas two inputs, \(\text{A}\) and \(\text{B}\). Each of these inputs can have a value of \(1\) (forhigh) or \(0\) (forlow).

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} \\\hline1 & 1 & 0 \\1 & 0 & 1 \\0 & 1 & 1 \\0 & 0 & 1 \\\end{array}\]

Construction of a NOT gateA

NOT gatenegates a signal. If the input is \(1\), then the output will be \(0\), andvice 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} \\\hline1 & 0 \\0 & 1 \\\end{array}\]

Construction of an AND gateAn

AND gateworks 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} \\\hline1 & 1 & 1 \\1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 0 \\\end{array}\]

Construction of an OR gateAn

OR gateworks 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 Bis equivalent toA̅ 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} \\\hline1 & 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.