Exercises 143for i < j and j > 0, A[i] < A[j]-that is, that the elements of A are in increasing or-
der. The loop invariant here is a formula that is supposed to be true at the beginning of
each pass through the loop as well as true after the last pass, when control returns-(here
with limit = -1) to test that the loop is finished. The accepted formal language for loop
invariant assertions uses quantified formulas.W Exercises
Let U = {1, 2, 3, 4) be the universal set for Exercises 1 through 4.1. Rewrite (Vx e U) P (x) as a conjunction that uses no quantifiers.
2. Rewrite (3x e U) P (x) as a disjunction that uses no quantifiers.
- Rewrite -(Vx e U) P(x) as a conjunction that uses no quantifiers.
4. Rewrite --(3x) P (x) as a conjunction that uses no quantifiers.
- For the following predicates with universal set IR, state the meaning of the predicate in
a sentence. If it is false, give an example to show why. (Example: Vx (ly (x < y)) says
"for every real number, there is a bigger number." This is true.)
(a) Vx(3y(x 0 0 -- xy = a))
(b) 3y(Vx(x # 0 -- xy = 1))
(c) 3x(Vy(y < x))
(d) Vx(3y(x + y = x))(e) 3y(Vx(x + y = x))
(f) Vx(Vy(3z(x < Z A Z < y)))(g) Vx(Vy(x 0 y -* 3z((x <Z AZ <y) V (x > Z A Z>y))))
(h) Vx(Vy(Vz((x > y A y > Z) -) x > Z)))- For each of the following formulas write a formula 0 (using quantifiers) expressing
the formula, find a formula in negation normal form equivalent to -'4, and express the
meaning of the negation in words.
(a) For every x and for every y, x + y = y + x.
(b) Every number x has a square root. (Do not use the square root symbol; use only
multiplication.)
(c) For some y, 2x^2 + 1 is always greater than x^2 y. (Hint: In this example, "always"
suggests a universal quantifier.)(d) For some x and y, x < y, and x^3 - x > y^3 _ y.
(e) For every x and y, there is a z where 2z = x + y.(f) For every x and y, if x3 + x - 2 = y^3 + y - 2, then x = y.
- For each quantified formula that follows: find a universe U and predicates A and B in
which the formula is true and U, A and B in which it is false.
(a) Vx(((A(x) V B(x)) A --(A(x) A B(x)))
(b) VxVy(P(x, y) - P(y, x))
(c) Vx(P(x) - 3yQ(x, y))
(d) 3x(A(x) A VyB(x, y))
(e) VxA(x) -- (VxB(x) -+ (Vx(A(x) -+ B(x))))