136 CHAPTER 2 Formal Logic
The second kind of quantification is existential quantification for the predicate P, such
as
3x (P(x)) read "For some x, P(x)" or "There exists an x such that P(x)"
is defined to mean "For some value of x in the universal set U, the predicate P(x) is true."Following the Vx or Ix, there is a formula in parentheses, such as (P (x)), although we
occasionally omit the parentheses. That formula, plus the Vx or the 3x itself, is called the
scope of the quantifier. Informally, we may leave out the parentheses, writing, for example,
just Vx P(x), but that is informal. The definition of scope is defined as if we had not left the
parentheses out. A similar idea of scope occurs in most computer programming languages.
In Section 2.7, we simply want to introduce predicates, formulas, and the use of quan-
tifiers. First Order Logic deals with predicates and quantification in much the same way as
propositional logic deals with propositions. We will focus on how universal and existential
quantifiers interact with each other and how they interact with negation. The study of in-
ferences in First Order Logic and other topics that we dealt with in propositional logic will
not be covered.
Example 2. For the universal set N and the usual meanings of the symbols - and =,
determine whether
3x(x - 3 = 1)
is true.Solution. We must find some x E N such that x - 3 = 1 is true. Choosing x = 4 is such
a value. 0
Clearly, many values for x may make the predicate T in Example 2. The quantifier
3x just says that we can definitely find one, if the predicate is T. The quantifier does not
exclude the possibility of finding more than one value for x that makes the predicate T.2.73 Restricted Quantification
It is understood that the universe U contains every object of concern to the current discus-
sion. In many applications, we want to discuss something more limited. Suppose V C U:
Vx E V (P(x)) read "For all x in V, P(x)"is defined to mean "For all values x in V, the assertion P (x) is true." Then,
3X E V(P(x))
read "For some x in V, P(x)" or "There exists an x in V such that P(x)"
is defined to mean "For some values of x in V, the assertion P(x) is true.'
Let i, j E N such that i < j. A set of j - i + 1 consecutive storage locations that cancontain the same type of values will be called an array, denoted as A[i .. j], where A
is any variable name. The contents of the individual storage locations will be denoted as
A[i], A[i + 11 ... I A[j]. For N E N, both A[0, .. N - 1] and A[l .. N] denote an array
with N elements.Example 3. Let V = {1, 2,..., 301, and let A[1.. 30] be an array such that for each index
i between 1 and 30, A[i] = i • i - 1. For the elements A[l], A[2] .... A[301, write a
predicate that says:
(a) Every entry in the array is nonnegative.
(b) The value A[30] is the largest value.
(c) That every element of A is nonzero.