maths.free › Discrete Math & Logic › 2. Logic › De Morgan’s Laws

De Morgan’s Laws

Use De Morgan’s Laws to negate conjunctions and disjunctions.

Learning Objectives

After completing this section, you should be able to:

  1. Use De Morgan’s Laws to negate conjunctions and disjunctions.
  2. Construct the negation of a conditional statement.
  3. Use truth tables to evaluate De Morgan’s Laws.

Negation of Conjunctions and Disjunctions

In Chapter 1, 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.

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.

Applying De Morgan’s Law for Negation of Conjunctions and Disjunctions

Try it.

Write the negation of each statement in words without using the phrase, “It is not the case that.”

  1. Kristin is a biomedical engineer and Thomas is a chemical engineer.
  2. A person had cake or they had ice cream.
Solution
  1. Kristin is a biomedical engineer and Thomas is a chemical engineer has the form “\(p∧q\),” where \(p\) is the statement, “Kristin is a biomedical engineer,” and \(q\) is the statement, “Thomas is a chemical engineer.” By De Morgan’s Law, the negation of a conjunction, \(\sim (p∧q)\), is logically equivalent to \(\sim p\ ∨\sim q.\) \(\sim p\) is “Kristen is not a biomedical engineer,” and \(\sim q\) is “Thomas is not a chemical engineer.” By De Morgan’s Law, the solution has the form “\(\sim p\ ∨\sim q\),” so the answer is: “Kristin is not a biomedical engineer or Tom is not a chemical engineer.”
  2. A person had cake or they had ice cream has the form “\(p∨q,\)” where \(p\) is the statement, “A person had cake,” and \(q\) is the statement, “A person had ice cream.” By De Morgan’s Law for the negations of a disjunction, \(\sim (p∨q)\ ≡\ \sim p\ ∧\sim q.\) The solution is the statement: “A person did not have cake and they did not have ice cream.”

Negation of a Conditional Statement

The negation of any statement has the opposite truth values of the original statement. The negation of a conditional, \(\sim (p\to q)\), is the conjunction of \(p\) and not \(q\), \(p\ ∧\sim q.\) Consider the truth table below for the negation of the conditional.

\(p\)\(q\)\(p\to q\)\(\sim (p\to q)\)
TTTF
TFFT
FTTF
FFTF

The only time the negation of the conditional statement is true is when \(p\) is true, and \(q\) is false. This means that \(\sim (p\to q)\) is logically equivalent to \(p∧\sim q,\) as the following truth table demonstrates.

\(p\)\(q\)\(p\to q\)\(\sim (p\to q)\)\(\sim q\)\(p∧\sim q\)\(\sim (p\to q)↔(p∧\sim q)\)
TTTFFFT
TFFTTTT
FTTFFFT
FFTFTFT
Constructing the Negation of a Conditional Statement

Try it.

Write the negation of each conditional statement.

  1. If Adele won a Grammy, then she is a singer.
  2. If Henrik Lundqvist played professional hockey, then he did not win the Stanley Cup.
Solution
  1. The negation of the conditional statement, \(p\to q,\) is the statement, \(p∧\sim q.\) The hypothesis of the conditional statement is \(p\): “Adele won a Grammy,” and conclusion of the conditional statement is \(q\): “Adele is a singer.” The negation of the conclusion, \(\sim q\), is the statement: “She is not a singer.” Therefore, the answer is \(p\ ∧\sim q:\) “Adele won a Grammy, and she is not a singer.”
  2. The hypothesis is \(p\): “Henrik Lundqvist played professional hockey,” and the conclusion of the conditional statement is \(q\): “He did not win the Stanley Cup.” The negation of \(q\) is the statement: “He won the Stanley Cup.” The negation of the conditional statement is equal to \(p\ ∧\sim q:\) “Henrick Lundqvist played professional hockey, and he won the Stanley Cup.”
Constructing the Negation of a Conditional Statement with Quantifiers

Try it.

Write the negation of each conditional statement.

  1. If all cats purr, then my partner’s cat purrs.
  2. If a penguin is a bird, then some birds do not fly.
Solution
  1. The negation of the conditional statement \(p\to q\) is the statement \(p∧\sim q.\) The hypothesis of the conditional statement is \(p\): “All cats purr,” and the conclusion of the conditional statement is \(q\): “My partner’s cat purrs.” The negation of the conclusion, \(\sim q\), is the statement: “My partner’s cat does not purr.” Therefore, the answer is \(p\ ∧\sim q:\) “All cats purr, but my partner’s cat does not purr.”
  2. The hypothesis is \(p\): “A penguin is a bird,” and the conclusion of the conditional statement is \(q\): “Some birds do not fly.” The negation of \(q\) is the statement: “All birds fly.” Therefore, the negation of the conditional statement is equal to \(p\ ∧\sim q:\) “A penguin is a bird, and all birds fly.”

Condensed — the full section is in OpenStax Contemporary Mathematics.

Evaluating De Morgan’s Laws with Truth Tables

In Chapter 1, 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 statement that you believe are equivalent. If the last column of the truth table is a tautology, then the two statements are logically equivalent.

Verifying De Morgan’s Law for Negation of a Conjunction

Try it.

Construct a truth table to verify De Morgan’s Law for the negation of a conjunction, \(\sim (p∧q)\ ≡\ \sim p∨\sim q\), is valid.

Solution

Step 1: To verify any logical equivalence, you must first replace the logical equivalence symbol, \(≡\), with the biconditional symbol, \(↔\). The statement \(\sim (p∧q)\ ≡\ \sim p\ ∨\sim q\) becomes \(\sim (p∧q)\ ↔\ \sim p\ ∨\sim q.\)
Step 2: Next, you create a truth table for the statement. Because we have two basic statements, \(p\), and \(q\), the truth table will have four rows to account for all the possible outcomes. The columns will be \(p\), \(q\), \(\sim p\), \(\sim q\), \(p∧q,\)\(\sim (p∧q),\)\(\sim p\ ∨\sim q,\) and the biconditional statement is \(\sim (p∧q)\ ↔\ \sim p\ ∨\sim q.\)

\(p\)\(q\)\(p∧q\)\(\sim (p∧q)\)\(\sim p\)\(\sim q\)\(\sim p∨\sim q\)\(\sim (p∧q)↔(\sim p∨\sim q)\)
TTTFFFFT
TFFTFTTT
FTFTTFTT
FFFTTTTT

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.

Key Concepts

  • De Morgan’s Law for the negation of a disjunction states that, \(\sim (p∨q)\) is logically equivalent to \(\sim p∧\sim q.\)
  • De Morgan’s Law The negation of a conjunction states that, \(\sim (p∧q)≡\sim p∨\sim q.\)
  • Use De Morgan’s Laws to negate conjunctions and disjunctions.
  • The negation of a conditional statement, if \(p\) then \(q\) is logically equivalent to the statement \(p\) and not \(q\). Use this property to write the negation of conditional statements.
  • Use truth tables to evaluate De Morgan’s Laws.

Practice (5)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Write the negation of each statement in words without using the phrase, “It is not the case that.”

    1. Kristin is a biomedical engineer and Thomas is a chemical engineer.
    2. A person had cake or they had ice cream.
    Cavabı göstər
    1. Kristin is a biomedical engineer and Thomas is a chemical engineer has the form “\(p∧q\),” where \(p\) is the statement, “Kristin is a biomedical engineer,” and \(q\) is the statement, “Thomas is a chemical engineer.” By De Morgan’s Law, the negation of a conjunction, \(\sim (p∧q)\), is logically equivalent to \(\sim p\ ∨\sim q.\) \(\sim p\) is “Kristen is not a biomedical engineer,” and \(\sim q\) is “Thomas is not a chemical engineer.” By De Morgan’s Law, the solution has the form “\(\sim p\ ∨\sim q\),” so the answer is: “Kristin is not a biomedical engineer or Tom is not a chemical engineer.”
    2. A person had cake or they had ice cream has the form “\(p∨q,\)” where \(p\) is the statement, “A person had cake,” and \(q\) is the statement, “A person had ice cream.” By De Morgan’s Law for the negations of a disjunction, \(\sim (p∨q)\ ≡\ \sim p\ ∧\sim q.\) The solution is the statement: “A person did not have cake and they did not have ice cream.”

  2. Write the negation of each conditional statement.

    1. If Adele won a Grammy, then she is a singer.
    2. If Henrik Lundqvist played professional hockey, then he did not win the Stanley Cup.
    Cavabı göstər
    1. The negation of the conditional statement, \(p\to q,\) is the statement, \(p∧\sim q.\) The hypothesis of the conditional statement is \(p\): “Adele won a Grammy,” and conclusion of the conditional statement is \(q\): “Adele is a singer.” The negation of the conclusion, \(\sim q\), is the statement: “She is not a singer.” Therefore, the answer is \(p\ ∧\sim q:\) “Adele won a Grammy, and she is not a singer.”
    2. The hypothesis is \(p\): “Henrik Lundqvist played professional hockey,” and the conclusion of the conditional statement is \(q\): “He did not win the Stanley Cup.” The negation of \(q\) is the statement: “He won the Stanley Cup.” The negation of the conditional statement is equal to \(p\ ∧\sim q:\) “Henrick Lundqvist played professional hockey, and he won the Stanley Cup.”

  3. Write the negation of each conditional statement.

    1. If all cats purr, then my partner’s cat purrs.
    2. If a penguin is a bird, then some birds do not fly.
    Cavabı göstər
    1. The negation of the conditional statement \(p\to q\) is the statement \(p∧\sim q.\) The hypothesis of the conditional statement is \(p\): “All cats purr,” and the conclusion of the conditional statement is \(q\): “My partner’s cat purrs.” The negation of the conclusion, \(\sim q\), is the statement: “My partner’s cat does not purr.” Therefore, the answer is \(p\ ∧\sim q:\) “All cats purr, but my partner’s cat does not purr.”
    2. The hypothesis is \(p\): “A penguin is a bird,” and the conclusion of the conditional statement is \(q\): “Some birds do not fly.” The negation of \(q\) is the statement: “All birds fly.” Therefore, the negation of the conditional statement is equal to \(p\ ∧\sim q:\) “A penguin is a bird, and all birds fly.”

  4. Write the negation of each conditional statement applying De Morgan’s Law.

    1. If mom needs to buy chips, then Mike had friends over and Bob was hungry.
    2. If Juan had pizza or Chris had wings, then dad watched the game.
    Cavabı göstər
    1. The conditional has the form “If \(p\) then \(q\) or \(r\),” where \(p\) is “Mom needs to buy chips,” \(q\) is “Mike had friends over,” and \(r\) is “Bob was hungry.” The negation of \(p\to (q∧r)\) is \(p∧\sim (q∧r).\) Applying De Morgan’s Law to the statement \(\sim (q∧r)\) the result is \(\sim q\ ∨\sim r\), so our conditional statement becomes \(p∧(\sim q∨\sim r).\) By the distributive property for conjunction over disjunction, this statement is equivalent to \((p∧\sim q)∨(p∧\sim r).\) Translating the statement \((p∧\sim q)∨(p∧\sim r)\) 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.”
    2. The conditional has the form “If \(p\) or \(q\), then \(r\),” where \(p\) is “Juan had pizza,” \(q\) is “Chris had wings,” and \(r\) is “Dad watched the game.” The negation of \((p∨q)\to r\) is \((p∨q)∧\sim r.\) By the distributive property for disjunction over conjuction, the statement is equivalent to \((p\ ∨\sim r)∧(q\ ∨\sim r).\) Translating the statement \((p\ ∨\sim r)∧(q\ ∨\sim r)\) 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.”

  5. Construct a truth table to verify De Morgan’s Law for the negation of a conjunction, \(\sim (p∧q)\ ≡\ \sim p∨\sim q\), is valid.

    Cavabı göstər

    Step 1: To verify any logical equivalence, you must first replace the logical equivalence symbol, \(≡\), with the biconditional symbol, \(↔\). The statement \(\sim (p∧q)\ ≡\ \sim p\ ∨\sim q\) becomes \(\sim (p∧q)\ ↔\ \sim p\ ∨\sim q.\)
    Step 2: Next, you create a truth table for the statement. Because we have two basic statements, \(p\), and \(q\), the truth table will have four rows to account for all the possible outcomes. The columns will be \(p\), \(q\), \(\sim p\), \(\sim q\), \(p∧q,\)\(\sim (p∧q),\)\(\sim p\ ∨\sim q,\) and the biconditional statement is \(\sim (p∧q)\ ↔\ \sim p\ ∨\sim q.\)

    \(p\)\(q\)\(p∧q\)\(\sim (p∧q)\)\(\sim p\)\(\sim q\)\(\sim p∨\sim q\)\(\sim (p∧q)↔(\sim p∨\sim q)\)
    TTTFFFFT
    TFFTFTTT
    FTFTTFTT
    FFFTTTTT

    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.

Symbols used here

n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.
\forall,\ \exists
for all, there exists
Quantifiers: every x; at least one x.
\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow
not, and, or, implies, iff
Logical connectives.
\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.
a \equiv b \pmod n
congruent modulo n
n divides a − b; a and b have the same remainder.
O(n^2),\ \Theta,\ \Omega
big-O notation
Grows no faster than n² (up to a constant), for large n.
a \bmod n
remainder
What is left after dividing a by n.

How to: De Morgan’s Laws

  1. Use De Morgan’s Laws to negate conjunctions and disjunctions.
  2. Construct the negation of a conditional statement.
  3. Use truth tables to evaluate De Morgan’s Laws.
  4. Kristin is a biomedical engineer and Thomas is a chemical engineer.
  5. A person had cake or they had ice cream.
  6. Kristin is a biomedical engineer and Thomas is a chemical engineer has the form “
  7. A person had cake or they had ice cream has the form “
  8. If Adele won a Grammy, then she is a singer.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

Özün sına

Parts of this page are adapted from OpenStax Contemporary Mathematics (CC BY-NC-SA 4.0). Condensed and re-explained here; errors are ours.

Daha çox Discrete Math & Logic

Truth tablesSums and inductionProof by inductionAlgorithms and growth of functions