j 84 LOGIC, PART II: THE PREDICATE CALCULUS Chapter 3
truth set of some propositional function, namely, the open sentence "x E P."
If P is the truth set of a propositional function p(x), then p(x) is logically
equivalent (over its domain U) to the open sentence "x E P."
We can also use the "truth set" concept to extend the applicability of
the five logical connectives defined in Chapter 2 from propositions to prop-
ositional functions. As one example, given propositional functions p(x)
and q(x) over a common domain U, what meaning should we attach to the
expression p(x) v q(x)? Having familiarity with the "or" connective from
the propositional calculus, we read such an expression as "either p(x) or
q(x)." The expression contains a single variable x; it seems reasonable to
treat this "compound predicate" just as we would any predicate in one
variable. On that basis its truth set should consist of all objects a in U such
that the compound proposition p(a) v q(a) is true. According to Definition
2(c), Article 2.1, this means that an object a should be in the truth set of
the predicate p(x) v q(x) if and only if either the proposition p(a) is true or
the proposition q(a) is true (or possibly both). Similar criteria could be ap-
plied to the compound predicates p(x) A q(x) and - p(x). An object a should
be in the truth set of p(x) A q(x) if and only if p(a) and q(a) are both true
statements; an object a should be in the truth set of -p(x) if and only if
the proposition p(a) is false.EXAMPLE (^1) Let U = (1, 2, 3,... , 10). Let predicates Ax), q(x), and r(x) be
defined over U by p(x): x is odd, q(x): 3 I x < 8, r(x): x is the square
of an integer. Use the criteria outlined previously to describe the truth sets
of the compound predicates -p(x), p(x) v q(x), and q(x) A r(x).
Solution According to our criteria, an element a of U is in the truth set of
-Ax) if and only if p(a) is false; that is, a is not odd, g, a is even. Thus
the truth set of -p(x) is (2,4,6,8, 10). An integer a, between 1 and 10
inclusive, is in the truth set of p(x) vq(x) if and only if either p(a) is
true or q(a) is true; that is, either a is odd or 3 I a < 8. The truth set
of p(x) v q(x) therefore equals (1, 3,4, 5,6,7,9). Finally, an element a of
U is in the truth set of q(x) A r(x) if and only if q(a) and r(a) are both true;
the truth set in this case equals (4). 0
The results of Example. 1 suggest an important connection between the
truth set of a compound predicate and the truth sets of its component pred-
icates. This connection highlights, at the same time, important connec-
tions between the algebra of logic and the algebra of sets, and more
specifically, correspondences between the logical connectives and, or, and
not, and the set operations intersection union, and complement, respectively.
In particular, in Example 1, we had P = (1, 3, 5, 7,9), Q = (3,4, 5, 6,7f,
and R = (1,4,9). Note that:
- The truth set of -Ax) equals (2,4,6, 8, 10) = (1, 3,5, 7,9)' = P'.