V SEMESTER

ARTIFICIAL
INTELLIGENCE(BCS515B)

2022 SCHEME VTU

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

FIRST ORDER LOGIC

Syllabus
First Order Logic: Representation Revisited, Syntax and Semantics of First Order logic, Using
First Order logic, Knowledge Engineering In First-Order Logic
Inference in First Order Logic: Propositional Versus First Order Inference, Unification,
Forward Chaining
Chapter 8- 8.1, 8.2, 8.3, 8.4
Chapter 9- 9.1, 9.2, 9.3

SESSION 8

8.1 REPRESETATION REVISITED

Programming languages (such as C++ or Java or Lisp) are by far the largest class of formal languages in
common use. Programs themselves represent, in a direct sense, only computational processes. Data structures
within programs can represent facts; for example, a program could use a 4 × 4 array to represent the contents of
the wumpus world. Thus, the programming language statement World [2,2]← Pit is a fairly natural way to
assert that there is a pit in square [2,2].

Drawbacks of using data structure/programming language:

1. Any general mechanism for deriving facts from other facts; each update to a data structure is done by a
domain-specific procedure whose details are derived by the programmer from his or her own knowledge of the
domain. This procedural approach can be contrasted with the declarative nature of propositional logic, in which
knowledge and inference are separate, and inference is entirely domain independent.

2. A second drawback of data structures in programs (and of databases, for that matter) is the lack of any easy
way to say, for example, “There is a pit in [2,2] or [3,1]” or “If the wumpus is in [1,1] then he is not in [2,2].”
Programs can store a single value for each variable, and some systems allow the value to be “unknown,” but
they lack the expressiveness required to handle partial information.

Propositional logic is a declarative language because its semantics is based on a truth relation between
sentences and possible worlds. It also has sufficient expressive power to deal with partial information, using
disjunction and negation. Propositional logic has a third COMPOSITIONALITY property that is desirable in
representation languages, namely, compositionality.

In a compositional language, the meaning of a sentence is a function of the meaning of its parts. For example,
the meaning of “S1,4 ∧ S1,2” is related to the meanings of “S1,4” and “S1,2.” It would be very strange if
“S1,4” meant that there is a stench in square [1,4] and “S1,2” meant that there is a stench in square [1,2], but
“S1,4 ∧ S1,2” meant that France and Poland drew 1–1 in last week’s ice hockey qualifying match. Clearly,
non-compositionality makes life much more difficult for the reasoning system.

8.1.1 The language of thought

The famous Sapir–Whorf hypothesis claims that our understanding of the world is strongly influenced by the
language we speak. Whorf (1956) wrote “We cut nature up, organize it into concepts, and ascribe significances
as we do, largely because we are parties to an agreement to organize it this way—an agreement that holds
throughout our speech community and is codified in the patterns of our language.” It is certainly true that
different speech communities divide up the world differently.

Canara Engineering College Module - 4 2

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

 Wanner (1974) did a similar experiment and found that subjects made the right choice at chance level—
about 50% of the time—but remembered the content of what they read with better than 90% accuracy. This
suggests that people process the words to form some kind of representation.

 More interesting is the case in which a concept is completely absent in a language. Speakers of the
Australian aboriginal language Guugu Yimithirr have no words for relative directions, such as front, back,
right, or left. Instead they use absolute directions, saying, for example, the equivalent of “I have a pain in my
north arm.” This difference in language makes a difference in behavior: Guugu Yimithirr speakers are better
at navigating in open terrain, while English speakers are better at placing the fork to the right of the plate.

 Language also seems to influence thought through seemingly arbitrary grammatical features such as the
gender of nouns. For example, “bridge” is masculine in Spanish and feminine in German. Boroditsky (2003)
asked subjects to choose English adjectives to describe a photograph of a particular bridge. Spanish speakers
chose big, dangerous, strong, and towering, whereasGerman speakers chose beautiful, elegant, fragile, and
slender. Words can serve as anchor points that affect how we perceive the world.

 Loftus and Palmer (1974) showed experimental subjects a movie of an auto accident. Subjects who were
asked “How fast were the cars going when they contacted each other?” reported an average of 32 mph,
while subjects who were asked the question with the word “smashed” instead of “contacted” reported
41mph for the same cars in the same movie.

 In a first-order logic reasoning system that uses CNF, we can see that the linguistic form “¬(A ∨ B)” and
“¬A ∧ ¬B” are the same because we can look inside the system and see that the two sentences are stored as
the same canonical CNF form. Can we do that with the human brain? Until recently the answer was “no,”
but now it is “maybe.” Mitchell et al. (2008) put subjects in an fMRI (functional magnetic resonance
imaging) machine, showed them words such as “celery,” and imaged their brains. The researchers were then
able to train a computer program to predict, from a brain image, what word the subject had been presented
with. Given two choices (e.g., “celery” or “airplane”), the system predicts correctly 77% of the time.

8.1.2 Combining the best of formal and natural languages

When we look at the syntax of natural language, the most obvious elements are nouns OBJECT and noun
phrases that refer to objects (squares, pits, wumpuses) and verbs and verb phrases RELATION that refer to
relations among objects (is breezy, is adjacent to, shoots). Some of these relaFUNCTION tions are
functions—relations in which there is only one “value” for a given “input.” It is easy to start listing
examples of objects, relations, and functions:

 Objects: people, houses, numbers, theories, Ronald McDonald, colors, baseball games, wars, centuries ...
PROPERTY
 Relations: these can be unary relations or properties such as red, round, bogus, prime, multistoried ..., or
more general n-ary relations such as brother of, bigger than, inside, part of, has color, occurred after, owns,
comes between, ...
 Functions: father of, best friend, third inning of, one more than, beginning of ... Indeed, almost any assertion
can be thought of as referring to objects and properties or relations. Some examples follow:
 “One plus two equals three.” Objects: one, two, three, one plus two; Relation: equals; Function: plus. (“One
plus two” is a name for the object that is obtained by applying the function “plus” to the objects “one” and
“two.” “Three” is another name for this object.)
 “Squares neighboring the wumpus are smelly.” Objects: wumpus, squares; Property: smelly; Relation:
neighboring.
 “Evil King John ruled England in 1200.” Objects: John, England, 1200; Relation: ruled; Properties: evil,

Canara Engineering College Module - 4 3

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

king.
 Propositional logic is a declarative language because its semantics is based on a truth relation between
sentences and possible words. It also has sufficient expressive power to deal with partial information using
disjunction and negation. The primary difference between propositional logic and first order logic lies in the
ontological commitment made by each language. Propositional logic assumes that there are facts that either
hold or do not hold in the world. Each fact can be in one of two states: true or false. First order logic
assumes that the world consists of objects with certain relations among them that do or do not hold.

 The language of first-order logic, whose syntax and semantics we define in the next section, is built around
objects and relations. It has been so important to mathematics, philosophy, and artificial intelligence
precisely because those fields—and indeed, much of everyday human existence—can be usefully thought of
as dealing with objects and the relations among them.

 First-order logic can also express facts about some or all of the objects in the universe. This enables one to
represent general laws or rules, such as the statement “Squares neighboring the wumpus are smelly.”

 The ontological and epistemological commitments of five different logics are summarized in below table:

8.2 SYNTAX AND SEMANTICS OF FIRST ORDER LOGIC

8.2.1 Models for first-order logic

 The models of a logical language are the formal structures that constitute the possible worlds under
consideration.
 Models for propositional logic are just sets of truth values for the proposition symbols.
 Models for first-order logic are more interesting.
 First they have objects in them.
 The domain of a model is the set of objects it contains; these objects are sometimes called domain
elements.
 The following diagram shows a model with five objects

Canara Engineering College Module - 4 4

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

 The five objects are, 1. Richard the Lionheart 2. His younger brother 3. The evil King John 4. The left
legs of Richard and John 5. A crown
 The objects in the model may be related in various ways, In the figure Richard and John are brothers.
 Formally speaking, a relation is just the set of tuples of objects that are related.
 A tuple is a collection of Objects arranged in a fixed order and is written with angle brackets
surrounding the objects.
 Thus, the brotherhood relation in this model is the set
{(Richard the Lionheart, King John), (King John, Richard the Lionheart)}
 The crown is on King John’s head, so the “on head” relation contains just one tuple, (the crown, King
John).
 The relation can be binary relation relating pairs of objects (Ex:- “Brother”) or unary relation
representing a common object (Ex:- “Person” representing both Richard and John)
 Certain kinds of relationships are best considered as functions that relates an object to exactly one
object.
 For Example:- each person has one left leg, so the model has a unary “left leg” function that includes
the following mappings
⟨Richard the Lionheart⟩ → Richard’s left leg
⟨King John⟩ → John’s left leg

8.2.2 Symbols and interpretations

 The basic syntactic elements of first-order logic are the symbols that stand for objects, relations and
functions
 The symbols come in three kinds namely,
o Constant Symbols standing for Objects (Ex:- Richard)
o Predicate Symbols standing for Relations (Ex:- King)
o Function Symbols stands for functions (Ex:- LeftLeg)
o Symbols will begin with uppercase letters
Canara Engineering College Module - 4 5
V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

o The choice of names is entirely up to the user o Each predicate and function symbol comes with
an arity
o Arity fixes the number of arguments.
 The semantics must relate sentences to models in order to determine truth.
 To do this, an interpretation is needed specifying exactly which objects, relations and functions are
referred to by the constant, predicate and function symbols.
 One possible interpretation called as the intended interpretation- is as follows;
o Richard refers to Richard the Lionheart and John refers to the evil King John.
o Brother refers to the brotherhood relation, that is the set of tuples of objects given in equation
{(Richard the Lionheart, King John),(King John, Richard the Lionheart)}
o OnHead refers to the “on head” relation that holds between the crown and King John; Person,
King and Crown refer to the set of objects that are persons, kings and crowns.
o Leftleg refers to the “left leg” function, that is, the mapping given in
{(Richard the Lionheart, King John),(King John, Richard the Lionheart)}
 There are many other possible interpretations relating these symbols to this particular model.
 The truth of any sentence is determined by a model and an interpretation for the sentence symbols.
 The syntax of the FOL with equality specified in BNF is as follows:

Canara Engineering College Module - 4 6

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

Figure 8.4. It shows that models vary in how many objects they contain—from one up to infinity—and in the
way the constant symbols map to objects. If there are two constant symbols and one object, then both
symbols must refer to the same object; but this can still happen even with more objects. When there are more
objects than constant symbols, some of the objects will have no names. Because the number of possible
models is unbounded, checking entailment by the enumeration of all possible models is not feasible for first-
order logic (unlike propositional logic). Even if the number ofobjects is restricted, the number of
combinations can be very large.

8.2.3 Terms
 A Term is a logical expression that refers to an object
 Constant symbol are therefore terms, but it is not always convenient to have a distinct symbol to name every
object.
 For Example:- in English we might use the expression “King Johns left leg” rather than giving a name to his
leg.
 A complex term is formed by a function symbol followed by a parenthesized list of terms as arguments to
the function symbol.
 It is just like a complicated kind of name. It’s not a “subroutine call” that returns a value”.
 The formal semantics of terms is straight forward, Consider a term f(t1……tn) Where f- some function in
the model (call it F) The argument terms – objects in the domain The term – object that is the value of the
function F applied to the domain
 For Example:- suppose the LeftLeg function symbol refers to the function is,
(Richard the Lionheart) ->Richards left leg (King John ) ->Johns left leg John refers to King John,
then LeftLeg (John) refers to king Johns left leg.
 In this way the Interpretation fixes the referent of every term.

8.2.4 Atomic sentences

 An atomic sentence is formed from a predicate symbol followed by a parenthesized list of terms:
Brother (Richard, John)
 This states that Richard the Lionheart is the brother of King John.
 Atomic Sentences can have complex terms as arguments.
 Thus, Married (Father (Richard), Mother (John)) states that Richard the Lionheart’s father is married to
King John’s mother.
 An atomic sentence is true in a given model, under a given interpretation, if the relation referred to by
the predicate symbol holds among the objects referred to by the arguments.

Canara Engineering College Module - 4 7

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

8.2.5 Complex sentences

 Logical connectives can be used to construct more complex sentences, just as in propositional calculus.
 The semantics of sentences formed with logical connectives is identical to that in the propositional case.

8.2.6 Quantifiers
 Quantifiers are used to express properties of entire collections of objects, instead of enumerating the objects
by name if a logic that allows object is found.
 The following are the types of standard quantifiers,
o Universal
o Existential

Universal quantification (∀ )
 Rules such as “Squares neighboring the wumpus are smelly” and “All kings are persons” are the
bread and butter of first-order logic.
 The second rule, “All kings are persons,” is written in first-order logic as

 ∀ is usually pronounced “For all . . .”. (Remember that the upside-down A stands for “all.”) Thus, the sentence
says,
“For all x, if x is a king, then x is a person.” The symbol x is called a variable.
 A variable is a term all by itself, and as such can also serve as the argument of a function for example, LeftLeg(x). A
term with no variables is called a ground term.
 We can extend the interpretation in five ways:
x → Richard the Lionheart,
x → King John,
x → Richard’s left leg,
x → John’s left leg,
x → the crown.
 The universally quantified sentence ∀ x King(x) ⇒ Person(x) is true in the original model if the sentence
King(x) ⇒ Person(x) is true under each of the five extended interpretations.
That is, the universally quantified sentence is equivalent to asserting the following five
sentences:
Richard the Lionheart is a king ⇒ Richard the Lionheart is a person.
King John is a king ⇒ King John is a person.
Richard’s left leg is a king ⇒ Richard’s left leg is a person.

Canara Engineering College Module - 4 8

V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

John’s left leg is a king ⇒ John’s left leg is a person.

The crown is a king ⇒ the crown is a person.

Existential quantification (∃)

 Universal quantification makes statements about every object. Similarly, we can make a statement about
some object in the universe without naming it, by using an existential quantifier.
 for example, that King John has a crown on his head, we write
∃x Crown(x) ∧ OnHead(x, John) .
∃x is pronounced “There exists an x such that . . .” or “For some x . . .”. Intuitively, the sentence ∃x P says
that P is true for at least one object x.
 More precisely, ∃x P is true in a given model if P is true in at least one extended interpretation that assigns
x to a domain element. That is, at least one of the following is true:

Richard the Lionheart is a crown ∧ Richard the Lionheart is on John’s head;

King John is a crown ∧ King John is on John’s head;
Richard’s left leg is a crown ∧ Richard’s left leg is on John’s head;
John’s left leg is a crown ∧ John’s left leg is on John’s head;
The crown is a crown ∧ the crown is on John’s head.

 Consider the following sentence:

∃ x Crown(x) ⇒ OnHead(x, John) .
 On the surface, this might look like a reasonable rendition of our sentence. Applying the semantics, we see
that the sentence says that at least one of the following assertions is true:

Richard the Lionheart is a crown ⇒ Richard the Lionheart is on John’s head;

King John is a crown ⇒ King John is on John’s head;
Richard’s left leg is a crown ⇒ Richard’s left leg is on John’s head;

Nested quantifiers:
1. The simplest case is where the quantifiers are of the same type. For example, “Brothers are siblings” can be
written as

2. Consecutive quantifiers of the same type can be written as one quantifier with several variables.
For example, to say that siblinghood is a symmetric relationship, we can write

3. In other cases we will have mixtures. “Everybody loves somebody” means that for every person, there is
someone that person loves:

4. On the other hand, to say “There is someone who is loved by everyone,” we write

5. The order of quantification is therefore very important. It becomes clearer if we insert parentheses.
says that everyone has a particular property, namely, the property
that they love someone.
6. On the other hand,
says that someone in the world has a particular property, namely the
property of being loved by everybody.
Canara Engineering College Module - 4 9
 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

7. Some confusion can arise when two quantifiers are used with the same variable name.
Consider the sentence

Here the x in Brother (Richard, x) is existentially quantified. The rule is that the variable belongs to the
innermost quantifier that mentions it; then it will not be subject to any other quantification. Another way to
think of it is this: ∃x Brother (Richard, x) is a sentence about Richard (that he has a brother), not about x; so
putting a ∃ x outside it has no effect. It could equally well have been written ∃ z Brother (Richard, z).
Because this can be a source of confusion, we will always use different variable names with nested
quantifiers.

Connections between ∀ and ∃

The two quantifiers are actually intimately connected with each other, through negation. Asserting that

1. everyone dislikes parsnips is the same as asserting there does not exist someone who likes them, and vice
versa:

2. “Everyone likes ice cream” means that there is no one who does not like ice cream:

3. Because ∀ is really a conjunction over the universe of objects and ∃ is a disjunction, it should not be
surprising that they obey De Morgan’s rules. The De Morgan rules for quantified and unquantified sentences
are as follows:

8.2.7 Equality
 First-order logic includes one more way to make atomic sentences, other than using a predicate and terms as
described earlier. We can use the equality symbol to signify that two terms refer to the same object. For
example,

says that the object referred to by Father (John) and the object referred to by Henry are the same.
 The equality symbol can be used to state facts about a given function, as we just did for the Father
symbol.
 It can also be used with negation to insist that two terms are not the same object. To
say that Richard has at least two brothers, we would write

consider the extended interpretation in which both x and y are assigned to King John. The addition of
¬(x=y) rules out such models. The notation x ̸= y is sometimes used as an abbreviation for ¬(x=y).

8.2.8 An alternative semantics?

Canara Engineering College Module - 4 10
 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

If Richard had two brothers, John and Geoffrey

Brother (John, Richard ) ∧ Brother (Geoffrey, Richard) ?
̸ Geoffrey.
1. First, this assertion is true in a model where Richard has only one brother we need to add John =

2. Second, the sentence doesn’t rule out models in which Richard has many more brothers besides John and
Geoffrey.

Thus, the correct translation of “Richard’s brothers are John and Geoffrey” is as follows:

Figure 8.5 shows some of the models, ranging from the model with no tuples satisfying the relation to the
model with all tuples satisfying the relation. With two objects, there are four possible two-element tuples, so
there are 2^4 =16 different subsets of tuples that can satisfy the relation. Thus, there are 16 possible models
in all a lot fewer than the infinitely many models for the standard first-order semantics. On the other hand,
the database semantics requires definite knowledge of what the world contains.

8.3 USING FIRST-ORDER LOGIC

8.3.1 Assertions and queries in first-order logic
Sentences are added to a knowledge base using TELL, exactly as in propositional logic. Such sentences are called
assertions. For example, we can assert that John is a king, Richard is a person, and all kings are persons:

TELL(KB, King(John)) .
TELL(KB, Person(Richard)) .
TELL(KB, ∀x King(x) ⇒ Person(x))

1. We can ask questions of the knowledge base using ASK.

ASK(KB, King(John)) returns true.
2. Questions asked with ASK are called queries or goals. given the two preceding assertions, the query
ASK(KB, Person(John)) returns true.
ASK(KB, ∃x Person(x)) returns true.
3. “Can you tell me the time?” with “Yes.” If we want to know what value of x makes the sentence true, we
will need a different function, ASKVARS, which we call with
ASKVARS(KB, Person(x))
4. In this case there will be two answers: {x/John} and {x/Richard}. Such an answer is called a substitution or
binding list.

Canara Engineering College Module - 4 11

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

8.3.2 The Kinship Domain

 The first example we consider is the domain of family relationships, or kinship.

 This domain includes facts such as “Elizabeth is the mother of Charles” and “Charles is the father of

William” and rules such as “One’s grandmother is the mother of one’s parent.”
 The objects in our domain are people.
 There are two unary predicates, Male and Female.
 Kinship relations—parenthood, brotherhood, marriage, and so on—are represented by binary predicates: Parent,
Sibling, Brother , Sister , Child , Daughter, Son, Spouse, Wife, Husband, Grandparent , Grandchild , Cousin,
Aunt, and Uncle.
 The functions used are Mother and Father, because every person has exactly one of each of these (at least according
to nature’s design).

Examples:

one’s mother is one’s female parent:

Canara Engineering College Module - 4 12

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

8.3.3 Numbers, Sets and Lists

 Natural numbers or non-negative.
 Natural numbers are defined recursively:

 0 is a constant symbol and for every object n, if n is a natural number, then S(n) is a natural number.
 So the natural numbers are 0, S(0), S(S(0)) and so on.

 defining addition in terms of the successor function:

 The first of these axioms says that adding 0 to any natural number m gives m itself.
 We can also write S(n) as n+ 1,

Sets:
 The empty set is a constant written as {}. There is one unary predicate, Set, which is true of sets.
 The binary predicates are x∈ s (x is a member of set s) and s1 ⊆ s2 (set s1 is a subset, not necessarily
proper, of set s2).
 The binary functions are s1 ∩ s2 (the intersection of two sets), s1 ∪ s2 (the union of two sets), and {x|s}
(the set resulting from adjoining element x to set s).
 One possible set of axioms is as follows:

Canara Engineering College Module - 4 13

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

Lists:

 Lists are similar to sets.

 The differences are that lists are ordered and the same element can appear more than once in a list.
 The vocabulary of Lisp for lists: Nil is the constant list with no elements; Cons, Append, First, and Rest
are functions.
 The empty list is [ ].
 The term Cons(x, y), where y is a nonempty list, is written [x|y].
 The term Cons(x, Nil) (i.e., the list containing the element x) is written as [x].
 A list of several elements, such as [A,B,C], corresponds to the nested term
Cons(A, Cons(B, Cons(C, Nil))).

8.3.4 The Wumpus World

 Recall that the wumpus agent receives a percept vector with five elements.

 The corresponding first-order sentence stored in the knowledge base must include both the
percept and the time at which it occurred; otherwise, the agent will get confused about

Canara Engineering College Module - 4 14

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

when it saw what.

 A typical percept sentence

Here, Percept is a binary predicate, and Stench and so on are constants placed in a list.
 The actions in the wumpus world can be represented by logical terms:

 To determine which is best, the agent program executes the query

which returns a binding list such as {a/Grab}. The agent program can then return Grab as the action to take.

 Simple “reflex” behavior can also be implemented by

quantified implication sentences.

 Adjacency of any two squares can be defined as

The agent’s location changes over time, so we write At(Agent, s, t) to mean that the
agent is at square s at time t. Wecanfixthewumpus’s locationwith+t At(Wumpus, [2, 2], t).
We can then say that objects can only be at one location at a time:

8.4 KNOWLEDGE ENGINEERING IN FIRST-ORDER LOGIC

A knowledge engineer is someone who investigate a particular domain, learns what concepts are important in
that domain, and creates a formal representation of the objects and relations in the domain.
8.4.1 The knowledge-engineering process

Canara Engineering College Module - 4 15

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

1. Identify the task. The knowledge engineer must delineate the range of questions that the knowledge base
will support and the kinds of facts that will be available for each specific problem instance. For example,
does the wumpus knowledge base need to be able to choose actions or is it required to answer questions only
about the contents of the environment? Will the sensor facts include the current location? The task will
determine what knowledge must be represented in order to connect problem instances to answers.

2. Assemble the relevant knowledge. The knowledge engineer might already be an expert in the domain, or
might need to work with real experts to extract what they know—a process called knowledge acquisition.
At this stage, the knowledge is not represented formally. The idea is to understand the scope of the
knowledge base, as determined by the task, and to understand how the domain actually works. For the
wumpus world, which is defined by an artificial set of rules, the relevant knowledge is easy to identify.
(Notice, however, that the definition of adjacency was not supplied explicitly in the wumpus-world rules.)
For real domains, the issue of relevance can be quite difficult—for example, a system for simulating VLSI
designs might or might not need to take into account stray capacitances and skin effects.

3. Decide on a vocabulary of predicates, functions, and constants. That is, translate the important domain-level
concepts into logic-level names. This involves many questions of knowledge-engineering style. Like
programming style, this can have a significant impact on the eventual success of the project. For example,
should pits be represented by objects or by a unary predicate on squares? Should the agent’s orientation be a
function or a predicate? Should the wumpus’s location depend on time? Once the choices have been made,
the result is a vocabulary that is known as the ontology of the domain. The word ontology means a
particular theory of the nature of being or existence. The ontology determines what kinds of things exist, but
does not determine their specific properties and interrelationships.

4. Encode general knowledge about the domain. The knowledge engineer writes down the axioms for all the vocabulary
terms. This pins down (to the extent possible) the meaning of the terms, enabling the expert to check the content.
Often, this step reveals misconceptions or gaps in the vocabulary that must be fixed by returning to step 3 and iterating
through the process.
5. Encode a description of the specific problem instance. If the ontology is well thought out, this step will be easy. It will
involve writing simple atomic sentences about instances of concepts that are already part of the ontology. For a logical
agent, problem instances are supplied by the sensors, whereas a “disembodied” knowledge base is supplied with
additional sentences in the same way that traditional programs are supplied with input data.
6. Pose queries to the inference procedure and get answers. This is where the reward is: we can let the inference
procedure operate on the axioms and problem-specific facts to derive the facts we are interested in knowing. Thus, we
avoid the need for writing an application-specific solution algorithm.
7. Debug the knowledge base. Alas, the answers to queries will seldom be correct on the first try. More precisely, the
answers will be correct for the knowledge base as written, assuming that the inference procedure is sound, but they
will not be the ones that the user is expecting. For example, if an axiom is missing, some queries will not be
answerable from the knowledge base. A considerable debugging process could ensue. Missing axioms or axioms that
are too weak can be easily identified by noticing places where the chain of reasoning stops unexpectedly.
For example,

9 INFERENCE IN FIRST-ORDER LOGIC

9.1 PROPOSITIONAL VS. FIRST-ORDER INFERENCE

Canara Engineering College Module - 4 16

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

9.1.1 Inference rules for quantifiers

All greedy kings are evil

Inference:

 The rule of Universal Instantiation (UI for short) says that we can infer any sentence obtained by substituting a
ground term (a term without variables) for the variable.
 Let SUBST(θ,α) denote the result of applying the substitution θ to the sentence α.
 Then the rule is written

For any variable v and ground term g.

 For example, the three sentences given earlier are obtained with the substitutions {x/John}, {x/Richard}, and
{x/Father (John)}.
 In the rule for Existential Instantiation, the variable is replaced by a single new constant symbol. The
formal statement is as follows: for any sentence α, variable v, and constant symbol k that does not appear
elsewhere in the knowledge base,

9.1.2 Reduction to propositional inference

Suppose the KB contains just the following:

Instantiating the universal sentence in all possible ways,

Canara Engineering College Module - 4 17

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

King(John),
Greedy(John),
Brother(Richard, John)
The new KB is proportionalized: Proposition symbols are
King(John), Greedy(John),Evil(John),King(Richard) and so on.

Problems with Propositionalization

 Propositionalization seems to generate lots of irrelevant sentence.
 With function symbols , there are infinitely many ground terms,
Example: Father(Father(Father(John)))

9.2 UNIFICATION AND LIFTING

Unification is a procedure that compares two literals & discovers whether there exists a set of
substitutions that makes them identified. Any substitution that makes 2 or more expressions equal is
called a unifier for the expressions. Unification can sometimes be applied to literals within the same
single clause. When an MGU exists such that 2 or more literals with in a clause are unified, the clause
remaining after deletion of all but one of the unified literals is called a factor of the original clause. The
basic idea of unification is very simple - to attempt to unify 2 literals, we first check if their initial
predicate symbols are the same, if so we can proceed otherwise there is no way they can be unified,
regardless of their arguments. Unification has deep mathematical roots and is a useful in many AI
programs. for ex: theorem proving and natural language parser.

9.1.1 First order inference rule

Canara Engineering College Module - 4 18

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

9.2.2

Canara Engineering College Module - 4 19

V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

Canara Engineering College Module - 4 20

V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

Canara Engineering College Module - 4 21

V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

Canara Engineering College Module - 4 22

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

9.2.3

Canara Engineering College Module - 4 23

V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

 Given a sentence to be stored, it is possible to construct indices for all possible queries that unify with it.
For the fact Employs(IBM , Richard), the queries are
Employs(IBM , Richard) Does IBM employ Richard?
Employs(x, Richard ) Who employs Richard?
Employs(IBM , y) Whom does IBM employ?
Employs(x, y) Who employs whom?

Canara Engineering College Module - 4 24

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

9.3 FORWARD CHAINING

 The idea is simple: start with the atomic sentences in the knowledge base and apply Modus Ponens in the
forward direction, adding new atomic sentences, until no further inferences can be made.
 Here, we explain how the algorithm is applied to first-order definite clauses.
 Definite clauses such as Situation ⇒ Response are especially useful for systems that make inferences in
response to newly arrived information.

 Consider the following problem:

“The law says that it is a crime for an American to sell weapons to hostile nations. The country Nono, an enemy of
America, has some missiles, and all of its missiles were sold to it by ColonelWest, who is American.”

Canara Engineering College Module - 4 25

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

Canara Engineering College Module - 4 26

V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

Canara Engineering College Module - 4 27

 V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

9.3.3 Efficient Forward chaining:-

 The above discussed FC Algorithm has three possible types of complexity

Canara Engineering College Module - 4 28

V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

Matching rule against known facts:

 The problem of matching the premise of a rule against the facts in the knowledge base might seem simple
enough. For example, suppose we want to apply the rule
Missile(x) ⇒ Weapon(x) .
 Then we need to find all the facts that unify with Missile(x); in a suitably indexed knowledge base, this can
be done in constant time per fact. Now consider a rule such as
Missile(x) ∧ Owns(Nono, x) ⇒ Sells(West, x, Nono)

Canara Engineering College Module - 4 29

V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

Canara Engineering College Module - 4 30

V SEMESTER ARTIFICIAL INTELLIGENCE(BCS515B)

Canara Engineering College Module - 4 31