Knowledge_base_and_inference_rules (2).pptx

AI subject

1. Artificial Intelligence (CSE3002) Winter Semester 2022-2023 Knowledge base and Inference Rules

2. The agent starts visiting from first square [1, 1], and we already know that this room is safe for the agent . To build a knowledge base for wumpus world, we will use some rules and atomic propositions. We need symbol [ i , j] for each location in the wumpus world, where i is for the location of rows, and j for column location . Atomic proposition variable for Wumpus world : Knowledge-base for Wumpus world Proves for the Wumpus -world using propositional logic: For a 4 * 4 square board, there will be 7*4*4 = 122 propositional variables. Propositional variables = True/False (Declarative statement)

3. Some Propositional Rules for the wumpus world: Representation of Knowledgebase for Wumpus world: Simple KB for W umpus world when an agent moves from room [ 1, 1], to room [2,1]:

4. The sentences we write will suffice to derive ¬P 1,2  there is no pit in [1,2] We label each sentence R i so that we can refer to them: Proportional logic to denote no pit in [1,2] A Simple Knowledge-Base

5. Proportional Logic to denote the presence of Wumpus in 1,3

6. Finding the Wumpus using Rules of Inference

7. Inference rules are the templates for generating valid arguments . Inference rules are applied to derive proofs in artificial intelligence , and the proof is a sequence of the conclusion that leads to the desired goal. Inference rules Rules of Inference in Artificial intelligence B

8. We can prove that wumpus is in the room (1, 3) using propositional rules which we have derived for the wumpus world and using inference rule . Apply Modus Ponens with ¬S11 and R1 : We will firstly apply MP rule with R1 which is ¬S 11  → ¬ W 11  ^ ¬ W 12  ^ ¬ W 21 , and  ¬S 11  which will give the output ¬ W 11  ^ W 12  ^ W 12 . Prove that Wumpus is in the room (1, 3 ) using rules of inference

9. 2. Apply And-Elimination Rule : After applying And-elimination rule to ¬ W 11  ∧ ¬ W 12  ∧ ¬ W 21 , we will get three statements: ¬ W 11 , ¬ W 12 , and ¬W 21 . 3 . Apply Modus Ponens to ¬S 21 , and R2: Now we will apply Modus Ponens to ¬S 21  and R2 which is ¬S 21  → ¬ W 21  ∧¬ W 22  ∧ ¬ W 31 , which will give the Output as  ¬ W 21  ∧ ¬ W 22  ∧¬ W 31

10. 4. Apply And -Elimination rule : Now again apply And-elimination rule to  ¬ W 21  ∧ ¬ W 22  ∧¬ W 31 , We will get three statements: ¬ W 21 , ¬ W 22 , and ¬ W 31 . 5. Apply MP to S 12  and R4: Apply Modus Ponens to  S 12  and  R 4  which is  S 12  → W 13  ∨. W 12  ∨. W 22  ∨.W 11 , we will get the output as  W 13 ∨ W 12  ∨ W 22  ∨.W 11 .

11. 6. Apply Unit resolution on W 13  ∨ W 12  ∨ W 22  ∨W 11  and ¬ W 11   : After applying Unit resolution formula on W 13  ∨ W 12  ∨ W 22  ∨W 11  and ¬ W 11  we will get W 13  ∨ W 12  ∨ W 22 . 7. Apply Unit resolution on W 13  ∨ W 12  ∨ W 22  and ¬ W 22   : After applying Unit resolution on  W 13  ∨ W 12  ∨ W 22 , and  ¬W 22 , we will get  W 13  ∨ W 12  as output .

12. 8. Apply Unit Resolution on W 13  ∨ W 12  and ¬ W 12   : After Applying Unit resolution on  W 13  ∨ W 12  and ¬ W 12 , we will get  W 13  as an output, hence it is proved that the Wumpus is in the room [1, 3 ].

13. Models are assignments of true or false to every proposition symbol. Wumpus world  the relevant proposition symbols are B 1,1 , B 2,1 , P 1,1 , P 1,2 , P 2,1 , P 2,2 , and P 3,1 With seven symbols, there are 2 7 = 128 possible models; in three of these, KB is true. In those three models, ¬P 1,2 is true, hence there is no pit in [1,2]. On the other hand, P 2,2 is true in two of the three models and false in one, so we cannot yet tell whether there is a pit in [2,2]. A Simple Inference Procedure

14. In the topic of Propositional logic, we have seen that how to represent statements using propositional logic. In propositional logic, we can only represent the facts , which are either true or false . PL is not sufficient to represent the complex sentences or natural language statements . The propositional logic has very limited expressive power. Consider the following sentence, which we cannot represent using PL logic. "Some humans are intelligent", or "Sachin likes cricket." To represent the above statements, PL logic is not sufficient, so we required some more powerful logic, such as first-order logic. Limitations of Proportional Logic

15. First-order logic is another way of knowledge representation in artificial intelligence . It is an extension to propositional logic. FOL is sufficiently expressive to represent the natural language statements in a concise way. First-order logic is a powerful language that develops information about the objects in a more easy way and can also express the relationship between those objects . First-order logic (like natural language) does not only assume that the world contains facts like propositional logic but also assumes the following things in the world: Objects :  A, B, people, numbers, colors , wars, theories, squares, pits, wumpus , .. Relations :   It can be unary relation such as:  red, round, is adjacent,  or n-any relation such as:  the sister of, brother of, has color , comes between Function :  Father of, best friend, third inning of, end of, ...... As a natural language, first-order logic also has two main parts: Syntax Semantics First order Logic

16. Formal languages

17. In Propositional logic Each model links the vocabulary of the logical sentences to elements of the possible world , so that the truth of any sentence can be determined . M odels for propositional logic link proposition symbols to predefined truth values . In first order logic They have objects in them. The domain of a model is the set of objects or domain elements it contains. The domain is required to be nonempty —every possible world must contain at least one object. I t doesn’t matter what these objects are—all that matters is how many there are in each particular model Syntax and semantics for FOL

18. Five Objects: Richard the Lionheart, King of England from 1189 to 1199; H is younger brother, the evil King John, who ruled from 1199 to 1215; T he left legs of Richard and John; and A crown First Order Logic: Example

19. Richard and John are brothers  a relation is just the set of tuples of objects that are related. The crown is on King John’s head, so the “on head” relation contains just one tuple, The “brother” and “on head” relations are binary relations—that is, they relate pairs of objects The model also contains unary relations, or properties: the “person” property is true of both Richard and John; the “king” property is true only of John (presumably because Richard is dead at this point); and the “crown” property is true only of the crown. First Order Logic: Example

20. Certain kinds of relationships are best considered as functions, in that a given object must be related to exactly one object in this way. For example, each person has one left leg, so the model has a unary “left leg” function that includes the following mappings M odels in first-order logic require total functions , that is, there must be a value for every input tuple. Thus, the crown must have a left leg and so must each of the left legs. First Order Logic: Example

21. Three kind of symbols Constant symbols: stand for objects; P redicate symbols: stand for relations; Function symbols: stand for functions T hese symbols will begin with uppercase letters C onstant symbols Richard and John ; P redicate symbols Brother , OnHead , Person, King, and Crown ; and the function symbol LeftLeg Each predicate and function symbol comes with an arity that fixes the number of arguments. Symbols and Interpretation

22. As in propositional logic, every model must provide the information required to determine if any given sentence is true or false. in addition to its objects, relations, and functions, each model includes an interpretation that specifies exactly which objects, relations and functions are referred to by the constant, predicate, and function symbols. Richard refers to Richard the Lionheart and John refers to the evil King John. Brother refers to the brotherhood relation, OnHead refers to the “on head” relation that holds between the crown and King John; Person, King, and Crown refer to the sets of objects that are persons, kings, and crowns. LeftLeg refers to the “left leg” function Symbols and Interpretation

23. Other Interpretations: For example, one interpretation maps Richard to the crown and John to King John’s left leg. There are five objects in the model, so there are 25 possible interpretations just for the constant symbols Richard and John. Notice that not all the objects need have a name—for example, the intended interpretation does not name the crown or the legs. It is also possible for an object to have several names; there is an interpretation under which both Richard and John refer to the crown. Symbols and Interpretation

24. An Atomic sentence (or atom for short) is formed from a predicate symbol optionally followed by a parenthesized list of terms, such as Brother (Richard, John). Atomic sentences can have complex terms as arguments  Married(Father (Richard), Mother (John)) An atomic sentence is true in a given model if the relation referred to by the predicate symbol holds among the objects referred to by the arguments. Atomic Sentences and Complex Sentences

25. We can use logical connectives to construct more complex sentences, with the same syntax and semantics as in propositional calculus. Here are four sentences that are true in the model of Figure under our intended interpretation: Atomic Sentences and Complex Sentences

26. The syntax of FOL determines which collection of symbols is a logical expression in first-order logic. The basic syntactic elements of first-order logic are symbols. We write statements in short-hand notation in FOL . Basic Elements of First-order logic : Syntax of First-Order logic

27. Atomic sentences are the most basic sentences of first-order logic. These sentences are formed from a predicate symbol followed by a parenthesis with a sequence of terms. We can represent atomic sentences as  Predicate (term1, term2, ......, term n) . Example: Ravi and Ajay are brothers: => Brothers(Ravi, Ajay).                 Chinky is a cat: => cat ( Chinky ) . Atomic sentences

28. Complex sentences are made by combining atomic sentences using connectives. First-order logic statements can be divided into two parts: Subject:  Subject is the main part of the statement. Predicate:  A predicate can be defined as a relation, which binds two atoms together in a statement. Consider the statement: "x is an integer." , it consists of two parts, the first part x is the subject of the statement and second part "is an integer," is known as a predicate. Complex Sentences

29. A quantifier is a language element which generates quantification, and quantification specifies the quantity of specimen in the universe of discourse. These are the symbols that permit to determine or identify the range and scope of the variable in the logical expression. There are two types of quantifier: Universal Quantifier, (for all, everyone, everything) Existential quantifier, (for some, at least one). Quantifiers in First-order logic

30. Universal quantifier is a symbol of logical representation , which specifies that the statement within its range is true for everything or every instance of a particular thing . The Universal quantifier is represented by a symbol ∀, which resembles an inverted A . If x is a variable, then ∀x is read as: For all x For each x For every x. Example: All man drink coffee. Let a variable x which refers to a cat so all x can be represented in UOD as below: Universal Quantifier

31. The main connective for universal quantifier  ∀  is implication  → . The main connective for existential quantifier  ∃  is and  ∧ .

32. Existential quantifiers are the type of quantifiers, which express that the statement within its scope is true for at least one instance of something. It is denoted by the logical operator ∃ , which resembles as inverted E. When it is used with a predicate variable then it is called as an existential quantifier. If x is a variable, then existential quantifier will be ∃x or ∃(x). And it will be read as : There exists a 'x.' For some 'x.' For at least one 'x.' Existential Quantifier :

33. Some Examples of FOL using quantifier: 1 . All birds fly. In this question the predicate is " fly(bird) ." And since there are all birds who fly so it will be represented as follows.                ∀x bird(x) →fly(x) . 2. Every man respects his parent. In this question, the predicate is " respect(x, y)," where x=man, and y= parent . Since there is every man so will use ∀, and it will be represented as follows:                ∀x man(x) → respects (x, parent) . 3. Some boys play cricket. In this question, the predicate is " play(x, y) ," where x= boys, and y= game. Since there are some boys so we will use  ∃, and it will be represented as :                ∃x boys(x) → play(x, cricket) . 4. Not all students like both Mathematics and Science. In this question, the predicate is " like(x, y)," where x= student, and y= subject . Since there are not all students, so we will use  ∀ with negation, so  following representation for this:                ¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)].