⊙ Forward chaining example Forward chaining example Forward ⊙ ③ ing example proved true,o repeated work:check if new subgoal Avoid lops:check if new subgoal is already on the goal stack Backward chaining General idea:comstruct any model of B by sound inference.check 5.true in every model of KB,incudingm Hence m is a madel of ithm has not derives every atomic sentence that is entailed by Proof of completeness Forward chai 。⊙ ning example Forward chaining example Q A 1 1 B 0 L 0 M 0 P Chapter 7 49 Forward chaining example Q A B 0 L 0 M 0 P 0 0 Chapter 7 50 Forward chaining example Q A B 0 L 0 M 0 P 0 0 Chapter 7 51 Forward chaining example A B 0 L 0 M 0 P 0 0 Q Chapter 7 52 Proof of completeness FC derives every atomic sentence that is entailed by KB 1. FC reaches a fixed point where no new atomic sentences are derived 2. Consider the final state as a model m, assigning true/false to symbols 3. Every clause in the original KB is true in m Proof: Suppose a clause a1 ∧ . . . ∧ ak ⇒ b is false in m Then a1 ∧ . . . ∧ ak is true in m and b is false in m Therefore the algorithm has not reached a fixed point! 4. Hence m is a model of KB 5. If KB |= q, q is true in every model of KB, including m General idea: construct any model of KB by sound inference, check α Chapter 7 53 Backward chaining Idea: work backwards from the query q: to prove q by BC, check if q is known already, or prove by BC all premises of some rule concluding q Avoid loops: check if new subgoal is already on the goal stack Avoid repeated work: check if new subgoal 1) has already been proved true, or 2) has already failed Chapter 7 54