We've updated our
Privacy Policy effective December 15. Please read our updated Privacy Policy and tap

TEXT
Unlock Solution Steps
Sign in to
Symbolab
Get full access to all Solution Steps for any math problem
By continuing, you agree to our Terms of Use
and have read our Privacy Policy

Study Guides > Mathematics for the Liberal Arts

DeMorgan's Laws

Learning Outcomes

  • Combine sets using Boolean logic, using proper notations
  • Use statements and conditionals to write and interpret expressions
  • Use a truth table to interpret complex statements or conditionals
  • Write truth tables given a logical implication, and it’s related statements – converse, inverse, and contrapositive
  • Determine whether two statements are logically equivalent
  • Use DeMorgan’s laws to define logical equivalences of a statement
There are two pairs of logically equivalent statements that come up again and again in logic. They are prevalent enough to be dignified by a special name: DeMorgan’s laws. The laws are named after Augustus De Morgan (1806–1871), who introduced a formal version of the laws to classical propositional logic. De Morgan's formulation was influenced by algebraization of logic undertaken by George Boole, which later cemented De Morgan's claim to the find. Nevertheless, a similar observation was made by Aristotle, and was known to Greek and Medieval logicians. For example, in the 14th century, William of Ockham wrote down the words that would result by reading the laws out. Jean Buridan, in his Summulae de Dialectica, also describes rules of conversion that follow the lines of De Morgan's laws. Still, De Morgan is given credit for stating the laws in the terms of modern formal logic, and incorporating them into the language of logic. De Morgan's laws can be proved easily, and may even seem trivial. Nonetheless, these laws are helpful in making valid inferences in proofs and deductive arguments.

DeMorgan’s Laws

  1. [latex]\sim\left(P{\wedge}Q\right)=({\sim}P)\vee\left(\sim{Q}\right)[/latex]
  2. [latex]\sim\left(P\vee{Q}\right)=\left(\sim{P}\right)\wedge\left(\sim{Q}\right)[/latex]
The first of DeMorgan’s laws is verified by the following table. You are asked to verify the second in an exercise.
[latex]P[/latex] [latex]Q[/latex] [latex]\sim{P}[/latex] [latex]\sim{Q}[/latex] [latex]P\wedge{Q}[/latex] [latex]\sim\left(P\wedge{Q}\right)[/latex] [latex]\left(\sim{P}\right)\vee\left(\sim{Q}\right)[/latex]
T T F F T F F
T F F T F T T
F T T F F T T
F F T T F T T
DeMorgan’s laws are actually very natural and intuitive. Consider the statement [latex]\sim\left(P\wedge{Q}\right)[/latex], which we can interpret as meaning that it is not the case that both P and Q are true. If it is not the case that both P and Q are true, then at least one of P or Q is false, in which case [latex]\left(\sim{P}\right)\vee\left(\sim{Q}\right)[/latex] is true. Thus [latex]\sim\left(P\wedge{Q}\right)[/latex] means the same thing as [latex]\left(\sim{P}\right)\vee\left(\sim{Q}\right)[/latex]. DeMorgan’s laws can be very useful. Suppose we happen to know that some statement having form [latex]\sim\left(P\vee{Q}\right)[/latex] is true. The second of DeMorgan’s laws tells us that [latex]\left(\sim{Q}\right)\wedge\left(\sim{P}\right)[/latex] is also true, hence [latex]\sim{P}[/latex] and [latex]\sim{Q}[/latex] are both true as well. Being able to quickly obtain such additional pieces of information can be extremely useful. Here is a summary of some significant logical equivalences. Those that are not immediately obvious can be verified with a truth table. [latex-display]\text{Contrapositive law}\begin{array}{c}P\rightarrow{Q}=(\sim{Q})\rightarrow(\sim{P})\end{array}[/latex-display] [latex-display]\text{DeMorgan's laws}\begin{array}{c}{\sim(P\land{Q})=\sim{P}\lor\sim{Q}}\\{\sim(P\lor{Q})=\sim{P}\land\sim{Q}}\end{array}[/latex-display] [latex-display]\text{Commutative laws}\begin{array}{c}{(P\land{Q})={P}\land{Q}}\\{(P\lor{Q})={P}\lor{Q}}\end{array}[/latex-display] [latex-display]\text{Distributive laws}\begin{array}{c}{{P}\land(Q\lor{R})=({P}\land{Q})\lor(P\land{R})}\\{P\lor(Q\land{R})=({P}\lor{Q})\land(P\lor{R})}\end{array}[/latex-display] [latex-display]\text{Associative laws}\begin{array}{c}{P\land(Q\land{R})=(P\land{Q})\land{R}}\\{P\lor(Q\lor{R})=(P\lor{Q})\lor{R}}\end{array}[/latex-display] Notice how the distributive law [latex]P\wedge\left(Q\vee{R}\right)=\left(P\wedge{Q}\right)\vee\left(P\wedge{Q}\right)\vee\left(P\wedge{R}\right)[/latex] has the same structure as the distributive law [latex]p\left(q+r\right)=p\cdot{q}+p\cdot{r}[/latex] from algebra. Concerning the associative laws, the fact that [latex]P\wedge\left(Q\wedge{R}\right)=\left(P\wedge{Q}\right)\wedge{R}[/latex] means that the position of the parentheses is irrelevant, and we can write this as [latex]P\wedge{Q}\wedge{R}[/latex] without ambiguity. Similarly, we may drop the parentheses in an expression such as [latex]P\vee\left(Q\vee{R}\right)[/latex]. But parentheses are essential when there is a mix of [latex]\wedge[/latex] and [latex]\vee[/latex], as in [latex]P\vee\left(Q\wedge{R}\right)[/latex]. Indeed, [latex]P\vee\left(Q\wedge{R}\right)[/latex] and [latex]P\vee\left(Q\wedge{R}\right)[/latex] and [latex]P\vee\left({Q}\right)\wedge{R}[/latex] are not logically equivalent.

Negating Statements

Given a statement R, the statement [latex]\sim{R}[/latex] is called the negation of R. If R is a complex statement, then it is often the case that its negation [latex]\sim{R}[/latex] can be written in a simpler or more useful form. The process of finding this form is called negating R. In proving theorems it is often necessary to negate certain statements. We now investigate how to do this. We have already examined part of this topic. DeMorgan’s laws [latex-display]\sim\left(P\wedge{Q}\right)=\left(\sim{P}\right)\vee\left(\sim{Q}\right)\\\sim\left(P\vee{Q}\right)=\left(\sim{P}\right)\wedge\left(\sim{Q}\right)[/latex-display] (from "Logical Equivalence") can be viewed as rules that tell us how to negate the statements [latex]P\wedge{Q}[/latex] and [latex]P\vee{Q}[/latex]. Here are some examples that illustrate how DeMorgan’s laws are used to negate statements involving “and” or “or.”

Example

Consider negating the following statement. R : You can solve it by factoring or with the quadratic formula.

Answer: Now, R means (You can solve it by factoring) [latex]\vee[/latex] (You can solve it with Q.F.), which we will denote as [latex]P\vee{Q}[/latex]. The negation of this is [latex]\sim\left(P\vee{Q}\right)=\left(\sim{P}\right)\wedge\left(\sim{Q}\right)[/latex]. Therefore, in words, the negation of R is [latex]\sim{R}[/latex] : You can’t solve it by factoring and you can’t solve it with the quadratic formula. Maybe you can find [latex]\sim{R}[/latex] without invoking DeMorgan’s laws. That is good; you have internalized DeMorgan’s laws and are using them unconsciously.

Example

We will negate the following sentence. R : The numbers x and y are both odd.

Answer: This statement means [latex]\left(x\text{ is odd}\right)\wedge\left(y\text{ is odd}\right)[/latex], so its negation is

[latex]\sim\left[\left(x\text{ is odd}\right)\wedge\left(y\text{ is odd}\right)\right]=\sim\left(x\text{ is odd}\right)\vee\sim\left(y\text{ is odd}\right)\\\left(x\text{ is odd}\right)\wedge\left(y\text{ is odd}\right)=\left(x\text{ is even}\right)\vee\left(y\text{ is even}\right)[/latex]

Therefore the negation of R can be expressed in the following ways: [latex]\sim{R}[/latex]: The number x is even or the number y is even. [latex]\sim{R}[/latex]: At least one of x and y is even.

Licenses & Attributions

CC licensed content, Original

CC licensed content, Shared previously

  • Math in Society. Authored by: Lippman, David. Located at: http://www.opentextbookstore.com/mathinsociety/. License: CC BY-SA: Attribution-ShareAlike. License terms: IMathAS Community License CC-BY + GPL.
  • DeMorgan's Laws. Authored by: Wikipedia. Located at: https://en.wikipedia.org/wiki/De_Morgan%27s_laws. License: CC BY-SA: Attribution-ShareAlike.
  • Question ID 109608, 109064. Authored by: Hartley,Josiah. License: CC BY: Attribution. License terms: IMathAS Community License CC-BY + GPL.