Textbook Notes
(363,149)

United States
(204,421)

Temple University
(1,805)

CIS 1166
(4)

David Shulman
(4)

Chapter

# QuantLogic2.pdf

Unlock Document

Temple University

Computer & Information Science

CIS 1166

David Shulman

Spring

Description

Quanti▯cational Logic Part 2
1 Nested Quanti▯ers
Part 2 of this note on quanti▯cational logic discusses nested quanti▯ers. Here
we might be quantifying over a statement that itself contains quanti▯ers. In
terms of computer implementation, we have a loop within a loop. There is
nothing essentially new with nested quanti▯ers. We have covered the basic
principles, but it helps to show more examples of how quanti▯ers work and
there are also special abbreviations that are often used when we have nesting
and that are helpful to know.
2 Nesting the Same Quanti▯er
You might nest several universal quanti▯ers to express some mathematical
laws such as
8x8y(x + y = y + x)
8x8y8z((x + y) + z = x + (y + z))
8x8y8z(x < y ^ y < z ! x < z)
Here we might let our domain for all variables be the reals and we are
expressing commutative and associative laws of addition and transitivity of
less than.
If S means SPEAKS as in part 1 of this note but this time our domain
for the ▯rst input is all people in our class and for the second input is all
Romance languages spoken by at least ▯ve million people, then we might
write 8x8yS(x;y) to means that everyone in our class speaks all the languages
we care about (Spanish, Italian, French, Romanian, Catalan etc.)
One point ot note is that often when we write mathematical or other
laws we do not explicitly write down all our quanti▯ers. We might write the
formula x + y = y + x and mean that the formula holds for all (relevant) x
1 and y. Thus there is a convention that variables that are not quanti▯ed over
by some explicitly written quanti▯er and that do not get speci▯c values by
other means are assumed to be quanti▯ed over by a universal quanti▯er.
We also have use for nested existential quanti▯cation. If we want to say
that someone speaks some lang2age,2we m2ght write 9x9yS(x;y).
We would write 9x9y9z(x + y = z ) to say that there are x, y, z in our
chosen domain that provide a solution for the equation x + y = z . 2
n
If we want to state Fermat’s last theorem, we would say :(9x9y9z9n(x +
y = z ^n > 2)). Here our domain of interest for all variables might as well
be the integers.
If we want to say that our chosen domain has at least two elements we
could write 9x9y(x 6= y).
2.1 Commutativity
If you are dealing with the same kind of quanti▯er, it does not matter how
you order the quanti▯ers.
8x8yP ▯ 8y8xP.
9x9yP ▯ 9y9xP.
(We shall see below that order de▯nitely does matter when the quanti▯ers
are di▯erent in kind.)
2.2 An Abbreviatory Convention
Since ordering of the same kind of quanti▯er does not a▯ect truth value, there
is a shortcut that is often used.
Instead of writing 8x8yP, we might write 8s;yP Instead of writing
9x9yP, we might write 9x;yP. There is a similar abbreviation if we had three
rather than two quanti▯ers so we might write 8x;y;z(x < y^y < z ! x < z).
DO NOT USE THIS ABBREVIATION if on a quiz or midterm I tell you
only to use basic quanti▯ers and do not use this abbreviation on the ▯nal
unless you are speci▯cally told that it is o.k. to use this abbreivation.
There is nothing wrong with the abbreviation; it is just that we might
be testing whether you understand what is really happening at the most
fundamental level.
When I write something like 9x;yP, I am really saying that there is a
pair x, y that makes P true and when I write something like 8x;yP, I am
really saying that all pairs x, y are such that P is true.
2 3 Heterogeneous Nested Quanti▯cation
Sometimes we need both forall and there exists. Let my domain be real
numbers for all variables, then we have 9x8y(x + y = y), there is an x such
that for all y, x + y = y. This statement is true (x = 0). Notice here we are
using the same x for all y.
We also have with the same domain, the real numbers, 8x9y(x + y = 0).
Here y is just the negative of x and we have to use a di▯erent y for each x.
So there is a di▯erence in meaning depending on which quanti▯er is ▯rst.
Another examples using our predicate S whose ▯rst input is a person and
whose second input is a language: If I write 8x9y(S(x;y)) that says everyone
speaks some language (but di▯erent people might not be able to communicate
because they have no language in common). 9y8x(S(x;y)) says there is a
universal language; there is a language y that everyone speaks so everyone
can communicate with everyone.
If I say 8y9x(S(x;y)), I am saying that every language is spoken by
someone; there are no languages without speakers. If I say 9x8y(S(x;y))
I am saying there is someone who speaks every language. Because the 9x
comes before the 8y I have to use the same x for all y and thus I am saying
that there is some one (the same person) who knows every single language;
there is no language this person does not know.
We see from these examples that with di▯erent kinds of quanti▯ers order
very much matters.
Another example with di▯erent quanti▯ers: To say that every two people
have a language in common you would say 8x8y9z(S(x;z)^S(y;z)) but here
the language z that x and y have in common could be di▯erent for di▯erent
pairs x, y.
4 Nested QUanti▯ers and Negation
I shall illustrate how one might apply De Morgan rules when there are many
quanti▯ers to rewrite expressions.
:8x9y8z:(:S(x;y) _ :S(y;z))

More
Less
Related notes for CIS 1166