Knowledge

2.1 Game playing

Game Playing is an important domain of artificial intelligence. Games don’t require much knowledge; the only knowledge we need to provide is the rules, legal moves and the conditions of winning or losing the game. Both players try to win the game. So, both of them try to make the best move possible at each turn. Searching techniques like BFS(Breadth First Search) are not accurate for this as the branching factor is very high, so searching will take a lot of time. Game playing in AI is an active area of research and has many practical applications, including game development, education, and military training. By simulating game playing scenarios, AI algorithms can be used to develop more effective decision-making systems for real-world applications.

The most common search technique in game playing is Minimax search procedure. It is depth-first depth-limited search procedure. It is used for games like chess and tic-tac-toe.

Mini-Max Algorithm

Mini-max algorithm is a recursive or backtracking algorithm which is used in decision-making and game theory. It provides an optimal move for the player assuming that opponent is also playing optimally. v Mini-Max algorithm uses recursion to search through the game-tree. v Min-Max algorithm is mostly used for game playing in AI. Such as Chess, Checkers, tic-tac-toe, go, and various tow-players game. This Algorithm computes the minimax decision for the current state. v In this algorithm two players play the game, one is called MAX and other is called MIN. v Both the players fight it as the opponent player gets the minimum benefit while they get the maximum benefit. v Both Players of the game are opponent of each other, where MAX will select the maximized value and MIN will select the minimized value. v The minimax algorithm performs a depth-first search algorithm for the exploration of the complete game tree. v The minimax algorithm proceeds all the way down to the terminal node of the tree, then backtrack the tree as the recursion.

Pseudo-code for MinMax Algorithm:

function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node

if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva

else // for Minimizer player minEva= 3+infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva

Initial call: Minimax(node, 3, true)

Working of Min-Max Algorithm:

Step 2: Now, first we find the utilities value for the Maximizer, its initial value is -∞, so we will compare each value in terminal state with initial value of Maximizer and determines the higher nodes values. It will find the maximum among the all.

Step 3: In the next step, it's a turn for minimizer, so it will compare all nodes value with +∞, and will find the 3^rd layer node values.

¨ For node B= min(4,6) = 4 ¨ For node C= min (-3, 7) = -3

Step 4: Now it's a turn for Maximizer, and it will again choose the maximum of all nodes value and find the maximum value for the root node. In this game tree, there are only 4 layers, hence we reach immediately to the root node, but in real games, there will be more than 4 layers.

¨ For node A max(4, -3)= 4

That was the complete workflow of the minimax two player game.

Properties of Mini-Max algorithm:

Limitation of the minimax Algorithm:

The main drawback of the minimax algorithm is that it gets really slow for complex games such as Chess, go, etc. This type of games has a huge branching factor, and the player has lots of choices to decide. This limitation of the minimax algorithm can be improved from alpha- beta pruning

2.2 Knowledge Reprsentation

Knowledge Representation in AI refers to the way in which artificial intelligence systems store, organize, and utilize knowledge to solve complex problems. It is a crucial aspect of AI, enabling machines to mimic human understanding and reasoning. Knowledge representation involves the creation of data structures and models that can efficiently capture information about the world, making it accessible and usable by AI algorithms for decision-making, inference, and learning.

Humans are best at understanding, reasoning, and interpreting knowledge. Human knows things, which is knowledge and as per their knowledge they perform various actions in the real world. But how machines do all these things comes under knowledge representation and reasoning. Hence we can describe Knowledge representation as following:

Knowledge representation and reasoning (KR, KRR) is the part of Artificial intelligence which concerned with AI agents thinking and how thinking contributes to intelligent behavior of agents. v It is responsible for representing information about the real world so that a computer can understand and can utilize this knowledge to solve the complex real world problems such as diagnosis a medical condition or communicating with humans in natural language.

It is also a way which describes how we can represent knowledge in artificial intelligence. Knowledge representation is not just storing data into some database, but it also enables an intelligent machine to learn from that knowledge and experiences so that it can behave intelligently like a human.

What to Represent:

Following are the kind of knowledge which needs to be represented in AI systems:

Fig. 2.1 Types of Knowledge.

1. Declarative Knowledge:

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

4. Heuristic knowledge:

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

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. v It describes the relationship that exists between concepts or objects.

The relation between knowledge and intelligence:

Knowledge of real-worlds plays a vital role in intelligence and same for creating artificial intelligence. Knowledge plays an important role in demonstrating intelligent behavior in AI agents. An agent is only able to accurately act on some input when he has some knowledge or experience about that input.

AI knowledge cycle:

An Artificial intelligence system has the following components for displaying intelligent behavior:

Perception v Learning v Knowledge Representation and Reasoning v Planning v Execution

The above diagram is showing how an AI system can interact with the real world and what components help it to show intelligence. AI system has Perception component by which it retrieves information from its environment. It can be visual, audio or another form of sensory input. The learning component is responsible for learning from data captured by Perception comportment. In the complete cycle, the main components are knowledge representation and Reasoning. These two components are involved in showing the intelligence in machine-like humans. These two components are independent with each other but also coupled together. The planning and execution depend on analysis of Knowledge representation and reasoning.

Approaches to knowledge representation:

There are mainly four approaches to knowledge representation, which are givenbelow:

1. Simple relational knowledge:

Table. 2.1 Simple relational knowledge.

2. Inheritable knowledge:

Example:

Fig. 2.2 Inheritable knowledge Example.

3. Inferential knowledge:

Inferential knowledge approach represents knowledge in the form of formal logics. v This approach can be used to derive more facts. v It guaranteed correctness.

Example: Let's suppose there are two statements:

Key Techniques in Knowledge Representation

1. First-Order Logic (FOL)

First-Order Logic is a formal system used in mathematics, philosophy, and computer science to represent and reason about propositions involving objects, their properties, and their relationships. Unlike propositional logic, FOL allows the use of quantifiers (like "forall" and "exists") to express more complex statements.

FOL is widely used in AI for knowledge representation and reasoning because it allows for expressing general rules and facts about the world. For example, FOL can be used to represent statements like "All humans are mortal" and "Socrates is a human," enabling AI systems to infer that "Socrates is mortal." It provides a powerful and flexible framework for representing structured knowledge and supports various forms of logical reasoning.

2. Fuzzy Logic

Fuzzy Logic is an approach to knowledge representation that deals with reasoning that is approximate rather than exact. It allows for the representation of concepts that are not black and white, but rather fall along a continuum, with degrees of truth ranging from 0 to 1.

Fuzzy Logic is particularly useful in domains where precise information is unavailable or impractical, such as control systems, decision-making, and natural language processing. For example, in a climate control system, fuzzy logic can be used to represent concepts like "warm," "hot," or "cold," and make decisions based on the degree to which these conditions are met, rather than relying on strict numerical thresholds.

3. Description Logics

Description Logics are a family of formal knowledge representation languages used to describe and reason about the concepts and relationships within a domain. They are more expressive than propositional logic but less complex than full first-order logic, making them well-suited for representing structured knowledge.

Description Logics form the foundation of ontologies used in the Semantic Web and are key to building knowledge-based systems that require classification, consistency checking, and inferencing. For example, they can be used to define and categorize different types of products in an e-commerce system, allowing for automated reasoning about product features,

relationships, and hierarchies.

4. Semantic Web Technologies

Semantic Web Technologies refer to a set of standards and tools designed to enable machines to understand and interpret data on the web in a meaningful way. Key technologies include Resource Description Framework (RDF), Web Ontology Language (OWL), and SPARQL, which are used to represent, query, and reason about knowledge on the web.

These technologies are essential for building intelligent applications that can access, share, and integrate data across different domains and systems. For example, Semantic Web Technologies are used in search engines, recommendation systems, and data integration platforms to provide more relevant and accurate results by understanding the context and meaning of the data. They enable AI systems to perform tasks like semantic search, data linking, and automated reasoning over distributed knowledge bases.

Challenges in Knowledge Representation

While knowledge representation is fundamental to AI, it comes with several challenges:

Complexity: Representing all possible knowledge about a domain can be highly complex, requiring sophisticated methods to manage and process this information efficiently.

Ambiguity and Vagueness: Human language and concepts are often ambiguous or vague, making it difficult to create precise representations.

Scalability: As the amount of knowledge grows, AI systems must scale accordingly, which can be challenging both in terms of storage and processing power.

Knowledge Acquisition: Gathering and encoding knowledge into a machine-readable format is a significant hurdle, particularly in dynamic or specialized domains.

Reasoning and Inference: AI systems must not only store knowledge but also use it to infer new information, make decisions, and solve problems. This requires sophisticated reasoning algorithms that can operate efficiently over large knowledge bases.

Applications of Knowledge Representation

Knowledge representation is applied across various domains in AI, enabling systems to perform tasks that require human-like understanding and reasoning. Some notable applications include:

Expert Systems: These systems use knowledge representation to provide advice or make

decisions in specific domains, such as medical diagnosis or financial planning. Natural Language Processing (NLP): Knowledge representation is used to understand and generate human language, enabling applications like chatbots, translation systems, and sentiment analysis.

Robotics: Robots use knowledge representation to navigate, interact with environments, and perform tasks autonomously.

Semantic Web: The Semantic Web relies on ontologies and other knowledge representation techniques to enable machines to understand and process web content meaningfully.

Cognitive Computing: Systems like IBM's Watson use knowledge representation to process vast amounts of information, reason about it, and provide insights in fields like healthcare and research.

2.3 Understanding using Predicate Logic

Logic is a formal system in which the formulas or sentences have true or false values. Logics are of different types:

Propositional logic, Predicate logic, Temporal logic, Modal logic, Description logic etc; They represent things and allow more or less efficient inference.

Propositional Logic is the study of statements and their connectivity.

Predicate Logic is the study of individuals and their properties. We need languages that allow us to describe properties (predicates) of objects, or a relationship among objects represented by the variables. Predicate logic satisfies the requirements of a language. Predicate logic is powerful enough for expression and reasoning. Predicate logic is built upon the ideas of propositional logic. Predicate Logic can represent Objects and Quantification. Theorem proving is semidecidable. Proposition is a declarative sentence whose value is either true or false

Basics of logic symbols:

“→” Material Implication “┐” Not “v” Or

“^” and “∀” for all “Ǝ” There exists

Representing simple facts in Logic

Proposition logic is simple where a decision procedure exists. v Represent Real-World facts as logical propositions, written as well – formed formulas in propositional logic as shown in figure below: Example: Conclusion

The fact “It is raining“ the fact it is not sunny v Limitations of propositional logic are overridden.

If we want to represent the fact stated by the classical sentence. It is raining RAINING Its is sunny SUNNY It is windy WINDY If it is raining, then it is not sunny RAINING → ⌐ SUNNY

Socrates is a man We could write: SOCRATESMAN

But if we also wanted to represent Plato is a man We would have to write something such as: PLATOMAN Which would be a totally separate assertion, and we would not be able to draw any conclusions about similarities between Socrates and Plato. It would be much better to represent these facts as:

MAN (SOCRATES) MAN (PLATO) Since, now the structure of the representation reflects the structure of the knowledge itself. But to do that, we need to be able to use predicates applied to arguments. We are in even more difficulty if we try to represent the equally classic sentence All men are mortal. We could represent this as: MORTALMAN To capture the relationship between any individual being a man and that individual being a mortal. To do this, we need variable and quantification unless willing to write separate statements about the mortality of every known man. Predicate Logic

This logic is one way of representing knowledge because it permits representations of things that cannot reasonably be represented in prepositional logic.

If we use logical statements as a way of representing knowledge, than we have good way of reasoning with that knowledge.

Determining the validity of a propositional logic is easy but may be computationally hard.

Predicate logic provides a good way of reasoning with knowledge. v It provides a way of deducing new statements from old ones.

It does not possess a decision procedure, even an exponential one. There exist

procedures that will find a proof of a proposed theorem if indeed it is a theorem. First order predicate logic is semi decidable. Such a procedure is to use the rules of inference to generate theorems form the axioms in some fashion, testing each to see if it is the one for which a proof is sought.

Examples of Predicate Logic

Let’s now explore the use of predicate logic as a way of representing knowledge by looking at aspecific example. Consider the following set of sentences:

1. Marcus was a man.

2. Marcus was a Pompeian.
3. All Pompeians were Romans.
4. Caesar was a ruler.
5. All Romans were either loyal to Caesar or hated him.
6. Everyone is loyal to someone.
7. People only try to assassinate rulers they are not loyal to.
8. Marcus tried to assassinate Caesar. The facts described by these sentences can be represented as a set of wff’s in predicate logic asfollows:

1. Marcus was a man

Man (Marcus)

Although this representation fails to represent the notion of past tense (which is clear in the Englishsentence), it captures the critical fact of Marcus being a man. Whether this omission is acceptableor not depends on the use to which we intend to put the knowledge.

2. Marcus was a Pompeian

Pompeian (Marcus)

3. All Pompeians were Romans

∀x : Pompeian (x) → Roman(x)

4.Caesar was a ruler

Ruler (Caesar) Since many people share the same name, the fact that proper names are often not references to unique individuals, overlooked here. Occasionally deciding which of several people of the same name is being referred to in a particular statement may require a somewhat more amount of knowledge and logic

5. All Romans were either loyal to Caesar or hated him

∀x: Roman(x)→ loyalto(x, Caesar) V hate(x, Caesar)

In English, the word “or” sometimes means the logical inclusive-or and sometimes means the logical exclusive-or (XOR). Here we have used the inclusive interpretation. Soome people will argue, however, That this English sentence is really stating an exclusive-or. To express that, we would have to write: ∀x: Roman(x) → [(loyalto (x, Caesar) V hate(x, Caesar)) V ¬ (loyalto(x, Caesar) ^ hate(x, Caesar))]

6. Everyone is loyal to someone

∀x:→Ǝy: loyalto (x,y)

The scope of quantifiers is a major problem that arises when trying to convert English sentences into logical statements. Does this sentence say, as we have assumed in writing the logical formula above, that for each person there exists someone to whom he or she is loyal, possibly a different someone for everyone? Or does it say that there is someone to whom everyone is loyal?

7. People only try to assassinate rulers they are not loyal to

∀x : ∀y : person(x) ˄ ruler(y) ˄ tryassassinate(x,y) → ¬loyalto(x,y)

Like the previous one this sentence too is ambiguous which may lead to more than one conclusion.The usage of “try to assassinate” as a single predicate gives us a fairly simple representation withwhich we can reason about trying to assassinate. But there might be connections as try to assassinate and not actually assassinate could not be made easily.

8. Marcus tried to assassinate Caesar

To produce a Formal proof, reasoning backward from the desired goal:

¬loyalto(Marcus, Caesar)

To prove the goal

Use the rules of inference to transform it into another goal that can be transformed and so on, until there are no unsatisfied goals remaining.

This process requires the search of an AND-OR graph when there is an alternative way of satisfying individual goals. We show only a single path for simpler way.

The below figure shows an attempt to produce a proof of the goal by reducing the set of necessarybut as yet unattained goals to the empty set. If attempt fails, there is no way to satisfy the goal person with the available statements. Problem: Marcus was a man, need to add the representationof another fact to our system.

9.All men are people

∀x : man(x) → person(x)

Now we can satisfy the last goal and produce a proof that Marcus was not loyal to Caesar.

-loyalto (Marcus, Caesar)

↑ (7,substitution)

person (Marcus) ^ ruler (Caesra) ^ tryassassinate (Marcus, Caesar)

↑ (4)

person (Marcus) tryassassinate (Marcus, Caesar)

↑ (8)

person (Marcus)

Computable functions and predicates

Some of the computational predicates like Less than, Greater than used in knowledge representation. Simple facts were expresses as combinations of individual predicates, such a: Tryassassinate (Marcus, Caesar) If Number of facts is not large or if the facts are unstructured thenthere is little alternative.

If we want to express simple facts, like greater than and less than relations:gt(1,0) lt(0,1)

gt(2,1)

lt(1,2)

gt(3,2)

lt(2,3)

There is infinite representation of each of these fact. But if we consider the finite number of themthat can be represented, using a single machine word per number, extremely inefficient to store explicitly large a set of statements. Instead, we compute each one as we need it.

Functions and predicate use

Consider the following set of facts Again involving Marcus:

1. Marcus was a man

Man (Marcus) Again we ignore the issue of tense.

2. Marcus was a pompeian

Pompeian (Marcus) Marcus was born in 40 A.D

Born (Marcus, 40) For simplicity, we will not represent A.D. explicitly, just as we normally omit it in everyday discussions. If we ever need to represent dates B.C., then we will have to decideon a way to do that such as by using negative numbers.

2. All men are mortal

∀x: men(x)→ mortal(x)

3. erupted(volcano,79)∀x :[pompeian(x)→died(x, 79)] This sentence clearly asserts the two facts represented above. It may also assert another that we have not shown, namely that the eruption of the volcano caused the death of the Pompeians. Peopleoften assume causality between concurrent events if such causality seems possible.

4. No mortal lives longer than150 years

∀x: ∀t1: ∀t2: mortal(x) ˄ born(x,t1) ˄gt(t2-t1,150)→ dead(x,t2)

There are several ways that the content of this sentence could be expressed.

For example, we could introduce a function age and assert that its value is never greater than

5. It is Now 1991

Now=1991

Here we exploit the idea of equal quantities that can be substituted for each other. Now suppose we want to answer the question “Is Marcus alive?” A quick glance through the statements we havesuggests that there may be two ways of deducing an answer. Either we can show that Marcus is dead because he was killed by the volcano or we can show that he must be dead because he wouldotherwise be more than 150 years old, which we know is not possible.

As soon as we attempt to follow either of those paths rigorously, however, we discover, just as wedid in the last example, that we need some additional knowledge. For example, our statements talkabout dying, but they say nothing that relates to being alive, which is what the question is asking.So we add the following facts:

6. Alive means not dead

∀x: ∀t: [ alive(x,t) → ¬ dead(x,t)] Ù[¬ dead(x,t)→alive(x,t)]

This is not strictly correct, since ¬ dead implies alive only for animate objects. This is an exampleof the fact that rarely do two expressions have truly identical meanings in all circumstances.

7. If someone dies then he is dead at all later times

∀x: ∀t1: ∀t2: died(x,t1) ˄gt(t2,t1)→ dead(x,t2) This representation says that one is dead in all yearsafter the one in which one died. It ignores the question of whether one is dead in the year in which one died.

2.4 Overview of Predicate Calculus

Predicate Calculus deals with predicates, which are propositions containing variables.

Predicate

A predicate is an expression of one or more variables defined on some specific domain. A predicate with variables can be made a proposition by either assigning a value to the variable or by quantifying the variable.

Consider the following statement.

v Ram is a student.

Now consider the above statement in terms of Predicate calculus.

Here "is a student" is a predicate and Ram is subject.

Let's denote "Ram" as x and "is a student" as a predicate P then we can write the above statement as P(x). v Generally a statement expressed by Predicate must have at least one object associated with Predicate. In our case, Ram is the required object with associated with predicate

P.

Statement Function

Earlier we denoted "Ram" as x and "is a student" as predicate P then we have statement as P(x). Here P(x) is a statement function where if we replace x with a Subject say Sunil then we'll be having a statement "Sunil is a student."

Thus a statement function is an expression having Predicate Symbol and one or multiple variables. This statement function gives a statement when we replaced the variables with objects. This replacement is called substitution instance of statement function.

Quantifiers

The variable of predicates is quantified by quantifiers. There are two types of quantifier in predicate logic − Universal Quantifier and Existential Quantifier.

Universal Quantifier

Universal quantifier states that the statements within its scope are true for every value of the specific variable. It is denoted by the symbol ∀.

∀ x P(x) is read as for every value of x, P(x) is true.

Example − "Man is mortal" can be transformed into the propositional form ∀ x P(x) where P(x) is the predicate which denotes x is mortal and ∀ x represents all men.

Existential Quantifier

Existential quantifier states that the statements within its scope are true for some values of the specific variable. It is denoted by the symbol ∃.

∃ x P(x) is read as for some values of x, P(x) is true.

Example − "Some people are dishonest" can be transformed into the propositional form ∃ x P(x) where P(x) is the predicate which denotes x is dishonest and ∃ x represents some dishonest men.

Predicate Formulas

Consider a Predicate P with n variables as P(x1, x2, x3, ..., xn). Here P is n-place predicate and x1, x2, x3, ..., xn are n individuals variables. This n-place predicate is known as atomic formula of predicate calculus. For Example: P(), Q(x, y), R(x,y,z)

Well Formed Formula

Well Formed Formula (wff) is a predicate holding any of the following −

All propositional constants and propositional variables are wffs v If x is a variable and Y is a wff, ∀ x Y and ∀ x Y are also wff v Truth value and false values are wffs v Each atomic formula is a wff v All connectives connecting wffs are wffs

Free and Bound variables

Consider a Predicate formula having a part in form of (∃ x) P(x) of (x)P(x), then such part is called x-bound part of the formula. Any occurrence of x in x-bound part is termed as bound occurrence and any occurrence of x which is not x-bound is termed as free occurrence. See the examples below-v (∃ x) (P(x) ∧ Q(x)) v (∃ x) P(x) ∧ Q(x)

In first example, scope of (∃ x) is (P(x) ∧ Q(x)) and all occurrences of x are bound occurrences. Whereas in second example, scope of (∃ x) is P(x) and last occurrence of x in Q(x) is a free occurrence.

Universe of Discourse

We can limit the class of individuals/objects used in a statment. Here limiting means confining the input variable to a set of particular individuals/objects. Such a restricted class is termed as Universe of Discourse/domain of individual or universe. See the example below:

Some cats are black.

C(x) : x is a cat. v B(x) : x is black. v (∃ x)(C(x) ∧ B(x))

If Universe of discourse is E = { Katy, Mille } where katy and Mille are white cats then our third statement is false when we replace x with either Katy or Mille where as if Universe of discourse is E = { Jene, Jackie } where Jene and Jackie black cats then our third statement stands true for Universe of Discourse F.

2.5 Resolution

l₁ V …… V lₖ, m₁ V …… V mₙ

SUBST (θ, l₁ V …… V lᵢ₋₁ V lᵢ₊₁ …… V lₖ V m₁ V …… V mⱼ₋₁ V mⱼ₊₁ …… V mₙ)

Where li and mj are complementary literals.

This rule is also called the binary resolution rule because it only resolves exactly two literals.

Example: We can resolve two clauses which are given below:

[Animal (g(x) V Loves (f(x), x)] and [￢ Loves(a, b) V ￢Kills(a, b)]

Where two complimentary literals are: Loves (f(x), x) and ￢ Loves (a, b)

These literals can be unified with unifier θ= [a/f(x), and b/x], and it will generate a resolvent clause:

[Animal (g(x) V ￢ Kills(f(x), x)].

Steps for Resolution:

1. Conversion of facts into first-order logic. 2. Convert FOL statements into CNF 3. Negate the statement which needs to prove (proof by contradiction) 4. Draw resolution graph (unification). To better understand all the above steps, we will take an example in which we will apply resolution.

Example:

Step-1: Conversion of Facts into FOL

In the first step we will convert all the given statements into its first order logic.

Step-2: Conversion of FOL into CNF

In First order logic resolution, it is required to convert the FOL into CNF as CNF form makes easier for resolution proofs.

Eliminate all implication (→) and rewrite

Move negation (¬)inwards and rewrite

Rename variables or standardize variables

Eliminate existential instantiation quantifier by elimination. In this step, we will eliminate existential quantifier ∃, and this process is known as Skolemization. But in this example problem since there is no existential quantifier so all the statements will remain same in this step.

Drop Universal quantifiers. In this step we will drop all universal quantifier since all the statements are not implicitly quantified so we don't need it.

Distribute conjunction ∧ over disjunction ¬. This step will not make any change in this problem.

Step-3: Negate the statement to be proved

In this statement, we will apply negation to the conclusion statements, which will be written as ¬likes(John, Peanuts)

Step-4: Draw Resolution graph:

Fig. 2.3 Resolution graph.

Hence the negation of the conclusion has been proved as a complete contradiction with the given set of statements.

Explanation of Resolution graph:

In the first step of resolution graph, ¬likes(John, Peanuts), and likes(John, x) get resolved(canceled) by substitution of {Peanuts/x}, and we are left with ¬ food(Peanuts) v In the second step of the resolution graph, ¬ food(Peanuts), and food(z) get resolved (canceled) by substitution of { Peanuts/z}, and we are left with ¬ eats(y, Peanuts) V killed(y). v In the third step of the resolution graph, ¬ eats(y, Peanuts) and eats (Anil, Peanuts) get resolved by substitution {Anil/y}, and we are left with Killed(Anil). v In the fourth step of the resolution graph, Killed(Anil) and ¬ killed(k) get resolve by substitution {Anil/k}, and we are left with ¬ alive(Anil). v In the last step of the resolution graph ¬ alive(Anil) and alive(Anil) get resolved.

2.6 Structured Representation of Knowledge

can be used in any number of ways. Facts can be easily added to declarative systems without changing the general procedures. **Procedural Method:-**In these knowledge is represented as procedures. Default reasoning and probabilistic reasoning are examples of procedural methods. In these, heuristic knowledge of “How to do things efficiently “can be easily represented. In practice most of the knowledge representation employ a combination of both. Most of the knowledge representation structures have been developed to handle programs that handle natural language input. One of the reasons that knowledge structures are so important is that they provide a way to represent information about commonly occurring patterns of things. such descriptions are some times called schema. One definition of schema is “Schema refers to an active organization of the past reactions, or of past experience, which must always be supposed to be operating in any well adapted organic response”. By using schemas, people as well as programs can exploit the fact that the real world is not random. There are several types of schemas that have proved useful in AI programs. They include Frames:- Used to describe a collection of attributes that a given object possesses (eg: description of a chair). Scripts:- Used to describe common sequence of events (eg:- a restaurant scene).

Stereotypes :- Used to described characteristics of people.

Rule models:- Used to describe common features shared among a set of rules in a production system. Frames and scripts are used very extensively in a variety of AI programs. Before selecting any specific knowledge representation structure, the following issues have to be considered. The basis properties of objects, if any, which are common to every problem domain must be identified and handled appropriately. The entire knowledge should be represented as a good set of primitives.

Mechanisms must be devised to access relevant parts in a large knowledge base.

=== CHAPTER-3