logic part of where the ai takes place p

Propositional logic it ha s

1. KNOWLEDGE BASES and LOGICAL REASONING LOGIC 1

2. Set of sentences in formal language Knowledge Representation Language : Each sentence expressed in language Concept of TELL and ASK LOGIC 2

3. KNOWLEDGE BASED AGENT LOGIC 3

4. LOGIC LOGIC 4

5. TYPES OF LOGIC LOGIC 5

6. ENTAILMENT LOGIC 6

7. MODEL LOGIC 7

8. INFERENCE LOGIC 8

9. PROPOSITIONAL LOGIC LOGIC 9

10. PROPOSITIONAL LOGIC ( Contd.) LOGIC 10

11. PROPOSITIONAL LOGIC - ENUMERATION LOGIC 11

12. PROPOSITIONAL INFERENCE - SOLUTION LOGIC 12

13. FORMS OF REPRESENTATION LOGIC 13

14. VALIDITY AND SATISFIABILITY LOGIC 14

15. PROOF METHODS LOGIC 15

16. INFERENCE RULES FOR PROPOSITIONAL LOGIC LOGIC 16

17. PROS and CONS of PROPOSITIONAL LOGIC LOGIC 17

18. FIRST ORDER LOGIC LOGIC 18

19. CONCEPTS Functions Predicates Constants Variables Connectives Equality ( Terms are true under a given interpretation ) Quantifiers with examples Atomic and Complex sentences with examples LOGIC 19

20. TRUTH IN FOL LOGIC 20

21. L 21 Atomic sentences Atomic sentence = predicate ( term 1 , . . . , term n ) or term 1 = term 2 Term = function ( term 1 , . . . , term n ) or constant or variable E.g., Brother ( KingJohn, RichardTheLionheart ) > ( Length ( LeftLegOf ( Richard )) , Length ( LeftLegOf ( KingJohn )))

22. LOGIC 22 Complex sentences Complex sentences are made from atomic sentences using connectives ¬ S, S 1 ∧ S 2 , S 1 ∨ S 2 , S 1 ⇒ S 2 , S 1 ⇔ S 2 E.g. Sibling ( KingJohn, Richard ) ⇒ Sibling ( Richard, KingJohn ) > (1 , 2) ∨ ≤ (1 , 2) > (1 , 2) ∧ ¬ > (1 , 2)

23. LOGIC 23 Truth in first- order logic Sentences are true with respect to a model and an interpretation Model contains ≥ 1 objects ( domain elements ) and relations among them Interpretation specifies referents for constant symbols → objects predicate symbols → relations function symbols → functional relations An atomic sentence predicate ( term 1 , . . . , term n ) is true iff the objects referred to by term 1 , . . . , term n are in the relation referred to by predicate

24. MODELS for FOL LOGIC 24

25. EXAMPLE for MODEL LOGIC 25

26. LOGIC 26 Models for FOL: Lots! Entailment in propositional logic can be computed by enumerating models We can enumerate the FOL models for a given KB vocabulary: For each number of domain elements n from 1 to ∞ For each k - ary predicate P k in the vocabulary For each possible k - ary relation on n objects For each constant symbol C in the vocabulary For each choice of referent for C from n objects . . . Computing entailment by enumerating FOL models is not easy!

27. PROPERTIES OF QUANTIFIERS LOGIC 27

28. OTHER INTERESTING SENTENCES LOGIC 28

29. 29 Equality term 1 = term 2 is true under a given interpretation if and only if term 1 and term 2 refer to the same object E.g., 1 = 2 and ∀ x × ( Sqrt ( x ) , Sqrt ( x )) = x are satisfiable 2 = 2 is valid E.g., definition of (full) Sibling in terms of Parent : ∀ x, y Sibling ( x, y ) ⇔ [ ¬ ( x = y ) ∧ ∃ m, f ¬ ( m = f ) ∧ Parent ( m, x ) ∧ Parent ( f, x ) ∧ Parent ( m, y ) ∧ Parent ( f, y )]

30. LOGIC 30 Interacting with FOL KBs Suppose a wumpus- world agent is using an FOL KB and perceives a smell and a breeze (but no glitter) at t = 5 : T ell ( KB, Percept ([ Smell, Breeze, None ] , 5)) Ask ( KB, ∃ a Action ( a, 5)) I.e., does KB entail any particular actions at t = 5 ? Answer: Y es, { a/Shoot } ← substitution (binding list) Given a sentence S and a substitution σ , Sσ denotes the result of plugging σ into S ; e.g., S = Smarter ( x, y ) σ = { x/Hillary, y/Bill } Sσ = Smarter ( Hillary, Bill ) Ask ( KB, S ) returns some/all σ such that KB | = Sσ

31. LOGIC 31 Knowledge base for the wumpus world “Perception” ∀ b, g, t Percept ([ Smell, b, g ] , t ) ⇒ Smelt ( t ) ∀ s, b, t Percept ([ s, b, Glitter ] , t ) ⇒ AtGold ( t ) Reflex : ∀ t AtGold ( t ) ⇒ Action ( Grab, t ) Reflex with internal state : do we have the gold already? ∀ t AtGold ( t ) ∧ ¬ Holding ( Gold, t ) ⇒ Action ( Grab, t ) Holding ( Gold, t ) cannot be observed ⇒ keeping track of change is essential

32. LOGIC 32 Deducing hidden properties Properties of locations: ∀ x, t At ( Agent, x, t ) ∧ Smelt ( t ) ⇒ Smelly ( x ) ∀ x, t At ( Agent, x, t ) ∧ Breeze ( t ) ⇒ Breezy ( x ) Squares are breezy near a pit: Diagnostic rule— infer cause from effect ∀ y Breezy ( y ) ⇒ ∃ x Pit ( x ) ∧ Adjacent ( x, y ) Causal rule— infer effect from cause ∀ x, y Pit ( x ) ∧ Adjacent ( x, y ) ⇒ Breezy ( y ) Neither of these is complete— e.g., the causal rule doesn’t say whether squares far away from pits can be breezy Definition for the Breezy predicate: ∀ y Breezy ( y ) ⇔ [ ∃ x Pit ( x ) ∧ Adjacent ( x, y )]

33. Keeping track of change Facts hold in situations , rather than eternally E.g., Holding ( Gold, Now ) rather than just Holding ( Gold ) Situation calculus is one way to represent change in FOL: Adds a situation argument to each non- eternal predicate E.g., Now in Holding ( Gold, Now ) denotes a situation Situations are connected by the Result function Result ( a, s ) is the situation that results from doing a in s PIT LOGIC 33 PIT PIT Gold PIT PIT PIT Gold S Forward S 1

34. LOGIC 34 Describing actions I “Effect” axiom— describe changes due to action ∀ s AtGold ( s ) ⇒ Holding ( Gold, Result ( Grab, s )) “Frame” axiom— describe non- changes due to action ∀ s HaveArrow ( s ) ⇒ HaveArrow ( Result ( Grab, s )) Frame problem : find an elegant way to handle non- change representation— avoid frame axioms inference— avoid repeated “copy- overs” to keep track of state Qualification problem : true descriptions of real actions require endless caveats— what if gold is slippery or nailed down or . . . Ramification problem : real actions have many secondary consequences— what about the dust on the gold, wear and tear on gloves, . . .

35. LOGIC 35 Describing actions II Successor- state axioms solve the representational frame problem Each axiom is “about” a predicate (not an action per se): P true afterwards ⇔ [ an action made P true ∨ P true already and no action made P false ] For holding the gold: ∀ a, s Holding ( Gold, Result ( a, s )) ⇔ [( a = Grab ∧ AtGold ( s )) ∨ ( Holding ( Gold, s ) ∧ a / = Release )]

36. LOGIC 36 Making plans Initial condition in KB: At ( Agent, [1 , 1] , S ) At ( Gold, [1 , 2] , S ) Query: Ask ( KB, ∃ s Holding ( Gold, s )) i.e., in what situation will I be holding the gold? Answer: { s/Result ( Grab, Result ( F orward, S )) } i.e., go forward and then grab the gold This assumes that the agent is interested in plans starting at S and that S is the only situation described in the KB

37. LOGIC 37 Making plans: Represent plans as action sequences [ a 1 , a 2 , . . . , a n ] PlanResult ( p, s ) is the result of executing p in s Then the query Ask ( KB, ∃ p Holding ( Gold, PlanResult ( p, S ))) has the solution { p/ [ F orward , Grab ]} Definition of PlanResult in terms of Result : ∀ s PlanResult ([ ] , s ) = s ∀ a, p, s PlanResult ([ a | p ] , s ) = PlanResult ( p, Result ( a, s )) Planning systems are special- purpose reasoners designed to do this type of inference more efficiently than a general- purpose reasoner

38. LOGIC 38 First- order logic: objects and relations are semantic primitives syntax: constants, functions, predicates, equality, quantifiers Increased expressive power: sufficient to define wumpus world Situation calculus: conventions for describing actions and change in FOL can formulate planning as inference on a situation calculus KB

39. REASONING PATTERNS IN PROPOSITIONAL LOGIC MODUS PONENS AND ELIMINATION RESOLUTION LOGIC 39

40. HORN CLAUSES Maximum – one positive literal Can be written as an implication Horn clauses with exactly one positive literal ( Head ) – Definite clauses ( Negative literal – body ) Inferences with Horn Clauses can be done through forward and backward chaining algorithms Deciding entailment with Horn clauses can be done in time that is linear with the size of the knowledge base. LOGIC 40

41. FORWARD and BACKWARD CHAINING Forward Chaining – Data driven reasoning Backward Chaining – Goal Directed reasoning LOGIC 41

42. INFERENCES IN FOL LOGIC 42

43. EXISTENTIAL INSTANTIATION LOGIC 43

44. REDUCTION TO PROPOSITIONAL INFERENCE LOGIC 44

45. PROBLEMS WITH PROPOSITIONALIZATION LOGIC 45

46. UNIFICATION LOGIC 46

47. GENERALIZED MODUS PONENS(GMP) LOGIC 47

48. SOUNDENSS OF GMP LOGIC 48

49. SAMPLE PROBLEM – KNOWLEDGE BASE LOGIC 49

50. CONVERSION for sentences LOGIC 50

51. FORWARD CHAINING ALGORITHM LOGIC 51

52. FORWARD CHAINING - PROOF LOGIC 52

53. FORWARD CHAINING PROOF – CONTD. LOGIC 53

54. FIRST ORDER LOGIC Forward Chaining used widely ind eductive databases Additional Properties Complete Semidecidable LOGIC 54

55. BACKWARD CHAINING LOGIC 55

56. BACKWARD CHAINING - EXAMPLE LOGIC 56

57. LOGIC 57

58. BACKWARD CHAINING – Contd. LOGIC 58

59. LOGIC 59

60. PROPERTIES OF BACKWARD CHAINING Depth first recursive proof search : Space – linear in size Incomplete due to infinite loops Insufficient due to repeated subgoals Widely used for logic programming LOGIC 60

61. RESOLUTION LOGIC 61

62. CONVERSION to CNF LOGIC 62

63. CONVERSION to CNF(Contd. ) LOGIC 63

64. RESOLUTION PROOF BY REFUTATION LOGIC 64

65. RESOLUTION STRATEGIES UNIT PREFERENCE Unit Resolution incomplete but complete for Horn Knowledge bases SET OF SUPPORT Goal Directed Reduces Search space Proper choice needed INPUT RESOLUTION Every resolution combines one of input sentences ( from knowledge base or query ) with some other sentence SUBSUMPTION Helps in keeping Knowledge Base small LOGIC 65