Discrete Mathematics for Computer Science

146 CHAPTER 2 Formal Logic

(e) 3x((P(x) v Q(x)) -+ R(x))

(f) 3x((P(x) -+ Q(x)) A R(x))

18. Find a formula in negation normal form equivalent to the negation of

Vx3y((P(x, y) A Q(x, y)) -* R(x, y))

19. Give a universal set U and interpretations to predicates A, B, P, and Q so that each of
    the following quantified formulas is false:
    (a) (3xA(x) A 3xB(x)) -+ (3x(A(x) A B(x)))
    (b) (Vx3yP(x, y)) -- (3x(VyP(x, y)))
    (c) (Vx(P(x) -- Q(x))) -- ((3xP(x)) -+ (Vx)Q(x))
    (d) Vx (-,A (x)) *+-• -(VxA (x))


20. To negate an expression with a single quantifier, we can replace it with the other quanti-
    fier and negate the formula inside. This generalizes to an arbitrary string of quantifiers.
    For instance,

-,Vx3y3zVtP(x, y, z, t)

is logically equivalent to

3xVyVz3t(--P(x, y, z, t))

Prove this generalization by induction.

21. Given an array Values with n elements

Values[0], Values[l],.... Values[n - 1]

each containing a real number, the following algorithm finds the sum of all the positive

values in Values. Write an invariant for the loop.

rollingSum = 0

fori = 0, 2 ... , n-I

if Values[i] > 0

rollingSum = rollingSum + Values[i]

Output rollingSum

22. Challenge: A much more sophisticated sorting algorithm is the MergeSort algorithm.
    It comes in various versions; we do one here. The algorithm involves copying the list
    back and forth between two arrays, the input array A and an extra array B, so it takes
    a lot of extra space.
    Our version is not "optimized." We have attempted to keep it relatively simple to
    make it as easily understood as possible. Moreover, to simplify things for this exercise,
    we assume that the size of the input array is a power of 2; relatively easy adjustments
    would make it work for arrays of arbitrary sizes.