ADS Equivalence and Implication

Section 3.3 Equivalence and Implication

Consider two propositions generated by

p

and

q :

\neg (p \land q)

and

\neg p \lor \neg q .

At first glance, they are different propositions. In form, they are different, but they have the same meaning. One way to see this is to substitute actual propositions for

p

and

q;

such as

p :

I’ve been to Toronto; and

q :

I’ve been to Chicago.

🔗

Then

\neg (p \land q)

translates to “I haven’t been to both Toronto and Chicago,” while

\neg p \lor \neg q

is “I haven’t been to Toronto or I haven’t been to Chicago.” Determine the truth values of these propositions. Naturally, they will be true for some people and false for others. What is important is that no matter what truth values they have,

\neg (p \land q)

and

\neg p \lor \neg q

will have the same truth value. The easiest way to see this is by examining the truth tables of these propositions.

🔗

Table 3.3.1. Truth Tables for

\neg (p \land q)

and

\neg p \lor \neg q

$p$	$q$	$\neg (p \land q)$	$\neg p \lor \neg q$
0	0	1	1
0	1	1	1
1	0	1	1
1	1	0	0

🔗

In all four cases,

\neg (p \land q)

and

\neg p \lor \neg q

have the same truth value. Furthermore, when the biconditional operator is applied to them, the result is a value of true in all cases. A proposition such as this is called a tautology.

🔗

Subsection 3.3.1 Tautologies and Contradictions

🔗

Definition 3.3.2. Tautology.

🔗

An expression involving logical variables that is true in all cases is a tautology. The number 1 is used to symbolize a tautology.

🔗

Example 3.3.3. Some Tautologies.

All of the following are tautologies because their truth tables consist of a column of 1’s.

$(\neg (p \land q)) \leftrightarrow (\neg p \lor \neg q) .$
$p \lor \neg p$
$(p \land q) \to p$
$q \to (p \lor q)$
$(p \lor q) \leftrightarrow (q \lor p)$

🔗

Definition 3.3.4. Contradiction.

🔗

An expression involving logical variables that is false for all cases is called a contradiction. The number 0 is used to symbolize a contradiction.

🔗

Example 3.3.5. Some Contradictions.

p \land \neg p

and

(p \lor q) \land (\neg p) \land (\neg q)

are contradictions.

🔗

Subsection 3.3.2 Equivalence

🔗

Definition 3.3.6. Equivalence.

🔗

Let

S

be a set of propositions and let

r

and

s

be propositions generated by

S .

r

and

s

are equivalent if and only if

r \leftrightarrow s

is a tautology. The equivalence of

r

and

s

is denoted

r ⟺ s .

🔗

Equivalence is to logic as equality is to algebra. Just as there are many ways of writing an algebraic expression, the same logical meaning can be expressed in many different ways.

🔗

Example 3.3.7. Some Equivalences.

The following are all equivalences:

$(p \land q) \lor (\neg p \land q) ⟺ q .$
$p \to q ⟺ \neg q \to \neg p$
$p \lor q ⟺ q \lor p .$

🔗

All tautologies are equivalent to one another.

🔗

Example 3.3.8. An equivalence to $1$ .

p \lor \neg p ⟺ 1 .

🔗

All contradictions are equivalent to one another.

🔗

Example 3.3.9. An equivalence to $0$ .

p \land \neg p ⟺ 0 .

🔗

Subsection 3.3.3 Implication

🔗

Consider the two propositions:

🔗

Table 3.3.10.

x :

The money is behind Door A; and

y :

The money is behind Door A or Door B.

🔗

Imagine that you were told that there is a large sum of money behind one of two doors marked A and B, and that one of the two propositions

x

and

y

is true and the other is false. Which door would you choose? All that you need to realize is that if

x

is true, then

y

will also be true. Since we know that this can’t be the case,

y

must be the true proposition and the money is behind Door B.

🔗

This is an example of a situation in which the truth of one proposition leads to the truth of another. Certainly,

y

can be true when

x

is false; but

x

can’t be true when

y

is false. In this case, we say that

x

implies

y .

🔗

Consider the truth table of

p \to q,

Table 3.1.7. If

p

implies

q,

then the third case can be ruled out, since it is the case that makes a conditional proposition false.

🔗

Definition 3.3.11. Implication.

🔗

Let

S

be a set of propositions and let

r

and

s

be propositions generated by

S .

We say that

r

implies

s

r \to s

is a tautology. We write

r \Rightarrow s

to indicate this implication.

🔗

Example 3.3.12. Disjunctive Addition.

A commonly used implication called “disjunctive addition” is

p \Rightarrow (p \lor q),

which is verified by truth table Table 3.3.13.

🔗

Table 3.3.13. Truth Table to verify that

p \Rightarrow (p \lor q)

$p$	$q$	$p \lor q$	$p \to p \lor q$
0	0	0	1
0	1	1	1
1	0	1	1
1	1	1	1

🔗

If we let

p

represent “The money is behind Door A” and

q

represent “The money is behind Door B,”

p \Rightarrow (p \lor q)

is a formalized version of the reasoning used in Example 3.3.12. A common name for this implication is disjunctive addition. In the next section we will consider some of the most commonly used implications and equivalences.

🔗

When we defined what we mean by a Proposition Generated by a Set, we didn’t include the conditional and biconditional operators. This was because of the two equivalences

p \to q \Leftrightarrow \neg p \lor q

and

p \leftrightarrow q \Leftrightarrow (p \land q) \lor (\neg p \land \neg q) .

Therefore, any proposition that includes the conditional or biconditional operators can be written in an equivalent way using only conjunction, disjunction, and negation. We could even dispense with disjunction since

p \lor q

is equivalent to a proposition that uses only conjunction and negation.

🔗

Subsection 3.3.4 A Universal Operation

🔗

We close this section with a final logical operation, the Sheffer Stroke, that has the interesting property that all other logical operations can be created from it. You can explore this operation in Exercise 3.3.5.8

🔗

Definition 3.3.14. The Sheffer Stroke.

🔗

The Sheffer Stroke is the logical operator defined by the following truth table:

Table 3.3.15. Truth Table for the Sheffer Stroke

$p$	$q$	$p ∣ q$
0	0	1
0	1	1
1	0	1
1	1	0

🔗

Exercises 3.3.5 Exercises

🔗

1.

🔗

Given the following propositions generated by

p,

q,

and

r,

which are equivalent to one another?

🔗
$(p \land r) \lor q$
🔗
$p \lor (r \lor q)$
🔗
$r \land p$
🔗
$\neg r \lor p$
🔗
$(p \lor q) \land (r \lor q)$
🔗
$r \to p$
🔗
$r \lor \neg p$
🔗
$p \to r$

Answer.

a \Leftrightarrow e, d \Leftrightarrow f, g \Leftrightarrow h

🔗

2.

🔗

🔗
Construct the truth table for $x = (p \land \neg q) \lor (r \land p) .$
🔗
Give an example other than $x$ itself of a proposition generated by $p,$ $q,$ and $r$ that is equivalent to $x .$
🔗
Give an example of a proposition other than $x$ that implies $x .$
🔗
Give an example of a proposition other than $x$ that is implied by $x .$

🔗

3.

🔗

Is an implication equivalent to its converse? Verify your answer using a truth table.

Solution.

No. In symbolic form the question is: Is

(p \to q) \Leftrightarrow (q \to p) ?

\begin{array}{ccccc} p & q & p \to q & q \to p & (p \to q) \leftrightarrow (q \to p) \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \end{array}

This table indicates that an implication is not always equivalent to its converse.

🔗

4.

🔗

Suppose that

x

is a proposition generated by

p,

q,

and

r

that is equivalent to

p \lor \neg q .

Write out the truth table for

x .

🔗

5.

🔗

How large is the largest set of propositions generated by

p

and

q

with the property that no two elements are equivalent?

Solution.

Let

x

be any proposition generated by

p

and

q .

The truth table for

x

has 4 rows and there are 2 choices for a truth value for

x

for each row, so there are

2 \cdot 2 \cdot 2 \cdot 2 = 2^{4}

possible propositions.

🔗

6.

🔗

Find a proposition that is equivalent to

p \lor q

and uses only conjunction and negation.

🔗

7.

🔗

Explain why a contradiction implies any proposition and any proposition implies a tautology.

Answer.

0 \to p

and

p \to 1

are tautologies.

🔗

8.

🔗

The significance of the Sheffer Stroke is that it is a “universal” operation in that all other logical operations can be built from it.

🔗
Prove that $p | q$ is equivalent to $\neg (p \land q) .$
🔗
Prove that $\neg p \Leftrightarrow p | p .$
🔗
Build $\land$ using only the Sheffer Stroke.
🔗
Build $\lor$ using only the Sheffer Stroke.

🔗

9.

🔗

Are the converse and inverse of a conditional proposition equivalent? Verify your answer using a truth table.

Solution.

Yes. In symbolic form the question is whether, if we have a conditional proposition

p \to q,

(q \to p) \Leftrightarrow (\neg p \to \neg q) ?

\begin{array}{ccccc} p & q & q \to p & \neg p \to \neg q & (q \to p) \leftrightarrow (\neg p \to \neg q) \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{array}

This table indicates that an converse is always equivalent to the inverse.

Applied Discrete Structures

Search Results:

Section 3.3 Equivalence and Implication

Subsection 3.3.1 Tautologies and Contradictions

Definition 3.3.2. Tautology.

Example 3.3.3. Some Tautologies.

Definition 3.3.4. Contradiction.

Example 3.3.5. Some Contradictions.

Subsection 3.3.2 Equivalence

Definition 3.3.6. Equivalence.

Example 3.3.7. Some Equivalences.

Example 3.3.8. An equivalence to $1$ .

Example 3.3.9. An equivalence to $0$ .

Subsection 3.3.3 Implication

Definition 3.3.11. Implication.

Example 3.3.12. Disjunctive Addition.

Subsection 3.3.4 A Universal Operation

Definition 3.3.14. The Sheffer Stroke.

Exercises 3.3.5 Exercises

1.

2.

3.

4.

5.

6.

7.

8.

9.

Section 3.3 Equivalence and Implication

Subsection 3.3.1 Tautologies and Contradictions

Definition 3.3.2. Tautology.

Example 3.3.3. Some Tautologies.

Definition 3.3.4. Contradiction.

Example 3.3.5. Some Contradictions.

Subsection 3.3.2 Equivalence

Definition 3.3.6. Equivalence.

Example 3.3.7. Some Equivalences.

Example 3.3.8. An equivalence to 1.

Example 3.3.9. An equivalence to 0.

Subsection 3.3.3 Implication

Definition 3.3.11. Implication.

Example 3.3.12. Disjunctive Addition.

Subsection 3.3.4 A Universal Operation

Definition 3.3.14. The Sheffer Stroke.

Exercises 3.3.5 Exercises

1.

2.

3.

4.

5.

6.

7.

8.

9.

Example 3.3.8. An equivalence to $1$ .

Example 3.3.9. An equivalence to $0$ .