Bridge to Abstract Mathematics: Mathematical Proof and Structures

3.1 BASIC CONCEPTS OF THE PREDICATE CALCULUS 85

2. The truth set of p(x) vq(x) equals (1, 3,4, 5,6, 79) = (1, 3,5,7,9) u
   {3,4, 5, 6, 7) = P u Q.


3. The truth set of q(x) A r(x) equals (4) = (3,4,5,6,7) n (1,4 9) =
   Q n R.

These observations set the pattern for our formal approach to compound
predicates:

DEFINITION 2

Let p(x) and q(x) be propositional functions over a domain of discourse

U, with truth sets P and Q, respectively. We define the truth set of

It is not so immediately evident how to define the truth sets of p(x) -, q(x)
and p(x) o q(x), but consider the following. Suppose that Ax) and q(x) are
propositional functions such that the proposition p(a) ++ q(a) is a tautology
for every specific substitution of an element a from U for the variable x.
For example, p(x) might be r(x) vs(x), while q(x) might be s(x) v r(x)
[recall that (r v s) - (s v r) is a tautology]. We would certainly expect
p(x) and q(x) to be logically equivalent (i.e., P = Q) over any domain of
discourse. With this in mind, we recall from Article 2.3 that (p -, q) t,
( - p v q) and (p - q) - [( - p v q) A (p v q)] are tautologies, leading to
the next definition.

DEFINITION 3

Given p(x) and q(x) as in Definition 2, we define the truth set of

(d) p(x) -* q(x), if p(x), then q(x), to be FY u Q

(e) p(x) ++ q(x), p(x) if and only if q(x), to be (P u Q) n (P u Q')

It may be instructive here to test the reasonableness of Definitions 2 and

3 (relative to the definitions of the connectives in Articles 2.1 and 2.2) by

looking at some specific open sentences. As one instance, it should be that,

if a is a specific element of U, and p(a) -, q(a) is a true statement (by the

truth tabular definition of Article 2.2), then a E P' u Q, the set we have just

designated as the truth set of p(x) -, q(x). On the other hand, if p(a) + q(a)

is false, then a should lie outside P' u Q. The following example illustrates

this correspondence.

EXAMPLE 2 Let U = R and define propositional functions in one variable,

p(x) and q(x), by p(x): 1x1 s 1 and q(x): I x - 1 I < 1. Use Definitions 2 and

3 to calculate the truth sets of p(x) A q(x) and p(x) -, q(x). Use specific

examples to check that these results are consistent with the truth tabular

definitions of the connectives A and + from Chapter 2.