Page 25 - Discrete Mathematics and Its Applications

4 1 / The Foundations: Logic and Proofs

Table 1 displays the truth table for the negation of a proposition p. This table has a row
TABLE 1 The
Truth Table for for each of the two possible truth values of a proposition p. Each row shows the truth value of
the Negation of a ¬p corresponding to the truth value of p for this row.
Proposition. The negation of a proposition can also be considered the result of the operation of the
negation operator on a proposition. The negation operator constructs a new proposition from
p ¬p
a single existing proposition. We will now introduce the logical operators that are used to form
T F new propositions from two or more existing propositions. These logical operators are also called
F T connectives.

DEFINITION 2 Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition
“p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise.

Table 2 displays the truth table of p ∧ q. This table has a row for each of the four possible
combinations of truth values of p and q. The four rows correspond to the pairs of truth values
TT, TF, FT, and FF, where the first truth value in the pair is the truth value of p and the second
truth value is the truth value of q.
Note that in logic the word “but” sometimes is used instead of “and” in a conjunction. For
example, the statement “The sun is shining, but it is raining” is another way of saying “The sun
is shining and it is raining.” (In natural language, there is a subtle difference in meaning between
“and” and “but”; we will not be concerned with this nuance here.)

EXAMPLE 5 Find the conjunction of the propositions p and q where p is the proposition “Rebecca’s PC has
more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s
PC runs faster than 1 GHz.”

Solution: The conjunction of these propositions, p ∧ q, is the proposition “Rebecca’s PC has
more than 16 GB free hard disk space, and the processor in Rebecca’s PC runs faster than 1
GHz.” This conjunction can be expressed more simply as “Rebecca’s PC has more than 16 GB
free hard disk space, and its processor runs faster than 1 GHz.” For this conjunction to be true,
both conditions given must be true. It is false, when one or both of these conditions are false. ▲

DEFINITION 3 Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the proposition
“p or q.” The disjunction p ∨ q is false when both p and q are false and is true otherwise.

Table 3 displays the truth table for p ∨ q.

TABLE 2 The Truth Table for TABLE 3 The Truth Table for
the Conjunction of Two the Disjunction of Two
Propositions. Propositions.

p q p ∧ q p q p ∨ q
T T T T T T
T F F T F T
F T F F T T
F F F F F F