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.
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\).
- 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)\).
- 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\).
- Answer
-
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
- 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.
- 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.
- 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.
- 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)\)
- 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)\)
- 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)\).
- 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)\)
- 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.
- 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)\)
- 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\).
- 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\).
- 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
- 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.
- Answer
-
Add texts here. Do not delete this text first.
