56 LOGIC. PART I: THE PROPOSITIONAL CALCULUS Chapter 2
know the truth values of p and q, and not p and q themselves. Clearly then,
the connectives are crucial. We deal in this article with the five most
common logical connectives, "and," "or," "not," "if... then," and "if and
only if." We define each connective by specifying when a compound
statement involving it is true. We begin with negation, conjunction, and
disjunction.
NEGATION, CONJUNCTION, AND DISJUNCTION
DEFINITION 2
Given statements p and q, we define three statements formed from p and q.
(a) The negation (or denial) of p, denoted --p and read "not p," is true precisely
when p is false.
(b) The conjunction of p and 9, denoted p~ q and read "p and q," is true
precisely when p and q are both true.
(c) Thedisjunction (or alternation) of p and 9, denoted p v q and read "p or q,"
is true when one or the other or both of the statements p and 9 is (or are) true.If p represents the statement "5 is a prime number" (true) and q the state-
ment "5 times 9 equals 46" (false), then the statement -p (5 is @ a prime
number) is false, the statement -q (5 times 9 does not equal 46) is true, and
p A q is false (since q is false), but p v q is true (since p is true).
Although our definition of "and" corresponds to its normal usage in
English, the same is not true of "or." Everyday usage of or is "one or the
other, but not both" (exclusive alternation). The alternation we've defined,
often called the mathematical or, is inclusive, corresponding to "and/orm in
English.
When dealing with expressions such as -p, p A q, and p v - q, in a case
where p and q are variables representing unknown statements with un-
known truth values, we refer to these expressions as statement forms. A state-
ment form becomes a statement when a specific statement is substituted
each of its unknowns (the latter sometimes referred to as components). As it
stands, a statement form is neither true nor false; indeed, our immediate
interest is to determine under what truth conditions a given statement form
is true and when it is false. The most convenient device for illustrating the
truth values of a compound statement form under the various possible
truth conditions is the truth table. We construct truth tables for the three
previously defined connectives in Figure 2.1.
These truth tables may well be thought of as the definitions of the con-
nectives "not," "and," "or." Note that each row of a truth table specifies a
particular combination of truth values of the component(s); hence the num-
ber of rows equals the number of possible combinations of those truth
values (see Exercise 2). We see tables with two and four rows in Figure 2.1;
another situation occurs in the following example.