Chapter 7 Logic
7.6 De Morgan’s Laws
Learning Objectives
By the end of this section, you will be able to:
- Use De Morgan’s laws to negate conjunctions and disjunctions
- Construct the negation of a conditional statement
- Use truth tables to evaluate De Morgan’s laws
The contributions to logic made by Augustus De Morgan and George Boole during the nineteenth century acted as a bridge to the development of computers, which may be the greatest invention of the twentieth century. Boolean logic is the basis for computer science and digital electronics, and without it the technological revolution of the late twentieth and early twenty-first centuries—including the creation of computer chips, microprocessors, and the Internet—would not have been possible. Every modern computer language uses Boolean logic statements, which are translated into commands understood by the underlying electronic circuits enabling computers to operate.
Negation of Conjunctions and Disjunctions
In a previous chapter we used a Venn diagram to prove De Morgan’s law for set complement over union. Because the complement of a set is analogous to negation and union is analogous to an or statement, there are equivalent versions of De Morgan’s laws for logic. (Recall that the symbol for logical equivalence is [latex]\equiv[/latex].)
De Morgan’s law for negation of a conjunction: [latex]\sim{(p \wedge q)}\equiv \sim{p} \vee \sim{q}[/latex]
De Morgan’s law for the negation of a disjunction: [latex]\sim{(p \vee q)} \equiv \sim{p} \wedge \sim{q}[/latex]
Negation of a conditional: [latex]\sim{(p \rightarrow q)} \equiv p \wedge \sim{q}[/latex]
Writing conditional as a disjunction: [latex]p \rightarrow q \equiv \sim{p} \vee q[/latex]
De Morgan’s laws allow us to write the negation of conjunctions and disjunctions without using the phrase “It is not the case that …” to indicate the parentheses. Avoiding this phrase often results in a written or verbal statement that is clearer or easier to understand.
Example 1
Write the negation of each statement in words without using the phrase “It is not the case that.”
a) Kristin is a biomedical engineer and Thomas is a chemical engineer.
Kristin is a biomedical engineer and Thomas is a chemical engineer has the form “[latex]p \wedge q[/latex],” where [latex]p[/latex] is the statement “Kristin is a biomedical engineer,” and [latex]q[/latex] is the statement “Thomas is a chemical engineer.” By De Morgan’s law, the negation of a conjunction, [latex]\sim{(p \wedge q)}[/latex], is logically equivalent to [latex]\sim{p} \vee \sim{q}[/latex]. [latex]\sim{p}[/latex] is “Kristen is not a biomedical engineer,” and [latex]\sim{q}[/latex] is “Thomas is not a chemical engineer.” By De Morgan’s law, the solution has the form”[latex]\sim{p} \vee \sim{q}[/latex]” so the answer is “Kristin is not a biomedical engineer or Tom is not a chemical engineer.”
b) A person had cake or they had ice cream.
A person had cake or they had ice cream has the form “[latex]p \vee q[/latex],” where [latex]p[/latex] is the statement “A person had cake” and [latex]q[/latex] is the statement “A person had ice cream.” By De Morgan’s law for the negations of a disjunction, [latex]\sim{(p \vee q)} \equiv \sim{p} \wedge \sim{q}[/latex]. The solution is the statement “A person did not have cake and they did not have ice cream.”
Exercise 1
a) Jackie played softball or she ran track.
b) Brandon studied for his certification exam, and he passed his exam.
Solution
a) Jackie did not play softball, and she did not run track.
b) Brandon did not study for his certification exam, or he did not pass his exam.
Negation of a Conditional Statement
The negation of any statement has the opposite truth values of the original statement. The negation of a conditional, [latex]\sim{(p \rightarrow q)}[/latex], is the conjunction of [latex]p[/latex] and not [latex]q[/latex], [latex]p \wedge \sim{q}[/latex].
Consider the truth table below for the negation of the conditional.
The only time the negation of the conditional statement is true is when [latex]p[/latex] is true, and [latex]q[/latex] is false. This means that [latex]\sim{(p \rightarrow q)}[/latex] is logically equivalent to [latex]p \wedge \sim{q}[/latex], as the following truth table demonstrates.
[latex]\begin{array}{|c|c|c|c|c|c|c|} \hline p&q&p\rightarrow q& \sim{(p \rightarrow q)} & \sim{q} & p \wedge \sim{q}& \sim{(p \rightarrow q)} \leftrightarrow (p \wedge \sim{q})\\ \hline \text{T}&\text{T}&\text{T}&\text{F}&\text{F}& \text{F}& \textbf{T} \\ \hline \text{T}&\text{F}&\text{F}&\text{T}&\text{T}&\text{T}&\textbf{T} \\ \hline \text{F}&\text{T}&\text{T}&\text{F}&\text{F}&\text{F}&\textbf{T} \\ \hline \text{F}&\text{F}&\text{T}&\text{F}&\text{T}&\text{F}&\textbf{T} \\ \hline \end{array}[/latex]
Example 2
Write the negation of each conditional statement.
a) If Adele won a Grammy, then she is a singer.
The negation of the conditional statement, [latex]p \rightarrow q[/latex], is the statement [latex]p \wedge \sim{q}[/latex]. The hypothesis of the conditional statement is [latex]p[/latex]: “Adele won a Grammy,” and the conclusion of the conditional statement is [latex]q[/latex]: “Adele is a singer.” The negation of the conclusion, [latex]\sim{q}[/latex], is the statement “She is not a singer.” Therefore, the answer is [latex]p \wedge \sim{q}[/latex]: “Adele won a Grammy, and she is not a singer.”
b) If Drew Brees played for the New Orleans Saints, then he did not win the Super Bowl.
The hypothesis is [latex]p[/latex]: “Drew Brees played for the New Orleans Saints,” and the conclusion of the conditional statement is [latex]q[/latex]: “He did not win the Super Bowl.” The negation of [latex]q[/latex] is the statement “He won the Super Bowl.” The negation of the conditional statement is equal to [latex]p \wedge \sim{q}[/latex]: “Drew Brees played for the New Orleans Saints, and he won the Super Bowl.”
Exercise 2
a) If Edna Mode makes a new superhero costume, then it will not include a cape.
b) If I had pancakes for breakfast, then I used maple syrup.
Solution
a) Edna Mode made a new superhero costume, and it includes a cape.
b) I had pancakes for breakfast, and I did not use maple syrup.
Example 3
Write the negation of each conditional statement.
a) If all cats purr, then my partner’s cat purrs.
The negation of the conditional statement [latex]p \rightarrow q[/latex] is the statement [latex]p \wedge \sim{q}[/latex]. The hypothesis of the conditional statement is [latex]p[/latex]: “All cats purr,” and the conclusion of the conditional statement is [latex]q[/latex]: “My partner’s cat purrs.” The negation of the conclusion, [latex]\sim{q}[/latex], is the statement “My partner’s cat does not purr.” Therefore, the answer is [latex]p \wedge \sim{q}[/latex]: “All cats purr, but my partner’s cat does not purr.”
b) If a penguin is a bird, then some birds do not fly.
The hypothesis is [latex]p[/latex]: “A penguin is a bird,” and the conclusion of the conditional statement is [latex]q[/latex]: “Some birds do not fly.” The negation of [latex]q[/latex] is the statement “All birds fly.” Therefore, the negation of the conditional statement is equal to [latex]p \wedge \sim{q}[/latex]: “A penguin is a bird, and all birds fly.”
Exercise 3
a) If some people like ice cream, then ice cream makers will make a profit.
b) If Raquel cannot play video games, then nobody will play video games.
Solution
a) Some people like ice cream, but ice cream makers will not make a profit.
b) Raquel cannot play video games, but somebody will play video games.
Many of the properties that hold true for number systems and sets also hold true for logical statements. The following table summarizes some of the most useful properties for analyzing and constructing logical arguments. These properties can be verified using a truth table.
[latex]\begin{array} {|c|c|c|} \hline \text{Property} & \text{Conjunction (AND)} & \text{Disjunction (OR)} \\ \hline \text{Commutative} & p\wedge q \equiv q\wedge p & p \vee q \equiv q \vee p \\ \hline \text{Associative} & (p \wedge q) \wedge r \equiv p \wedge (q \wedge r)& (p \vee q) \vee r \equiv p \vee(q \vee r)\\ \hline \text{Distributive} & p \wedge (q \wedge r) \equiv (p \wedge q) \vee (p \wedge r) & p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r) \\ \hline \text{De Morgan's} & \sim{(p\wedge q)} \equiv \sim{p} \vee \sim{q} & \sim{(p\vee q)} \equiv \sim{p} \wedge \sim{q} \\ \hline \text{Conditional} & \sim{(p\rightarrow q )} \equiv p \wedge \sim{q} & p \rightarrow q \equiv \sim{p} \vee q \\ \hline \end{array}[/latex]
Example 4
Write the negation of each conditional statement applying De Morgan’s law.
a) If Mom needs to buy chips, then Mike had friends over and Bob was hungry.
The conditional has the form “If [latex]p[/latex], then [latex]q[/latex] or [latex]r[/latex],” where [latex]p[/latex] is “Mom needs to buy chips,” [latex]q[/latex] is “Mike had friends over,” and [latex]r[/latex] is “Bob was hungry.” The negation of [latex]p \rightarrow (q \wedge r)[/latex] is [latex]p \wedge \sim{(q \wedge r)}[/latex]. Applying De Morgan’s law to the statement [latex]\sim{(q \wedge r)}[/latex], the result is [latex]\sim{q} \vee \sim{r}[/latex], so our conditional statement becomes [latex]p \wedge (\sim{q} \vee \sim{r})[/latex]. By the distributive property for conjunction over disjunction, this statement is equivalent to [latex](p \wedge \sim{q}) \vee (p \wedge \sim{r})[/latex]. Translating the statement [latex](p \wedge \sim{q}) \vee (p \wedge \sim{r})[/latex] into words, the solution is “Mom needs to buy chips and Mike did not have friends over, or Mom needs to buy chips and Bob was not hungry.”
b) If Juan had pizza or Chris had wings, then Dad watched the game.
The conditional has the form “If [latex]p[/latex] or [latex]q[/latex], then [latex]r[/latex],” where [latex]p[/latex] is “Juan had pizza, ” [latex]q[/latex] is “Chris had wings,” and [latex]r[/latex] is “Dad watched the game.” The negation of [latex](p \vee q) \rightarrow r[/latex] is [latex](p \vee q)\wedge \sim r[/latex]. By the distributive property for disjunction over conjunction, the statement is equivalent to [latex](p\vee \sim r)\wedge(q \vee \sim r)[/latex]. Translating the statement [latex](p \vee \sim r) \wedge (q \vee \sim r)[/latex] into words, the solution is “Juan had pizza or Dad did not watch the game, and Chris had wings or Dad did not watch the game.”
Exercise 4
Write the negation of each conditional statement applying De Morgan’s law.
a) If Eric needs to replace the light bulb, then Marcus left the light on all night or Dan broke the bulb.
b) If Trenton went to school and Regina went to work, then Merika cleaned the house.
Solution
a) Eric needs to replace the light bulb, and Marcos did not leave the light bulb on all night, and Dan did not break the light bulb.
b) Trenton went to school, and Regina went to work, and Merika did not clean the house.
Evaluating De Morgan’s Laws with Truth Tables
In Chapter 5, you learned that you could prove the validity of De Morgan’s laws using Venn diagrams. Truth tables can also be used to prove that two statements are logically equivalent. If two statements are logically equivalent, you can use the form of the statement that is clearer or more persuasive when constructing a logical argument.
The next example will prove the validity of one of De Morgan’s laws using a truth table. The same procedure can be applied to any two logical statements that you believe are equivalent. If the last column of the truth table is a tautology, then the two statements are logically equivalent.
Example 5
Construct a truth table to verify De Morgan’s law for the negation of a conjunction, [latex]\sim (p \wedge q) \equiv \sim p \vee \sim q[/latex], is valid.
Step 1: To verify any logical equivalence, you must first replace the logical equivalence symbol, [latex]\equiv[/latex], with the biconditional symbol, [latex]\leftrightarrow[/latex]. The statement [latex]\sim (p \wedge q) \equiv \sim q \vee \sim q[/latex] becomes [latex]\sim (p \wedge q) \leftrightarrow \sim p \vee \sim q[/latex].
Step 2: Next, you create a truth table for the statement. Because we have two basic statements, [latex]p[/latex] and [latex]q[/latex], the truth table will have four rows to account for all the possible outcomes. The columns will be [latex]p, q, \sim p, \sim q, p \wedge q, \sim (p \wedge q), \sim p \vee \sim q[/latex], and the biconditional statement is [latex]\sim (p \wedge q) \leftrightarrow \sim p \vee \sim q[/latex].
[latex]\begin{array}{|c|c|c|c|c|c|c|c|} \hline p&q&p\wedge q& \sim{(p \wedge q)} & \sim{p} & \sim{q} &\sim{p} \vee \sim{q}& \sim{(p \wedge q)} \leftrightarrow (\sim {p} \vee \sim{q})\\ \hline \text{T}&\text{T}&\text{T}&\text{F}&\text{F}&\text{F}& \text{F}& \textbf{T} \\ \hline \text{T}&\text{F}&\text{F}&\text{T}&\text{F}&\text{T}&\text{T}&\textbf{T} \\ \hline \text{F}&\text{T}&\text{F}&\text{T}&\text{T}&\text{F}&\text{T}&\textbf{T} \\ \hline \text{F}&\text{F}&\text{F}&\text{T}&\text{T}&\text{T}&\text{T}&\textbf{T} \\ \hline \end{array}[/latex]
Step 3: Finally, verify that the statement is valid by confirming it is a tautology. In this instance, the last column is all true. Therefore, the statement is valid, and De Morgan’s law for the negation of a conjunction is verified.
Exercise 5
Construct a truth table to verify De Morgan’s law for the negation of a disjunction, [latex]\sim (p \vee q) \equiv \sim p \wedge \sim q[/latex], is valid.
Solution
[latex]\begin{array}{|c|c|c|c|c|c|c|c|} \hline p&q&p\vee q& \sim{(p \vee q)} & \sim{p} & \sim{q} &\sim{p} \wedge \sim{q}& \sim{(p \vee q)} \leftrightarrow (\sim {p} \wedge \sim{q})\\ \hline \text{T}&\text{T}&\text{T}&\text{F}&\text{F}&\text{F}& \text{F}& \textbf{T} \\ \hline \text{T}&\text{F}&\text{T}&\text{F}&\text{F}&\text{T}&\text{F}&\textbf{T} \\ \hline \text{F}&\text{T}&\text{FT}&\text{F}&\text{T}&\text{F}&\text{F}&\textbf{T} \\ \hline \text{F}&\text{F}&\text{F}&\text{T}&\text{T}&\text{T}&\text{T}&\textbf{T} \\ \hline \end{array}[/latex]
A type of logic where results are determined as TRUE or FALSE which is the basis for computer science and digital electronics.
The negation of any statement has the opposite truth values of the original statement.
