Unit 4

UNIT 4
Knowledge Representation
MISSION VISION CORE VALUES

CHRIST is a nurturing ground for an Excellence and Service Faith in God | Moral Uprightness
individual’s holistic development to make Love of Fellow Beings
effective contribution to the society in a Social Responsibility | Pursuit of
CHRIST
Deemed to be University
Syllabus
KNOWLEDGE REPRESENTATION
First order logic – representation revisited – Syntax and
semantics for first order logic – Using first order logic –
Knowledge engineering in first order logic - Inference in
First order logic – propositional versus first order logic –
unification and lifting – forward chaining – backward
chaining - Resolution - Knowledge representation -
Ontological Engineering - Categories and objects.
Excellence and Service

CHRIST
Knowledge Base
● An intelligent agent needs knowledge about the

real world for taking decisions and reasoning to act
efficiently.
● Knowledge base consist of sentences.
● These sentences are expressed using
○ Syntax
○ Semantics

CHRIST
Knowledge Base
● Syntax - Specify the sentences that are well

formed.
Example: x+y=4
x4y+=
● Semantics – Define the meaning of the sentence.
It specifies the truth of each sentence
Example: x+y=4 is true if x=2 and y=2
● Model is used in place of possible world. It is a
mathematical abstraction, which simply fixes the
truth or falsehood Excellence
of every and Service
relevant sentence.
CHRIST
Logic
● It is the proof of validation behind any reason

provided.
○ Propositional Logic (PL)
○ First Order Logic (FOL)

CHRIST
Proposition Logic (PL)
● It is the simplest form of logic.

● All the statements are made by propositions.
● A proposition is a declarative statement which is
either true or false.
● Symbolic variables such as A, B, C, P, Q, R, etc.
can be used to represent the logic.
● Propositions can be either true or false, but it
cannot be both.
Example:
● 5 is a prime number
● 3+4= 8 Excellence and Service
CHRIST
Propositional Logic - Syntax
● The syntax of propositional logic defines the

allowable sentences.
● There are two types of Sentences (Propositions):
1.Atomic Propositions or Atomic
Sentences
2.Compound propositions or Compound

Sentences

CHRIST
Atomic Sentences:
● Atomic propositions are the simple propositions.
● It consists of a single proposition symbol.
Example: 2+2 = 4 - True
The sun is cold - False

CHRIST
Compound Sentences:
● Constructed by combining simpler or atomic
propositions, using parentheses and logical
connectives.
● Example - "It is raining today, and street is wet."
"Ankit is a doctor, and his clinic is in
Mumbai."

CHRIST
Compound Sentences:
There are five connectives
○ Negation (~) - NOT
○ Conjunction (∧) - AND
○ Disjunction (V) - OR
○ Implication (🡪) - IMPLIES
○ Biconditional (⬄) - IF AND ONLY IF

CHRIST
Propositional Logic - Semantics
● It defines the rules for determining the truth of a

sentence with respect to a particular model.
● It specifies how to compute the truth of atomic
sentences formed with five connectives.
● Atomic Sentences - True is true in every model
and False is false.
● Complex Sentences - Five Rules
○ ~P is true iff P is false
○ P∧Q is true iff P and Q are true
○ PVQ is true iff either
ExcellenceP orService
and Q is true
CHRIST
Propositional Logic - Semantics
○ P🡪Q is true iff unless P is true and Q is false

○ P⬄Q is true iff P and Q are both true or false
● Truth Table - The rules can also be expressed
with truth tables.
● A proposition formula which is always true is called
Tautology.
● A proposition formula which is always false is
called Contradiction.

CHRIST
Propositional Logic - Drawbacks
● ALL, some, or none with propositional logic.

○ Example: All the girls are intelligent.
Some apples are sweet.
● It has limited expressive power.
● Statements cannot be described in terms of their
properties or logical relationships.
● In propositional logic, we can only represent the
facts, which are either true or false.

CHRIST
First Order Logic (FOL)
● First-order logic is another way of knowledge

representation in artificial intelligence.
● It is an extension to propositional logic.
● It is sufficiently expressive to represent the natural
language statements in a concise way.
● First-order logic is also known as Predicate logic or
First-order predicate logic.

CHRIST
First Order Logic
● It is much more expensive than PL.

● It is built around objects and relations.
○ Objects (noun or noun phrases) : A, B, people,
numbers etc. [Subject]
○ Relations (verb and verb phrases): It can be
unary relation or properties such as: red, round,
prime, or n-any relation such as: the sister of,
brother of, part of etc. [Predicate]
○ Function (return object for the given relation):
Father of, bestExcellence
friend andof,Service
etc.
CHRIST
Difference between PL and FOL
Langua Ontological Epistemological

ge Commitment Commitment (What
(What exists in an agent believe
the world) about facts)
PL Facts true/false/unknown
FOL Facts, objects, true/false/unknown
relations

CHRIST
Syntax and Semantics of FOL
Model - Models of FOL have objects.

○ The domain of a model is the set of objects and
it should not be empty
○ A tuple is a collection of objects arranged in a
fixed order.

CHRIST
Syntax and Semantics of FOL - Symbols

and Interpretation
Symbols - Names begin with uppercase letters
● Constant symbols - objects
Ex: Richard, John
● Predicate symbols - Relations
Ex: Brother , OnHead, Person, King, Crown
● Function symbols - Functions
Ex: Father of, Brother of

CHRIST
Statements in FOL
FOL statements can be divided into 2 Parts:

1. Subject - Subject is the main part of the statement
2. Predicate - A predicate can be defined as a relation,
which binds two objects together in a statement.
Example: "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.

CHRIST
Atomic Sentences
● It is the most basic sentence of first-order logic.

● These sentences are formed from a predicate symbol
followed by a parenthesis with a sequence of terms.
● Predicate (term1, term2, ......, term n).
Examples:
1. “Ravi and Ajay are brothers” can be represented in FOL
as
Brothers(Ravi, Ajay)
2. “Jack is a dog” can be represented in FOL as
Dog(Jack)
CHRIST
Compound Sentences
● Complex sentences are made by combining atomic

sentences using connectives.
● Example: Brother (Richard,John) ∧ Brother
(John,Richard)

CHRIST
Quantifiers in FOL
● It is used to express the properties of entire collection of

objects.
● It specifies the quantity of specimen in the universe of
disclosure.
● There are two types of quantifier:
1. Universal Quantifier (for all, everyone, everything)
2. Existential quantifier (for some, at least one).

CHRIST
Universal Quantifier (∀)
● It 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 ∀.
● In universal quantifier we use implication "→".
● ∀x is read as: For all x OR For each x OR For every x.

CHRIST
Universal Quantifier (∀)
Example: All man drink coffee

Let x be a variable which refers to man, the
representation of the above sentence in FOL is as
shown below:
∀x man(x) → drink(x, coffee)
It will be read as: For all x where x is a man who drinks
coffee.
All Kings are Persons
Let x be a variable which refers to King, the
representation of the above sentence in FOL is as
shown below: Excellence and Service
CHRIST
Existential Quantifier (∃)
● It express that the statement within its scope is true for at
least one instance of something.
● It is denoted by the logical operator ∃.
● In Existential quantifier we always use AND or Conjunction
symbol (Ʌ).
● ∃x or ∃(x) will be read as: There exists a 'x’ OR For some 'x’
OR For at least one ‘x’.
Example: Some boys are intelligent
∃x: boys(x) ∧ intelligent(x)
It will be read as: There are some x, where x is a boy who is
intelligent Excellence and Service
CHRIST
Nested Quantifiers
● Compound sentences can be expressed using multiple
quantifiers.
Properties of Quantifiers
1. In universal quantifier, ∀x∀y is similar to ∀y∀x.
2. In Existential quantifier, ∃x∃y is similar to ∃y∃x.
3. ∃x∀y is not similar to ∀y∃x.

CHRIST
Connections between ∀ and ∃
● ∀ and ∃ are connected through negation.

Example:
○ Everyone likes ice cream
∀ x Likes(x, IceCream)
○ There does not exist someone who dislikes them
¬∃ x ¬Likes(x, IceCream)
∀ x Likes(x, IceCream) is equivalent to ¬∃ x

¬Likes(x, IceCream)
27
CHRIST
Connections between ∀ and ∃
Example:
○ Everyone dislikes Junks

∀ x ¬Likes(x, Junks )
○ There does not exist someone who likes them

¬∃ x Likes(x, Junks)
∀ x ¬Likes(x, Junks ) is equivalent to ¬∃ x Likes(x,

Junks)
28
CHRIST
Syntax of FOL

CHRIST
Examples Of FOL
All birds fly
∀x bird(x) →
fly(x)

CHRIST
Examples Of FOL
Every man respects his parent
∀x man(x) → respects(x,
Parent)

CHRIST
Examples Of FOL
Every Gardener likes the Sun
∀x Gardener(x) → likes(x,
Sun)

CHRIST
Examples Of FOL
Denny is not tall
~tall(Denny)

CHRIST
Examples Of FOL
All Pompeians are Romans
∀x Pompeians(x) →
Romans(x)

CHRIST
Examples Of FOL
Picasso was a Painter
Painter(Picasso)

CHRIST
Examples Of FOL
Every Elephant is Grey
∀x Elephant(x) → Grey(x)

CHRIST
Examples Of FOL
Fenny is a Professor
Professor(Fenny)

CHRIST
Examples Of FOL
Lucy criticize John
Criticize(Lucy,John)

CHRIST
Examples Of FOL
Some boys play cricket
∃x boys(x) Ʌ play (x,

Cricket)

CHRIST
Examples Of FOL
There exists a White Alligator
∃x Alligator(x) Ʌ White (x)

CHRIST
Examples Of FOL
There exists some bird that doesn’t fly
∃x bird(x) Ʌ ~fly (x)

CHRIST
Examples Of FOL
Not all students like both Mathematics and Science
~∀x [student (x) → like(x, Mathematics) Ʌ

like(x, Science) ]

CHRIST
Examples Of FOL
Lipton is a Tea
Tea (Lipton)

CHRIST
Examples Of FOL
Every man is mortal
∀x man(x) → mortal(x)

CHRIST
Examples Of FOL
All girls are beautiful
∀x girls(x) → beautiful(x)

CHRIST
Examples Of FOL
All that glitters are not gold
∀x glitters(x) → ~gold(x)

CHRIST
Examples Of FOL
Some boys are obedient
∃x boys(x) Ʌ obedient(x)

CHRIST
Examples Of FOL
Some cows are black and some cows are white
∃x cows(x) Ʌ black(x) Ʌ white(x)

CHRIST
Examples Of FOL
Everyone likes Ice cream
∀x likes(x, Ice Cream)

CHRIST
Examples Of FOL
Brothers are siblings
∀x ∀y Brothers(x, y) → Siblings(x, y)

CHRIST
Examples Of FOL
Everybody loves somebody
∀x ∃y Loves(x, y)

CHRIST
Examples Of FOL
There is someone who is loved by everyone
∃y ∀x Loves(x, y)

CHRIST
Examples Of FOL
King John has a crown on his head
∃x Crown(x) Ʌ Onhead(x, John)

CHRIST
Examples Of FOL
Everyone dislikes parsnips

∀x ~Likes(x, Parsnips) or ~∃x Likes(x, Parsnips)
None of my friends are perfect
∀x F(x) → ~P(x) or ~ ∃x F(x) Ʌ P(x)
Every house is a physical object
∀x (house(x) → physical object(x))
Some physical objects are houses
∃x (physical object(x) ∧ house(x))
Every house has an owner
∀x(house(x) → ∃y.owns(y, x)),
CHRIST
Examples Of FOL
Everybody owns a house

∀x ∃y (owns(x, y) ∧ house(y))
Sue owns a house
∃x (owns(Sue, x) ∧ house(x))
Somebody does not own a house
∃x ∀y (owns(x, y) → ¬house(y))
All Kings who are Greedy are Evil
∀x King(x) ∧ Greedy (x) → Evil(x)

CHRIST
Examples of FOL Deemed to be University
John likes all kind of food.

∀x: food(x) → likes(john, x)
Apple and vegetable are food
Food(Apple) ∧ Food(Vegetable)
Anything anyone eats and not killed is food.
∀x ∀y eats(x,y) ∧ ¬Killed(x)→Food(y)
Anil eats peanuts and still alive
eats(Anil,peanuts)∧Alive(Anil)
Harry eats everything that Anil eats.
∀x: eats(Anil,x)→eats(Harry,x)
John likes peanuts Likes(John,Peanuts)
CHRIST
Syllabus
Ontological Engineering - Categories and objects

CHRIST
Knowledge Engineering in FOL
● The process of constructing a knowledge-base in

first-order logic is called as knowledge- engineering.
● Knowledge engineer investigates a specific domain,
learn the important concepts regarding that domain,
and creates the formal representation of the objects
and relations in that domain.

CHRIST
Knowledge Engineering in FOL -

Steps
● Identify the tasks
● Assemble the relevant Knowledge
● Decide on Vocabulary
● Encode general Knowledge about the domain
● Encode a description of the problem instance
● Pose queries to the inference procedure and get
answers
● Debug the knowledge base

CHRIST

CHRIST
Knowledge Engineering Process
Identify the task:

● A knowledge engineer should be able to identify the
task by asking a few questions like:
○ Do the knowledge base will support?
○ What kinds of facts will be available for each
specific problem?
The task will identify the knowledge requirement
needed to connect the problem instance with the
answers.

CHRIST
Assemble the relevant knowledge:
● A knowledge engineer should be an expert in the

domain.
● If not, he should work with the real experts to extract
their knowledge.
● This concept is known as Knowledge Acquisition.

CHRIST
Decide on a vocabulary of constants, predicates,

and functions:
● Translating important domain-level concepts into
logical level concepts.
● Here, the knowledge engineer asks questions
like:
○ What are the elements which should be
represented as objects?
○ What functions should be chosen?
○ After satisfyingExcellence
all theandchoices,
Service
the vocabulary is
CHRIST
Encode general knowledge about the domain:
● In this step, the knowledge engineer pen down the

axioms/rules for all the chosen vocabulary terms.
Encode description of the specific problem
instance:
● We write the simple atomic sentences for the
selected vocabulary terms.
● We encode the chosen problem instances.

CHRIST
Raise queries to the inference procedure and get

answers:
● It is the testing step.
● We apply the inference procedure on those axioms
and problem-specific facts which we want to know.
Debug the knowledge base:
● It is the last step of the knowledge engineering
process where the knowledge engineer debugs all
the errors.
CHRIST
Inferences in FOL
● Inferences in FOL is used to create new facts or

sentences from the existing sentences.
● Inference rules for Quantifiers:
○ Universal Instantiation (Substitution)
○ Existential Instantiation

CHRIST
Inferences in FOL
Universal Instantiation:
● Any sentence can be inferred by substituting a
ground term for the variable
● Ground Term - Term without variable
● Rule - Let denote
the result of applying the substitutions θ to
sentence α

CHRIST
Inferences in FOL
Universal Instantiation: Example

All Greedy Kings are Evil
From the above statement we can infer the

following:
{x/John}

CHRIST
Inferences in FOL
Existential Instantiation:
● Variable is replaced by a single new constant
symbol
● Rule - For any sentence α, variable v and constant
symbol k (that does not appear elsewhere in the
knowledge base)
● The new constant symbol used is known as Skolem

CHRIST
Inferences in FOL
Existential Instantiation - Example
● C1 must not appear elsewhere in knowledge base.

● If many rules have the same variable x and this
variable differs from one rule to another.
● So to differentiate, we create new variables that
represent a new Inference.
CHRIST
Inferences in FOL
Reduction to Propositional Inference

● Using the inference rules, it is possible to reduce
first-order logic inference to propositional
inference.
● A universally quantified sentence can be replaced
by the set of all possible instantiations.

CHRIST
Inferences in FOL
● Suppose our KB contains the Sentences.
● Apply UI using { x/John } and {X/Richard}
● Discard the Universal Quantified Sentence.

● If there is a substitutions that satisfies the premises in
the KB, then I can add the conclusions into the KB
CHRIST
Inferences – Generalised Modus Ponens
● For atomic sentences pi, pi', q, where there is a

substitution θ such that SUBST (θ, pi',) = SUBST(θ, pi),
for all i
Example:
p1' is king(John) p1 is king(x)
p2' is Greedy(y) p2 is Greedy(x)
θ is {x/John, y/John} q is evil(x)
SUBST(θ,q) is Evil(John)Excellence and Service
CHRIST
Syllabus

CHRIST
Unification
● It is the process of finding substitutions that make

different logical expressions look identical.
● The UNIFY algorithm takes two sentences and returns a
unifier for them if one exists.
UNIFY(p,q)=Θ where SUBST(Θ,p) =
SUBST(Θ,q)
● If no Unifier exists then the Unification algorithm
returns FAILURE. Θ=
Example: {x/John}
p = knows(Richard, x) Excellence and Service

q = knows(Richard, John)
CHRIST
Rules for Unification
1. Predicate symbol must be same, atoms or expressions

with different predicate symbols can never be Unified.
2. Number of arguments in both the expressions must be
identical.
3. Unification will fail if there are two similar variables
present in the same expression.

CHRIST
Unification
Example:
p = knows(John, x) q = knows(John,ΘJane)
=
p = knows(John, x) {x/Jane}
Θ = {x/Mary,
q = knows(y, Mary)
p = knows(John, x) y/John}
q = knows(y,ΘMother(y))
= {y/John,
p = knows(John, x) q = knows(x, Mary)
x/Mother(John)}
fail
● This problem can be avoided by standardizing apart
one of the two sentences being unified (i.e renaming
its variables to avoid name clashes)
p=knows(John,x) q= knows(x17, Mary)

CHRIST
Unification
● One more complication is there can be more than

one unifiers. Θ = {y/John, x/z}
p = knows(John, x) or {x/John,
q = knows(y, z) y/John,
z/John}
● The Most General Unifier (MGU) is the general

unifier with fewer restrictions on the values of the
variables.
Θ = {y/John, x/z} is selected
CHRIST
Syllabus

CHRIST
Forward Chaining
● It is a simple algorithm.
● It starts from the known facts, it triggers all the
rules whose premises are satisfied adding their
conclusions to the known facts.
● The process repeats until the query is answered or
new facts are added.
Known facts → Goal

CHRIST
Forward Chaining - Steps
1. Represent the facts as first-order definite clauses.

2. Use Forward Chaining Algorithm

Forward Chaining - First Order CHRIST
Definite Clauses
● A definite clause is either atomic or is an implication
whose antecedent is a conjunction of positive literals
and whose consequent is a single positive literal.
● Literal is any predicate applied to a set of terms.
● First order literals can include variables and they are
assumed to be universally quantified.
Example:
King(John)
Greedy(y)
King(x) ∧ Greedy (x) → Evil (x)
CHRIST
Example - As per the law, it is a crime for an

American to sell weapons to hostile nations.
Country A, an enemy of America, has some missiles,
and all the missiles were sold to it by Robert, who is
an American citizen. Prove that "Robert is criminal."
Solution: Step 1 - Identify the facts
● It is a crime for an American to sell weapons to hostile
nations.
● Country A has some missiles.
● All of the missiles were sold to country A by Robert.
● Missiles are weapons.
● Enemy of America is known as hostile.
● Country A is an enemy of America.
● Robert is American Excellence and Service
CHRIST
Example
Step 2 - Conversion of facts into First Order Definite

Clauses
nations. (Let's say p, q, and r are variables)
American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧
hostile(r) → Criminal(p) .....(1)
∃p Owns(A, p) ∧ Missile(p)
It can be written in two definite clauses by using
Existential Instantiation, introducing new Constant T1.
CHRIST
Example
● All of the missiles were sold to country A by

Robert.
∀p Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A)
or
Missiles(p) ∧ Owns (A, p) → Sells (Robert,
p, A) ......(4)
Missile(p) → Weapons (p) .......(5)
Enemy(p, America) →Hostile(p) ........
CHRIST
Example

Enemy (A, America) .........(7)
● Robert is American
American(Robert). ..........(8)

CHRIST
Example - Step 2: Conversion of facts

into First Order Definite Clauses
1. American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧

hostile(r) → Criminal(p)
2. Owns(A, T1)
3. Missile(T1)
4. Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A)
5. Missile(p) → Weapons (p)
6. Enemy(p, America) →Hostile(p)
7. Enemy (A, America)
8. American(Robert).

CHRIST
Example
Step 3: Use Forward Chaining Algorithm

Step 3.1: Start with known facts and choose the
sentences which do not have implications

CHRIST
Example
Step 3.2: Select the facts which infer from

available facts and with satisfied premises
Rule-(1) does not satisfy premises, so it will not be
added in the first iteration. [American (p) ∧
weapon(q) ∧ sells (p, q, r) ∧ hostile(r) →
Criminal(p)]
Rule-(2) and (3) are already added. [Owns(A, T1),
Missile(T1)]

CHRIST
Example
Rule-(4) satisfy with the substitution {p/T1}, so

Sells (Robert, T1, A) is added, which infers from the
conjunction of Rule (2) and (3).
Missiles(p) ∧ Owns (A, p) → Sells (Robert, p,
A)

CHRIST
Example
Rule-(5) is satisfied with the substitution(p/T1), and

Weapon(T1) is added
Missile(p) → Weapons (p)

CHRIST
Example
Rule-(6) is satisfied with the substitution(p/A), so

Hostile(A) is added
Enemy(p, America) →Hostile(p)
Rule-(7) and Rule(8) are already added

Enemy (A, America), American(Robert)
CHRIST
Example
Step 3.3: Rule-(1) is satisfied with the substitution

{p/Robert, q/T1, r/A}, Criminal(Robert) can be added,
which infers all the available facts
American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧
hostile(r) → Criminal(p)

CHRIST
Syllabus

CHRIST
Backward Chaining
● It works backward from the goal, chaining through rules

to find known facts that support the proof
Goal → known facts
● Example: As per the law, it is a crime for an American
to sell weapons to hostile nations. Country A, an enemy
of America, has some missiles, and all the missiles were
sold to it by Robert, who is an American citizen. Prove
that "Robert is criminal."

CHRIST
Example - As per the law, it is a crime for an

American to sell weapons to hostile nations.
Country A, an enemy of America, has some missiles,
and all the missiles were sold to it by Robert, who is
an American citizen. Prove that "Robert is criminal."
Solution: Step 1 - Identify the facts
nations.
● All of the missiles were sold to country A by Robert.
● Robert is American Excellence and Service
CHRIST
1. American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) → Criminal(p)
2. Owns(A, T1)
3. Missile(T1)
Criminal(Robert)
97
CHRIST
2. Owns(A, T1)
3. Missile(T1)
Criminal(Robert)
1: { p / Robert }
American(Robert) Weapon(q) Sells(Robert,q,r) Hostile(r)
{ }
98
CHRIST
2. Owns(A, T1)
3. Missile(T1)
Criminal(Robert)
1: { p / Robert }
American(Robert) Weapon(q) Sells(Robert,q,r) Hostile(r)
8: { }
99
CHRIST
2. Owns(A, T1)
3. Missile(T1)
Criminal(Robert)
Criminal(West)
1: { p / Robert }
American(Robert)
American(West) Weapon(q)
Weapon(y) Sells(Robert,q,r)
Sells(West,y,z) Hostile(z)
Hostile(r)
8: { }
5:{p/q}
Missile(q)
100
CHRIST
2. Owns(A, T1)
3. Missile(T1)
Criminal(Robert)
Criminal(West)
1: { p / Robert }
American(Robert)
American(West) Weapon(T1)
Weapon(y) Sells(Robert,T1,r)
Sells(West,M1,z)
Sells(West,y,z) Hostile(z)
Hostile(r)
8: { }
5:{p/q}
Missile(M1)
Missile(T1)
3: { q / T1 }
101
CHRIST
2. Owns(A, T1)
3. Missile(T1)
Criminal(Robert)
Criminal(West)
1: { p / Robert }
American(Robert)
American(West) Weapon(T1)
Weapon(y) Sells(Robert,T1,A)
Sells(West,M1,z)
Sells(West,y,z) Hostile(A)
Hostile(z)
8: { }
5:{p/q}
Missile(M1)
Missile(T1) 4 : { p / T1}
{r/A}
3: { q / T1 }
Missile(T1) Owns(A,T1)
102
CHRIST
2. Owns(A, T1)
3. Missile(T1)
Criminal(Robert)
Criminal(West)
1: { p / Robert }
American(Robert)
Sells(West,M1,z)
Sells(West,y,z) Hostile(Nono)
Hostile(A)
Hostile(z)
8: { }
5:{p/q}
4 : { p / T1}
Missile(M1)
Missile(T1)
{r/A}
3: { q / T1 }
Missile(M1)
Missile(T1) Owns(Nano,M1)
Owns(A,T1)
3: { } 2: { }
103
CHRIST
2. Owns(A, T1)
3. Missile(T1)
Criminal(Robert)
Criminal(West)
1: { p / Robert }
American(Robert)
Sells(West,M1,z)
Hostile(A)
Hostile(z)
8: { } 5:{p/q} 6 : { p / A}
Missile(M1)
Missile(T1)
4 : { p / T1}
Enemy(A, America)
3: { q / T1 } {r/A}
Missile(M1)
Owns(A,T1)
3: { } 2: { }
104
CHRIST
2. Owns(A, T1)
3. Missile(T1)
Criminal(Robert)
Criminal(West)
1: { p / Robert }
American(Robert)
Sells(West,M1,z)
Hostile(A)
Hostile(z)
8: { } 5:{p/q} 6 : { p / A}
Missile(M1)
Missile(T1)
4 : { p / T1}
Enemy(A, America)
3: { q / T1 } {r/A}
7: { }
Missile(M1)
Owns(A,T1)
3: { } 2: { }
105
CHRIST
Resolution
● It proves by Contradiction
● The sentences must be Conjunctive Normal Form
● It is a single inference rule, that yields a complete
inference algorithm.
● Resolution can resolve two clauses if they contain
complementary literals, which are assumed to be
standardized apart so that they share no variables.

CHRIST
Steps For Resolution
1. Conversion of facts into FOL
2. Convert FOL to CNF

○ Eliminate all implication (→) and rewrite
○ Move negation (¬)inwards and rewrite
3. Negate the Statement to be Proved
4. Draw Resolution Graph

CHRIST
Resolution - Example
As per the law, it is a crime for an American to sell

weapons to hostile nations. Country A, an enemy of
America, has some missiles, and all the missiles
were sold to it by Robert, who is an American
citizen. Prove that "Robert is criminal."
Step 1 - Conversion of facts into FOL
● American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) →
Criminal(p)
● Owns(A, T1)
● Missile(T1)
● Missiles(p) ∧ Owns (A, p) → Sells (Robert, p, A)
● Missile(p) → Weapons (p)
● Enemy(p, America) →Hostile(p)
● Enemy (A, America)
● American(Robert). Excellence and Service
CHRIST
Step 2 - Convert FOL to CNF

1. American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) →
Criminal(p)
¬[American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r)]
∨ Criminal(p)
¬American (p) ∨ ¬weapon(q) ∨ ¬sells (p, q, r) ∨
¬hostile(r) ∨ Criminal(p)
2. Owns(A, T1)
3. Missile(T1) Excellence and Service
CHRIST

4. Missile(p) ∧ Owns (A, p) → Sells (Robert, p, A)
¬ [Missile(p) ∧ Owns (A, p)] ∨ Sells (Robert, p, A)
¬ Missile(p) ∨ ¬ Owns (A, p) ∨ Sells (Robert, p, A)

¬ Missile(p) ∨ Weapons (p)

CHRIST

¬Enemy(p, America) ∨ Hostile(p)

CHRIST
Step 3 - Negate the Statement to be Proved
¬Criminal (Robert)

CHRIST
Step 4 – Draw the Resolution Graph

1. ¬American (p) ∨ ¬weapon(q) ∨ ¬sells (p, q, r) ∨
¬hostile(r) ∨ Criminal(p)
2. Owns(A, T1)
3. Missile(T1)
4. ¬ Missile(p) ∨ ¬ Owns (A, p) ∨ Sells (Robert, p, A)
5. ¬ Missile(p) ∨ Weapons (p)
6. ¬Enemy(p, America) ∨ Hostile(p)
8. American(Robert) Excellence and Service
CHRIST
Step 4 - Resolution Proof
¬American (p) ∨ ¬weapon(q) ∨ ¬sells (p, q, r) ∨ ¬Criminal
¬hostile(r) ∨ Criminal(p) (Robert)
1: Θ =
American ¬American (Robert) ∨ ¬weapon(q){p/Robert}
∨ ¬sells
(Robert) (Robert, q, r) ∨ ¬hostile(r)
8: Θ = { }
¬ Missile(p) ∨ ¬Weapon(q) ∨ ¬sells (Robert, q, r) ∨
Weapon (p) ¬hostile(r)
5: Θ = {
¬ Missile(p) ∨p/q } (Robert, q, r) ∨
¬sells
¬hostile(r)

CHRIST
Step 4 - Resolution Proof
¬American (p) ∨ ¬weapon(q) ∨ ¬sells (p, q, r) ∨ ¬Criminal
¬hostile(r) ∨ Criminal(p) (Robert)
1: Θ =
American ¬American (Robert) ∨ ¬weapon(q){p/Robert}
∨ ¬sells
(Robert) (Robert, q, r) ∨ ¬hostile(r)
8: Θ = { }
¬ Missile(p) ∨ ¬Weapon(q) ∨ ¬sells (Robert, q, r) ∨
Weapon (p) ¬hostile(r)
5: Θ = {
¬ Missile(q) ∨p/q } (Robert, q, r) ∨
¬sells
Missile(T1)
¬hostile(r)
3: Θ = {
¬ Missiles(p) ∨ ¬ Owns (A, p) ∨ Sells ¬sells
q/T1 } (Robert, T1, r) ∨
(Robert, p, A) ¬hostile(r)

CHRIST
¬ Missiles(p) ∨ ¬ Owns (A, p) ∨ Sells ¬sells (Robert, T1, r) ∨
(Robert, p, A) ¬hostile(r)
4: Θ = { p/T1,
r/AOwns
¬ Missiles(T1) ∨ ¬ } (A, T1) ∨
Missile(T1)
¬hostile(A)
3: Θ = { }
Owns(A, T1)
¬ Owns (A, T1) ∨ ¬hostile(A)
2: Θ = { }
¬Enemy(p, America) ∨
Hostile(p) ¬hostile(A)
6: Θ = {p/A }
Enemy(A, America) ¬Enemy(A, America)
7: Θ = { }

CHRIST
Syllabus

CHRIST
Knowledge representation - Ontological

Engineering
● Representing the general concepts like Events, Time,
Physical objects, Belief are called Ontological
Engineering.
● The need of ontological engineering is to give the
Overall Idea of the Domain using the abstract concept.
● This helps the agent to learn about the environment
and reason about each and every actions.
● The main objective is to create the more generic and
the flexible representation.
CHRIST
Ontological Engineering – General

Framework
● The general framework of concepts is called Upper

Ontology
● The generic concepts are at the Top and the more
specific concepts are at the Bottom.
Upper ontology of the World

CHRIST
General Purpose Ontologies -

Characteristics
1. The general purpose ontologies should be applicable in
more or less to any specific domain and the user can
define the additional axioms.
2. All the general item must be unified that can help the
agent for reasoning and problem solving.

CHRIST
Categories and Objects
● The organisations of objects into categories is a

important part of Knowledge Representation.
● Reasoning happens at the level of categories.
● Categories play a important role in prediction.
● There are two choices for representing categories
in FOL
○ Predicates
○ Objects

CHRIST
● Categories organise and simplify the KB through
Inheritance.
● Example: All Foods are edible
Fruit is a subclass of food
Apple is a subclass of Fruit
Inference:Apple is edible

CHRIST
● Some facts types are listed below:

○ An object is a member of category.
Apple ∈ Fruit
● A category is a subclass of another category.
Fruit ⊂ Food
● All members of a category have some
properties
(x ∈ Apple) ⇒ Red(x)
● Members of a category can be recognized by
some properties
CHRIST
● A category as a whole has some properties
Dogs ∈ Domesticatedspecies
● Disjoint Relation: Two or more categories are disjoint if
they have no members in Common.
Disjoint({Animals, Vegetables})

CHRIST
Categories and Objects - Physical

Composition
● One object can be part of another object - Partof
Relation.
Example:

CHRIST
Categories and Objects - Measurements
● Some Objects have properties such as height, mass,

cost etc.
● The values that we assign for these properties are
called the measures.
Example: length of a line segment
It is represented by a units function which takes
number as arguments:
● Conversion between units is done by equating multiples

of one unit with another
d ∈ Days -> Duration(d) ⇒ Hours(24)

Unit 4 - AI

Uploaded by

Copyright:

Available Formats

Unit 4 - AI

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 4 - AI

Uploaded by

Copyright:

Available Formats

MISSION VISION CORE VALUES

Excellence and Service

● An intelligent agent needs knowledge about the

Excellence and Service

● Syntax - Specify the sentences that are well

● It is the proof of validation behind any reason

Excellence and Service

Proposition Logic (PL)

● It is the simplest form of logic.

● The syntax of propositional logic defines the

2.Compound propositions or Compound

Excellence and Service

Excellence and Service

Excellence and Service

Excellence and Service

● It defines the rules for determining the truth of a

○ P🡪Q is true iff unless P is true and Q is false

Excellence and Service

● ALL, some, or none with propositional logic.

Excellence and Service

● First-order logic is another way of knowledge

Excellence and Service

● It is much more expensive than PL.

Langua Ontological Epistemological

Excellence and Service

Syntax and Semantics of FOL

Model - Models of FOL have objects.

Excellence and Service

Syntax and Semantics of FOL - Symbols

Excellence and Service

FOL statements can be divided into 2 Parts:

Excellence and Service

● It is the most basic sentence of first-order logic.

● Complex sentences are made by combining atomic

Excellence and Service

● It is used to express the properties of entire collection of

Excellence and Service

● It specifies that the statement within its range is true for

Excellence and Service

Example: All man drink coffee

Excellence and Service

Connections between ∀ and ∃

● ∀ and ∃ are connected through negation.

○ Everyone likes ice cream

○ There does not exist someone who dislikes them

∀ x Likes(x, IceCream) is equivalent to ¬∃ x

Connections between ∀ and ∃

○ Everyone dislikes Junks

○ There does not exist someone who likes them

∀ x ¬Likes(x, Junks ) is equivalent to ¬∃ x Likes(x,

Excellence and Service

All birds fly

Excellence and Service

Every man respects his parent

Excellence and Service

Every Gardener likes the Sun

Excellence and Service

Denny is not tall

Excellence and Service