Question about Final Exam I will have a date for you by Tuesday of next week CS 416 Artificial Intelligence Lecture 13 First Order Logic Chapter 8 What do we like about propositional logic First order logic We saw how propositional logic can create intelligent behavior It is Declarative Relationships between variables are described A method for propagating relationships But propositional logic is a poor representation for complex environments Expressive Can represent partial information using disjunction Why Compositional First order logic is a more expressive and powerful representation If A means foo and B means bar A B means foo and bar What don t we like about propositional logic Natural Language English appears to be expressive Lacks expressive power to describe the environment concisely Squares adjacent to pits are breezy Separate rules for every square square relationship in Wumpus world But natural language is a medium of communication not a knowledge representation Much of the information and logic conveyed by language is dependent on context Information exchange is not well defined Not compositional combining sentences may mean something different It is ambiguous Page 1 But we borrow representational ideas from natural language Ontology Natural language syntax a specification of a conceptualization A description of the objects and relationships that can exist Nouns and noun phrases refer to objects People houses cars Verbs and verb phrases refer to relationships btw objects Propositional logic had only true false relationships First order logic has many more relationships Red round nearby eaten Some relationships are clearly defined functions where there is only one output for a given input The ontological commitment of languages is different Best friend first thing plus How much can you infer from what you know We build first order logic around objects and relations Temporal logic defines additional ontological commitments because of timing constraints Higher order logic Another characterization of a logic First order logic is first because you relate objects the first order entities that actually exist in the world Epistemological commitments The possible states of knowledge permitted with respect to each fact There are 10 chickens chickens number 10 There are 10 ducks ducks number 10 In first order logic each sentence is a statement that is You cannot build relationships between relations or functions True false or unknown There are as many chickens as ducks chickens number ducks number the number of objects belonging to a group must be a property of the group and not the objects themselves Cannot represent Leibniz s law If x and y share all properties x is y Formal structure of first order logic First order logic syntax Models of first order logic contain Constant Symbols A set of objects its domain A B Bob Alice Hat Alice Alice s left arm Bob Bob s hat Predicate Symbols Relationships between objects Is onHead hasColor person Represented as tuples Function Symbols Sibling Alice Bob Sibling Bob Alice On head Bob hat Person Bob Person Alice Mother leftLeg Some relationships are functions if a given object is related to exactly one object in a certain way Each predicate and function symbol has an arity Alice Alice s left arm A constant the fixes the number of arguments Page 2 First order logic syntax Syntax Names of things are abitrary Term Knowledge base adds meaning A logical expression that refers to an object Constants Number of possible domain elements is unbounded We could assign names to all objects like providing a name for every shoe in your closet Number of models is unbounded Function symbols Used in place of a constant symbol OnLeftFoot John Checking enumeration by entailment is impossible Atomic Sentences Complex sentences Formed by a predicate symbol followed by parenthesized list of terms We can use logical connectives Sibling LeftLeg Alice Bob Sibling Alice Bob Sibling Bob Alice Sibling Alice Bob Married Father Alice Mother Bob An atomic sentence is true in a given model under a given interpretation if the relation referred to by the predicate symbol holds among the objects referred to by the arguments Quantifiers Universal Quantification A way to express properties of entire collections of objects Forall x P P is true for every object x Forall x King x Person x Universal quantification forall The power of first order logic Forallx King x Person x is a xvariable x xKing Person x Page 3 Richard the Lionheart King John Richard s left leg John s left leg The crown Universal Quantification Existential Quantification There exists There exists an x such that Crown x OnHead x John It is true for at least one object Note that all of these are true Implication is true if premise is false Using AND instead of implication is overly strong By asserting a universally quantified sentence you assert a whole list of individual implications AND is the appropriate connective Existential Quantification Nested Quantifiers Building more complex sentences What if we used implication as the connective Everybody loves somebody There is someone who is loved by everyone Implication is true if both premise and conclusion are true or if premise is false Use unique variable names and parentheses when appropriate Richard the Lionheart is not a crown first assertion is true and existential is satisfied Combining Combining Everyone who dislikes parsnips there does not exist someone who likes parsnips De Morgan s rules apply Everyone likes ice cream there is no one who does not like ice cream Page 4 Equality An Example A Tell Ask interface for a first order knowledge base Two terms refer to the same object Sentences are added with Tell Father John Henry These are called assertions Tell KB King John Tell KB Forall x King x Person x Richard has at least two brothers Queries are made with Ask Ask KB King John Ask KB Person John Notice this sentence is not the same An Example The Wumpus World Quantified queries More precise axioms than with propositional logic Ask KB exist x Person x Percept has five values Time is important A typical sentence KB should return a list of variable term pairs that satisfy the query Percept Stench Breeze Glitter None None 5 The actions are terms Turn right Turn left Forward Shoot Grab Release Computing best action with a query Exist a BestAction a 5 The Wumpus World Wumpus World After executing query KB responds with variable term list a Grab Then tell the