9 Pages
Unlock Document

Computer & Information Science
CIS 1166
David Shulman

Quanti▯cational Logic Part 1 1 What is Quanti▯cational Logic? Quanti▯cational Logic is the logic of the operators for all and there exists. We need to be able to reason automatically about these operations and we need notation to help us express precisely certain requirements and relationships that can be expressed in terms of these operators. Quanti▯cational Logic allows us to reason about more things than we could reason with just using propositional logic. There are many di▯erent names for the quanti▯cational logic this note descrbes. We also could call it predicate calculus, ▯rst-order logic and many other things. The name predicate calculus comes from the fact that predi- cates play an important role in this logic; this logic allows us to reason not only about whole sentences but also about individual entities such as Socrates or the number 6 and their properties such as being mortal or greater than 3. The name ▯rst-order logic comes from the fact that certain more complex constructions are not allowed in our logic. In this note I shall try to explain the semantics and syntax of some of the more basic aspects of this logic. I shall also discuss some simple rules that help you; among these rules will be De Morgan rules for quanti▯cation. One thing to keep in mind when you write your own formulae in Quan- ti▯cation logic is that this logic should be treated like a strictly typed pro- gramming language. In a language like C or Java if you declare f to be a function that takes 3 integers as inputs and outputs integers, then if you give it the wrong number of inputs or inputs of the wrong type, you get nonsense and you cannot write f(g, x, z) if x is a char, g is another function, and z is complex expression that evaluates to a string of integers because f takes three integers as input. It is very important that you not write similar nonsense when working with quanti▯cational logic. 1 2 Predicates Before we can discuss quanti▯ers such as for all and there exists, we need to say something about predicates. When we say all x have some property such as being mortal or greater than 3, it helps us if we do not have to think about all entities including your father’s father’s favorite song, the ▯rst boat to use a harbor in Portugal to depart for the Far East and other irrelevant things when we only care about all animals or all people or all real numbers. There is also a danger of paradox if we do not restrict our domain of interest. So we need to talk about predicates that apply to certain lists of inputs, only inputs satisfying certain type constraints. 3 Variables We have symbols representing variables, symbols such as x, y, z. Associated with each of these variables is a domain of things that they might possibliy represent. In the simplest case all variables represent things belonging to the same domain such as real numbers, people, words etc. But in general variables can be of di▯erent types. 4 Constants We also have symbols such as 3, SOCRATES etc. that designate indivual objects. 5 Predicates An m place predicate is something that takes a list of m entities that belong to the correct domains and outputs a truth value truth or false. So for example there is the 1 place or monadic predicate HEALTHY that takes as input a person and outputs true or false depnding of whether that person is healthy. Of course there is also a similar predicate with a somewhat di▯eent domain where we allow our input to be any animal or maybe any animal or machine. We have the two place predicate KNOWS which has as input a list of 2 people x and y and if the input is given with x ▯rst y second, then the output is true i▯ x knows y; otherwise the output is false. We have the two 2 place predicate < which is input a list x, y of integers and outputs true or false depending on whether x is less than y or not; there is also a very similar predicate (represented by the same symbol) that takes as input 2 reals and outputs true or false depending on whether the ▯rst number is less than the second number. Some more predicates: There is a three place predicate PLUS such that for PLUS (x, y, z) to make sense x, y, z must be integers and PLUS(x, y, z) is TRUE i▯ x+y = z; otherwise we output false. There are also very similar predicates that use real number input. 6 Universal and Existential Quanti▯cation There are two quanti▯ers we use. We have 8 and 9 meaning for all and there exists respectively. There are other quanti▯ers but these are the two basic quanti▯ers and in fact it will turn out that we could get away with using just one of these quanti▯ers. If P is a propositional formula (something that would become a propo- sition if we gave de▯nite values to the variables appearing in the formula), then 8xP means no matter what allowed value is given to x, P is true and 9xP means there is an allowed value for x that makes P true. There might be many such values but as long as we have one, we are o.k. Note in the special case where your domain is empty (say you are quan- tifying over unicorns and there are no unicorns), then 9xP must be false; if there are no unicorns hence there is no unicorn that makes P true. If there are no unicorns and unicorns is our domain then 8x;P is TRUE because there is no unicorn available to prove the statement false. (If this seems strange to you, just accept that this rule makes reasoning by computer simpler.) 7 Warnings and Cautions about Quanti▯ers and Predicates I can de▯ne a four place predicate S whose input domain (for all inputs) is the real numbers and such that S(x;y;z;w) i▯ x + y = z. Here w is totally irrelevant but you have to write the fourth input. So S(3;2;5;81) is true and S(3;4;98;7) is false. 3 Another important point is that input must be of the required type. If I de▯ne a predicate SPEAKS whose ▯rst input has domain the set of people and whose second input has domain the set of languages, it is ▯ne to write SPEAKS(Alice, Latin), but it not ▯ne to write SPEAKS(Alice, a romance language). A romance language is not one speci▯c language. You could instead write 9x SPEAKS(Alice, x) ^ RomanceLanguage(x). Another example of type violation: Let SUM(x, y, z) be true i▯ x+y = z where the required domains are all the integers. Then it is bad to write SUM(3, 5, < 9). < 9 does not represent an integer. It actually by itself does not represent anything but if it represented anything it would be the set of integers less than 9 and that is not an integer. You also must not write SPEAKS(Ebenezer, Latin and Greek). You would write instead SPEAKS(Ebenezer, Latin) ^ SPEAKS(Ebenezer, Greek). I will discuss later the precise rules of quanti▯ciational logic syntax but things are a little more complicated if we use di▯erent domains for all our vari- ables. We could instead use one big domain. So for the predicate SPEAKS, we might have one domain that includes both people and languages and say SPEAKS(x, y) is true i▯ x is a person and y is a language and x speaks y and false otherwise. (But of course SPEAKS(x, y) is nonsense if x or y represents something that is neither a language nor a person. So we can say SPEAKS(Latin, Alice) or SPEAKS(Latin, Latin), which are both false but SPEAKS(4, Latin) is nonsense because 4 is neither a language nor a person. If you wanted to say that 4 people speak Latin, you would say 9x9y9z9w (SPEAKS(x, Latin) and SPEAKS(y, Latin) and SPEAKS (z, Latin) and SPEAKS (w, Latin) and NOT EQUAL(x, y) and NOT EQUAL (x, z) and NOT EQUAL (x, w) and NOT EQUAL (y, z) and NOT EQUAL (y, w) and NOT EQUAL (z, w)) where you must use ^ where I wrote the word and and use y 6= z instead of NOT EQUAL(y, z) and similarly with the other occurences of NOT EQUAL. 8 Implementing Quanti▯ers with a Program If your domain D is ▯nite and the variable x has to represent an element of domain D, then you can implement 8xP(x) on your computer if you can implement P on your computer and you can also implement 9xP(x). To implement 8xP, proceed as follows: Initialize RESULT = true then loop through all possible values of x and for each value d, do if P has value false 4 when x = d, set RESULT = false and escape loop. When done with the loop return RESULT. Thus if you never get P has truth value false, you return TRUE. To implement 9xP, proceed as follows: Initialize RESULT = false then loop through all possible valiues of x and for each value d, do if P has value true when x = d, set RESULT = true and escape loop. When done with the loop return RESULT. This way if you never get P has truth value true, you return FALSE. In practice you would not really implement such a loop, but thinking about such an imaginary program might help us understand precisely how quanti▯ers work. 9 Some Example Translations Let S be a two place predicate such that S(x, y) means person x speaks language y and other than that I will just use standard relations such as < on the real numbers. Notice that predicates are usually written before their inputs but special predicate
More Less

Related notes for CIS 1166

Log In


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.