View Question
Q: Predicate Logic Translations for Comparisons ( Answered ,   0 Comments )
 Question
 Subject: Predicate Logic Translations for Comparisons Category: Science > Math Asked by: istarius-ga List Price: \$20.00 Posted: 23 May 2006 19:16 PDT Expires: 22 Jun 2006 19:16 PDT Question ID: 731853
 ```I am looking for someone who can show how to translate into predicate logic sentences which compare the qualities of two terms. The specific example I'm looking for is a universal generalization which would claim: Oranges have more Vitamin C than Apples. This is to say that each and every object which is an orange has more vitamin c than each and every object which is an apple. I imagine that this would be done in second-order predicate logic, using the universal quantifier (?), and entail an explanation about the various terms and symbolization.```
 ```Hi istarius-ga, It is not necessary to use second-order predicate logic to express that Oranges have more Vitamin C than Apples. First-order predicate logic includes the universal quantifier (?) and functions, which is sufficient for your example. First we define a function: "Let C(x) represent the Vitamin C content of 'x'." Then we can express that Oranges have more Vitamin C than Apples: ? orange, apple: C(orange) > C(apple) You can read this as: "For all possible pairings of an orange and an apple, the Vitamin C content of the orange is greater than the Vitamin C content of the apple" Unlike colloquial English, where we can express a generalization such as "Oranges have more Vitamin C than Apples", first-order predicate logic makes us specify a property that holds for EVERY possible pairing of apple and orange. (We could also express a property that holds for SOME possible pairings of apple and orange by using "There Exists" (?). However, "There Exists" is not applicable to your example.) A note of caution: a wide range of notational variants is in use for first-order predicate logic. For example, we could also write your formula this way: ?orange ?apple greater(C(orange), C(apple)) Here's another variant, using just ASCII characters: \A orange,apple . greater(C(orange), C(apple)) That notation is interesting, because you can use it to type your formula into the online "Kniffel" application, which can process the formula in various ways. Kniffel can typeset it into LaTex or PNG format, represent it as a tree, convert it to conjunctive normal form or disjunctive normal form, check for structural errors, etc: "Kniffel: First Order Predicate Logic Converter" http://www.raboof.at/cgi-bin/kniffel_cgi?input_formula=%5CA+orange%2Capple+.+greater%28C%28orange%29%2C+C%28apple%29%29&convert=none&submit=Submit You can find much further information about First-order logic at Wikipedia: http://en.wikipedia.org/wiki/Predicate_logic I hope I have answered your question at the level that you are seeking. If anything is not clear, please use the "Request Clarification" feature. Regards, eiffel-ga Google Search Strategy: "predicate logic" ://www.google.com/search?q=%22predicate+logic%22&hl=en``` Request for Answer Clarification by istarius-ga on 24 May 2006 21:46 PDT ```Eiffel, Thanks for taking interest in my question, though I am hoping for some clarification. Predicate logic, fully formalized, as I remember it, translates terms such as 'orange' and 'apple' into terms like Ox, for 'x is an orange'. So, a statement such as "all presidents are liars" might be represented as: ?x(Px -> Lx) Or so I remember. Given these constraints, could you clarify the answer to represent a full predicate logic formalization? (I have an idea of what this would look like, but then again my memory of translations is faded, indeed.)``` Clarification of Answer by eiffel-ga on 25 May 2006 05:57 PDT ```Hi istarius-ga, In my earlier answer, I used 'apple' and 'orange' as typed variables. The types were implicit: the variable 'apple' ranged over apples, and the variable 'orange' ranged over oranges: "Values of the variables are taken from an understood universe of discourse; a refinement of first-order logic allows variables ranging over different sorts of object." http://en.wikipedia.org/wiki/Predicate_logic We can make the typing explicit, by using variables 'x' and 'y' which range over 'things': ? x, y: orange(x) and apple(y) implies C(x) > C(y) This is well-formed, yet it doesn't correspond to your example unless the following things are known about the "universe of discourse": 1. orange(z) is a predicate indicating whether z is an orange 2. apple(z) is a predicate indicating whether z is an apple 3. C(z) is a function giving the Vitamin C content of z 4. ">" represents the greater-than relation 5. 'x' and 'y' are variables ranging over 'things' As before, there are different notational conventions in use, and we can write this in more than one way. The version above uses words rather than symbols for logical-and ("and") and logical-conditional ("implies"), and has a precedence convention where ">" and "and" have a higher precedence than "implies", which avoids the need to use parentheses. Here is a version that can be used as input to the Kniffel tool: \A x,y . (orange(x) & apple(y) => greater(C(x), C(y))) http://www.raboof.at/cgi-bin/kniffel_cgi?input_formula=%5CA+x%2Cy+.+%28orange%28x%29+%26+apple%28y%29+%3D%3E+greater%28C%28x%29%2C+C%28y%29%29%29&convert=none&submit=Submit and here's another version, using symbols throughout and maximum parenthesization: ?x ?y ( (orange(x) ? apple(y)) ? (C(x) > C(y)) ) Informally, we can read this as "For all 'x' and 'y': if 'x' is an orange and 'y' is an apple, it implies that the Vitamin C content of 'x' is greater than the Vitamin C content of 'y'". We can apply various transformations to this, resulting in alternative ways of expressing the same thing. For example, here it is re-cast into conjunctive normal form: ?x ?y ( ¬(orange(x) ? ¬apple(y) ? (C(x) > C(y)) ) This says that for all 'x' and 'y': EITHER 'x' is not an orange OR ELSE 'y' is not an apple OR ELSE the Vitamin C content of 'x' is greater than the Vitamin C content of 'y'. I hope this clarification provide the information that you are seeking. If not, feel free to request further clarification. Regards, eiffel-ga``` Clarification of Answer by eiffel-ga on 25 May 2006 06:03 PDT ```Hi istarius-ga, One more thing: using a notation similar to the one you used for your "President" example leads to this version... ?x,y ( (Ox ? Ay) ? (C(x) > C(y)) ) where: 1. Oz is a predicate indicating whether z is an orange 2. Az is a predicate indicating whether z is an apple 3. C(z) is a function giving the Vitamin C content of z 4. ">" represents the greater-than relation 5. 'x' and 'y' are variables ranging over 'things' Regards, eiffel-ga```