CS 416 Artificial Intelligence Lecture Lecture 15 15 First Order First Order Logic Logic Chapter Chapter 99 Guest Speaker Topics Topics in in Optimal Optimal Control Control Minimax Minimax Control Control and and Game Game Theory Theory March March 28 28thth 22 p m p m OLS OLS 005 005 Onesimo Onesimo Hernandez Lerma Hernandez Lerma Department Department of of Mathematics Mathematics CINVESTAV IPN CINVESTAV IPN Mexico Mexico City City This This is is aa nontechnical nontechnical introduction introduction mainly mainly thru thru examples examples to to some some recent recent topics topics in in control control and and game game theory theory including including adaptive adaptive control control minimax minimax control control a k a a k a worst case worst case control control or or games games against against nature nature partially partially observable observable systems systems a k a a k a controlled controlled hidden hidden Markov Markov models models cooperative cooperative and and noncooperative noncooperative game game equilibria equilibria etc etc Final Exam Final Final Exam Exam will will be be May May 66thth at at 7 00 7 00 p m p m This This conflicts conflicts with with the the fewest fewest number number of of other other exams exams Forward Chaining Remember Remember this this from from propositional propositional logic logic Start Start with with atomic atomic sentences sentences in in KB KB Apply Apply Modus Modus Ponens Ponens add add new new sentences sentences to to KB KB discontinue discontinue when when no no new new sentences sentences Hopefully Hopefully find find the the sentence sentence you you are are looking looking for for in in the the generated generated sentences sentences Lifting forward chaining First order First order definite definite clauses clauses all all sentences sentences are are defined defined this this way way to to simplify simplify processing processing disjunction disjunction of of literals literals with with exactly exactly one one positive positive clause clause is is either either atomic atomic or or an an implication implication whose whose antecedent antecedent is is aa conjunction conjunction of of positive positive literals literals and and whose whose consequent consequent is is aa single single positive positive literal literal Example The The law law says says itit is is aa crime crime for for an an American American to to sell sell weapons weapons to to hostile hostile nations nations The The country country Nono Nono an an enemy enemy of of America America has has some some missiles missiles and and all all of of its its missles missles were were sold sold to to itit by by Colonel Colonel West West who who is is American American We We will will prove prove West West is is aa criminal criminal Example ItIt is is aa crime crime for for an an American American to to sell sell weapons weapons to to hostile hostile nations nations Nono Nono has has some some missles missles Owns Owns Nono Nono M1 M1 Missile Missile M1 M1 All All of of its its missiles missiles were were sold sold to to itit by by Colonel Colonel West West Example We We also also need need to to know know that that missiles missiles are are weapons weapons and and we we must must know know that that an an enemy enemy of of America America counts counts as as hostile hostile West West who who is is American American The The country country Nono Nono an an enemy enemy of of America America Forward chaining Starting Starting from from the the facts facts find find all all rules rules with with satisfied satisfied premises premises add add their their conclusions conclusions to to known known facts facts repeat repeat until until query query is is answered answered no no new new facts facts are are added added First iteration of forward chaining Look Look at at the the implication implication sentences sentences first first must must satisfy satisfy unknown unknown premises premises We We can can satisfy satisfy this this rule rule by by substituting substituting x M1 x M1 and and adding adding Sells West Sells West M1 M1 Nono Nono to to KB KB First iteration of forward chaining We We can can satisfy satisfy with with x M1 x M1 and and Weapon Weapon M1 M1 is is added added We We can can satisfy satisfy with with x Nono x Nono and and Hostile Hostile Nono Nono is is added added Second iteration of forward chaining We We can can satisfy satisfy with with x West x West y M1 y M1 z Nono z Nono and and Criminal Criminal West West is is added added Analyze this algorithm Sound Sound Does Does itit only only derive derive sentences sentences that that are are entailed entailed Yes Yes because because only only Modus Modus Ponens Ponens is is used used and and itit is is sound sound Complete Complete Does Does itit answer answer every every query query whose whose answers answers are are entailed entailed by by the the KB KB Yes Yes ifif the the clauses clauses are are definite definite clauses clauses Proving completeness Assume Assume KB KB only only has has sentences sentences with with no no function function symbols symbols What s What s the the most most number number of of iterations iterations through through algorithm algorithm Depends Depends on on the the number number of of facts facts that that can can be be added added Let Let kk be be the the arity arity the the max max number number of of arguments arguments of of any any predicate predicate and and Let Let pp be be the the number number of of predicates predicates Let Let nn be be the the number number of of constant constant symbols symbols At At most most pn pnkk distinct distinct ground ground facts facts Fixed Fixed point point is is reached reached after after this this many many iterations iterations A A proof proof by by contradiction contradiction shows shows that that the the final final KB KB is is complete complete Complexit of this algorithm Three Three sources sources of of complexity complexity inner inner loop loop requires requires finding finding all all unifiers unifiers such such that that premise premise of of rule rule unifies unifies with with facts facts of of database database this this pattern pattern matching matching is is expensive expensive must must check check every every rule rule on on every every iteration iteration to to check check ifif its its premises premises are are satisfied satisfied many many facts facts are are generated generated that that are are irrelevant