Unit III Knowledge Representation in AI K.Sundar,AP/CSE,VEC

K.Sundar,AP/CSE,VEC presentation on Knowledge Representation in AI

1. 19CS308T: Artificial Intelligence
UNIT-III
KNOWLEDGE REPRESENTATION
Faculty:Mr.K.Sundar

2. Syllabus
•FirstOrderPredicateLogic–Prolog
Programming–Unification–Forward
Chaining-Backward Chaining –
Resolution–KnowledgeRepresentation
–OntologicalEngineering-Categories
andObjects–Events–MentalEvents
andMentalObjects–Reasoning
SystemsforCategories–Reasoningwith
DefaultInformation.
•Casestudy:Sets,KingDomain,
Mammal,Hostilenationsetc.

3. FIRST ORDER
PREDICATE
CALCULUS
1
2

4. KNOWLEDGE REPRESENTATION
□Symboliclogic
□Powerofrepresentation
□Formal language:syntax,semantics
□Conceptualization+representationina
language
□Inferencerules

5. PROPOSITIONAL
LOGIC
⚫Repesented in Formal language
Syntax
□A well-formed formula(wff) in propositional
logic is:
(1)An atom is a wff
(2)If P is a wff, then ~P is a wff.
(3)If P and Q are wffs then P∧Q, P∨Q, P→Q &
P↔Q are wffs.
(4)The set of all wffs can be generated by
repeatedly applying rules (1)..(3).
3
4

6. PROPOSITIONAL LOGIC: SYNTAX
□Propositional logic is the simplest logic
□The proposition symbols S
1
, S
2
etc are sentences
⚫If S is a sentence, ¬S is a sentence (negation)
⚫If S
1
and S
2
are sentences, S
1
∧ S
2
is a sentence (conjunction)
⚫If S
1
and S
2
are sentences, S
1
∨ S
2
is a sentence (disjunction)
⚫If S
1
and S
2
are sentences, S
1
⇒ S
2
is a sentence (implication)
⚫If S
1
and S
2
are sentences, S
1
⇔ S
2
is a sentence (biconditional)

7. PROPOSITIONAL LOGIC:SEMANTICS
Each model specifiestrue/falseforeach propositionsymbol
E.g.
With these symbols, 8 possible models, can be enumerated
automatically.
Rules for evaluating truth with respect to a model m:
¬S is true iffS is false
S
1
∧ S
2
is true iffS
1
is true andS
2
is true S
1
∨
S
2
is true iffS
1
is true or S
2
is true
S
1
⇒ S
2
is true iffS
1
is false orS
2
is true
i.e., is false iff S
1
is true and S
2
is false
1
S
1
⇔ S
2
is true iffS ⇒S
2
is true and
2
5
6

8. TRUTHTABLESFORCONNECTIVES

9. LOGICALEQUIVALENCE
•□Two sentences are logically equivalent} iff true in same models
•: α ≡ ß iff α╞ β and β╞ α

10. VALIDITY AND SATISFIABILITY
7
A sentence is valid if it is true in all
models,
e.g., True, A ∨¬A, A ⇒ A,(A ∧ (A ⇒
B)) ⇒ B
Validity is connected to inference via the
Deduction Theorem:
KB ╞ α if and only if (KB ⇒ α) is valid
A sentence is satisfiable if it is true in some model
e.g., A∨ B, C
A sentence is unsatisfiable if it is true in no models
e.g., A∧¬A
Satisfiability is connected to inference via the
following:
KB ╞ α if and only if (KB ∧¬α) is unsatisfiable
8

11. INFERENCERULES
□ModusPonens
□Chainrule
□ANDintroduction
□Transposition

12. 9
Soundness of resolution inference rule:
l
i
∨… ∨ l
k
,m
1
∨ … ∨ m
n
l
i
∨ … ∨ l
i-1
∨ l
i+1
∨ … ∨ l
k
∨ m
1
∨ … ∨ m
j-1
∨
m
j+1
∨... ∨ m
n
li, mi –contradictory
10
RESOLUTION

13. CNF,DNF
□Conjunctive normal form (CNF)
F
1
… ∧F
n
,∧F
i
, i=1,n
□Disjunctive normal form (DNF)
F
1
∨ … ∨F
n
, F
i
, i=1,n
11
CONVERSION TO CLAUSE FORM
1.Convert all the propositions of KB to clause form
(S).
2.Negate α and convert it to clause form. Add it to S.
3.Repeat until either a contradiction is found or no
progress can be made.
a.Select two clauses (α ∨ ¬P) and ( γ ∨ P).
b.Add the resolvent (α ∨ γ) to S.
12

14. WUMPUSWORLD
13
❖Wemustexploreacaveconsistingofrooms
connectedbypassageways.
❖Lurkingsomewhereinthecaveisabeast(the
wumpus)thateatsanyonewhoentershisroom.
❖Someroomscontainbottomlesspits,butanother
containsgold.
14

15. 1
5
16

16. CONVERSION TOCNF
•
B1,1
⇔ (P1,2
∨ P2,1
)
1.Eliminate ⇔, replacing α ⇔ β with (α ⇒ β)∧(β ⇒ α).
•(B
1,1
⇒ (P
1,2
∨ P
2,1
)) ∧ ((P
1,2
∨ P
2,1
) ⇒ B
1,1
)
2.Eliminate ⇒, replacing α ⇒ β with ¬α∨ β.
•(¬B
1,1
∨ P
1,2
∨ P
2,1
) ∧ (¬(P
1,2
∨ P
2,1
) ∨ B
1,1
)
3.Move ¬ inwards using de Morgan's rules and double-negation:
•(¬B
1,1
∨ P
1,2
∨ P
2,1
) ∧ ((¬P
1,2
∧ ¬P
2,1
) ∨ B
1,1
)
4.Apply distributive law (∧ over ∨) and flatten:
•(¬B
1,1
∨ P
1,2
∨ P
2,1
) ∧ (¬P
1,2
∨ B
1,1
) ∧ (¬P
2,1
∨ B
1,1
)

17. 17
PROS AND CONS OF PROPOSITIONAL
LOGIC
☺Propositional logic is declarative
⚫Propositional logic allows
⚫partial/disjunctive/negated information
☺Meaning in propositional logic is context-
Independent
⚫(unlike natural language, where meaning
depends on context)
☹Propositional logic has very limited expressive
Power
⚫(unlike natural language)
18

18. □Whereas propositional logic assumes the world contains facts,
□first-order logic (like natural language) assumes the world contains
⚫Objects: people, houses, numbers, colors, baseball games, wars, …
⚫Relations: round, prime, brother of, bigger than, part of, comes between,
…
⚫Functions: Gt(), Lt(), Age=Curr-DOB…
20
FIRST ORDER PREDICATE LOGIC

19. •It has three more logical notions as compared to PL.
•–Terms, Predicates and Quantifiers
●Term
–a constant (single individual or concept i.e.,5, john etc.),
–a variable that stands for different individuals
–n-place function f(t1, …, tn) where t1, …, tn are terms.
–A function is a mapping that maps n terms to a term.
●Predicate
–a relation that maps n terms to a truth value true (T) or false (F).
●Quantifiers
–Universal or existential quantifiers i.e. ∀ and ∃ used in
–conjunction with variables.
• 19
PREDICATELOGIC

20. UNIVERSAL QUANTIFICATION
□∀x P(x)
□Example: “Everyone at UNC is smart”
∀x At(x,UNC) ⇒ Smart(x)
□Roughly speaking, equivalent to the conjunction of
all possible instantiations of the variable:
At(John, UNC) ⇒ Smart(John) ∧ ...
At(Richard,UNC) ⇒ Smart(Richard) ∧ ...
□∀x P(x) is true in a model m iff P(x) is true with x
being each possible object in the model
21
22

21. EXISTENTIAL QUANTIFICATION
□∃x P(x)
□Example: “Someone at UNC is smart”
•∃x At(x,UNC) ∧ Smart(x)
□Roughly speaking, equivalent to the disjunction of all possible instantiations:
•[At(John,UNC) ∧ Smart(John)] ∨
•[At(Richard,UNC) ∧ Smart(Richard)] ∨ …
□∃x P(x) is true in a model m iff P(x) is true with x being some possible
object in the model

22. PROPERTIES OF QUANTIFIERS
□∀x ∀y is the same as ∀y ∀x
□∃x ∃y is the same as ∃y ∃x
□∃x ∀y is not the same as ∀y ∃x
“There is a person who loves everyone”
∃x ∀y Loves(x,y)
“Everyone is loved by at least one person”
∀y ∃x Loves(x,y)
□Quantifier duality: each quantifier can be
expressed using the other with the help of negation
∀x Likes(x,IceCream)¬∃x ¬Likes(x,IceCream)
∃x Likes(x,Broccoli) ¬∀x ¬Likes(x,Broccoli)
23
24

23. EQUIVALENCE OFQUANTIFIERS

24. SUBSTITUTION
□Substitution of variables by ground terms:
•SUBST({g/v},P)
⚫Result of SUBST({Harry/x, Sally/y}, Loves(x,y)):
Loves(Harry,Sally)
⚫Result of SUBST({John/x}, King(x) ∧ Greedy(x) ⇒
Evil(x)): King(John) ∧ Greedy(John) ⇒ Evil(John)

25. INFERENCERULES
▪ModusPonens
▪Substitution
▪Chaining
▪Transposition
▪ANDelimination(AE)
▪ANDintroduction(AI)
▪UniversalInstantiation(UI)
▪ExistentialInstantiation(EI)
▪Resolution
25
26

26. GENERALIZEDMODUSPONENS(GMP)
p1', p2', … , pn', ( p1 ∧ p2 ∧ … ∧ pn ⇒q)
Subst(θ,q)
where p
i
'θ = p
i
θ for all i
□GMP used with KB of definite clauses (positive literal)
□All variables assumed universally quantified
27
28

27. UNIVERSAL INSTANTIATION (UI)
•□A universally quantified sentence entails every instantiation
of it:
∀v P(v)
SUBST({g/v}, P(v))
•for any variable v and ground term g
□E.g., ∀x King(x) ∧ Greedy(x) ⇒ Evil(x) yields:
King(John) ∧ Greedy(John) ⇒ Evil(John)
King(Richard) ∧ Greedy(Richard) ⇒ Evil(Richard)
King(Father(John)) ∧ Greedy(Father(John)) ⇒
Evil(Father(John))

28. EXISTENTIAL INSTANTIATION (EI)
□An existentially quantified sentence entails the
instantiation of that sentence with a new constant:
∃v P(v)
SUBST({C/v}, P(v))
for any sentence P, variable v, and constant C that
does not appear elsewhere in the knowledge base
□E.g., ∃x Crown(x) ∧ OnHead(x,John) yields:
Crown(C
1
) ∧ OnHead(C
1
,John)
provided C
1
is a new constant symbol, called a Skolem
constant
29
SUBST(θ,q)isEvil(John)
30

29. GENERALIZED MODUS PONENS (GMP)
•p
1
', p
2
', … , p
n
', (p
1
∧ p
2
∧ … ∧ p
n
⇒q)
•such that SUBST(θ, p
i
')= SUBST(θ, p
i
) for all I
•SUBST(θ,q)
Used with definite clauses (exactly one positive literal)
□All variables assumed universally quantified
□Example:
•p
1
' is King(John)p
1
is King(x) p
2
' is Greedy(y)p
2
is Greedy(x) θ is {x/John,y/John}
•q is Evil(x)

30. EXAMPLEKNOWLEDGE
BASE
□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 Colonel West,
who is American.
□Prove that Col. West is a criminal
31
32

31. EXAMPLE KNOWLEDGE BASE
•It is a crime for an American to sell weapons to hostile nations:
•∀ x ∀ y ∀ z American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧
Hostile(z) ⇒ Criminal(x)
•Nono has some missiles
•∃y Owns(Nono,y) ∧ Missile(y) Owns(Nono,M
1
) Missile(M
1
)
•All of its missiles were sold to it by Colonel West
•∀y Missile(y) ∧ Owns(Nono,y) ⇒ Sells(West,y,Nono) Missile(M
1
) ∧ Owns(Nono, M
1
) ⇒
•Sells(West, M
1
,Nono)
•West is American
•American(West)
•The country Nono is an enemy of America
Enemy(Nono,America)
General KW
Missiles are weapons:
•∀y Missile(y) ⇒ Weapon(y) Missile(M
1
) ⇒
•Weapon(M
1
)
•An enemy of America counts as “hostile”:
•∀z Enemy(z,America) ⇒ Hostile(z) Enemy(Nono,America) ⇒ Hostile(Nono)

32. USINGPREDICATELOGIC
1.
8.
1.Marcus was a man.
2.Marcus was a Pompeian.
3.All Pompeians were Romans.
4.Caesar was a ruler.
5.All Pompeians were either loyal to Caesar or
hated him.
6.Every one is loyal to someone.
7.People only try to assassinate rulers they are not
loyal to. Marcus tried to assassinate Caesar.
33
34
1.

33. 1.Marcus was a man. man(Marcus)
2.Marcus was a Pompeian. Pompeian(Marcus)
3.All Pompeianswere Romans.
∀x: Pompeian(x) → Roman(x)
4.Caesar was a ruler. ruler(Caesar)
5.All Pompeianswere either loyal to Caesar or hated him. inclusive-or
∀x: Roman(x) → loyalto(x, Caesar) ∨ hate(x, Caesar)
exclusive-or
∀x: Roman(x) → (loyalto(x, Caesar) ∧ ¬hate(x, Caesar)) ∨(¬loyalto(x, Caesar) ∧
hate(x, Caesar))
USING PREDICATE LOGIC

34. USINGPREDICATELOGIC
6.Every one is loyal to someone.
∀x: ∃y: loyalto(x, y)∃y: ∀x: loyalto(x, y)
39
7.
7.People onlytryto assassinaterulerstheyare not
loyalto.
40
∀x: ∀y: person(x) ∧ ruler(y) ∧ tryassassinate(x, y)
→ ¬loyalto(x, y)
8.Marcus tried to assassinate Caesar.
tryassassinate(Marcus, Caesar)
Was Marcus loyal to Caesar?
man(Marcus) ruler(Caesar)tryassassinate(Marcus, Caesar)
⇓
∀x: man(x) → person(x)
¬loyalto(Marcus, Caesar)

35. RESOLUTION REFUTATION IN PREDICATE
LOGIC
●Resolutionmethodisusedtotestunsatisfiabilityof
asetSofclausesinPredicateLogic.
●ItisanextensionofresolutionmethodforPL.
●Theresolutionprinciplebasicallycheckswhether
emptyclauseiscontainedorderivedfromS.
●Resolutionfortheclausescontainingnovariables
isverysimpleandissimilartoPL.
●Itbecomescomplicatedwhenclausescontainvariables.
●Insuchcase,twocomplementaryliteralsareresolvedafter
propersubstitutionssothatboththeliteralshavesame
arguments.

36. RESOLUTION
The basic ideas
KB |= α⇔
KB ∧ ¬α |= false
(α ∨ ¬β) ∧ ( γ ∨ β)⇒(α ∨ γ)
47
RESOLUTION: FOL VERSION
p
1
∨ ··· ∨ p
k
,q
1
∨ ··· ∨ q
n
such that
UNIFY(p
i
, ¬q
j
) = θ
SUBST(θ, p
1
∨ ··· ∨ p
i-1
∨ p
i+1
∨ ··· ∨ p
k
∨ q
1
∨ ··· ∨ q
j-1
∨ q
j+1
∨ ···
∨ q
n
)
□Apply resolution steps to CNF(KB ∧ ¬α); complete for
FOL
48

37. CONVERSION TOCLAUSEFORM
4.
5.
6.
7.
8.
9.
1.Eliminate→.
2.Reducethescopeofeach¬toasingleterm.
3.Standardizevariablessothateachquantifierbindsa
uniquevariable.4.Moveallquantifierstotheleft
withoutchangingtheirrelativeorder.5.Eliminate∃
(Skolemization).
6.Drop ∀.
7.Convert the formula into a conjunction of disjuncts.
Create a separate clause corresponding to each
conjunct.
8.Standardize apart the variables in the set of obtained
clauses.
49
50
1.
2.
3.

38. CONVERSION TOCLAUSEFORM
•Eliminate →.
P → Q ≡ ¬P ∨ Q
•Reduce the scope of each ¬ to a single term.
¬(P ∨ Q) ≡ ¬P ∧ ¬Q
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
¬∀x: P ≡ ∃x: ¬P
¬∃x: p ≡ ∀x: ¬P
¬¬ P ≡ P
•Standardize variables so that each quantifier binds a unique variable
•(∀x: P(x)) ∨ (∃x: Q(x)) ≡ (∀x: P(x)) ∨ (∃y: Q(y))

39. CONVERSION TOCLAUSEFORM
4.
Move all quantifiers to the left without changing their
relative order.
(∀x: P(x)) ∨ (∃y: Q(y)) ≡ ∀x: ∃y: (P(x) ∨ (Q(y))
Eliminate ∃ (Skolemization).
5.
∃x: P(x) ≡ P(c)
Skolem constant
∀x: ∃y P(x, y) ≡ ∀x:
P(x, f(x))
Skolem function
6.
7.
Drop ∀.
∀x: P(x) ≡ P(x)
Convert the formula into a conjunction of disjuncts.
(P ∧ Q) ∨ R ≡ (P ∨ R) ∧ (Q ∨ R)
8.Create a separate clause corresponding to each conjunct.
9.Standardize apart the variables in the set of obtained
clauses.
52

40. EXAMPLEKNOWLEDGE BASECONTD.
..
. it is a crime for an American to sell weapons to hostile nations:
American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧ Hostile(z) ⇒ Criminal(x)
¬(American(x) ∧ Weapon(y) ∧ Sells(x,y,z) ∧
Hostile(z) ) ∨ Criminal(x)
¬American(x) ∨ ¬ Weapon(y) ∨ ¬ Sells(x,y,z) ∨ ¬ Hostile(z) )∨ Criminal(x)
Nono … has some missiles, i.e., ∃x Owns(Nono,x) ∧ Missile(x):
Owns(Nono,M
1
) ∧ Missile(M
1
)
Owns(Nono,M
1
) , Missile(M
1
)
… all of its missiles were sold to it by Colonel West
Missile(x) ∧ Owns(Nono,x) ⇒ Sells(West,x,Nono)
¬(Missile(x) ∧ Owns(Nono,x) )∨ Sells(West,x,Nono)
¬Missile(x) ∨ ¬ Owns(Nono,x) ∨ Sells(West,x,Nono)
Missilesareweapons:
¬ Missile(x) ∨ Weapon(x)
An enemy of America counts as "hostile“:
Enemy(x,America) ⇒ Hostile(x)
¬Enemy(x,America) ∨ Hostile(x)
53
54

41. RESOLUTIONPROOF

42. EXAMPLE
1.
8.
1. Marcus was a man.
2.Marcus was a Pompeian.
3.All Pompeians were Romans.
4.Caesar was a ruler.
5.All Pompeians were either loyal to Caesar or
hated him.
6.Every one is loyal to someone.
7.People only try to assassinate rulers they are
not loyal to. Marcus tried to assassinate Caesar.
55
56
6.
7.

43. EXAMPLE
1.Man(Marcus).
2.Pompeian(Marcus).
3.∀x: Pompeian(x) → Roman(x).
4.ruler(Caesar).
5.∀x: Roman(x) → loyalto(x, Caesar) ∨ hate(x, Caesar).
6.∀x: ∃y: loyalto(x, y).
7.∀x: ∀y: person(x) ∧ ruler(y) ∧ tryassassinate(x, y)
→ ¬loyalto(x, y).
8.tryassassinate(Marcus, Caesar).

44. EXAMPLE
Prove:
hate(Marcus,Caesar)
UsingResolution
ProofbyContradiction
57
58

45. 5
9
60

46. •Unification:
•UNIFY(p,q) = unifier θwhereSUBST(θ,p)
= SUBST(θ,q)
RESOLUTIONINPREDICATELOGIC

47. RESOLUTIONINPREDICATELOGIC
Unification:
∀x: knows(John, x) → hates(John, x) knows(John, Jane)
∀y: knows(y, Leonid)
∀y: knows(y, mother(y))
∀x: knows(x, Elizabeth)
UNIFY(knows(John, x), knows(John, Jane)) = {Jane/x} UNIFY(knows(John, x),
knows(y, Leonid)) = {Leonid/x, John/y}
UNIFY(knows(John, x), knows(y, mother(y))) =
{John/y, mother(John)/x} UNIFY(knows(John, x), knows(x, Elizabeth)) = FAIL
61
RESOLUTIONINPREDICATELOGIC
Unification:Mostgeneralunifier
UNIFY(knows(John,x),knows(y,z))=
{John/y,John/x, John/z}
={John/y,Jane/x, Jane/z}
={John/y,v/x,v/z}
62

48. CHAINING
□To predict outcomes using the given pool of knowledge.
□Knowledge base is given and using logical rules and reasoning, one has
to predict the outcome.
□These problems are usually solved using Inference Engines,
□Utilize their two special modes:
I.Forward Chaining
II.Backward Chaining
63
FORWARD CHAINING
□Step1:Startfromthealreadystatedfacts,andthen,
subsequentlychoosethefactsthatdonothaveany
implicationsatall.
□Step2:Now,thosefactsthatcanbeinferredfromavailable
factswithsatisfiedpremises.
□Step3:Instep3,checkthegivenstatementthatneedstobe
checkedandcheckwhetheritissatisfiedwiththesubstitution
whichinfersallthepreviouslystatedfacts.Thuswereachourgoal.
64

49. 6
5
FORWARDCHAININGEXAMPLE
66

50. FORWARDCHAINING
67
FORWARDCHAINING
68

51. BACKWARD CHAINING
□Step 1. In the first step, take the Goal Fact and from
the goal fact, we’ll derive other facts that we’ll prove
true.
□Step 2: derive other facts from goal facts that satisfy
the rules
□Step 3: At step-3, extract further fact which infers
from facts inferred in step 2.
□Step 4: Repeat the same until we get to a certain fact
that satisfies the conditions.
69
70

52. BACKWARDCHAINING
71
BACKWARDCHAINING
72

53. BACKWARDCHAINING
73
74

54. BACKWARDCHAINING

55. BACKWARDCHAINING
75

56. S.no Forward Chaining Backward Chaining
1 Forward chaining starts from
known facts and applies inference
rule to extract more data unit it
reaches to the goal.
Backward chaining starts from the goal and
works backward through inference rules to
find the required facts that support the goal.
2 It is a bottom-up approach It is a top-down approach
3 Forward chaining is known as
data-driven inference technique as
we reach to the goal using the
available data.
Backward chaining is known as goal-driven
technique as we start from the goal and
divide into sub-goal to extract the facts.
4 Forward chaining reasoning
applies a breadth-first search
strategy.
Backward chaining reasoning applies a
depth-first search strategy.
5 Forward chaining tests for all the
available rules
Backward chaining only tests for few
required rules.
6 Forward chaining is suitable for the
planning, monitoring, control, and
interpretation application.
Backward chaining is suitable for diagnostic,
prescription, and debugging application.
7 Forward chaining can generate an
infinite number of possible
conclusions.
Backward chaining generates a finite number
of possible conclusions.
8 Forward chaining is aimed for any
conclusion.
Backward chaining is only aimed for the
required data.

57. LOGICPROGRAMMING
∙Logic programming is based on FOPL.
∙Clause in logic programming is special
form of formula.
∙Program in logic programming is a collection of
clauses.
∙Queries are solved using resolution principle.
∙A clause in logic programming is represented in a
clausal notation as
A
1
, …, A
k
← B
1
,…, B
t
,
where A
j
are positive literals and B
k
are negative literals.
77
78
FOPL

58. LOGICPROGRAMMING -PROLOG
•Prologis a declarativeprogramminglanguage basedon
logic.
•AProlog program isalist of facts.
• There arevariouspredicates and functions
• suppliedtosupportI/O, graphics, etc.
• InsteadofCNF, prologusesan implicative
•normal form:AÙBÙ... ÙCÞD

59. 79
80

60. PROLOG
:
□Only Horn sentences are acceptable
□The occur-check is omitted from the unification:
unsound
test ← P(x, x) P(x, f(x))
□Backward chaining with depth-first search:
incomplete
P(x, y) ← Q(x, y) P(x, x)
Q(x, y) ← Q(y, x)
81
82

61. Special case: Horn clauses
•Horn clausesare implications with only positive literals
•x
1AND x
2 AND x
4=> x
3 AND x
6
•TRUE => x
1
•Try to figure out whether some x
jis entailed
•Simply follow the implications (modus ponens) as far as you
can, see if you can reach x
j
•x
j is entailed if and only if it can be reached (can set
everything that is not reached to false)
•Can implement this more efficiently by maintaining, for each
implication, a count of how many of the left-hand side
variables have been reached

62. Ontological Engineering
•WhatisOntologicalEngineering?
Ontologyreferstoorganizingeverythingintheworld(complex
domain)intohierarchyofcategories.Representingtheabstract
conceptssuchasActions,Time,PhysicalObjects,andBeliefs
withrespecttocomplexdomainssuchasshoppingonthe
internetorcontrollingarobotinachangingenvironmentis
calledOntological

63. CATEGORIES AND OBJECTS
The organization of objects into categories is a vital part of
knowledge representation. Although interaction with the world
takes place at the level of individual objects, much reasoning takes
place at the level of categories.
Categories play a role in predictions about objects
•Based on perceived properties
•Categories can be represented in two ways by
•first-order logid(FOL)
•Predicates: apple(x)
•Reification of categories into objects: apples
•Category is considered as set of its
members(Relation=Inheritance).
•For eg: All instance of food are edible, fruit is a subclass
offoodand apples is a subclass of fruit then an apple is edible.
•

64. Actions, Situations, and Events
ActionsarelogicaltermssuchasForwardandTurn(Right).For
now,wewillassumethattheenvironmentcontainsonlyone
agent.(Ifthereismorethanone,anadditionalargumentcanbe
insertedtosaywhichagentisdoingtheaction.)
Situations are logical terms consisting of the initial situation
(usually called So) and all situations that are generated by
applying an action to a situation. The function Result(a, s)
(sometimes called Do) names the situation that results when
action a is executed in situation s. Figure 10.2 illustrates this
idea.

66. Agentcannowreasonaboutthebeliefsofagents.
Turningapropositionintoanobjectiscalledreification.
Technically,thepropertyofbeingabletosubstituteaterm
freelyforanequaltermis
calledreferentialtransparency.
Therearetwowaystoachievethis.
OThefirstistouseadifferentformoflogiccalledmodal
logic,inwhichpropositional
attitudessuchasBelievesandKnowsbecomemodaloperators
thatarereferentially
opaque.Thisapproachiscoveredinthehistoricalnotes
section.

67. Knowledgeandbelief
Therelationbetweenbelievingandknowinghasbeen
studiedextensivelyinphilosophy.Itiscommonly
saidthatknowledgeisjustifiedtruebelief
.
Knowledge,time,andactionActionscanhave
knowledgepreconditionsandknowledgeeffects.
Planstogatheranduseinformationareoften
representedusingashorthandnotationcalledruntime
variables,Planstogatheranduseinformationare
oftenrepresentedusingashorthandnotationcalled
runtimevariables.

68. Reasoning Systems for Categories
Semantic networks
Visualize knowledge-base
Efficient algorithms for category membership
inference
Description logics
Formal language for constructing and
combining category definitions
Efficient algorithms to decide subset and
superset relationships between categories.

69. Semantic Networks
•Semantic networks are capable of
representing individual objects,categories
of objects,and relation among objects.
Objects or Category names are
represented in ovals and are connected
by labeled arcs.
•Semantic network example

71. Default reasoning
This is a very common form of non-monotonic
reasoning. Here We want to draw conclusions
based on what is most likely to be true.
Non-Monotonic logic.
Default logic
This is basically an extension of first-order predicate
logic to include a modal operator, M. The purpose of this
is to allow for consistency.
For example:: plays_instrument(x) (and) improvises(x)
→ jazz_musician(x)
states that for all x is x plays an instrument and if the fact
that x can improvise is consistent with all other knowledge
then we can conclude that x is a jazz musician.
to show that fact P is true attempt to prove negation P. If

72. Truth Maintenance Systems
(TMS)
Many inferences have default status rather
than being absolutely certain.
•Inferred facts can be wrong and need to
be retracted (new info) and it is called as
belief revision.

73. Types of TMS
1)Justification-Based Truth Maintenance Systems (JTMS)
▪This is a simple TMS in that it does not know anything about
the structure of the assertions themselves.
▪Each supported belief (assertion) in has a justification.
▪Each justification has two parts:
An IN-List --which supports beliefs held.
An OUT-List --which supports beliefs not held.
▪An assertion is connected to its justification by an arrow.One
assertion can
feed another justification thus creating the network.Assertions may
be labelled with a belief status.

74. Fig: A JTMS Assertion

75. 2)Logic-Based Truth Maintenance Systems (LTMS)
Similar to JTMS except:
Nodes (assertions) assume no relationships among them except ones
explicitly stated in justifications.
JTMS can represent P and ¬P simultaneously. An LTMS would throw a
contradiction here.
If this happens network has to be reconstructed.
3)Assumption-Based Truth Maintenance Systems (ATMS)
JTMS and LTMS pursue a single line of reasoning at a time and backtrack
(dependency-directed) when needed --depth first search.
ATMS maintain alternative paths in parallel --breadth-first search
Backtracking is avoided at the expense of maintaining multiple contexts.