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
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]
[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 |
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
- Revision and Adaptation. Provided by: Lumen Learning License: CC BY: Attribution.
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.