Knowledge Representation in Artificial Intelligence

AI

1. Knowledge Representation in Artificial Intelligence Dr. Mehak Saini

2. Knowledge Representation A knowledge representation system should provide ways of representing complex knowledge and should possess the following characteristics: 1. The representation scheme should have a set of well-defined syntax and semantics. 2. The knowledge representation scheme should have a good expressive capacity. 3. The representation must be efficient, i.e., it should use only limited resources without compromising on the expressive power.

3. How is a knowledge base different from a database?

4. 1. Propositional Logic

5. Commonly Used Propositional logic connectives S. no. Name Connective Symbol 1. Conjunction AND & 2. Inclusive disjunction OR V 3. Negation NOT ̄ 4. Material Condition IMPLIES 5. Material biconditional IFF 6. Exclusive disjunction XOR 7. Joint Denial NAND ׀ 8. Disjoint Denial NOR S. no. Name Connective Symbol 1. Conjunction AND & 2. Inclusive disjunction OR V 3. Negation NOT ̄ 4. Material Condition IMPLIES 5. Material biconditional IFF 6. Exclusive disjunction XOR 7. Joint Denial NAND ׀ 8. Disjoint Denial NOR

6. A B ̄ A ̄B AVB A&B A B A B A+B A ׀ B A B T T F F T T T T F F F F T T F T F T F T T F T F F T T F F F T T F F F T T F F T T F T T A B ̄ A ̄B AVB A&B A+B A ׀ B T T F F T T T T F F F F T T F T F T F T T F T F F T T F F F T T F F F T T F F T T F T T Truth table for logical connectives

7. Logical Equivalence

8. Problem: To verify that ((A & (A B)) B) is a tautology  

9. Commonly used logical Equivalences

10. What is tautology in propositional logic? A tautology in propositional logic is a formula or statement that is always true, regardless of the truth values of its component propositions. For example, "P ∨ ¬P" (P or not P) is a tautology because it is always true whether P is true or false.   Another example of a tautology in propositional logic is: "(P → Q) ∨ (Q → P)" This means "if P implies Q or Q implies P," which is always true, regardless of the truth values of P and Q.   "(P ∧ True) → P" This means "P and true implies P," which is always true, regardless of the truth value of P.

11. Statements that are tautologies Statements that are Contradictions

12. Normal forms in Propositional Logic Conjunctive Normal Form (CNF) Disjunctive Normal Form (DNF) *A formula A is said to be in CNF if it has the form A= & & … & , n≥1 Where … is a disjunction of an atom or negation of an atom *A formula A is said to be in DNF if it has the form A= … V , n≥1 Where … is a conjunction of an atom or negation of an atom  

13. Conversion Procedure of formula to Normal Form Eliminate implications and biconditionals . 2. Reduce the scope of NOT symbol by the formula ( ̄( ̄A))=A and apply DeMorgan’s theorem to bring the negations before the atoms. 3. Use Distributive laws and other formulae to obtain the normal form.

14. 2. Predicate Logic

15. Predicate or First order logic A predicate is defined as a relation that binds two atoms together, e.g., Bhaskar likes aeroplanes is represented as LIKES ( Bhaskar , aeroplanes ). Here, LIKES is a predicate that links two atoms “ Bhaskar ” and “ aeroplanes ”. This predicate can be generalized as, LIKES( x,y ) where x and y are variables meaning x likes y.

16. Main purpose of predicate logic in AI ? The main purpose of predicate logic in AI is to provide a formal framework for representing and reasoning about facts and relationships in a domain. It helps in defining rules, making inferences, and solving problems that involve logical relationships.

17. What are universal and existential quantifiers Universal Quantifier ( ∀ ): It denotes "for all" or "for every." It implies that a statement applies to all elements within a certain domain. For example, ∀ x P(x) means that the predicate P(x) is true for all x. Existential Quantifier ( ∃ ): It denotes "there exists" or "for some." It implies that there is at least one element in the domain for which the statement is true. For example, ∃ x P(x) means that there exists at least one x for which P(x) is true.

18. Quantifiers

19. NORMAL FORMS IN PREDICATE LOGIC In predicate logic normal form is Prenex Normal form. A formula A in predicate logic is said to be in Prenex Normal form if it has the form ( ) ( )… ( ) B Where ( is either a V or 3 and B is a formula without any quantifiers. ( ) ( )… ( ) is called the prefix and B is called matrix of the formula .  

20. Formulae for Prenex Normal form Conversion

21. Rules of Inference S. no. Description Rule of Inference 1. 2. 3. 4. 5. Addition Simplification Modus Ponens Modus Tollens Disjunctive Syllogism

22. Rules of Inference (Contd.)

23. Describe the rule represented by the following statement in predicate logic: " ∀ x Animal(x) → Eats(x, 'Food')" This statement in predicate logic can be read as: "For all x, if x is an animal, then x eats food." It means that every animal eats food.

24. Resolution Given any two clauses A and B, if there is a literal P1 in A which has a complementary literal P2 in B, delete P1 and P2 from A and B and construct a disjunction of the remaining clauses. The clause so constructed is called the resolvent of A and B. Example:

25. Limitations of Logic as knowledge representation Scheme * * * * * *

26. 3. Rule Based System

27. 4. Semantic Networks

28. Definition Semantic net (or semantic network) in AI is a graphical representation of knowledge that uses nodes to represent objects, concepts, or entities, and edges (links) to represent the relationships between them. It is commonly used to show hierarchical relationships or associations between different elements in a system, aiding in knowledge representation and reasoning.

29. Semantic Networks A semantic network is a structure for representing knowledge as a pattern of interconnected nodes and arcs. It is defined as a graphical representation of knowledge. The objects under consideration serve as nodes and the relationship with other nodes give the arcs. Nodes in the semantic net can be generic or individual node.

30. Draw the semantic net for the following information: Alice is a doctor. Alice works at City Hospital. City Hospital is located in New York. Alice drives a red car.

31. Here’s the answer to the semantic net for the provided information:   1. A node for "Alice" connected to a node labeled "Doctor" with an "is-a" relationship. 2. A node for "Alice" connected to a node labeled "City Hospital" with a "works-at" relationship. 3. A node for "City Hospital" connected to a node labeled "New York" with a "located-in" relationship. 4. A node for "Alice" connected to a node labeled "Red Car" with a "drives" relationship.   Graphically, it looks like this:     This graph represents the relationships and information given in the question.

32. Draw the semantic net for the following information: John is a professor. John works at Harvard University. Harvard University is located in Boston. John teaches Computer Science.

33. Here’s the semantic net for the provided information:   1. A node for "John" connected to a node labeled "Professor" with an "is-a" relationship. 2. A node for "John" connected to a node labeled "Harvard University" with a "works-at" relationship. 3. A node for "Harvard University" connected to a node labeled "Boston" with a "located-in" relationship. 4. A node for "John" connected to a node labeled "Computer Science" with a "teaches" relationship.   Graphically, it looks like this:     This graph represents the relationships and information in the question.

34. Semantic net

35. Representation of variables in Semantic nets

36. Hierarchial structure in a network

37. 5 . Frames

38. Frames A frame can be defined as a data structure that has slots for various objects and a collection of frames consists of expectations for a given situation. Example: Sample frame of a computer centre .

39. Declarative Frames A frame that merely contains description about objects is called a declarative/factual/ situational frame.

40. Procedural frame