First Order Predicate Logic (FOPL) PDF

First order predicate logic (FOPL) Artificial intelligence Kristóf Karacs PPKE-ITK Recap n What is intelligence? n Agent model n Problem solving by search n Propositional logic 1 Outline n Semantics n New e...

First order predicate logic (FOPL) Artificial intelligence Kristóf Karacs PPKE-ITK Recap n What is intelligence? n Agent model n Problem solving by search n Propositional logic 1 Outline n Semantics n New elements ¨ Predicates ¨ Functions ¨ Variables ¨ Quantifiers n Parts of logic formulas n Instantiation and substitution First order predicate logic n More powerful than propositional logic n Models contain objects ¨ Domain of a model is its set of objects (domain elements) n Domain elements are related in various ways; formally as a set of ordered tuples ¨ capital = {, , … } 2 Semantics of FOPL n An interpretation maps domain objects, relations, and functions to symbols n Domains may have infinitely many objects (e.g., all integers) ¨ Number of models and interpretations is unbounded ¨ Model checking not applicable to check entailment Predicates n Predicates express relations between certain things ¨ Predicate name identifies the relationship ¨ Arguments are the things being related (constants, functions and variables) ¨ Arity is the number of arguments n Examples ¨ Binary (arity=2): capital = {, , … } ¨ Unary (arity=1) city = {Budapest, Rome, … } 3 Functions n Special predicates n In a function of arity n ¨ The first n - 1 arguments are inputs ¨ The last argument is the output (single-valued) n Example ¨ Predicate form: sum_of(2,3,5) ¨ Functional form: sum_of(2,3) ® 5 ¨ inputs: 2,3; output: 5 Variables n How to express a sentence like ¨ “There’s a drink in Starbucks the price of which is $2.” n price_of(drink, starbucks) = $2 ¨ Problem: drink is a constant n price_of(X, starbucks) = $2 ¨X is a variable referring to some drink ¨ Problem: which drink? 4 Quantifiers n Symbol for “there exists”: $ (“existential quantifier”) ¨$ X (price_of(X, Starbucks) = $2) n Symbol “for all”: " (“universal quantifier”) ¨ “All cats like milk.” : " X (cat(X) → likes(X, milk)) ¨ “All drinks cost $2.” expresses n “Beer costs $2.” n “Wine costs $2.” n etc. n Variables can be instantiated Terms n A term is a logical expression that refers to an object in the domain ¨ Constant symbols (e.g. Hungary) ¨ Variables ¨ Function values (e.g. capital(Hungary)) 5 Logic formulas n An atomic formula is statement that combines ¨ Terms (referring to objects), and ¨ Predicate symbols (referring to relations) n Example: capital(Hungary, Budapest) n A literal is an atomic formula or its negation n A compound formula is formed from literals using logical connectives n A sentence is a logic formula in which all variables are bound Instantiation and substitution n FOPL sentences have quantified variables ¨ Instantiation (“grounding”) ¨ Ground terms (constants, functions of ground terms) n Substitution of a variable ¨ Grounding: replacing the variable by a ground term ¨ Replacing the variable by another variable n Example ¨ " X,Y friend(X, Y) ¨ Subst({X/Sue, Y/Mary}) ¨ friend(X, Y) = friend(Sue, Mary) 6 Summary n Semantics n New elements ¨ Predicates ¨ Functions ¨ Variables ¨ Quantifiers n Parts of logic formulas n Instantiation and substitution 7