Logically Equivalent Statements

Section 2.2 Logically Equivalent Statements

Beginning Activity Beginning Activity 1: Logically Equivalent Statements
A4 US

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:

🔗

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 $\neg (P \land Q)$ and $\neg P \lor \neg Q .$

🔗

2.

Are the expressions $\neg (P \land Q)$ and $\neg P \lor \neg 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 ?$ 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 Exercise 6 and compare it to a truth table for $\neg (P \to Q) .$ What do you observe?

🔗

Beginning Activity Beginning Activity 2: Converse and Contrapositive
A4 US

🔗

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 $\neg Q \to \neg 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} \neq 9,$ then $x \neq 3 .$

🔗

(d)

If $x \neq 3,$ then $x^{2} \neq 9 .$

🔗

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 $\neg Q \to \neg P .$

🔗

(b)

$P \to Q$ is not logically equivalent to its converse $Q \to P .$

🔗

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,$

The statement $\neg (P \land Q)$ is logically equivalent to $\neg P \lor \neg Q .$ This can be written as $\neg (P \land Q) \equiv \neg P \lor \neg Q .$

The statement $\neg (P \lor Q)$ is logically equivalent to $\neg P \land \neg Q .$ This can be written as $\neg (P \lor Q) \equiv \neg P \land \neg Q .$

🔗

The first equivalency in Theorem 2.8 was established in Beginning Activity 1. Table 2.9 establishes the second equivalency.

🔗

Table 2.9. Truth Table for One of De Morgan's Laws

$P$	$Q$	$P \lor Q$	$\neg (P \lor Q)$	$\neg P$	$\neg Q$	$\neg P \land \neg 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,$

The conditional statement $P \to Q$ is logically equivalent to $\neg P \lor Q .$
The statement $\neg (P \to Q)$ is logically equivalent to $P \land \neg Q .$
The conditional statement $P \to Q$ is logically equivalent to its contrapositive $\neg Q \to \neg P .$

🔗

Subsection The Negation of a Conditional Statement

🔗

The logical equivalency

\neg (P \to Q) \equiv P \land \neg 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

\neg (P \to Q) \equiv P \land \neg 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

\neg (P \to Q) \equiv P \land \neg Q .

So, the negation can be written as follows:

- 5 < - 3 and \neg ({(- 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} ⩾ {(- 3)}^{2} .

🔗

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 $\neg P \lor Q .$ So
$\neg (P \to Q)$ is logically equivalent to $\neg (\neg P \lor Q) .$
Hence, by Theorem 2.8 (one of DeMorgan's Laws), $\neg (P \to Q)$ is logically equivalent to $\neg (\neg P) \land \neg Q .$
This means that $\neg (P \to Q)$ is logically equivalent to $P \land \neg Q .$

🔗

The last step used the fact that

\neg (\neg 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.11.

🔗

Progress Check 2.11.

In Section 2.1, we constructed a truth table for $(P \land \neg Q) \to R .$ See Table 2.4.

🔗

(a)

Although it is possible to use truth tables to show that $P \to (Q \lor R)$ is logically equivalent to $(P \land \neg 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 \land \neg Q) \to R .$ Start with

(P \land \neg Q) \to R \equiv \neg (P \land \neg Q) \lor R,

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 $\neg (P \land \neg Q) .$

Solution.

Starting with the suggested equivalency, we obtain

\begin{aligned} (P \land \neg Q) \to R & \equiv \neg (P \land \neg Q) \lor R \\ \equiv (\neg P \lor \neg (\neg Q)) \lor R \\ \equiv \neg P \lor (Q \lor R) \\ \equiv P \to (Q \lor R) \end{aligned}

🔗

(b)

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

Solution.

For this, let $P$ be, “3 is a factor of $a \cdot b,$ ” let $Q$ be, “3 is a factor of $a,$ ” and let $R$ be, “3 is a factor of $b .$ ” Then the stated proposition is written in the form $P \to (Q \lor R) .$ Since this is logically equivalent to $(P \land \neg Q) \to R,$ if we prove that if 3 is a factor of $a \cdot b$ and 3 is not a factor of $a,$ then 3 is a factor of $b,$ 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 (Q \lor R) .

The logical equivalency in Progress Check 2.11 gives us another way to attempt to prove a statement of the form

P \to (Q \lor R) .

The advantage of the equivalent form,

(P \land \neg Q) \to R,

is that we have an additional assumption,

\neg Q,

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,$ $Q,$ and $R,$

🔗

De Morgan's Laws.

\neg (P \land Q) \equiv \neg P \lor \neg Q

\neg (P \lor Q) \equiv \neg P \land \neg Q

🔗

Conditional Statements.

P \to Q \equiv \neg Q \to \neg P ()

P \to Q \equiv \neg P \lor Q

\neg (P \to Q) \equiv P \land \neg Q

🔗

Biconditional Statement.

(P \leftrightarrow Q) \equiv (P \to Q) \land (Q \to P)

🔗

Double Negation.

\neg (\neg P) \equiv P

🔗

Distributive Laws.

P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)

P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)

🔗

Conditionals with Disjunctions.

P \to (Q \lor R) \equiv (P \land \neg Q) \to R

(P \lor Q) \to R \equiv (P \to R) \land (Q \to R)

🔗

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,$ then $a^{2} = 25 .$

Section 2.2 Logically Equivalent Statements

Beginning Activity Beginning Activity 1: Logically Equivalent Statements A4US

Definition.

1.

2.

3.

4.

5.

6.

7.

Beginning Activity Beginning Activity 2: Converse and Contrapositive A4US

Definition.

1.

(a)

(b)

(c)

(d)

2.

3.

(a)

(b)

Theorem 2.8. De Morgan's Laws.

Subsection Logical Equivalencies Related to Conditional Statements

Theorem 2.10.

Subsection The Negation of a Conditional Statement

Subsection Another Method of Establishing Logical Equivalencies

Progress Check 2.11.

(a)

(b)

Theorem 2.12. Important Logical Equivalencies.

De Morgan's Laws.

Conditional Statements.

Biconditional Statement.

Double Negation.

Distributive Laws.

Conditionals with Disjunctions.

Exercises Exercises

1.

(a)

(b)

(c)

(d)

2.

3.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

4.

(a)

(b)

(c)

5.

(a)

(b)

6.

7.

(a)

(b)

8.

9.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

10.

(a)

(b)

(c)

(d)

Beginning Activity Beginning Activity 1: Logically Equivalent Statements
A4 US

Beginning Activity Beginning Activity 2: Converse and Contrapositive
A4 US