Knowledge & logic in Artificial Intelligence.pptx

So primary component of a knowledge-based agent is its knowledge-base. A knowledge-base is a set of sentences in a knowledge domain. There are mechanisms to derive new sentences from old ones called as inference or reasoning.

1. KNOWLEDGE REPRESENTATION & LOGIC

2. To solve complex problems in AI we need: A large amount of knowledge. Some mechanisms for manipulating that knowledge to get solution of the problems. Does Knowledge have any role in demonstrating intelligent behavior?????

3. How can we represent the Knowledge in a machine? We need a language to represent domain knowledge. There must be a method to use this knowledge. Inference mechanism. Semantics of the Language.

4. So primary component of a knowledge-based agent is its knowledge-base. A knowledge-base is a set of sentences in a knowledge domain. Each sentence is expressed in a language called the knowledge representation language. Sentences represent some assertions about the world. There are mechanisms to derive new sentences from old ones called as inference or reasoning .

5. Types of knowledge

6. 1. Declarative Knowledge: Declarative knowledge is to know about something. It includes concepts, facts, and objects. It is also called descriptive knowledge and expressed in declarativesentences. It is simpler than procedural language.

7. 2. Procedural Knowledge It is also known as imperative knowledge. Procedural knowledge is a type of knowledge which is responsible for knowing how to do something. It can be directly applied to any task. It includes rules, strategies, procedures, agendas, etc. Procedural knowledge depends on the task on which it can be applied.

8. Meta-knowledge: Knowledge about the other types of knowledge is called Meta-knowledge.

9. 4. Heuristic knowledge: Heuristic knowledge is representing knowledge of some experts in a filed or subject. Heuristic knowledge is rules of thumb based on previous experiences, awareness of approaches, and which are good to work but not guaranteed.

10. 5. Structural knowledge: Structural knowledge is basic knowledge to problem-solving. It describes relationships between various concepts such as kind of, part of, and grouping of something. It describes the relationship that exists between concepts or objects.

11. Techniques of knowledge representation There are mainly four ways of knowledge representation which are given as follows: Logical Representation Semantic Network Representation Frame Representation Production Rules

12. Logic Logic is the study of information encoded in the form of logical sentences. New Delhi is capital of India. Kolkata is not the capital of India. Chandigarh is capital of Chandigarh or Punjab. If Pune is not the capital of Maharashtra, then it is Mumbai There is some city that is capital of Nagaland. Every state has a capital.

13. Logic We use logic sentence when we state definition, encode physical laws or write personal affairs. We use Logic reasoning to derive conclusion. to convince others. Where it is used Email readers Artificial Intelligence Logic Programming languages Etc.

14. Logic in AI is used to represent and reason about knowledge. Specifically in AI, formal logic as it is precise and definite. This may have severe limitations as: reasoning carried out by humans depends on handling knowledge that is uncertain. Logic cannot represent this uncertainty well. Similarly, natural language reasoning requires inferring hidden state, namely, the intention of the speaker.

15. A logic consists of, a language and a method of reasoning . A logical language has, syntax and semantics . Syntax: The atomic symbols of the logical language, and the rules for constructing well-formed, non-atomic expressions of the logic. Syntax specifies the symbols in the language and how they can be combined to form sentences . Hence facts about the world are represented as sentences in logic.

16. Semantics: Gives the meanings of the atomic symbols of the logic, and the rules for determining the meanings of non-atomic expressions of the logic. Syntactic Inference Method: The rules for determining a subset of logical expressions, called theorems of the logic. Allows mechanically computing (deriving) new (true) sentences from existing sentences.

17. A fact is a claim about the world, and may be true or false. Sentences are physical configuration of the agent. Reasoning is a process of constructing new physical configurations from old ones. If a Knowledge base is true in real world, then any sentence derived from Knowledge Base by a sound inference procedure is also true in the real world.

18. All a are y Some y are z. Therefore, some x are z. Some can have faulty reasoning pattern. Leading to wrong conclusion. E,g: All Toyotas are Japanese Some Japanese cars are made in America Therefore Some Toyotas are made in America. All Maruti are cars Some cars are Tatas Therefore some Marutis are Tatas.

19. Propositional Logic: Here we have some propositions used as logic: X in Intelligent. X is hardworking. If X is intelligent and X is hardworking then X scores good marks. Intelligent (X)== X is Intelligent Hardworking (X) == X is Hardworking. Intelligent-X What is the syntax of this language? P stands for Intelligent (X) Q stands for Hardworking (X). P AND Q (P Q) P OR Q (PQ). These are compound statements. Propositions returns True or False.

20. Vocabulary of Propositional Logic: A set of Propositional symbols (P,Q,R etc.) which can be individually True or False. A set of Logical Operators  and () used for grouping. Two special symbols called constants True or False. Nothing else is sentence. Sentences are also called as well formed formulas (wffs). Implication : P  Q, If P is true then Q is True. If it rains then roads are wet. If roads are wet then it rains ??? Equivalence : P  Q If two sides of a triangle are equal, then two base angles of the triangle are also equal.

21. Semantics of wffs means interpreting a sentence. We assign meaning to it and evaluates it to either true or false. Sentence can be compound proposition. Each atomic proposition has to interpreted in the same world. And assign truth value to it. Finally find the truth value of compound proposition If a statement is true under all interpretation, it is valid . Also called Tautology , P P is TRUE. E.g If it rains today and one does not carry umbrella he will be drenched.

22. An interpretation is mapping to a world. A sentence is SATISFIABLE by an interpretation IF under that Interpretation the statement evaluates TRUE. A truth assignment satisfies a sentence if and only if it assigns the value 1 to the sentence. A truth assignment falsifies a sentence if and only if it assigns the value to the sentence. A truth assignment satisfies a set of sentence if and only if it satisfies every element in the set. A truth assignment falsifies a set of sentence if and only if it falsifies at least one element in the set.

23. Satisfaction Example: Find a truth assignment that satisfies the following q r, p qr, r

24. Logical Entailment: Set of Sentences (S) Interpretation S1 True True If a sentence S1has a value TRUE for all interpretations of a set of all sentence, then S - S1. Can also be said as: S1 logically follows from S OR S1 is a logical consequence of S OR S logically entails S1.

25. Prove that p q, m pq and m logical entails q

26. Inference Rule in Propositional logic: Modem Ponens – One Inference Rule. P  Q P _____ Q Proof: P  Q can be written as P Q, Conjoined with P we can write P P Q = (P P) Q = F  Q = Q Thus irrespective of meaning Modem Ponens allows us to infer the truth of Q. Modem Ponens is an Inference rule that allows us to deduce, the truth of a consequent depending on truth of antecedents.

27. Inference Rule in Propositional logic: If NOT (NOT (P) then P. Chain Rule: IF P then Q If Q then R Leads to if P then R (((P  Q) and (Q  R)) |-- (P  R) Modus tollens If (P  Q) and Q is false, then P is false, written also as (((P  Q) and ¬Q) |-- ¬P)

28. Example-1 : If a triangle is equilateral then it is Isosceles. If a triangle is Isosceles then two sides AB and AC are equal. IF AB and AC are equal then angle AB and AC are equal. ABC is an equilateral triangle. Prove Angle AB and AC are equal. Example-2 If it is hot and humid, then it is raining. If it is humid, then it is hot. It is humid. Prove that it is Raining

29. There's a proof strategy for this called as resolution refutation. Steps involved in it are: First, convert all of your sentences to CNF. Then , write each clause down as a premise or given in your proof. Second , negate the desired conclusion and convert that to CNF. Third, apply the resolution rule until one of two things happens. We might derive "false", which means that the conclusion did, in fact, follow from the things that we had assumed. Or, we might find ourselves in a situation where we can't apply the resolution rule any more, but we still haven't managed to derive false. Which means that that the thing that you were trying to prove can't be proved.

30. Pros and cons of propositional logic: Propositional logic is declarativ e. Propositional logic allows partial/disjunctive/negated information (unlike most data structures and databases). Propositional logic is compositional : Meaning propositional logic is context-independent (unlike natural language, where meaning depends on context). Propositional logic has very limited expressive power (unlike natural language).

31. All dogs are faithful Tommy is a dog Tommy is faithful??? Jack is Intelligent. Jack is hardworking. Jack is Intelligent and Jack is hardworking so jack scores good marks.!!!! What about Jill??? All students who are hardworking and intelligent scores high marks. For all x such that x is a student and x is intelligent and x is hardworking then x scores good marks.

32. FIRST ORDER LOGIC : First Order Logic or Predicate Logic is a generalization of Propositional Logic that allows us to express and infer arguments in infinite models. Whereas propositional logic assumes world contains fact s , first-order logic (like natural language) assumes the world contains: Objects: people, houses, numbers, theories, Ronald McDonald, colors, baseball games, wars, centuries etc. Relations: red, round, bogus, prime, multistoried, inside, part of, has color, occurred after, owns, comes between, Functions: father of, best friend, third inning of, one more than, beginning of

33. FIRST ORDER LOGIC : The syntax of FOL : Terms. Predicate. Quantifiers.

34. The syntax of FOL: Terms. A term denotes some object other than True or False. All men are mortal. Terms constitutes of constants, variables and functions : A constant of type W denotes a particular object of that set W. 5, Jack A variable of type W denotes any element of the set W. x  N is a Natural Number. d is a name of dog. A functional term of n-ary N takes n objects of type W 1 to W n as input and returns an object of type W. f(W1, W2, W3….Wn). plus(4,3)=7

35. The syntax of FOL: Predicate: These are also functions, but its return types are either True or False. gt (x,y) : Predicate This is TRUE. if x is greater than y, and x and y are natural numbers . A Predicate with no variable is a proposition . Lion is a mammal. A Predicate with one variable is a property . mortal (y), dog (x).

36. The syntax of FOL: Relationships between objects are represented by predicates with more arguments: E.g: "father(Tom, Bob)" represents the fact that Tom is the father of Bob. Also if P(x,y) and Q(x,y) are predicate then : P Q, PQ,P and PQ are also predicates.

37. The syntax of FOL: Quantifiers: The quantifiers  and  are used to build new formulas from old ones.

38. The syntax of FOL: Universal Quantifier  (“for all”) "  x P(x)" expresses that for all elements of the domain, P(x) is true. All dogs are faithful: dog(x), faithful(x), x (dog(x)  faithful(x)) All birds can not fly: fly (x), bird (x),  (x (bird(x) fly(x))

39. The syntax of FOL: Existential Quantifiers  (“There exists”) E.g:"  x P(x)" expresses that there is at least one element of the domain that makes P(x) true. "  x mother(x, Bob)" means that there is x such that x is mother of Bob or, otherwise stated, Bob has a mother. At least one planet has life in it. planet(x), haslife(x),  x(planet(x)  life(x)) There exists a bird that cannot fly. fly(x), bird(x),  x(bird(x)   fly(x)) All birds can not fly There exists a bird that cannot fly.

40. Duality of Quantifiers: All men are mortal and No man is Immortal. x(man(x)  mortal(x))   ( x(man(x)   mortal(x)) ) There exists bird that can fly and It is not the case that all birds can not fly.  x(bird(x)  fly(x))  ( x( bird(x)   fly(x)) )

41. The Vocabulary of FOL: If P and P’ are sentences and x is a variable, then (P), P,  x P, x P, P  P’, PP’ PP’ are sentences. Nothing else is a sentence.

42. Examples : Some dogs bark. All dogs has four legs. Fathers are male parents with childrens. If n is natural number, then n is either even or odd.

43. Examples: Some dogs bark.  x (dog(x)  bark(x)) All dogs has four legs. x dog(x)  has_four legs(x) Fathers are male parents with childrens. x(father(x)  male(x)  children(x) If n is natural number, then n is either even or odd. natural(n)  even(n)  odd(n).

44. Examples: birthday(x, y) – x celebrate birthday on y day. y, x birthday (x, y)- For all dates, there exists a person who celebrates his/her birthday on that date. OR “Every day someone celebrate his/her birthday” brother(x, y) – x is y’s brother loves(x, y)- x loves y x,y brother(x,y) loves (x, y) Everyone loves all of his / her brother. If m(x) is mother of x Express “Everyone loves his/her mother” x Loves (x, m(x))

45. Examples: Any number is the successor of its predecessor. This could also be written as

46. Examples: Any number is the successor of its predecessor. succ(x), pred(x), equal(x,y) x equal(x,succ (pred (x)) This could also be written as x (succ (pred (x)) = x FOL with Equality We can use equality sign between two function. This is just for representational case.

47. Inference Rule: The inference rules of logic are used to infer new facts from the explicitly represented ones. Universal Elimination: For any wffs of the form "  x F (x)", we can conclude "F(A)" for any individual "A". This rule is also written as ((  x F (x)) |-- F(A))  x, Likes (x, Flower), Say Shirin loves flower: Likes (Shirin, Flower), x, Man (x)  Mortal (x), we can apply this to the individual Socrates, to get Man (Socrates)  Mortal (Socrates)

48. Inference Rule: Existential Elimination (Skolemization): skolemize , named after a logician called Thoralf Skolem . If we have a sentence like: “there exists an x such that P(x) .” The goal here is to somehow arrive at a representation that doesn't have any existential quantifiers in it. x, likes (x, flower) If we know that shahid loves flower then we can conclude that: likes (shahid, flower) Existential Introduction: likes (shahid, flower) x, likes (x, flower)

49. Example: If a perfect square is divisible by prime p, then it is also divisible by square of prime p. Every perfect square is divisible by some prime. 36 is a perfect square Prove that : There exists a prime q such that square of q divides 36.

50. Example: (1)x,y perfect_sq(x)prime(y)  divides (x, y) divides(x, square(y)) (2)x, y perfect_sq(x)  prime(y)  divides(x, y) (3)perfect_sq(36) To prove y prime(y)  divides (36, square(y)) Reasoning or Inference From 2 and Universal elimination: (4) y perfect_sq(36)  prime(y)  divides(36, y) From 4 and Existential Elimination: (5) perfect_sq(36)  prime(P)  divides(36, P) From (1) and (5) (6) divides(36, square(P)) From (5) and (6) prime(P)  divides(36, square(P)) From (7) and inclusion of existential quantifiers y prime(y)  divides (36, square(y))

51. Horn Sentence or Horn Clause: Horn sentence constitute of : Atomic sentence: perfect_sq(36). Implication with a conjunction of atomic sentence on the left and a single atom in the right x,y perfect_sq (x)  prime (y)  divides (x, y)  divides (x, square (y) No existential quantifier

52. Horn Sentence or Horn Clause: Conversion to horn clause: Existential quantifier can be removed by skolemization If existential quantifier is outside any universal quantifier, Skolem constant is introduced: y, prime (y) becomes prime (P), where P is skolem constant. Or introduce a skolem function. x y prime (y)  divides (x, y)  x prime (PD (x))  divides (x, PD (x)), where PD(x) are skolem function .

53. Horn Sentence or Horn Clause: Conversion to horn clause: And Elimination prime(P)  divides (x, P), can be written as Prime(P) Divides (x,P)

54. Substitution: Substitution replaces variable with constant. SUBST{x/49}, perfect_sq(x)  perfect_sq(49). SUBST{x/49, y/7}, divides (x, y)  divides (49,7)

55. Unification: Process of finding a substitution that makes two expressions match each other exactly. So, expressions  1 and  2 are unifiable if and only if there exists a substitution S such that we get the same thing, when we apply S to  1 as we do when we apply S to  2 . That substitution, S, is called a unifier of  1 and  2 . UNIFY (prime(x), prime(7), (x/7) UNIFY (divides(49,x), divides(y,7)), {y/49,x/7} UNIFY(prime(7),prime(17)?? UNIFY(divides(49,x), divides(x,7))???

56. G is a most general unifier of  1 and  2 If and only if for all unifiers S, there exists an S Such that the result of applying G followed by S  to  1 is the same as the result of applying S to  1 and the result of applying G followed by S  to  2 is the same as the result of applying S to  2 . A unifier is most general if every single one of the other unifiers can be expressed as an extra substitution added onto the most general one.

57. Example: UNIFY(Knows(John,x), Knows(y,z)) returns {y/John, x/z} or {y/john, x/John, z/John} First unifier gives Knows (John,z) and second gives Knows (John, John). The second can be obtained from first by substituting {z/John}. SO {y/John, x/z} is the most general unifier .

58. Proof by resolution using refutation method in FOL Example : All people who are graduating are happy. All happy people smile. Someone is graduating. Is someone smiling?

59. Step -1 Selecting the predicates. Step -2 Encoding sentence into predicates. Step -3 List the Knowledge base or predicates (including negation of proven clause). Step-4 Converting to clausal form. Step-5 Reduce the scope of negation. Step-6 Standardize variables apart. Step-7: Converting to Canonical form (move all quantifiers to left). x[P(x) y Q(y)] Step-8: Skolemization (Eliminate ). Step-9: Drop all quantifiers. Step-10: Convert to conjunct of disjunct from. [P(x)  Q(x)] [R(x)  Z(x)] P(x)  Q(x), R(x)  Z(x) Step-11: Make each conjunct a separate clause. Step-12:Standradize variables apart again. Step-13: Resolve

60. Select the predicates: graduating(x), happy(x), smiling(x) x {graduating(x) happy(x)} x {h appy(x)smiling(x)} x graduating (x) x smiling (x) Eliminate  x  graduating(x) happy(x) x  h appy(x)  smiling(x) x graduating (x) x smiling (x)

61. Reduce the scope of negation x  graduating(x) happy(x) x  h appy(x)  smiling(x) x graduating (x) x smiling (x) Standardize variables apart x  graduating(x) happy(x) y  h appy(y)  smiling(y) z graduating (z) w smiling (w) Remove existential quantifiers x  graduating(x) happy(x) y  h appy(y)  smiling(y) graduating (name1), where name1 is a skolemization constant w smiling (w)

62. Drop all quantifiers as they are implicitly universally quantified  graduating(x) happy(x)  h appy(y)  smiling(y) graduating (name1), where name1 is a skolemization constant smiling (w) Convert to conjunct of disjunct from Make each conjunct a separate clause. Standardize variables apart again. Resolve (5) From (4) and (2),  h appy(y) (6)From (5) and (1),  graduating(x) (7)From (6) and (3) we get  [Null clause]

63. Resolution of FOL can be used for answering question : Example: All package of Room 27 are smaller than those in Room 28. Package A is either in Room 27 or in Room 28. Package B is in Room 27. Package B is not smaller than Package A. Where is Package A? P(x)P(y) I(x,27) I(y,28) S(x,y)  P(x)  P(y)   I(x,27)   I(y,28)  S(x,y) P(A) P(B) I(A,27)  I(A,28) I(B,27) S(B,A) To Prove: Where is Package A or u, I(A,u).

64. I(A,u)  Ans(u) I(A,27)  I(A,28) {27/u} I(A,28)  Ans(27)  P(x)  P(y)   I(x,27)   I(y,28)  S(x,y) {A/y}  P(x)  P(A)   I(x,27)  S(x,A)  Ans(27) P(A )  P(x)  I(x,27)  S(x,A)  Ans(27) P(B ) {B/x}  I(B,27)  S(B,A)  Ans(27) I(B,27) S(B,A)  Ans(27)  S(B,A) Ans(27)