Page 31 - Discrete Mathematics and Its Applications

10 1 / The Foundations: Logic and Proofs

EXAMPLE 10 Let p be the statement “You can take the flight,” and let q be the statement “You buy a ticket.”
Then p ↔ q is the statement
“You can take the flight if and only if you buy a ticket.”

This statement is true if p and q are either both true or both false, that is, if you buy a ticket and
can take the flight or if you do not buy a ticket and you cannot take the flight. It is false when
p and q have opposite truth values, that is, when you do not buy a ticket, but you can take the
flight (such as when you get a free trip) and when you buy a ticket but you cannot take the flight
(such as when the airline bumps you). ▲

IMPLICIT USE OF BICONDITIONALS You should be aware that biconditionals are not
always explicit in natural language. In particular, the “if and only if” construction used in
biconditionals is rarely used in common language. Instead, biconditionals are often expressed
using an “if, then” or an “only if” construction. The other part of the “if and only if” is implicit.
That is, the converse is implied, but not stated. For example, consider the statement in English
“If you finish your meal, then you can have dessert.” What is really meant is “You can have
dessert if and only if you finish your meal.” This last statement is logically equivalent to the
two statements “If you finish your meal, then you can have dessert” and “You can have dessert
only if you finish your meal.” Because of this imprecision in natural language, we need to
make an assumption whether a conditional statement in natural language implicitly includes its
converse. Because precision is essential in mathematics and in logic, we will always distinguish
between the conditional statement p → q and the biconditional statement p ↔ q.

Truth Tables of Compound Propositions

We have now introduced four important logical connectives—conjunctions, disjunctions, con-
ditional statements, and biconditional statements—as well as negations. We can use these con-
nectives to build up complicated compound propositions involving any number of propositional
variables. We can use truth tables to determine the truth values of these compound propositions,
as Example 11 illustrates. We use a separate column to find the truth value of each compound
expression that occurs in the compound proposition as it is built up. The truth values of the
compound proposition for each combination of truth values of the propositional variables in it
is found in the final column of the table.

EXAMPLE 11 Construct the truth table of the compound proposition

(p ∨¬q) → (p ∧ q).

Solution: Because this truth table involves two propositional variables p and q, there are four
rows in this truth table, one for each of the pairs of truth values TT, TF, FT, and FF. The first
two columns are used for the truth values of p and q, respectively. In the third column we find
the truth value of ¬q, needed to find the truth value of p ∨¬q, found in the fourth column. The
fifth column gives the truth value of p ∧ q. Finally, the truth value of (p ∨¬q) → (p ∧ q) is
found in the last column. The resulting truth table is shown in Table 7. ▲

TABLE 7 The Truth Table of (p ∨¬ q) → (p ∧ q).
p q ¬q p ∨¬q p ∧ q (p ∨¬q) → (p ∧ q)

T T F T T T
T F T T F F
F T F F F T
F F T T F F