
# 2.2: Logically Equivalent Statements

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Preview Activity $$\PageIndex{1}$$: Logically Equivalent Statements

In Exercises (5) and (6) from Section 2.1, we observed situations where two different statements have the same truth tables. Basically, this means these statements are equivalent, and we make the following definition:

Definition

Two expressions are logically equivalent provided that they have the same truth value for all possible combinations of truth values for all variables appearing in the two expressions. In this case, we write $$X \equiv Y$$ and say that $$X$$ and $$Y$$ are logically equivalent.

1. Complete truth tables for $$\urcorner (P \wedge Q)$$ and $$\urcorner P \vee \urcorner Q$$.
2. Are the expressions $$\urcorner (P \wedge Q)$$ and $$\urcorner P \vee \urcorner Q$$ logically equivalent?

3. Suppose that the statement “I will play golf and I will mow the lawn” is false. Then its negation is true. Write the negation of this statement in the form of a disjunction. Does this make sense?

Sometimes we actually use logical reasoning in our everyday living! Perhaps you can imagine a parent making the following two statements:

Statement 1. If you do not clean your room, then you cannot watch TV.
Statement 2. You clean your room or you cannot watch TV.

4. Let $$P$$ be “you do not clean your room,” and let $$Q$$ be “you cannot watch TV.” Use these to translate Statement 1 and Statement 2 into symbolic forms.

5. Construct a truth table for each of the expressions you determined in Part(4). Are the expressions logically equivalent?

6. Assume that Statement 1 and Statement 2 are false. In this case, what is the truth value of $$P$$ and what is the truth value of $$Q$$? Now, write a true statement in symbolic form that is a conjunction and involves $$P$$ and $$Q$$.

7. Write a truth table for the (conjunction) statement in Part (6) and compare it to a truth table for $$\urcorner (P \to Q)$$. What do you observe?

Preview Activity $$\PageIndex{2}$$: Converse and Contrapositive

We now define two important conditional statements that are associated with a given conditional statement.

Definition

If $$P$$ and $$Q$$ are statements, then

• The converse of the conditional statement $$P \to Q$$ is the conditional statement $$Q \to P$$.
• The contrapositive of the conditional statement $$P \to Q$$ is the conditional statement $$Q \to P$$.
1. For the following, the variable x represents a real number. Label each of the following statements as true or false.
(a) If $$x = 3$$, then $$x^2 = 9$$.
(b) If $$x^2 = 9$$, then $$x = 3$$.
(c) If $$x^2 \ne 9$$, then $$x \ne 3$$.
(d) If $$x \ne 3$$, then $$x^2 \ne 9$$.
2. Which statement in the list of conditional statements in Part (1) is the converse of Statement (1a)? Which is the contrapositive of Statement (1a)?

3. Complete appropriate truth tables to show that
$$P \to Q$$is logically equivalent to its contrapositive $$\urcorner Q \to \urcorner P$$.
$$P \to Q$$is not logically equivalent to its converse $$Q \to P$$

In Preview Activity $$\PageIndex{1}$$, we introduced the concept of logically equivalent expressions and the notation $$X \equiv Y$$ to indicate that statements $$X$$ and $$Y$$ are logically equivalent. The following theorem gives two important logical equivalencies. They are sometimes referred to as De Morgan’s Laws.

Theorem 2.5: De Morgan’s Laws

For statements $$P$$ and $$Q$$,

• The statement $$\urcorner (P \wedge Q)$$ is logically equivalent to $$\urcorner P \vee \urcorner Q$$. This can be written as $$\urcorner (P \wedge Q) \equiv \urcorner P \vee \urcorner Q$$.
• The statement $$\urcorner (P \vee Q)$$ is logically equivalent to $$\urcorner P \wedge \urcorner Q$$. This can be written as $$\urcorner (P \vee Q) \equiv \urcorner P \wedge \urcorner Q$$.
Proof

The first equivalency in Theorem 2.5 was established in Preview Activity $$\PageIndex{1}$$. Table 2.3 establishes the second equivalency.

Table 2.3: Truth Table for One of De Morgan’s Laws
$$P$$ $$Q$$ $$P \vee Q$$ $$\urcorner (P \vee Q)$$ $$\urcorner P$$ $$\urcorner Q$$ $$\urcorner (P \vee Q) \equiv \urcorner P \wedge \urcorner Q$$
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T

It is possible to develop and state several different logical equivalencies at this time. However, we will restrict ourselves to what are considered to be some of the most important ones. Since many mathematical statements are written in the form of conditional statements, logical equivalencies related to conditional statements are quite important.

## Logical Equivalencies Related to Conditional Statements

The first two logical equivalencies in the following theorem were established in Preview Activity $$\PageIndex{1}$$, and the third logical equivalency was established in Preview Activity $$\PageIndex{2}$$.

Theorem 2.6

For statements $$P$$ and $$Q$$,

1. The conditional statement $$P \to Q$$ is logically equivalent to $$\urcorner P \vee Q$$.
2. The statement $$\urcorner (P \to Q)$$ is logically equivalent to $$P \wedge \urcorner Q$$.
3. The conditional statement $$P \to Q$$ is logically equivalent to its contrapositive $$\urcorner Q \to \urcorner P$$.

## The Negation of a Conditional Statement

The logical equivalency $$\urcorner (P \to Q) \equiv P \wedge \urcorner Q$$ is interesting because it shows us that the negation of a conditional statement is not another conditional statement. The negation of a conditional statement can be written in the form of a conjunction. So what does it mean to say that the conditional statement

If you do not clean your room, then you cannot watch TV,

is false? To answer this, we can use the logical equivalency $$\urcorner (P \to Q) \equiv P \wedge \urcorner Q$$. The idea is that if $$P \to Q$$ is false, then its negation must be true. So the negation of this can be written as

You do not clean your room and you can watch TV.

For another example, consider the following conditional statement:

If $$-5 < -3$$, then $$(-5)^2 < (-3)^2$$.

This conditional statement is false since its hypothesis is true and its conclusion is false. Consequently, its negation must be true. Its negation is not a conditional statement. The negation can be written in the form of a conjunction by using the logical equivalency $$\urcorner (P \to Q) \equiv P \wedge \urcorner Q$$. So, the negation can be written as follows:

$$5 < 3$$ and $$\urcorner ((-5)^2 < (-3)^2)$$.

However, the second part of this conjunction can be written in a simpler manner by noting that “not less than” means the same thing as “greater than or equal to.” So we use this to write the negation of the original conditional statement as follows:

$$5 < 3$$ and $$(-5)^2 \ge (-3)^2$$.

This conjunction is true since each of the individual statements in the conjunction is true.

Another Method of Establishing Logical Equivalencies

We have seen that it often possible to use a truth table to establish a logical equivalency. However, it is also possible to prove a logical equivalency using a sequence of previously established logical equivalencies. For example,

• $$P \to Q$$ is logically equivalent to $$\urcorner P \vee Q$$. So
• $$\urcorner (P \to Q)$$ is logically equivalent to $$\urcorner (\urcorner P \vee Q)$$.
• Hence, by one of De Morgan’s Laws (Theorem 2.5), $$\urcorner (P \to Q)$$ is logically equivalent to $$\urcorner (\urcorner P) \wedge \urcorner Q$$.
• This means that $$\urcorner (P \to Q)$$ is logically equivalent to$$P \wedge \urcorner Q$$.

The last step used the fact that $$\urcorner (\urcorner P)$$ is logically equivalent to $$P$$.

When proving theorems in mathematics, it is often important to be able to decide if two expressions are logically equivalent. Sometimes when we are attempting to prove a theorem, we may be unsuccessful in developing a proof for the original statement of the theorem. However, in some cases, it is possible to prove an equivalent statement. Knowing that the statements are equivalent tells us that if we prove one, then we have also proven the other. In fact, once we know the truth value of a statement, then we know the truth value of any other logically equivalent statement. This is illustrated in Progress Check 2.7.

Progress Check 2.7 (Working with a logical equivalency)

In Section 2.1, we constructed a truth table for $$(P \wedge \urcorner Q) \to R$$.

1. Although it is possible to use truth tables to show that $$P \to (Q \vee R)$$ is logically equivalent to $$P \wedge \urcorner Q) \to R$$, we instead use previously proven logical equivalencies to prove this logical equivalency. In this case, it may be easier to start working with $$P \wedge \urcorner Q) \to R$$. Start with

$$P \wedge \urcorner Q) \to R \equiv \urcorner (P \wedge \urcorner Q) \vee R$$,

which is justified by the logical equivalency established in Part (5) of Preview Activity 1. Continue by using one of De Morgan's Laws on $$\urcorner (P \wedge \urcorner Q)$$.
2. Let a and b be integers. Suppose we are trying to prove the following:

If 3 is a factor of $$a \cdot b$$, then 3 is a factor of $$a$$ or 3 is a factor of $$b$$.

Explain why we will have proven this statement if we prove the following:

If 3 is a factor of $$a \cdot b$$ and 3 is not a factor of $$a$$, then 3 is a factor of $$b$$.

Add texts here. Do not delete this text first.

As we will see, it is often difficult to construct a direct proof for a conditional statement of the form $$P \to (Q \vee R)$$. The logical equivalency in Progress Check 2.7 gives us another way to attempt to prove a statement of the form $$P \to (Q \vee R)$$. The advantage of the equivalent form, $$P \wedge \urcorner Q) \to R$$, is that we have an additional assumption, $$\urcorner Q$$, in the hypothesis. This gives us more information with which to work.

Theorem 2.8 states some of the most frequently used logical equivalencies used when writing mathematical proofs.

Theorem 2.8: important logical equivalencies

For statement $$P$$, $$Q$$, and $$R$$,

De Morgan's Laws $$\urcorner (P \wedge Q) \equiv \urcorner P \vee \urcorner Q$$.
$$\urcorner (P \vee Q) \equiv \urcorner P \wedge \urcorner Q$$.

Conditional Statement. $$P \to Q \equiv \urcorner Q \to \urcorner P$$ (contrapositive)
$$P \to Q \equiv \urcorner P \vee Q$$
$$\urcorner (P \to Q) \equiv P \wedge \urcorner Q$$

Biconditional Statement $$(P leftrightarrow Q) \equiv (P \to Q) \wedge (Q \to P)$$

Double Negation $$\urcorner (\urcorner P) \equiv P$$

Distributive Laws $$P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$$
$$P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$$

Conditionals withDisjunctions $$P \to (Q \vee R) \equiv (P \wedge \urcorner Q) \to R$$
$$(P \vee Q) \to R \equiv (P \to R) \wedge (Q \to R)$$

We have already established many of these equivalencies. Others will be established in the exercises.

Exercises for Section 2.2

1. Write the converse and contrapositive of each of the following conditional statements.
(a) If $$a = 5$$, then $$a^2 = 25$$.
(b) If it is not raining, then Laura is playing golf.
(c) If $$a \ne b$$, then $$a^4 \ne b^4$$.
(d) If $$a$$ is an odd integer, then $$3a$$ is an odd integer.
2. Write each of the conditional statements in Exercise (1) as a logically equiva- lent disjunction, and write the negation of each of the conditional statements in Exercise (1) as a conjunction.

3. Write a useful negation of each of the following statements. Do not leave a negation as a prefix of a statement. For example, we would write the negation of “I will play golf and I will mow the lawn” as “I will not play golf or I will not mow the lawn.”
(a) We will win the first game and we will win the second game.
(b) They will lose the first game or they will lose the second game.
(c) If you mow the lawn, then I will pay you \$20.
(d) If we do not win the first game, then we will not play a second game.
(e) I will wash the car or I will mow the lawn.
(f) If you graduate from college, then you will get a job or you will go to graduate school.
(g) If I play tennis, then I will wash the car or I will do the dishes.
(h) If you clean your room or do the dishes, then you can go to see a movie.
(i) It is warm outside and if it does not rain, then I will play golf.

4. Use truth tables to establish each of the following logical equivalencies dealing with biconditional statements:
(a) $$(P \leftrightarrow Q) \equiv (P \to Q) \wedge (Q \to P)$$
(b) $$(P \leftrightarrow Q) \equiv (Q \leftrightarrow P)$$
(c) $$(P \leftrightarrow Q) \equiv (\urcorner P \leftrightarrow \urcorner Q)$$

5. Use truth tables to prove each of the distributive laws from Theorem 2.8.

(a) $$P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$$
(b $$P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$$

6. Use truth tables to prove the following logical equivalency from Theorem 2.8:

$$[(P \vee Q) \to R] \equiv (P \to R) \wedge (Q \to R)$$.

7. Use previously proven logical equivalencies to prove each of the following logical equivalencies about conditionals with conjunctions:

(a) $$[(P \wedge Q) \to R] \equiv (P \to R) \vee (Q \to R)$$
(b) $$[P \to (Q \wedge R)] \equiv (P \to R) \wedge (P \to R)$$

8. If $$P$$ and $$Q$$ are statements, is the statement $$(P \vee Q) \wedge \urcorner (P \wedge Q)$$ logically equivalent to the statement $$(P \wedge \urcorner Q) \vee (Q \wedge \urcorner P)$$? Justify your conclusion.

9. Use previously proven logical equivalencies to prove each of the following logical equivalencies:

(a) $$[\urcorner P \to (Q \wedge \urcorner Q)] \equiv P$$
(b) $$(P \leftrightarrow Q) \equiv (\urcorner P \vee Q) \wedge (\urcorner Q \vee p)$$
(c) $$\urcorner (P \leftrightarrow Q) \equiv (P \wedge \urcorner Q) \vee (Q \wedge \urcorner P)$$
(d) $$(P \to Q) \to R \equiv (P \wedge \urcorner Q) \vee R$$
(e) $$(P \to Q) \to R \equiv (\urcorner P \to R) \wedge (Q \to R)$$
(f) $$[(P \wedge Q) \to (R \vee S)] \equiv [(\urcorner R \wedge \urcorner S) \to (\urcorner P \vee \urcorner Q)]$$
(g) $$[(P \wedge Q) \to (R \vee S)] \equiv [(P \wedge Q \wedge \urcorner R) \to S]$$
(h) $$[(P \wedge Q) \to (R \vee S)] \equiv (\urcorner P \vee \urcorner Q \vee R \vee S)$$
(i) $$\urcorner [(P \wedge Q) \to (R \vee S)] \equiv (P \wedge Q \wedge \urcorner R \wedge \urcorner S)$$
10. Let a be a real number and let f be a real-valued function defined on an interval containing $$x = a$$. Consider the following conditional statement:

If $$f$$ is differentiable at $$x = a$$, then $$f$$ is continuous at $$x = a$$.

Which of the following statements have the same meaning as this conditional statement and which ones are negations of this conditional statement?

Note: This is not asking which statements are true and which are false. It is asking which statements are logically equivalent to the given statement. It might be helpful to let P represent the hypothesis of the given statement, $$Q$$ represent the conclusion, and then determine a symbolic representation for each statement. Instead of using truth tables, try to use already established logical equivalencies to justify your conclusions.

(a) If $$f$$ is continuous at $$x = a$$, then $$f$$ is differentiable at $$x = a$$.
(b) If $$f$$ is not differentiable at $$x = a$$, then $$f$$ is not continuous at $$x = a$$.
(c) If $$f$$ is not continuous at $$x = a$$, then $$f$$ is not differentiable at $$x = a$$.
(d) $$f$$ is not differentiable at $$x = a$$ or $$f$$ is continuous at $$x = a$$.
(e) $$f$$ is not continuous at $$x = a$$ or $$f$$ is differentiable at $$x = a$$.
(f) $$f$$ is differentiable at $$x = a$$ or $$f$$ is not continuous at $$x = a$$.

11. Let $$a$$, $$b$$, and $$c$$ be integers. Consider the following conditional statement:

If $$a$$ divides $$bc$$, then $$a$$ divides $$b$$ or $$a$$ divides $$c$$.

Which of the following statements have the same meaning as this conditional statement and which ones are negations of this conditional statement?

The note for Exercise (10) also applies to this exercise.

(a) If $$a$$ divides $$b$$ or $$a$$ divides $$c$$, then $$a$$ divides $$bc$$.
(b) If $$a$$ does not divide $$b$$ or $$a$$ does not divide $$c$$, then $$a$$ does not divide $$bc$$.
(c) $$a$$ divides $$bc$$, $$a$$ does not divide $$b$$, and $$a$$ does not divide $$c$$.
(d) If $$a$$ does not divide $$b$$ and $$a$$ does not divide $$c$$, then $$a$$ does not divide $$bc$$.
(e) $$a$$ does not divide $$bc$$ or $$a$$ divides $$b$$ or $$a$$ divides $$c$$.
(f) If $$a$$ divides $$bc$$ and $$a$$ does not divide $$c$$, then $$a$$ divides $$b$$.
(g) If $$a$$ divides $$bc$$ or $$a$$ does not divide $$b$$, then $$a$$ divides $$c$$.

12. Let $$x$$ be a real number. Consider the following conditional statement:

If $$x^3 - x = 2x^2 +6$$, then $$x = -2$$ or $$x = 3$$.

Which of the following statements have the same meaning as this conditional statement and which ones are negations of this conditional statement? Explain each conclusion. (See the note in the instructions for Exercise (10).)

(a) If $$x \ne -2$$ and $$x \ne 3$$, then $$x^3 - x \ne 2x^2 +6$$.
(b) If $$x = -2$$ or $$x = 3$$, then $$x^3 - x = 2x^2 +6$$.
(c) If $$x \ne -2$$ or $$x \ne 3$$, then $$x^3 - x \ne 2x^2 +6$$.
(d) If $$x^3 - x = 2x^2 +6$$ and $$x \ne -2$$, then $$x = 3$$.
(e) If $$x^3 - x = 2x^2 +6$$ or $$x \ne -2$$, then $$x = 3$$.
(f) $$x^3 - x = 2x^2 +6$$, $$x \ne -2$$, and $$x \ne 3$$.
(g) $$x^3 - x \ne 2x^2 +6$$ or $$x = -2$$ or $$x = 3$$.

Explorations and Activities

13. Working with a Logical Equivalency. Suppose we are trying to prove the following for integers $$x$$ and $$y$$:

If $$x \cdot y$$ is even, then $$x$$ is even or $$y$$ is even.

We notice that we can write this statement in the following symbolic form:

$$P \to (Q \vee R)$$,

where $$P$$ is“$$x \cdot y$$ is even,” $$Q$$ is“$$x$$ is even,”and $$R$$ is “$$y$$ is even.”

(a) Write the symbolic form of the contrapositive of $$P \to (Q \vee R)$$. Then use one of De Morgan’s Laws (Theorem 2.5) to rewrite the hypothesis of this conditional statement.
(b) Use the result from Part (13a) to explain why the given statement is logically equivalent to the following statement:

If $$x$$ is odd and $$y$$ is odd, then $$x \cdot y$$ is odd.

The two statements in this activity are logically equivalent. We now have the choice of proving either of these statements. If we prove one, we prove the other, or if we show one is false, the other is also false. The second statement is Theorem 1.8, which was proven in Section 1.2.