Page 46 - Discrete Mathematics and Its Applications

1.3 Propositional Equivalences 25

1.3 Propositional Equivalences

Introduction

An important type of step used in a mathematical argument is the replacement of a statement
with another statement with the same truth value. Because of this, methods that produce propo-
sitions with the same truth value as a given compound proposition are used extensively in the
construction of mathematical arguments. Note that we will use the term “compound proposi-
tion” to refer to an expression formed from propositional variables using logical operators, such
as p ∧ q.
We begin our discussion with a classification of compound propositions according to their
possible truth values.

DEFINITION 1 A compound proposition that is always true, no matter what the truth values of the proposi-
tional variables that occur in it, is called a tautology. A compound proposition that is always
false is called a contradiction. A compound proposition that is neither a tautology nor a
contradiction is called a contingency.

Tautologies and contradictions are often important in mathematical reasoning. Example 1 illus-
trates these types of compound propositions.
EXAMPLE 1 We can construct examples of tautologies and contradictions using just one propositional vari-
able. Consider the truth tables of p ∨¬p and p ∧¬p, shown in Table 1. Because p ∨¬p is
always true, it is a tautology. Because p ∧¬p is always false, it is a contradiction. ▲

Logical Equivalences

Compound propositions that have the same truth values in all possible cases are called logically
equivalent. We can also define this notion as follows.

DEFINITION 2 The compound propositions p and q are called logically equivalent if p ↔ q is a tautology.
The notation p ≡ q denotes that p and q are logically equivalent.

Remark: The symbol ≡ is not a logical connective, and p ≡ q is not a compound proposition
but rather is the statement that p ↔ q is a tautology. The symbol ⇔ is sometimes used instead
of ≡ to denote logical equivalence.

One way to determine whether two compound propositions are equivalent is to use a truth
table. In particular, the compound propositions p and q are equivalent if and only if the columns

TABLE 1 Examples of a Tautology
and a Contradiction.
p ¬p p ∨¬p p ∧¬p
T F T F
F T T F