1First Order LogicFirst Order LogicRussell and Norvig: Chapters 8 and 9CMSC421 – Fall 2002based on material from Marie desJardins, Jean-Claude Latombe, Stuart RussellPropositional logic is a weak languageHard to identify “individuals.” E.g., Mary, 3 Can’t directly talk about properties of individuals or relations between individuals. E.g. “Bill is tall” Generalizations, patterns, regularities can’t easily be represented. E.g., all triangles have 3 sides First-Order Logic (abbreviated FOL or FOPC) is expressive enough to concisely represent this kind of situation. FOL adds relations, variables, and quantifiers, e.g., “Every elephant is gray”: ∀ x (elephant(x) → gray(x)) “There is a white alligator”: ∃ x (alligator(X) ^ white(X))ExampleConsider the problem of representing the following information:  Every person is mortal.  Confucius is a person.  Confucius is mortal. How can these sentences be represented so that we can infer the third sentence from the first two? Example cont.In PL we have to create propositional symbols to stand for all or part of each sentence. For example, we might do:  P = “person”; Q = “mortal”; R = “Confucius”so the above 3 sentences are represented as:  P => Q; R => P; R => Q Although the third sentence is entailed by the first two, we needed an explicit symbol, R, to represent an individual, Confucius, who is a member of the classes “person” and “mortal.”To represent other individuals we must introduce separate symbols for each one, with means for representing the fact that all individuals who are “people” are also "mortal.”Problems with the propositional Wumpus hunter Lack of variables prevents stating more general rules. E.g., we need a set of similar rules for each cellChange of the KB over time is difficult to represent Standard technique is to index facts with the time when they’re true This means we have a separate KB for every time point.First-order logicFirst-order logic (FOL) models the world in terms of  Objects, which are things with individual identities Properties of objects that distinguish them from other objects Relations that hold among sets of objects Functions, which are a subset of relations where there is only one “value” for any given “input”Examples:  Objects: Students, lectures, companies, cars ...  Relations: Brother-of, bigger-than, outside, part-of, has-color, occurs-after, owns, visits, precedes, ...  Properties: blue, oval, even, large, ...  Functions: father-of, best-friend, second-half, one-more-than ...2A BNF for FOLS := <Sentence> ;<Sentence> := <AtomicSentence> | <Sentence> <Connective> <Sentence> |<Quantifier> <Variable>,... <Sentence> |"NOT" <Sentence> |"(" <Sentence> ")"; <AtomicSentence> := <Predicate> "(" <Term>, ... ")" |<Term> "=" <Term>;<Term> := <Function> "(" <Term>, ... ")" |<Constant> |<Variable>;<Connective> := "AND" | "OR" | "IMPLIES" | "EQUIVALENT";<Quantifier> := "EXISTS" | "FORALL" ;<Constant> := "A" | "X1" | "John" | ... ;<Variable> := "a" | "x" | "s" | ... ;<Predicate> := "Before" | "HasColor" | "Raining" | ... ; <Function> := "Mother" | "LeftLegOf" | ... ;Domain of DiscourseConstant symbols, which represent individuals in the world Mary 3 GreenFunction symbols, which map individuals to individuals father-of(Mary) = John color-of(Sky) = Blue Predicate symbols, which map individuals to truth values greater(5,3) green(Grass)  color(Grass, Green) FOL SyntaxVariable symbols E.g., x, y, fooConnectives Same as in PL: not (~), and (^), or (v), implies (=>), if and only if (<=>) Quantifiers Universal ∀x or (Ax) Existential ∃x or (Ex) QuantifiersUniversal quantification  (∀x)P(x) means that P holds for all values of x in the domain associated with that variable E.g., (∀x) dolphin(x) => mammal(x) Existential quantification  (∃ x)P(x) means that P holds for some value of x in the domain associated with that variable E.g., (∃ x) mammal(x) ^ lays-eggs(x) Permits one to make a statement about some object without naming itSentences and WFFsA term (denoting a real-world individual) is a constant symbol, a variable symbol, or an n-place function of n terms.  x and f(x1, ..., xn) are terms, where each xi is a term.  A term with no variables is a ground term An atomic sentence (which has value true or false) is either  an n-place predicate of n terms, or, term = termA sentence is an atomic sentence ~P(x) , P(x) ∨ Q(y), P(x) ^ Q(y), P(x) =>Q(y), P(x) <=> Q(y) where P(x) and Q(y) are sentences if P (x) is a sentence and x is a variable, then (∀x)P(x) and (∃x)P(x) are sentences A well-formed formula (wff) is a sentence containing no “free” variables. i.e., all variables are “bound” by universal or existential quantifiers.  (∀x)R(x,y) has x bound as a universally quantified variable, but y is free. QuantifiersUniversal quantifiers are often used with “implies” to form “rules”: (∀x) student(x) => smart(x) means “All students are smart”Universal quantification is rarely used to make blanket statements about every individual in the world:  (∀x)student(x)^smart(x) means “Everyone in the world is a student and is smart”Existential quantifiers are usually used with “and” to specify a list of properties about an individual: (∃x) student(x) ^ smart(x) means “There is a student who is smart”A common mistake is to represent this English sentence as the FOL sentence: (∃x) student(x) => smart(x) What’s the problem?3Quantifier ScopeSwitching the order of universal quantifiers does not change the meaning:  (∀x)(∀y)P(x,y) <=> (∀y)(∀x) P(x,y)Similarly, you can switch the order of existential quantifiers: (∃x)(∃y)P(x,y) <=> (∃y)(∃x) P(x,y) Switching the order of universals and existential does change meaning:  Everyone likes someone: (∀x)(∃y) likes(x,y)  Someone is liked by everyone: (∃y)(∀x) likes(x,y)Connections between All and ExistsWe can relate sentences involving ∀and ∃ using De Morgan’s laws: (∀x) ~P(x)<=> ~(∃x) P(x) ~(∀x)P(x) <=> (∃x) ~P(x) (∀x) P(x) <=> ~ (∃x) ~P(x) (∃x) P(x) <=> ~(∀x) ~P(x)Translating English to FOLEvery gardener likes the sun. (∀x) gardener(x) => likes(x,Sun) You can fool some of the people all of the time. (∃x) (∀t) can-fool(x,t) (∃x) (person(x) ^ ((∀t)(