6 Pages
Unlock Document

Temple University
Computer & Information Science
CIS 1166
David Shulman

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

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.