Bridge to Abstract Mathematics: Mathematical Proof and Structures

3.4 QUANTIFICATION OF PROPOSITIONAL FUNCTIONS IN SEVERAL VARIABLES 107

NEGATION OF PROPOSITIONAL

FUNCTIONS IN SEVERAL VARIABLES

In parts (a) and (b) of Theorem 1, Article 3.3, we saw how to formulate a
positive statement of the negation of universally and existentially quantified
predicates in one variable. We now extend this to propositional functions
of two variables; in particular, we look at propositions involving mixed
quantifiers.

EXAMPLE 4 Formulate a positive statement of the negation of
(W(~Y)HX, Y).

Solution We must find a quantified predicate equivalent to

• [(Vx)(Iy)p(x, y)] in which negation is not a main connective. Let s(x)
  represent (3y)p(x, y). Then - [(Vx)(3y)p(x, y)] is the same as - [(Vx)(s(x))]
  which, by Theorem l(a), Article 3.3, is equivalent to (3x)(-s(x)). But


• s(x) in turn is - [(3y)p(x, y)] which, by Theorem l(b), Article 3.3, is
  equivalent, for fixed x, to (Vy)(-p(x, y)). Hence our original statement


• [(W(3y)p(x, y)] is equivalent to (3x)(vy)( -- p(x, Y)). €I

Example 4 indicates that a statement of the form (Vx)(3y)p(x, y) is negated
by changing V to 3,3 to V, and negating the predicate p(x, y). It is left to you
[Exercise 5(c)J to provide an argument, similar to that given in Example 4,
showing that the same process is used to negate (3x)(Vy)p(x, y). We sum-
marize these facts and deal, for the record, with negations of nonmixed
quantifiers as well in the next theorem:

THEOREM 3

For any propositional function p(x, y) in two variables:

Like Theorem 2, Theorem 3 generalizes to propositional functions in
any finite number of variables. To negate a statement involving the predi-
cate p(x,, x,,... , x,), preceded by n quantifiers, we use the guiding rule:

Change each universal quantifier V to 3, change each existential

quantifier 3 to V, and negate the predicate.

EXAMPLE 5 Express the negation of (Vw)(3~)(3y)(Vz)p(w, x, y, z) in a form
that does not have negation as a main connective.

Soh tion By the preceding principle, - [(Vw)(3x)(3 y)(Vz)p(w, x, y, z)] is
equivalent to (3w)(Vx)(V y)(3z)(- p(w, x, y, z)). 0