CMSC 671 Fall 2001Today’s classBasic Knowledge Representation in First-Order LogicFirst-order logicA BNF for FOLUser providesFOL ProvidesQuantifiersSentences are built from terms and atomsTranslating English to FOLSlide 11Quantifier ScopeConnections between All and ExistsAxioms, definitions and theoremsAxioms for Set Theory in FOLExtensions to FOLHigher-order logicLambda operatorExpressing uniquenessNotational differencesLogical agents for the Wumpus WorldA simple reflex agentRepresenting change: The frame problemRepresenting changeSituationsSituation calculusDeducing hidden propertiesDeducing hidden properties IIDeducing hidden properties IIIPreferences among actionsSlide 31Slide 32Goal-based agentsCMSC 671CMSC 671Fall 2001Fall 2001Class #12/13 – Thursday, October 11 / Tuesday, October 16Today’s class•First-order logic–Properties, relations, functions, quantifiers, …–Terms, sentences, wffs, axioms, theories, proofs, …•Extensions to first-order logic•Logical agents–Reflex agents–Representing change: situation calculus, frame problem–Preferences on actions–Goal-based agentsBasic Knowledge Basic Knowledge Representation in Representation in First-Order LogicFirst-Order LogicChapter 7Some material adopted from notes by Andreas Geyer-SchulzFirst-order logic•First-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 ...A 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" | ... ;User provides•Constant symbols, which represent individuals in the world–Mary–3–Green•Function 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 Provides•Variable symbols–E.g., x, y, foo•Connectives–Same as in PL: not (~), and (^), or (v), implies (=>), if and only if (<=>) •Quantifiers–Universal x or (Ax)–Existential x or (Ex)Quantifiers•Universal 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 are built from terms and atoms•A 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 atom (which has value true or false) is either an n-place predicate of n terms, or, ~P, PQ, P^Q, P=>Q, P<=>Q where P and Q are atoms•A sentence is an atom, or, if P is a sentence and x is a variable, then (x)P and ( x)P 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)P(x,y) has x bound as a universally quantified variable, but y is free.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) (person(x) ^ time(t)) => can-fool(x,t) You can fool all of the people some of the time.(x)(t) (person(x) ^ time(t) => can-fool(x,t) All purple mushrooms are poisonous.(x) (mushroom(x) ^ purple(x)) => poisonous(x) No purple mushroom is poisonous.~(x) purple(x) ^ mushroom(x) ^ poisonous(x) (x) (mushroom(x) ^ purple(x)) => ~poisonous(x) There are exactly two purple mushrooms.(x)(y) mushroom(x) ^ purple(x) ^ mushroom(y) ^ purple(y) ^ ~(x=y) ^ (Az) (mushroom(z) ^ purple(z)) => ((x=z) v (y=z)) Clinton is not tall.~tall(Clinton) X is above Y if X is on directly on top of Y or there is a pile of one or more other objects directly on top of one another starting with X and ending with Y.(x)(y) above(x,y) <=> (on(x,y) v (z) (on(x,z) ^ above(z,y)))Quantifiers•Universal 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) –But what happens when there is a person who is not a student?Quantifier Scope•Switching 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) P~(x)P <=> (x) ~P(x) P <=> ~ (x) ~P(x)