Skip to ContentGo to accessibility pageKeyboard shortcuts menu
OpenStax Logo
Contemporary Mathematics

2.6 De Morgan’s Laws

Contemporary Mathematics2.6 De Morgan’s Laws

Table of contents
  1. Preface
  2. 1 Sets
    1. Introduction
    2. 1.1 Basic Set Concepts
    3. 1.2 Subsets
    4. 1.3 Understanding Venn Diagrams
    5. 1.4 Set Operations with Two Sets
    6. 1.5 Set Operations with Three Sets
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  3. 2 Logic
    1. Introduction
    2. 2.1 Statements and Quantifiers
    3. 2.2 Compound Statements
    4. 2.3 Constructing Truth Tables
    5. 2.4 Truth Tables for the Conditional and Biconditional
    6. 2.5 Equivalent Statements
    7. 2.6 De Morgan’s Laws
    8. 2.7 Logical Arguments
    9. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Projects
      5. Chapter Review
      6. Chapter Test
  4. 3 Real Number Systems and Number Theory
    1. Introduction
    2. 3.1 Prime and Composite Numbers
    3. 3.2 The Integers
    4. 3.3 Order of Operations
    5. 3.4 Rational Numbers
    6. 3.5 Irrational Numbers
    7. 3.6 Real Numbers
    8. 3.7 Clock Arithmetic
    9. 3.8 Exponents
    10. 3.9 Scientific Notation
    11. 3.10 Arithmetic Sequences
    12. 3.11 Geometric Sequences
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  5. 4 Number Representation and Calculation
    1. Introduction
    2. 4.1 Hindu-Arabic Positional System
    3. 4.2 Early Numeration Systems
    4. 4.3 Converting with Base Systems
    5. 4.4 Addition and Subtraction in Base Systems
    6. 4.5 Multiplication and Division in Base Systems
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Projects
      5. Chapter Review
      6. Chapter Test
  6. 5 Algebra
    1. Introduction
    2. 5.1 Algebraic Expressions
    3. 5.2 Linear Equations in One Variable with Applications
    4. 5.3 Linear Inequalities in One Variable with Applications
    5. 5.4 Ratios and Proportions
    6. 5.5 Graphing Linear Equations and Inequalities
    7. 5.6 Quadratic Equations with Two Variables with Applications
    8. 5.7 Functions
    9. 5.8 Graphing Functions
    10. 5.9 Systems of Linear Equations in Two Variables
    11. 5.10 Systems of Linear Inequalities in Two Variables
    12. 5.11 Linear Programming
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  7. 6 Money Management
    1. Introduction
    2. 6.1 Understanding Percent
    3. 6.2 Discounts, Markups, and Sales Tax
    4. 6.3 Simple Interest
    5. 6.4 Compound Interest
    6. 6.5 Making a Personal Budget
    7. 6.6 Methods of Savings
    8. 6.7 Investments
    9. 6.8 The Basics of Loans
    10. 6.9 Understanding Student Loans
    11. 6.10 Credit Cards
    12. 6.11 Buying or Leasing a Car
    13. 6.12 Renting and Homeownership
    14. 6.13 Income Tax
    15. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  8. 7 Probability
    1. Introduction
    2. 7.1 The Multiplication Rule for Counting
    3. 7.2 Permutations
    4. 7.3 Combinations
    5. 7.4 Tree Diagrams, Tables, and Outcomes
    6. 7.5 Basic Concepts of Probability
    7. 7.6 Probability with Permutations and Combinations
    8. 7.7 What Are the Odds?
    9. 7.8 The Addition Rule for Probability
    10. 7.9 Conditional Probability and the Multiplication Rule
    11. 7.10 The Binomial Distribution
    12. 7.11 Expected Value
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Formula Review
      4. Projects
      5. Chapter Review
      6. Chapter Test
  9. 8 Statistics
    1. Introduction
    2. 8.1 Gathering and Organizing Data
    3. 8.2 Visualizing Data
    4. 8.3 Mean, Median and Mode
    5. 8.4 Range and Standard Deviation
    6. 8.5 Percentiles
    7. 8.6 The Normal Distribution
    8. 8.7 Applications of the Normal Distribution
    9. 8.8 Scatter Plots, Correlation, and Regression Lines
    10. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  10. 9 Metric Measurement
    1. Introduction
    2. 9.1 The Metric System
    3. 9.2 Measuring Area
    4. 9.3 Measuring Volume
    5. 9.4 Measuring Weight
    6. 9.5 Measuring Temperature
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  11. 10 Geometry
    1. Introduction
    2. 10.1 Points, Lines, and Planes
    3. 10.2 Angles
    4. 10.3 Triangles
    5. 10.4 Polygons, Perimeter, and Circumference
    6. 10.5 Tessellations
    7. 10.6 Area
    8. 10.7 Volume and Surface Area
    9. 10.8 Right Triangle Trigonometry
    10. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  12. 11 Voting and Apportionment
    1. Introduction
    2. 11.1 Voting Methods
    3. 11.2 Fairness in Voting Methods
    4. 11.3 Standard Divisors, Standard Quotas, and the Apportionment Problem
    5. 11.4 Apportionment Methods
    6. 11.5 Fairness in Apportionment Methods
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  13. 12 Graph Theory
    1. Introduction
    2. 12.1 Graph Basics
    3. 12.2 Graph Structures
    4. 12.3 Comparing Graphs
    5. 12.4 Navigating Graphs
    6. 12.5 Euler Circuits
    7. 12.6 Euler Trails
    8. 12.7 Hamilton Cycles
    9. 12.8 Hamilton Paths
    10. 12.9 Traveling Salesperson Problem
    11. 12.10 Trees
    12. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  14. 13 Math and...
    1. Introduction
    2. 13.1 Math and Art
    3. 13.2 Math and the Environment
    4. 13.3 Math and Medicine
    5. 13.4 Math and Music
    6. 13.5 Math and Sports
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Formula Review
      4. Projects
      5. Chapter Review
      6. Chapter Test
  15. A | Co-Req Appendix: Integer Powers of 10
  16. Answer Key
    1. Chapter 1
    2. Chapter 2
    3. Chapter 3
    4. Chapter 4
    5. Chapter 5
    6. Chapter 6
    7. Chapter 7
    8. Chapter 8
    9. Chapter 9
    10. Chapter 10
    11. Chapter 11
    12. Chapter 12
    13. Chapter 13
  17. Index
A landscape view of a bridge built over a body of water.
Figure 2.12 De Morgan’s Laws were key to the rise of logical mathematical expression and helped serve as a bridge for the invention of the computer. (credit: modification of work “Golden Gate Bridge (San Francisco Bay, California, USA)” by James St. John/Flickr, CC BY 2.0)

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.

The contributions to logic made by Augustus De Morgan and George Boole during the 19th century acted as a bridge to the development of computers, which may be the greatest invention of the 20th century. Boolean logic is the basis for computer science and digital electronics, and without it the technological revolution of the late 20th and early 21st 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. But how did this logic get its name?

People in Mathematics

George Boole

A motherboard of a computer circuit.
Figure 2.13 Boole’s algebra of logic was foundational in the design of digital computer circuits. (credit: “Circuit Board” by Squeezyboy/Flickr, CC BY 2.0)

George Boole was born in Lincolnshire, England in 1815. He was the son of a cobbler who provided him some initial education, but Boole was mostly self-taught. He began teaching at 16 years of age, and opened his own school at the age of 20. In 1849, at the age of 34, he was appointed Professor of Mathematics at Queens College in Cork, Ireland. In 1853, he published the paper, An Investigation of the Laws of Thought, on Which Are Founded the Mathematical Theories of Logic and Probabilities, which is the treatise that the field of Boolean algebra and digital circuitry was built on.

Reference: Posamentier, Alfred and Spreitzer Christian, “Chapter 35 George Boole: English (1815-1864)” pp. 279-283, Math Makers: The Lives and Works of 50 Famous Mathematicians, Prometheus Books, 2019.

Negation of Conjunctions and Disjunctions

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

FORMULA

De Morgan’s Law for negation of a conjunction: ~(pq) ~p~q~(pq) ~p~q

De Morgan’s Law for the negation of a disjunction: ~(pq) ~p~q~(pq) ~p~q

Negation of a conditional: ~(pq) p~q~(pq) p~q

Writing conditional as a disjunction: pq ~pqpq ~pq

Checkpoint

Recall that the symbol for logical equivalence is: ..

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 2.26

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

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.

Your Turn 2.26

Write the negation of each statement in words without using the phrase, it is not the case that.
1.
Jackie played softball or she ran track.
2.
Brandon studied for his certification exam, and he passed 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, ~(pq)~(pq), is the conjunction of pp and not qq, p ~q.p ~q. Consider the truth table below for the negation of the conditional.

pp qq pqpq ~(pq)~(pq)
T T T F
T F F T
F T T F
F F T F

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

pp qq pqpq ~(pq)~(pq) ~q~q p ~qp ~q ~(pq)(p ~q)~(pq)(p ~q)
T T T F F F T
T F F T T T T
F T T F F F T
F F T F T F T

Example 2.27

Constructing the Negation of a Conditional Statement

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.

Your Turn 2.27

Write the negation of each conditional statement.
1.
If Edna Mode makes a new superhero costume, then it will not include a cape.
2.
If I had pancakes for breakfast, then I used maple syrup.

Example 2.28

Constructing the Negation of a Conditional Statement with Quantifiers

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.

Your Turn 2.28

Write the negation of each conditional statement.
1.
If some people like ice cream, then ice cream makers will make a profit.
2.
If Raquel cannot play video games, then nobody 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.

Property Conjunction (AND) Disjunction (OR)
Commutative pqqppqqp pqqppqqp
Associative (pq)rp(qr)(pq)rp(qr) (pq)rp(qr)(pq)rp(qr)
Distributive p(qr)(pq)(pr)p(qr)(pq)(pr) p(qr)(pq)(pr)p(qr)(pq)(pr)
De Morgan’s ~(pq) ~p~q~(pq) ~p~q ~(pq) ~p~q~(pq) ~p~q
Conditional ~(pq) p~q~(pq) p~q pq ~pqpq ~pq

Example 2.29

Negating a Conditional Statement with a Conjunction or Disjunction

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.

Your Turn 2.29

Write the negation of each conditional statement applying De Morgan’s Law.
1.
If Eric needs to replace the light bulb, then Marcus left the light on all night or Dan broke the bulb.
2.
If Trenton went to school and Regina went to work, then Merika cleaned the house.

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.

Example 2.30

Verifying De Morgan’s Law for Negation of a Conjunction

Construct a truth table to verify De Morgan’s Law for the negation of a conjunction, ~(pq) ~p~q~(pq) ~p~q, is valid.

Your Turn 2.30

1.
Construct a truth table to verify De Morgan’s Law for the negation of a disjunction, ~ ( p q ) ~ p ~ q , is valid.

Check Your Understanding

30.
De Morgan’s Law for the negation of a conjunction states that ~ ( p q ) is logically equivalent to ___________________.
31.
De Morgan’s Law for the negation of a disjunction states that ~ ( p q ) is logically equivalent to __________________.
32.
The negation of the conditional statement, ~ ( p q ) , is logically equivalent to _____________.
33.
~ ( ~ ( p q ) ) p q , which means the conditional statement is logically equivalent to ~ ( p ~ q ) . Apply _______________________ to the statement ~ ( p ~ q ) to show that the conditional statement p q ~ p q .

Section 2.6 Exercises

For the following exercises, use De Morgan’s Laws to write each statement without parentheses.
1 .
~ ( ~ p q )
2 .
~ ( ~ p ~ q )
3 .
~ ( p ~ q )
4 .
~ ( ~ p ~ q )
For the following exercises, use De Morgan’s Laws to write the negation of each statement in words without using the phrase, “It is not the case that, …”
5 .
Sergei plays right wing and Patrick plays goalie.
6 .
Mario is a carpenter, or he is a plumber.
7 .
Luigi is a plumber, or he is not a video game character.
8 .
Ralph Macchio was the original Karate Kid, and karate is not for defense only.
9 .
Some people like broccoli, but my siblings did not like broccoli.
10 .
Some people do not like chocolate or all people like pizza.
For the following exercises, write each statement as a conjunction or disjunction in symbolic form by applying the property for the negation of a conditional.
11 .
~ ( p q )
12 .
~ ( p ~ q )
13 .
~ ( ~ p q )
14 .
~ ( ~ p ~ q )
15 .
~ ( p q ~ r )
16 .
~ ( p q r )
17 .
~ ( p q ~ r )
18 .
~ ( p q r )
For the following exercises, write the negation of each conditional in words by applying the property for the negation of a conditional.
19 .
If a student scores an 85 on the final exam, then they will receive an A in the class.
20 .
If a person does not pass their road test, then they will not receive their driver’s license.
21 .
If a student does not do their homework, then they will not play video games.
22 .
If a commuter misses the bus, then they will not go to work today.
23 .
If a racecar driver gets pulled over for speeding, then they will not make it to the track on time for the race.
24 .
If Rene Descartes was a philosopher, then he was not a mathematician.
25 .
If George Boole invented Boolean algebra and Thomas Edison invented the light bulb, then Pacman is not the best video game ever.
26 .
If Jonas Salk created the polio vaccine, then his child received the vaccine or his child had polio.
27 .
If Billie Holiday sang the blues or Cindy Lauper sang about true colors, then John Lennon was not a Beatle.
28 .
If Percy Jackson is the lightning thief and Artemis Fowl is a detective, then Artemis Fowl will catch Percy Jackson.
29 .
If all rock stars are men, then Pat Benatar is not a rock star.
30 .
If Lady Gaga is a rock star, then some rock stars are women.
31 .
If yellow combined with blue makes green, then all colors are beautiful.
32 .
If leopards have spots and zebras have stripes, then some animals are not monotone in color.
For the following exercises, construct a truth table to verify that the logical property is valid.
33 .
p q ~ p q
34 .
p ~ q ~ p ~ q
35 .
~ p q p q
36 .
~ ( p ~ q ~ r ) p q r
Order a print copy

As an Amazon Associate we earn from qualifying purchases.

Citation/Attribution

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.

Attribution information
  • If you are redistributing all or part of this book in a print format, then you must include on every physical page the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
  • If you are redistributing all or part of this book in a digital format, then you must include on every digital page view the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
Citation information

© Apr 17, 2023 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.