Learning Objectives
- DeMorgan’s Laws
- Use DeMorgan’s laws to define logical equivalences of a symbolic statements
- Use DeMorgan’s laws to define logical equivalences of a English statements
Continuing on with our discussion of equivalent statements in the previous section. 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.
success strategy
Get plenty of practice and repetition with the ideas in this page! The notation will become more familiar as you do. Remember to get help if you need it!
DeMorgan’s Laws
[latex]\sim\left(P{\wedge}Q\right)=({\sim}P)\vee\left(\sim{Q}\right)[/latex]
[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.
Try It
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]\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]
(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.
Example
We will negate the following sentence.
R : The numbers x and y are both odd.
Try It
This is the end of the section. Close this tab and proceed to the corresponding assignment.