Unification Soundness of GMP Need to show that =/John,y/John)works provided thatp=p for all i UN1FY(a,到=8ifa8=8 Lemma:For any definite clause p.we have p=pe by Ul 1.(A..AB,→=(A..AA→g8=(h8A..AB,8→8 0 I.v/. her(John) 3.From 1 and 2,ge follows by ordinary Modus Ponens y/John.r/ Unification Example knowledge base ce immediately if The law that it is a crime for an Am can to sell v r/John.u/Jotn)works UNIFY(a.3)=e if 0=80 Prove that Col. on Jane) John.r/Mother(John) nows(.O zing ap eg.. Knows(en.O.n) -t鞋 Generalized Modus Ponens(GMP) Example knowledge base contd. where p'=p:e for all is Kin Unification We can get the inference immediately if we can find a substitution θ such that King(x) and Greedy(x) match King(John) and Greedy(y) θ = {x/John, y/John} works Unify(α, β) = θ if αθ = βθ p q θ Knows(John, x) Knows(John, Jane) {x/Jane} Knows(John, x) Knows(y, OJ) {x/OJ, y/John} Knows(John, x) Knows(y, Mother(y)) {y/John, x/Mother(John)} Knows(John, x) Knows(x, OJ) Chapter 9 13 Unification We can get the inference immediately if we can find a substitution θ such that King(x) and Greedy(x) match King(John) and Greedy(y) θ = {x/John, y/John} works Unify(α, β) = θ if αθ = βθ p q θ Knows(John, x) Knows(John, Jane) {x/Jane} Knows(John, x) Knows(y, OJ) {x/OJ, y/John} Knows(John, x) Knows(y, Mother(y)) {y/John, x/Mother(John)} Knows(John, x) Knows(x, OJ) fail Standardizing apart eliminates overlap of variables, e.g., Knows(z17, OJ) Chapter 9 14 Generalized Modus Ponens (GMP) p1 0 , p2 0 , . . . , pn 0 , (p1 ∧ p2 ∧ . . . ∧ pn ⇒ q) qθ where pi 0 θ = piθ for all i p1 0 is King(John) p1 is King(x) p2 0 is Greedy(y) p2 is Greedy(x) θ is {x/John, y/John} q is Evil(x) qθ is Evil(John) GMP used with KB of definite clauses (exactly one positive literal) All variables assumed universally quantified Chapter 9 15 Soundness of GMP Need to show that p1 0 , . . . , pn 0 , (p1 ∧ . . . ∧ pn ⇒ q) |= qθ provided that pi 0 θ = piθ for all i Lemma: For any definite clause p, we have p |= pθ by UI 1. (p1 ∧ . . . ∧ pn ⇒ q) |= (p1 ∧ . . . ∧ pn ⇒ q)θ = (p1θ ∧ . . . ∧ pnθ ⇒ qθ) 2. p1 0 , . . . , pn 0 |= p1 0 ∧ . . . ∧ pn 0 |= p1 0 θ ∧ . . . ∧ pn 0 θ 3. From 1 and 2, qθ follows by ordinary Modus Ponens Chapter 9 16 Example knowledge base The law says that it is a crime for an American to sell weapons to hostile nations. The country Nono, an enemy of America, has some missiles, and all of its missiles were sold to it by Colonel West, who is American. Prove that Col. West is a criminal Chapter 9 17 Example knowledge base contd. . . . it is a crime for an American to sell weapons to hostile nations: Chapter 9 18