Discrete Mathematics for Computer Science

140 CHAPTER 2 Formal Logic

Example 7. For the universal set N, is 3x ((x - 3 = 1) A (x > 3)) true?

Solution. Since the quantifier is 3x, there need be only one such x for the formula to be

true; 4 is such an x. U

Example 8. For the universal set N, which of the following formulas are true?

(a) 3x((x+3=2) V(x-2= 1))

(b) 3x ((x .x - 3 =) v (x > 3))

Solution.

(a) True; choose x = -1. Because -1 + 3 = 2 is true, (-1 + 3 = 2) v (-1 -2 = 1) is

also true.

(b) Also true; choose x = 4. Then, 4 > 3 is true, so the disjunction is also true. How about

x =2,2.2-3=1. U

Example 9. In universe N, which of the following formulas are true?

(a) Vx ((x^2 - 2x + 1 = 0) V (x > x))

(b) Vx ((x < 3) v (x > 3))

Solution. This solution is left as an exercise for the reader. U

In Table 2.10 we summarize the relationship between quantification and A and v.

Since all the logical operators can be expressed in terms of - and A or -- and v (see

Exercise 1 in Section 2.9.4), this table should provide a guide to answering questions about

the relationships between other logical operators and quantification. Below, 4) =• * stands

for "40 logically implies 4'," and 4) .ý *' stands for "o) is logically equivalent to 4'."

Table 2.10 Logical Relations for Quantified Formulas

in One Variable

3x (P(x) A Q(x)) =: (3x P(x)) A (=x Q(x))

3x (P(x) v Q(x)) (3x P(x)) v (3x Q(x))

Vx (P(x) A Q(x)) € (Vx P(x)) A (Vx Q(x))

(Vx P(x)) V (Vx Q(x)) W= Vx (P(x) V Q(x))

The formulas 3x P(x) A 3y P(y) and 3x 3y (P(x) A P(y)), at first sight, both seem

to say that there are (at least) two objects satisfying predicate P. This, however, is not true.

There is nothing in the formula saying that x : y-that is, that x and y refer to different

objects. So, both formulas say there is (at least) one object satisfying P. To say there are

two different objects satisfying P, one would have to say they're different-for example,

3x 3y (P(x) A P(y) A x 0 y)

Example 10. For an array of 20 entries with integer entries, write a predicate that says

all the elements are distinct.

Solution. Let V = { 1, 2. 201 represent the indexes for the entries into an array

A[ 1.. 20]. Now,

Vm E V (Vn E V ((m :A n) -* (A[m] A A[n]))

says that all the elements are distinct. In this case, another predicate is Vm E V (Vn E

V ((m < n) -- (A[mi] : A[n]))). We leave it for the reader to explain why. 0