# Logic

## De Morgan’s Laws


### 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?

### 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.

### Negation of a Conditional Statement

The negation of any statement has the opposite truth values of the original statement. The negation of a conditional, , is the conjunction of  and not ,  Consider the truth table below for the negation of the conditional.
The only time the negation of the conditional statement is true is when  is true, and  is false. This means that  is logically equivalent to  as the following truth table demonstrates.
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.

###  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.

### Check Your Understanding


### Key Terms

1. Boolean logic
2. negation of a conditional

### Key Concepts

1. De Morgan’s Law for the negation of a disjunction states that,  is logically equivalent to 
2. De Morgan’s Law The negation of a conjunction states that, 
3. Use De Morgan’s Laws to negate conjunctions and disjunctions.
4. The negation of a conditional statement, if  then  is logically equivalent to the statement  and not . Use this property to write the negation of conditional statements.
5. Use truth tables to evaluate De Morgan’s Laws.