Bridge to Abstract Mathematics: Mathematical Proof and Structures

60 LOGIC, PART I: THE PROPOSITIONAL CALCULUS Chapter 2

Figure 2.3 The statement form p A -p

is always false, whereas p v - p is always

true.

F T

both statement forms. Column 3 of the table in Figure 2.3 consists en-

tirely of F's and column 4 solely of T's, as claimed. 0

Can you think of any other examples of tautologies or contradictions by

using the three connectives -, v , and A available to us so far? (Hint: One

occurred in Exercise 3, Article 2.1 .) Another possible idea is that we can

always generate a contradiction if we know a tautology, by negating that

tautology, and vice versa. What new examples are suggested by this

comment?

A large part of our study of statement forms concerns relationships

among various forms. One such important relationship is given by the next

definition.

DEFINITION 2

Two compound statement forms that have the same truth values as each other

under all possible truth conditions for their components are said to be logically

equivalent.

EXAMPLE 2 Show that the statement forms -(pvq) and -PA -q are

logically equivalent.

Solution We do this by constructing a truth table of four rows and seven

columns, as shown in Figure 2.4, noting that the entries in the columns

/'

headed by - p A - q and - (p v q) are identical.

Figure 2.4 The statement forms - p A - q and - (p v q) have the same

truth values as each other, under all possible truth conditions.