LESSON 20: INTRODUCTION TO QUANTIFIERS (sections 9.1-9.4)POWERPOINT SLIDE #1Assigned reading pp. 229-241:Examples of quantification (phrases that refer to quantities of things):every cubesome students from USCmost vipers in the playpenthe dodecahedron in the bathroomthree blind miceno student of logicwheneverPOWERPOINT SLIDE #2Quantification is not truth functional. For example, the truth or falsity of the sentence “Every rich actor is a good actor” cannot be determinedby checking the truth values of parts of the sentence, not in the same way as you can check “b is cube and c is a cube”. Instead, the truth of the first sentence must be determined by the relationship between the collection of rich actors and the collection of good actors (i.e., by whether all members of the former set are also members of the latter set). This is a new animal compared to what we’ve dealt with before.POWERPOINT SLIDE #3Two kinds of terms: individual constants (e.g., a, b, claire) and variables (e.g., t, x, y18,). Variables do not refer to specific objects the way individual constants do; variables are placeholders that indicate relationships between quantifiers and the arguments of predicates. (This last statement will make more sense soon . . .)POWERPOINT SLIDE #4The Universal Quantifier: ∀means “every” (or “all”) ∀x is translated “for every object x …”POWERPOINT SLIDE #5∀x Home(x) = “For every object x, x is at home”, or simply “everything is at home”Binding: In the above expression we say that the universal quantifier ∀ binds the variable x. Without the quantifier present, as in just the expression Home(x), the variable is said to be unbound or free. POWERPOINT SLIDE #6∀x (Doctor(x) Smart(x)) = “Every doctor is smart” (literally: “For every x, if x is a doctor, then x is smart”)Scope: In the above sentence, the scope of the quantifier is shown by the outer parentheses; that is, the quantifier binds the x-variables on both the predicate ‘Doctor’ and the predicate ‘Smart’. POWERPOINT SLIDE #7In the earlier example, ∀x Home(x), no parentheses are needed because the scope of the quantifier is simply over the one predicate Home and its variable x. POWERPOINT SLIDE #8The Existential Quantifier: ƎMeans “some” (i.e., at least one)Ǝx = “for some object x …” POWERPOINT SLIDE #9Ǝx Home(x) = “For some object x, x is at home” or just “something is at home”Ǝx (Doctor(x) ᴧ Smart(x)) = “Some doctor is smart” or “There is at least one smart doctor”POWERPOINT SLIDE #10Binding and scope work exactly the same with the existential quantifier as they did with the universal quantifier. POWERPOINT SLIDE #11Be careful, though: The expression Ǝx Doctor(x) ᴧ Smart(x) looks misleadingly similar to the above example, but notice that it is missing the enclosing parentheses. This indicates that the scope of the existential quantifier in the latter example is only over Doctor(x) and NOT over Smart(x). We say that the first x-variable (as an argument of the predicate Doctor) is bound but the second x-variable (as an argument of Smart) is free.POWERPOINT SLIDE #12For an expression containing variables to be a sentence, all of the variables must be bound by some or other quantifier. If there are any unbound variables in the expression, the expression can at most be a well-formed formula (wf), not a sentence.Well-formed formulas (wfs): Expressions that have the proper formal structure of sentences of FOL (i.e., they contain predicates with terms as arguments—either constants or variables—and possibly quantifiers and connectives as well), all generated according to the grammatical rules of FOL, but possibly containing unbound variables. Sentences: Those wffs in which all variables (if any) are bound.POWERPOINT SLIDE #13On pp. 233-234, the texbook provides a list of the generative rules of FOL. Basically, these rules say that you can take atomic wffs, or wffs that have the same sort of structure as atomic sentences—as the wff Doctor(x) parallels the structure of Doctor(max)—and you can negate them or combine them with any of the connectives we’ve already studied (conjunction, disjunction, material conditional, biconditional) or place a quantifier in front of them. And you can do this over and over to construct increasingly complex wffs.POWERPOINT SLIDE #14 (wffs that are not sentences)So, taking everything we’ve said above into account, all of the following expressions #1-8 are wfs of FOL,but only #5-8 are also sentences: 1. Cube(x) ᴧ ¬Cube(y)2. ∀x Doctor(x) Smart(x)3. Ǝy RightOf (x,y)4. (Cube(x) ᴧ Small(x)) Ǝy LeftOf (x,y)POWERPOINT SLIDE #15 (wffs that are also sentences)5. Cube(a) ᴧ Cube(b) “a and b are cubes”[notice a and b are individual constants, not variables, so they don’t need to be bound] 6. ∀x (Doctor(x) Smart(x)) “Every doctor is smart”7. ∀x ((Cube(x) ᴧ Small(x)) Ǝy LeftOf (x,y)) “Every small cube is to the left of some object”8. Ǝz (Tet(z) ᴧ Large(z)) “There is a large tetrahedron”POWERPOINT SLIDE #16 (ill-formed expressions)The following four sentences are not wffs at all (we can say they are ‘ill-formed’) because they are not generated by (i.e., they violate) the grammatical rules of FOL:9. SameSize ¬(a, b)(ill-formed because negation misplaced)10. ∀b SameRow(b,c)(ill-formed because individual constant b can’t be quantified)11. FrontOf(b,c,d) Cube(x) (ill-formed only because FrontOf should have only two arguments)12. Ǝu RightOf (u,a) Tet(z5) ᴠ Between(u,a,z5)(ill-formed only because a set of parentheses is missing to disambiguate the phrasing of the different connectives ) POWERPOINT SLIDE #17The last important concept from today’s reading is that of satisfaction. We need this concept because otherwise we would not be able to determine whether sentences containing quantifiers are true or false.The book goes into somewhat tedius detail on this point in section 9.4, but the basic idea is really simple:A sentence like Ǝx (Cube(x) ᴠ Tet(x)) is true iff there is at least one actual object which, if ‘plugged into’ the x-variable placeholder positions of the sentence, would ‘satisfy’ the wff Cube(x) ᴠ Tet(x) by being either a Cube or a Tet. POWERPOINT SLIDE #18 Similarly, the sentence ∀x (Doctor(x) Smart(x)) is true iff every object ‘plugged into’ the wff (Doctor(x)
View Full Document
Unlocking...