Section 2.2 Logically Equivalent Statements
Beginning Activity Beginning Activity 1: Logically Equivalent Statements
In Exercise 5 and Exercise 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: 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.Definition.
1.
Complete truth tables for \(\mynot \left( {P \wedge Q} \right)\) and \(\mynot P \vee \mynot Q\text{.}\)
2.
Are the expressions \(\mynot \left( {P \wedge Q} \right)\) and \(\mynot P \vee \mynot 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 Exercise 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\text{?}\) Now, write a true statement in symbolic form that is a conjunction and involves \(P\) and \(Q\text{.}\)
7.
Write a truth table for the (conjunction) statement in Exercise 6 and compare it to a truth table for \(\mynot \left( {P \to Q} \right)\text{.}\) What do you observe?
Beginning Activity Beginning Activity 2: Converse and Contrapositive
We now define two important conditional statements that are associated with a given conditional statement. If \(P\) and \(Q\) are statements, then The converse of the conditional statement \(P \to Q\) is the conditional statement \(Q \to P\text{.}\) The contrapositive of the conditional statement \(P \to Q\) is the conditional statement \(\mynot Q \to \mynot P\text{.}\)Definition.
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\text{,}\) then \(x^2 = 9\text{.}\)
(b)
If \(x^2 = 9\text{,}\) then \(x = 3\text{.}\)
(c)
If \(x^2 \ne 9\text{,}\) then \(x \ne 3\text{.}\)
(d)
If \(x \ne 3\text{,}\) then \(x^2 \ne 9\text{.}\)
2.
Which statement in the list of conditional statements in Exercise 1 is the converse of Task 1.a? Which is the contrapositive of Task 1.a?
3.
Complete appropriate truth tables to show that
(a)
\(P \to Q\) is logically equivalent to its contrapositive \(\mynot Q \to \mynot P\text{.}\)
(b)
\(P \to Q\) is not logically equivalent to its converse \(Q \to P\text{.}\)
In Beginning Activity 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.8. De Morgan's Laws.
For statements \(P\) and \(Q\text{,}\)
The statement \(\mynot \left( {P \wedge Q} \right)\) is logically equivalent to \(\mynot P \vee \mynot Q\text{.}\) This can be written as \(\mynot \left( {P \wedge Q} \right) \equiv \;\mynot P \vee \mynot Q\text{.}\)
The statement \(\mynot \left( {P \vee Q} \right)\) is logically equivalent to \(\mynot P \wedge \mynot Q\text{.}\) This can be written as \(\mynot \left( {P \vee Q} \right) \equiv \;\mynot P \wedge \mynot Q\text{.}\)
The first equivalency in Theorem 2.8 was established in Beginning Activity 1. Table 2.9 establishes the second equivalency.
| \(P\) | \(Q\) | \(P \vee Q\) | \(\mynot \left( {P \vee Q} \right)\) | \(\mynot P\) | \(\mynot Q\) | \(\mynot P \wedge \mynot 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.
Subsection Logical Equivalencies Related to Conditional Statements
The first two logical equivalencies in Theorem 2.10 were established in Beginning Activity 1, and the third logical equivalency was established in Beginning Activity 2.
Theorem 2.10.
For statements \(P\) and \(Q\text{,}\)
The conditional statement \(P \to Q\) is logically equivalent to \(\mynot P \vee Q\text{.}\)
The statement \(\mynot \left( {P \to Q} \right)\) is logically equivalent to \(P \wedge \mynot Q\text{.}\)
The conditional statement \(P \to Q\) is logically equivalent to its contrapositive \(\mynot Q \to \mynot P\text{.}\)
Subsection The Negation of a Conditional Statement
The logical equivalency \(\mynot \left( {P \to Q} \right) \equiv P \wedge \mynot 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 \(\mynot \left( {P \to Q} \right) \equiv P \wedge \mynot Q\text{.}\) 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:
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 \(\mynot \left( {P \to Q} \right) \equiv P \wedge \mynot Q\text{.}\) So, the negation can be written as follows:
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:
This conjunction is true since each of the individual statements in the conjunction is true.
Subsection Another Method of Establishing Logical Equivalencies
We have seen that it is 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 \(\mynot P \vee Q\text{.}\) So
\(\mynot \left( {P \to Q} \right)\) is logically equivalent to \(\mynot \left( {\mynot P \vee Q} \right)\text{.}\)
Hence, by Theorem 2.8 (one of DeMorgan's Laws), \(\mynot \left( {P \to Q} \right)\) is logically equivalent to \(\mynot \left( {\mynot P} \right) \wedge \mynot Q\text{.}\)
This means that \(\mynot \left( {P \to Q} \right)\) is logically equivalent to \(P \wedge \mynot Q\text{.}\)
The last step used the fact that \(\mynot \left( {\mynot P} \right)\) is logically equivalent to \(P\text{.}\)
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.11.
Progress Check 2.11.
In Section 2.1, we constructed a truth table for \(\left( {P \wedge \mynot Q} \right) \to R\text{.}\) See Table 2.4.
(a)
Although it is possible to use truth tables to show that \(P \to \left( {Q \vee R} \right)\) is logically equivalent to \(\left( {P \wedge \mynot Q} \right) \to R\text{,}\) we instead use previously proven logical equivalencies to prove this logical equivalency. In this case, it may be easier to start working with \(\left( {P \wedge \mynot Q} \right) \to R\text{.}\) Start with
which is justified by the logical equivalency established in Exercise 5 of Beginning Activity 1. Continue by using one of De Morgan's Laws on \(\mynot \left( P \wedge \mynot Q \right)\text{.}\)
Starting with the suggested equivalency, we obtain
(b)
Let \(a\) and \(b\) be integers. Suppose we are trying to prove the following:
If 3 is a factor of \(a \cdot b\text{,}\) then 3 is a factor of \(a\) or 3 is a factor of \(b\text{.}\)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\text{,}\) then 3 is a factor of \(b\text{.}\)
For this, let \(P\) be, “3 is a factor of \(a \cdot b\text{,}\)” let \(Q\) be, “3 is a factor of \(a\text{,}\)” and let \(R\) be, “3 is a factor of \(b\text{.}\)” Then the stated proposition is written in the form \(P \to \left( {Q \vee R} \right)\text{.}\) Since this is logically equivalent to \(\left( {P \wedge \mynot Q} \right) \to R\text{,}\) if we prove that if 3 is a factor of \(a \cdot b\) and 3 is not a factor of \(a\text{,}\) then 3 is a factor of \(b\text{,}\) then we have proven the original proposition.
As we will see, it is often difficult to construct a direct proof for a conditional statement of the form \(P \to \left( {Q \vee R} \right)\text{.}\) The logical equivalency in Progress Check 2.11 gives us another way to attempt to prove a statement of the form \(P \to \left( {Q \vee R} \right)\text{.}\) The advantage of the equivalent form, \(\left( {P \wedge \mynot Q} \right) \to R\text{,}\) is that we have an additional assumption, \(\mynot Q\text{,}\) in the hypothesis. This gives us more information with which to work.
Theorem 2.12 states some of the most frequently used logical equivalencies used when writing mathematical proofs.
Theorem 2.12. Important Logical Equivalencies.
For statements \(P\text{,}\) \(Q\text{,}\) and \(R\text{,}\)
De Morgan's Laws.
Conditional Statements.
Biconditional Statement.
Double Negation.
Distributive Laws.
Conditionals with Disjunctions.
We have already established many of these equivalencies. Others will be established in the exercises.
Exercises Exercises
1.
Write the converse and contrapositive of each of the following conditional statements.
(a)
If \(a = 5\text{,}\) then \(a^2 = 25\text{.}\)
Converse: If \(a^2 = 25\text{,}\) then \(a = 5\text{.}\) Contrapositive: If \(a^2 \ne 25\text{,}\) then \(a \ne 5\text{.}\)
(b)
If it is not raining, then Laura is playing golf.
Converse: If Laura is playing golf, then it is not raining. Contrapositive: If Laura is not playing golf, then it is raining.
(c)
If \(a \ne b\text{,}\) then \(a^4 \ne b^4\text{.}\)
Converse: If \(a^4 \ne b^4\text{,}\) then \(a \ne b\text{.}\) Contrapositive: If \(a^4 = b^4\text{,}\) then \(a = b\text{.}\)
(d)
If \(a\) is an odd integer, then \(3a\) is an odd integer.
Converse: If \(3a\) is an odd integer, then \(a\) is an odd integer. Contrapositive: If \(3a\) is an even integer, then \(a\) is an even integer.
2.
Write each of the conditional statements in Exercise 1 as a logically equivalent disjunction, and write the negation of each of the conditional statements in Exercise 1 as a conjunction.
Part (a). Disjunction: \(a \ne 5\) or \(a^2 = 25\text{.}\) Negation: \(a = 5\) and \(a^2 \ne 25\text{.}\)
Part (b). Disjunction: It is raining or Laura is playing golf. Negation: It is not raining and Laura is not playing golf.
Part (c). Disjunction: \(a = b\) or \(a^4 \ne b^4\text{.}\) Negation: \(a \ne b\) and \(a^4 = b^4\text{.}\)
Part (d). Disjunction: \(a\) is an even integer or \(3a\) is an odd integer. Negation: \(a\) is an odd integer and \(3a\) is an even integer.
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.
We will not win the first game or we will not win the second game.
(b)
They will lose the first game or they will lose the second game.
They will not lose the first game and they will not lose the second game.
(c)
If you mow the lawn, then I will pay you $20.
You mow the lawn and I will not pay you $20.
(d)
If we do not win the first game, then we will not play a second game.
We do not win the first game and we will play a second game.
(e)
I will wash the car or I will mow the lawn.
I will not wash the car and I will not 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)
\(\left( {P \leftrightarrow Q} \right) \equiv \left( {P \to Q} \right) \wedge \left( {Q \to P} \right)\)
(b)
\(\left( {P \leftrightarrow Q} \right) \equiv \left( {Q \leftrightarrow P} \right)\)
(c)
\(\left( {P \leftrightarrow Q} \right) \equiv \left( {\mynot P \leftrightarrow \mynot Q} \right)\)
5.
Use truth tables to prove each of the distributive laws from Theorem 2.12.
(a)
\(P \vee \left( {Q \wedge R} \right) \equiv \left( {P \vee Q} \right) \wedge \left( {P \vee R} \right)\)
(b)
\(P \wedge \left( {Q \vee R} \right) \equiv \left( {P \wedge Q} \right) \vee \left( {P \wedge R} \right)\)
6.
Use truth tables to prove the following logical equivalency from Theorem 2.12:
7.
Use previously proven logical equivalencies to prove each of the following logical equivalencies about conditionals with conjunctions:
(a)
\(\left[ {\left( {P \wedge Q} \right) \to R} \right] \equiv \left( {P \to R} \right) \vee \left( {Q \to R} \right)\)
In this case, it may be better to work with the right side first.
(b)
\(\left[ {P \to \left( {Q \wedge R} \right)} \right] \equiv \left( {P \to Q} \right) \wedge \left( {P \to R} \right)\)
In this case, we start with the left side.
8.
If \(P\) and \(Q\) are statements, is the statement \(\left( P \vee Q \right) \wedge \mynot \left( P \wedge Q \right)\) logically equivalent to the statement \(\left( P \wedge \mynot Q \right) \vee \left( Q \wedge \mynot P \right)\text{?}\) Justify your conclusion.
9.
Use previously proven logical equivalencies to prove each of the following logical equivalencies:
(a)
\(\left[ {\mynot P \to \left( {Q \wedge \mynot Q} \right)} \right] \equiv P\)
(b)
\(\left( P \leftrightarrow Q \right) \equiv \left( \mynot P \vee Q \right) \wedge \left( \mynot Q \vee P \right)\)
(c)
\(\mynot \left( P \leftrightarrow Q \right) \equiv \left( P \wedge \mynot Q \right) \vee \left( Q \wedge \mynot P \right)\)
(d)
\(\left( P \to Q \right) \to R \equiv \left( P \wedge \mynot Q \right) \vee R\)
(e)
\(\left( P \to Q \right) \to R \equiv \left( \mynot P \to R \right) \wedge \left( Q \to R \right)\)
(f)
\(\left[ \left( P \wedge Q \right) \to \left( R \vee S \right) \right] \equiv \left[ \left( \mynot R \wedge \mynot S \right) \to \left( \mynot P \vee \mynot Q \right) \right]\)
(g)
\(\left[ \left( P \wedge Q \right) \to \left( R \vee S \right) \right] \equiv \left[ \left( P \wedge Q \wedge \mynot R \right) \to S \right]\)
(h)
\(\left[ \left( P \wedge Q \right) \to \left( R \vee S \right) \right] \equiv \left( \mynot P \vee \mynot Q \vee R \vee S \right)\)
(i)
\(\mynot \left[ \left( P \wedge Q \right) \to \left( R \vee S \right) \right] \equiv \left( P \wedge Q \wedge \mynot R \wedge \mynot S \right)\)
10.
Let \(a\) be a real number and let \(f\) be a real-valued function defined on an interval containing \(x = a\text{.}\) Consider the following conditional statement:
If \(f\) is differentiable at \(x = a\text{,}\) then \(f\) is continuous at \(x = a\text{.}\)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\text{,}\) then \(f\) is differentiable at \(x = a\text{.}\)
(b)
If \(f\) is not differentiable at \(x = a\text{,}\) then \(f\) is not continuous at \(x = a\text{.}\)
(c)
If \(f\) is not continuous at \(x = a\text{,}\) then \(f\) is not differentiable at \(x = a\text{.}\)
This statement is logically equivalent to the given conditional statement.
(d)
\(f\) is not differentiable at \(x = a\) or \(f\) is continuous at \(x = a\text{.}\)
This statement is logically equivalent to the given conditional statement.
(e)
\(f\) is not continuous at \(x = a\) or \(f\) is differentiable at \(x = a\text{.}\)
(f)
\(f\) is differentiable at \(x = a\) and \(f\) is not continuous at \(x = a\text{.}\)
This statement is the negation of the given conditional statement.
11.
Let \(a, b\text{,}\) and \(c\) be integers. Consider the following conditional statement:
If \(a\) divides \(bc\text{,}\) then \(a\) divides \(b\) or \(a\) divides \(c\text{.}\)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\text{,}\) then \(a\) divides \(bc\text{.}\)
(b)
If \(a\) does not divide \(b\) or \(a\) does not divide \(c\text{,}\) then \(a\) does not divide \(bc\text{.}\)
(c)
\(a\) divides \(bc\text{,}\) \(a\) does not divide \(b\text{,}\) and \(a\) does not divide \(c\text{.}\)
(d)
If \(a\) does not divide \(b\) and \(a\) does not divide \(c\text{,}\) then \(a\) does not divide \(bc\text{.}\)
This is the contrapositive of the given statement and hence, it is logically equivalent to the given statement.
(e)
\(a\) does not divide \(bc\) or \(a\) divides \(b\) or \(a\) divides \(c\text{.}\)
(f)
If \(a\) divides \(bc\) and \(a\) does not divide \(c\text{,}\) then \(a\) divides \(b\text{.}\)
(g)
If \(a\) divides \(bc\) or \(a\) does not divide \(b\text{,}\) then \(a\) divides \(c\text{.}\)
12.
Let \(x\) be a real number. Consider the following conditional statement:
If \(x^3 - x = 2x^2 + 6\text{,}\) then \(x = - 2\) or \(x = 3\text{.}\)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 instruction for Exercise 10.)
(a)
If \(x \ne - 2\) and \(x \ne 3\text{,}\) then \(x^3 - x \ne 2x^2 + 6\text{.}\)
(b)
If \(x = - 2\) or \(x = 3\text{,}\) then \(x^3 - x = 2x^2 + 6\text{.}\)
(c)
If \(x \ne - 2\) or \(x \ne 3\text{,}\) then \(x^3 - x \ne 2x^2 + 6\text{.}\)
(d)
If \(x^3 - x = 2x^2 + 6\) and \(x \ne - 2\text{,}\) then \(x = 3\text{.}\)
(e)
If \(x^3 - x = 2x^2 + 6\) or \(x \ne - 2\text{,}\) then \(x = 3\text{.}\)
(f)
\(x^3 - x = 2x^2 + 6\text{,}\) \(x \ne - 2\text{,}\) and \(x \ne 3\text{.}\)
(g)
\(x^3 - x \ne 2x^2 + 6\) or \(x = - 2\) or \(x = 3\text{.}\)
Activity 6. Working with a Logical Equivalency.
Suppose we are trying to prove the following for integers \(x\) and \(y\text{:}\)
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:
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 \left( {Q \vee R} \right)\text{.}\) Then use one of De Morgan's Laws (Theorem 2.8) to rewrite the hypothesis of this conditional statement.
(b)
Use the result from Task 6.a 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.10, which was proven in Section 1.2.