Page 27 - Discrete Mathematics and Its Applications

6 1 / The Foundations: Logic and Proofs

TABLE 4 The Truth Table for TABLE 5 The Truth Table for
the Exclusive Or of Two the Conditional Statement
Propositions. p → q.
p q p ⊕ q p q p → q

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

DEFINITION 4 Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q, is the proposition
that is true when exactly one of p and q is true and is false otherwise.

The truth table for the exclusive or of two propositions is displayed in Table 4.

Conditional Statements

We will discuss several other important ways in which propositions can be combined.

DEFINITION 5 Let p and q be propositions. The conditional statement p → q is the proposition “if p, then
q.” The conditional statement p → q is false when p is true and q is false, and true otherwise.
In the conditional statement p → q, p is called the hypothesis (or antecedent or premise)
and q is called the conclusion (or consequence).

The statement p → q is called a conditional statement because p → q asserts that q is true
on the condition that p holds. A conditional statement is also called an implication.
The truth table for the conditional statement p → q is shown in Table 5. Note that the
statement p → q is true when both p and q are true and when p is false (no matter what truth
value q has).
Because conditional statements play such an essential role in mathematical reasoning, a
variety of terminology is used to express p → q. You will encounter most if not all of the
following ways to express this conditional statement:

“if p, then q” “p implies q”
“if p, q” “p only if q”
“p is sufficient for q” “a sufficient condition for q is p”
“q if p” “q whenever p”
“q when p” “q is necessary for p”
“a necessary condition for p is q” “q follows from p”
“q unless ¬p”
A useful way to understand the truth value of a conditional statement is to think of an
obligation or a contract. For example, the pledge many politicians make when running for office
is

“If I am elected, then I will lower taxes.”