AI UNIT II QB new - Lecture notes 2 PDF

Preview

Summary

AI QB ...

Description

PRATHYUSHA ENGINEERING COLLEGE ARTIFICIAL INTELLIGENCE IMPORTANT QUESTIONS PART-A UNIT II 1. List out the operators used in propositional logic and predicate calculus. And Represent the following sentence in predicate form “All children like sweets” Operators used in propositional logic

Operators used in predicate calculus

“All children like sweets” in Predicate logic : x y Child(x) Sweet(y) Likes(x,y) 2. For the Given sentences “All Pompeian’s were Roman”. Write a well formed formula in Predicate Logic. All Pompeians were Romans. x : Pompeian(x) → Romon(x) 3. What are the limitations in using propositional logic to represent the knowledge base? Propositional logic: • Represents statements about the world without reflecting the structure and without modelling the entities explicitly Consequence:  some knowledge is hard or impossible to encode in the propositional logic.  Two cases that are hard to represent: – Statements about similar objects, relations – Statements referring to groups of objects.  Generalizations, patterns, regularities can’t easily be represented (e.g., “all triangles have 3 sides”) 4. What is the significance of clause form? Give example for horn clause. A Horn Clause is a wff (well formed formula) in Clause Form that contains at most one literal in positive form. Ex.: {B, D,  A, C} Horn clauses like this one with exactly one positive literal are called definite clauses. The positive literal is called the head and the negative literals form the body of the clause.

1

5. Distinguish between predicate and prepositional logic. Predicate Logic: Predicate logic is the general form of all logics that uses predicates, like q(x). Here q is predicate. Predicate logic supports the ability to have variables, and quantifiers. For example, ∀x∃y.p(x,y) means "For all x there exists a y such that the proposition p(x,y) is true". Propositional Logic: Propositional logic means without ability to do predication. For example, in P ^ Q, both p and q are propositions. 6. What is the difference between Facts and Representation? FACT REPRESENTATION Facts is the real world data without interpretation, To represent fact & knowledge we need obtained as the definition of the problem 1. Its structure 2. What for the intelligent agents will use it For example: 3. How it will be used by intelligent agents The numerical data from a blood test 4. How it will be acquired The data from the sensors of a chemical process 5. How it will be stored and manipulated

7. What is uncertainty? How is it handled? Agents may need to handle uncertainty, due to partial observability, non-determinism, or a combination of the two. An agent may never know for certain what state it's in or where it will end up after a sequence of actions. Approaches to handle uncertainity: • Fuzzy Logic • Probabilistic Reasoning • Certainty Factors and Qualitative Fuzzy Logics • Neural Networks

8.What is synchronic and diachronic?  The sentences dealing with time have been synchronic(“same time”) sentences, that is , they relate properties of a world state to other properties of the same world state. 

The sentences that allow reasoning “across time”are called diachronic.

9. What are the two kinds of synchronic rules?  Diagnostic rules- lead from observed effects to hidden causes. 

Causal rules – reflect the assumed direction of causality in the world

10. Give the steps in knowledge engineering projects.  Identify the task 

Assemble the relevant knowledge



Decide on a vocabulary of predicates , functions and constants



Encode general knowledge about the domain



Encode a description of the specific problem instance.



Pose queries to the inference procedures and get answers

 Debug the knowledge base 11. What is an atomic sentence? 2



An atomic sentence consists of a predicate applied to one or more terms;



It is true when the relation named by the predicate holds between the objects named by the terms.

12. What are the characteristics of knowledge representation languages? It should be  Declarative 

Compositional



Expressive



Context-independent



Unambiguous

13. What is Alpha-Beta Pruning? Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). 14. Mention the standard logic symbols used in predicate logic. Standard logic symbols used in predicate logic

15. What is the significance of clause form? Give example for horn clause. The canonical representation is called clausal form. Using a canonical form we can get a sound and complete proof theory which is amenable to automation. A Horn clause is a clause with at most one positive literal. Example : ~man(X) V mortal(X) (All men are mortal) 16. What is unification? Give example. o The unification algorithm is a recursive procedure that attempts to unify two literals. o It is a matching procedure used for determining the contradictions. o First it checks whether their initial predicate symbols are the same. o Then it compares two literals and discovers whether there exists a set of substitutions that makes them identical. Example : UNIFY (Knows (John, x), Knows (John, Jane)) = {x/Jane} 17. Write the algorithm for unification. Give example. Unification Algorithm Input : x - a variable, constant, list or compound y - a variable, constant, list or compound  - Substitution built so far. // Imagine moving a pointer left-to-right across both expressions until parts are encountered that are not the same in both expressions. If one is a variable, and the other is a term not containing that variable, //

3

Steps: 1. substitute the term for the variable in both expressions, 2. substitute the term for the variable in the existing substitution set [This is necessary so that the substitution set will be simultaneous.] 3. add the substitution to the substitution set. Algorithm 1. If L1 or L2 are both variables or constants, then: (a) If L1 and L2 are identical, then return NIL. (b) Else if L1 is a variable, then if L1 occurs in L2 then return {FAIL}, else return (L2/L1). (c) Else if L2 is a variable then if L2 occurs in L1 then return {FAIL}, else return (L1/L2). (d) Else return {FAIL}. 2. If the initial predicate symbols in L1 and L2 are not identical, then return {FAIL). 3. If LI and L2 have a different number of arguments, then return {FAIL}. 4. Set SUBST to NIL. 5. For i ← 1 to number of arguments in L1: (a) Call Unify with the /th argument of L1 and the ith argument of L2, putting result in S. (b) If S contains FAIL then return {FAIL}. (c) If S is not equal to NIL then: (i) Apply S to the remainder of both L1 and L2. (ii) SUBST := APPEND(S, SUBST). 6. Return SUBST. 18. Mention the types of weak and strong slot and filler structures.  A slot is an attribute value pair in its simplest form  A filler is a value that a slot can take  Weak slot and filler structure does not consider the content of the representation. Types 1. Semantic Nets. 2. Frames  Strong slot and filler Represent links between objects according to more rigid rules.  Specific notions of what types of object and relations between them are provided.  Represent knowledge about common situations. Types 1. Scripts : structure that prescribes a set of circumstances which could be expected to follow on from one another. Events, Causal relationships, Entry conditions Prerequisites are specified. 2. Conceptual Dependency : captures maximum concepts to provide canonical form of meaning of sentences. Sentences are represented as a series of diagrams depicting actions using both abstract and real physical situations 3. CYC : An ambitious attempt to form a very large knowledge base aimed at capturing commonsense reasoning. 19. What is resolution /refutation? Resolution is proof procedure which operates on statements that have been converted into convenient standard into Conjunctive normal form. Resolution produces proofs by refutation. Resolution attempts to prove a statement (show that it is valid) by showing that the negation of the statement produces the contradiction with the known statement.

4

20. Define Skolemization.

Skolemization is the process of removing existential quantifiers by elimination.

21.What is a script? What is its use? A script is a structure that describes a stereotyped sequence of events in a particular context. A script consists of a set of slots. Associated with each slot may be some information about what kinds of values it may contain as well as default value to be used if no other information is available. Scripts are useful because in the real world, there are no patterns to the occurrence of events. These patterns arise because of clausal relationships between events. 22. What is Predicate Calculus? Propositional logic assumes the world contains facts, Predicate Calculus (first-order logic) assumes the world contains Objects : people, houses, numbers, colors, baseball games, wars,… Relations : red, round, prime, brother of, bigger than, part of, comes between, … Functions: father of, best friend, one more than, plus, Basic elements of Predicate Calculus : • Constants John, 2, DIT, Marcus... • Predicates Brother, >, King,... • Functions Sqrt, LeftLegOf,... • Variables x, y, a, b,... • Connectives , , , ,  • Equality = • Quantifiers ,  23. What is an assertion?

Sentences are added to a knowledge base using TELL , exactly as in prepositional logic. Such sentences are called assertions. Ex: Assert that John is a king and that kings are persons:  TELL(KB,King(John)) 

TELL(KB,

24. What is Semantic Net? A semantic network is a graphical knowledge representation technique. This knowledge representation system is primarily on network structure. A semantic net consists of nodes connected by arcs. The arcs are defined in a variety of ways, depending upon the kind of knowledge being represented. The main idea behind semantic net is that the meaning of a concept comes, from the ways in which it is connected to other concepts

5

25. What are frames? How do they differ from semantic nets A frame is a knowledge representation technique consists of collection of attributes and associated values that describe some entity in the world. Frames are general record like structures which consist of a collection of slots and slot values. A semantic network is a graphical knowledge representation technique. This knowledge representationsystem is primarily on network structure. The semantic networks were basically developed to modelhuman memory. A semantic net consists of nodes connected by arcs 26. What is propositional logic? propositional logicis a way of representing knowledge. Propositional calculus or logic is a formal system in which formulae representing propositions can be formed by combining atomic propositions using logical connectives Sentences considered in propositional logic are not arbitrary sentences but are the ones that are either true or false, but not both. This kind of sentences are called propositions. Elements of Propositional logic : NOT, AND, OR, IF_THEN (or IMPLY), IF_AND_ONLY_IF. They are also denoted by the symbols: , , , , , respectively. 27. What is entailment? Propositions tell about the notion of truth and it can be applied to logical reasoning.We can have logical entailment between sentences. This is known as entailment where a sentence follows logically from another sentence. In mathematical notation we write :

28. Why does uncertainty arise ?  Agents almost never have access to the whole truth about their environment.  Agents cannot find a caterorial answer.  Uncertainty can also arise because of incompleteness, incorrectness in agents understanding of properties of environment. 29. Define a game. Formal Definition of Game We will consider games with two players, whom we will call MAX and MIN. MAX moves first, and then they take turns moving until the game is over. At the end of the game, points are awarded to the winning player and penalties are given to the loser. A game can be formally defined as a search problem with the following components : o The initial state, which includes the board position and identifies the player to move. o A successor function, which returns a list of (move, state) pairs, each indicating a legal move and the resulting state. o A terminal test, which describes when the game is over. States where the game has ended are called terminal states. A utility function (also called an objective function or payoff function),which give a numeric value for the terminal states. In chess, the outcome is a win, loss, or draw, with values +1,-1,or 0. he payoffs in backgammon range from +192 to -192. 6

1. 2. 3. 4. 5. 6.

PART B Explain in detail about the structured representation of the knowledge Explain in detail and give a proof with example about Resolution Explain Procedural Versus Declarative Knowledge Explain with example the Predicate Calculus Write short note on Unification Explain the following Game Playing algorithm and example : i. Minimax Search Procedure (7) ii. Alpha-Beta Pruning (7) iii. Iterative Deepening (2)

7. Illustrate the use of Predicate Calculus (first-order logic) to represent knowledge.(6) 8. Translate the following sentences into formulas in predicate logic. John likes all kinds of food. Apples are food. Chicken is food. Anything anyone eats and isn’t killed by is food. Bill eats peanuts and is still alive. 9. Sue eats everything Bill eats 10. Describe the issues of Knowledge representation in detail. (8) 11. Explain the following set of facts in Predicate Logic and prove that “Marcus is dead” (8) 1. Marcus was a man 2. Marcus was a Pompeian 3. Marcus was born in 40 A.D. 4. All men are mortal. 5. All Pompeians died when the volcano erupted in 79 A.D. 6. No mortal lives longer than 150 years. 7. It is now 1991. 8. Alive means not dead. 9. If someone dies, then he is dead at all later times.

10. Give the Syntax and Semantics of a first order logic in detail with an eg. (16) 11. Explain the steps needed for Knowledge engineering Process in predicate logic. 12. Explain in detail about the unification with an algorithm in a first order logic.(8) 13. Discuss briefly about the weak slot and filler structure representation of Knowledge. 14. Discuss briefly about the strong slot and filler structure representation of Knowledge. 15. Explain the following in detail a. Resolution in Propositional Logic (6) b. Give resolution proof for example problem statement (10) Hate (Marcus, Caesar)

16. Using resolution verify that “Did Curiosity kill the cat” • Jack owns a dog. • Every dog owner is an animal lover. • No animal lover kills an animal. • Either Jack or Curiosity killed the cat, who is named Tuna. • Did Curiosity kill the cat? 7

17. Prove by resolution that Ravi likes peanuts using resolution. Problem Statement: 1. Ravi likes all kind of food. 2. Apples and chicken are food 3. Anything anyone eats and is not killed is food 4. Ajay eats peanuts and is still alive 5. Rita eats everything that Ajay eats Prove by resolution that Ravi likes peanuts using resolution.

8...