17.7: De Morgan’s Laws

Last updated
Save as PDF

Page ID: 41406

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

A contemporary of Boole’s, Augustus De Morgan, formalized two rules of logic that had previously been known informally. They allow us to rewrite the negation of a conjunction as a disjunction, and vice-versa.

For example, suppose you want to schedule a meeting with two colleagues at \(4: 30 \mathrm{PM}\) on Friday, and you need both of them to be available at that time. What situation would make it impossible to have the meeting? It is NOT the case that colleague \(a\) is available AND colleague \(b\) is available: \(\sim(a \wedge b) .\) /This situation is equivalent to either colleague \(a\) NOT being available OR colleague \(b\) NOT being available: \(\sim a \vee \sim b\)

De Morgan's Laws

The negation of a conjunction is equivalent to the disjunction of the negation of the statements making up the conjunction. To negate an “and” statement, negate each part and change the “and” to “or”.

\(\sim(p \wedge q)\) is equivalent to \(\sim p \vee \sim q\)

The negation of a disjunction is equivalent to the conjunction of the negation of the statements making up the disjunction. To negate an “or” statement, negate each part and change the “or” to “and”.

\(\sim(p \vee q)\) is equivalent to \(\sim p \wedge \sim q\)

Example 28

For Valentine’s Day, you did not get your sweetie flowers or candy: Which of the following statements is logically equivalent?

You did not get them flowers or did not get them candy.
You did not get them flowers and did not get them candy.
You got them flowers or got them candy.

Solution

This statement does not go far enough; it leaves open the possibility that you got them one of the two things.
This statement is equivalent to the original; \(\sim (f \vee c)\) is equivalent to \(-f \wedge \sim c\)
This statement says that you got them something, but we know that you did not.

Try it Now 8

To serve as the President of the US, a person must have been born in the US, must be at least 35 years old, and must have lived in the US for at least 14 years. What minimum set of conditions would disqualify someone from serving as President?

Answer: Failing to meet just one of the three conditions is all it takes to be disqualified. A person is disqualified if they were not born in the US, or are not at least 35 years old, or have not lived in the US for at least 14 years. The key word here is “or” instead of “and”.