MODULE-

Knowl
edgeRepr
esent
ati
onI
ssues
I
ntr
oduct
ion:
Knowledgeplaysani mpor tantroleinAIsyst
ems.Theki ndsofknowl edgemi ghtneedtobe
repr
esentedinAIsy stems:
 Obj ects:Fact saboutobj ectsinourwor l
ddomai n.e.g.Guit
arshavest ri
ngs,tr
umpetsarebrass
inst
rument s.
 Ev ents:Actionst hatoccuri nourworld.e.g.Stev
eVai pl
ayedtheguitarinFrankZappa'
sBand.
 Per formance: Abehav iorli
keplayi
ngthegui tari
nvolvesknowledgeabouthowt odothings.
 Met a-knowl edge: Knowl edgeaboutwhatweknow.e. g.Bobrow'sRobotwhopl an'
sat r
ip.It
knowst hatitcanr eadst r
eetsignsal
ongt hewayt of i
ndoutwher eitis.

Repr
esent
ati
ons&Mappi
ngs:
I
nor
dert
osolv
ecomplexprobl
emsi nAIweneed:
- Alar
geamountofknowledge
- Somemechani
smsf ormanipul
ati
ngthatknowl
edget
ocr
eat
esol
uti
onst
onewpr
obl
em.

Avari
etyofwaysofr epr
esentingknowledgehavebeenexploi
tedi
nAIpr
oblems.Inthisregar
dwe
deal
withtwodiff
erentkindsofent i
ti
es:
 Facts:t
ruthsaboutt herealworl
dandthesearethethi
ngswewanttorepresent.
 Representat
ionoft hefactsinsomechosenformali
sm.Thesear
ethethingswhichwewil
l
act
ual
lybeabl et
omani pul
ate.

Onewaytothi
nkofst ructur
ingt
heseentiti
esisastwol evel
s:
• KnowledgeLev el,
atwhichfactsaredescr
ibed.
• Symbol Level,
atwhichrepr
esentati
onsofobj ect
sattheknowl
edgel
evel
aredef
inedi
nter
ms
ofsymbol sthatcanbemani pul
atedbyprograms.

Mappi
ngsbet
weenFact
sandRepr
esent
ati
ons:

Themodel int
heabov efigur
efocusesonfact
s,representati
onsandont he2-waymappi ngsthatmust
existbetweenthem.Thesel i
nksarecaledRepr
l esentationMappi ngs.
- For wardRepresentat
ionmappingsmapsf rom FactstoRepr esentat
ions.
- Backwar dRepresentati
onmappingsmapsf r
om Repr esentat
ionstoFact s.
Englishornaturall
anguageisanobv i
ouswayofr epresenti
ngandhandl ingfacts.Regar
dlessof
representat
ionforfact
s,weusei nprogr
am,weneedt obeconcer nedwi thEngli
sh
Repr
esent
ati
onoft
hosef
act
sinor
dert
ofaci
l
itat
eget
ti
ngi
nfor
mat
ioni
ntooroutoft
hesy
stem.

Mappi
ngf
unct
ionsf
rom Engl
i
shSent
encest
oRepr
esent
ati
ons:
Mat
hemat
ical
logi
cas
MODULE-
2

repr
esent
ati
onal
for
mal
i
sm.
Example:
“
Spotisadog”
Thefactr
epresent
edbythatEngl
ishsent encecanalsoberepr
esentedi
nlogi
cas:
dog(Spot)
Supposethatwealsohav
eal ogi
calrepresentat
ionofthef
actthat

Then, usi
ngt hededuct i
vemechanismsoflogi
c,wemaygener
atethenew
representat
ionobj ect: hast
ail
(Spot
)
Usinganappr opr
iatebackwardmappingfunct
iont
heEngl
ishsent
ence“Spothasa
tai
l”canbegener at ed.

Fact
-Repr
esent
ati
onmappi
ngmaynotbeone- t
o-onebutrat
herar
emany-
to-
manywhichar
ea
char
acter
ist
icofEngl
i
shRepr
esent
ati
on.GoodRepresent
ati
oncanmakeareasoni
ngpr
ogr
am
si
mple.
Example:
“
All dogshavet
ail
s”
“
Ev erydoghasatail
”
From thetwostat
ement swecanconcl
udethat“
Eachdoghasatail
.”Fr
om t
he
statement1,weconcludethat“
Eachdoghasmorethanonet
ail
.”
Whenwet rytoconv
ertEngli
shsent encei ntosomeotherrepr
esentsuchasl ogi
calproposi
ti
ons,we
f
ir
stdecodewhatfactsthesentencesr epresentandthenconvertthosefactsint
othenew
r
epresent
ati
ons.WhenanAIpr ogram mani pul
atest
heinter
nalrepresent
ationoffactsthesenew
r
epresent
ati
onsshouldalsobeinter
pr etableasnewrepresent
ationsoffacts.

Mut i
latedChecker
boardPr obl
em:
Problem:I nanormalchessboardtheopposi
tecor
nersquar
eshavebeenel
iminat
ed.Thegi
ven
taskist ocoveral
lthesquaresonther
emaini
ngboardbydominoessot
hateachdominocov
ers
twosquar es.Noov er
lappingofdominoesisall
owed,canitbedone?Considerthr
eedata
structures
MODULE-
2

Thefir
str epr
esent
ationdoesnotdi r
ectl
ysuggesttheanswert otheprobl
em.Thesecondmay
suggest.Thethi
rdrepresentat
iondoes,whencombinedwiththesingl
eaddi
ti
onal
fact
sthateach
dominomustcov erexactlyonewhitesquareandoneblacksquare.

Thepuzzleisimpossibl
et ocomplete.Adomi nopl acedonthechessboardwi l
lalwayscoverone
whitesquareandonebl acksquare.Therefor
eacol l
ecti
onofdominoespl acedont heboardwil
l
coveranequalnumber sofsquaresofeachcol or .I
fthetwowhitecornersareremov edfr
om the
boardthen30whi tesquaresand32bl acksquar esremaintobecov er
edbydomi noes,sothi
sis
i
mpossi bl
e.Ifthetwobl ackcor
nersar eremov edi nst
ead,t
hen32whi t
esquar esand30bl ack
squaresremain,soiti
sagainimpossible.

Thesol
uti
oni
snumberofsquar
esmustbeequal
forposi
ti
vesol
uti
on.

I
nt heabovef i
gure,t
hedottedli
neacrossthetoprepresentstheabst r
actr
easoni
ngprocesst
hat
apr ogram isintendedtomodel .Thesol i
dlineacr osst hebot t
om repr
esentstheconcr
ete
reasoningprocesst hatapart
icul
arprogram per
forms.Thi spr ogr
am successf
ull
ymodelsthe
abstractpr
ocesst otheext
entthat,whenthebackwardr epresentat
ionmappingi
sappli
edtothe
program’soutput,t
heappropri
atefi
nalfact
sareactuallygenerated.

I
fnogoodmappingcanbedef
inedf
oraprobl
em,thennomat t
erhowgoodtheprogram t
osol
ve
theprobl
em i
s,i
twil
lnotbeablet
oproduceanswersthatcorr
espondt
or ealanswer
st ot
he
probl
em.
MODULE-
2

Usi
ngKnowl
edge
Letusconsidertowhatappl i
cationsandhowknowl edgemaybeused.
 Lear ni
ng:acqui ri
ngknowl edge.Thisismor et hansi mplyaddingnewf actstoaknowl edge
base.Newdat amayhav etobecl assi
fi
edpr iortostorageforeasyr et
ri
eval,
etc..Interacti
on
andinferencewi thexistingfactstoav oidredundancyandr epli
cati
onintheknowl edgeand
al
sosot hatf actscanbeupdat ed.
 Ret r
ieval:Ther epresentati
onschemeusedcanhav eacrit
icaleff
ectontheef f
iciencyoft he
method.Humansar ev erygoodati t
.ManyAImet hodshavet r
iedtomodel human.
 Reasoni ng:Inferfactsfrom exist
ingdat a.

I
fasy stem ononlyknows:
• Mi lesDav i
sisaJazzMusi ci
an.
• Al lJazzMusicianscanplaythei
rinstr
ument
swell
.
I
fthingslkeI
i sMil
esDav i
saJazzMusi ci
an?orCanJazzMusi
cianspl
ayt
heiri
nstrument
swel
l
?ar
e
askedthent heanswerisreadi
l
yobtainedfrom t
hedat
astr
uct
uresandpr
ocedures.

Howeveraquesti
onl i
ke“CanMilesDavispl
ayhisi
nstr
umentwell
?”requir
esr
easoni
ng.The
abovear
eal
lrel
ated.Forexampl
e,iti
sfai
rl
yobvi
oust
hatl
ear
ningandreasoni
ngi
nvol
ver
etr
ieval
etc.

Appr
oachest
oKnowl
edgeRepr
esent
ati
on
AgoodKnowl edger
epresent
ationenabl
esfastandaccurat
eaccesstoKnowledgeandunder
standi
ng
ofcont .Thegoal
ent ofKnowledgeRepresent
ati
on(KR)istofaci
l
itat
econcl
usions
fr
om knowledge.

Thef
oll
owi
ngpropert
iesshoul
dbepossessedbyaknowledgerepr
esent
ati
onsy
stem.
• Represent
ati
onalAdequacy
:theabil
i
tytorepresental
lki
ndsofknowledget
hatar
e
neededinthatdomain;

• I
nfer
enti
alAdequacy:t
heabil
it
ytomanipul
atet
heknowledgerepr
esent
edt
opr
oduce
newknowledgecorr
espondi
ngtothati
nfer
redf
rom t
heori
ginal
;

• I
nfer
ent
ialEff
ici
ency
:theabil
it
ytoincor
porat
eint
otheknowl
edgestr
uct
ureaddi
ti
onal
i
nfor
mationthatcanbeusedt ofocustheatt
ent
ionofthei
nfer
encemechani
smsin
t
hemostpr omisi
ngdir
ect
ions.

• Acquisit
ionalEff
ici
ency:theabil
it
ytoacqui
renew i
nformati
oneasil
y.Thesi
mplest
casei nvol
vesdi r
ectinsert
ion,byapersonofnew knowledgeint
ot hedat
abase.
Ideal
l
y ,t
hepr ogr
am it
selfwouldbeabl
etocont
rol
knowledgeacqui
sit
ion.

Nosi
nglesyst
em thatopti
mizesal
lofthecapabi
li
ti
esforal
lki
ndsofknowl
edgehasy
etbeenf
ound.
Asaresul
t,mul
ti
pletechni
quesforknowledger
epresent
ati
onexi
st.

Knowl
edgeRepr
esent
ati
onSchemes
MODULE-
2

Ther
earefourty pesofKnowl edgeRepr esentation:
 Rel
ational Knowl edge:
– pr ovidesaf ramewor kt ocompar etwoobj ectsbasedonequi v
alentat
tri
butes
– anyi nstancei nwhi cht wo differentobj ectsarecompar ed isar el
ationaltypeof
knowl edge
 I
nheritableKnowl edge:
– i sobt ainedf r
om associ at
edobj ects
– i tpr escribesast r
uctureinwhi chnew obj ect
sar ecreat
edwhi chmayi nheri
tallora
subsetofat t
ri
butesf rom exi
stingobj ects.
 I
nferentialKnowl edge
– i si nferr
edf rom objectsthroughr elat
ionsamongobj ects
– Exampl e: awor daloneissimpl esy ntax,butwiththehelpofotherwordsinphrase
ther eadermayi nfermor ef r
om awor d;thisinf
erencewithi
nl i
ngui
sti
ci scall
ed
semant ics.

 Decl
arativeKnowl edge
– ast atementi nwhi chknowl edgeisspeci f
ied,
buttheuset owhichthatknowledgei
sto
beputi snotgi v
en.
– Exampl e:laws, people’
sname; therearefactswhi
chcanst andal
one,notdependenton
otherknowl edge
 Pr
ocedur alKnowl edge
– ar epresent at
ioninwhi chthecont r
olinformati
on,tousetheknowledgeisembeddedi n
theknowl edgei tself
.
– Exampl e:comput erprograms, dir
ecti
onsandr eci
pes;theseindi
catespecif
icuseor
i
mpl ement ati
on

Si
mpl
erel
ati
onal
knowl
edge
Thesimpl
estwayofst ori
ngf actsistousear el
ati
onalmet hodwher eeachfactaboutasetof
obj
ectsissetoutsy stemati
callyincol umns.Thisr epresentat
iongivesli
tt
leopport
uni
tyfor
i
nfer
ence,buti
tcanbeusedast heknowl edgebasisforinfer
enceengines.
• Simplewayt ostorefacts.
• Eachfactaboutasetofobj ect
sissetoutsy stematical
l
yincol
umns.
• Lit
tl
eoppor t
unityfori
nference.
• Knowledgebasi sfori
nferenceengines.
MODULE-
2

Giventhefact
siti
snotpossi
blet
oanswersimplequesti
onsuchas"Whoi stheheaviestplayer
?"
butifapr ocedur
eforfindi
ngheavi
estplayerisprovi
ded,thenthesefactswi l
lenabl ethat
proceduretocomput
eananswer.Wecanaskt hi
ngsli
kewho"bats-lef
t"and"thr
ows-r ight"
.

I
nher
it
abl
eKnowl
edge
Heretheknowl edgeelementsinheritatt
ri
butesfrom theirpar
ents.Theknowl
edgeisembodied
i
nt hedesi gnhierar
chiesfoundint hefuncti
onal,phy si
calandprocessdomains.Withi
nthe
hier
archy,elementsinher
itat
tri
butesf r
om thei
rpar ents,buti
nmanycasesnotal lat
tri
but
esof
theparentelementsbeprescri
bedt othechil
delement s.

Theinher
it
anceisapowerf
ulf
orm ofi
nfer
ence,
butnotadequat
e.Thebasi
cKRneedst
obe
augmentedwit
hinfer
encemechani
sm.

TheKRi nhierarchicalstr
ucture,shownbel
ow,iscal
l
ed“semanti
cnetwork”oracoll
ect
ionof
“f
rames”or“ slot-and-
fi
ll
erstructure”
.Thestr
uct
ureshowspropert
yinheri
tanceandwayfor
i
nsert
ionofaddi t
ionalknowledge.

Pr
opert
yinheri
tance:Theobj
ectsorel
ementsofspeci
fi
ccl
assesi
nheri
tatt
ribut
esandv
aluesf
rom
moregeneral
classes.Thecl
assesareor
ganizedi
nagener
ali
zedhi
erarchy
.

Basebal
lKnowledge
-i
sa:showclassinclusi
on
-i
nstance:
showcl assmember
shi
p

• Thedir
ect
edarr
owsr epresentatt
ri
but
es(i
sa,i
nstance,team)ori
ginat
esatobj
ectbei
ngdescr
ibed
andter
minat
esatobjectoritsval
ue.
• Theboxnodesr
epresentobjectsandval
uesoftheattr
ibutes.

Viewi
nganodeasaf r
ame
Example:
Basebal
l
-pl
ayer
MODULE-
2

I
sa: Adult
-Mal
e
Bat
s: EQUALhanded
Hei
ght: 6-
1
Bat
ti
ng-av
erage:0.
252

Thi
salgori
thm i
ssi
mple.I
tdescr
ibesthebasi
cmechanism ofi
nheri
tance.I
tdoesnotsaywhatt
o
doift
hereismorethanoneval
ueoftheinst
anceor“
isa”at
tri
bute.

Thi
scanbeappl i
edt otheexampl eofknowledgebase,
toder
iveanswer
stot
hef
oll
owi
ngquer
ies:
 team (Pee-Wee-Reese)=Br ookl
yn-Dodger
 batti
ng-aver
age( Three-Fi
nger-
Brown)=0.106
 height(Pee-Wee-Reese)=6. 1
 bats(Three-Fi
nger-Brown)=right

I
nfer
ent
ial
Knowl
edge:
Thi
sknowledgegener at
esnew infor
mationfrom t
hegi v
eni nf
ormation.Thi
snew i nfor
mat
ion
doesnotrequi
ref urt
herdat
agat heri
ngf r
om source,butdoesr equir
eanalysi
soft hegi
ven
i
nfor
mati
ont ogeneratenewknowledge.I
nthis,wer
epresentknowledgeasformallogic.

Exampl
e:
- givenasetofr el
ati
onsandv al
ues,onemayi nf
erot herval
uesorrelat
ions
- apr edicat
elogi
c(amat hemati
caldeduct
ion)isusedt oinf
erfrom asetofattr
ibutes.
- inf
er encethr
oughpredicat
elogi
cusesasetofl ogicaloperat
ionstorelat
eindi
v i
dualdat
a.
- thesy mbolsusedforthelogi
coperati
onsare:
MODULE-
2

Pr
ocedur
alKnowl
edge
Procedur
alknowledgecanber epresent
edinprogr
amsi nmanyway s.Themostcommonwayi s
si
mpl yasfordoingsomet hi
ng.Themachi neusestheknowledgewhenitexecutesthecodet
o
perfor
m atask.Procedur
alKnowledgeistheknowledgeencodedi
nsomepr ocedures.

Unfort
unatel
y,thiswayofr epresenti
ngproceduralknowledgeget slowscoreswithrespecttothe
proper
tiesofinferenti
aladequacy(becauseitisverydiffi
culttowriteaprogr
am thatcanr eason
aboutanotherpr ogram’sbehavior
)andacquisit
ionaleff
iciency(becauset
hepr ocessofupdat i
ng
anddebuggingl argepiecesofcodebecomesunwi eldy
).

Themostcommonlyusedt
echni
quef
orr
epr
esent
ingpr
ocedur
alknowl
edgei
nAIpr
ogr
amsi
sthe
useofpr
oduct
ionr
ules.

Product
ionrul
es,part
icul
ar l
yonesthatareaugment edwi thinfor
mat i
ononhow theyar
etobe
used,aremor eproceduralt hanaretheot herrepresentati
onmet hods.Butmakingaclean
di
st i
nct
ionbet
weendecl arati
veandproceduralknowl edgeisdiff
icul
t.Thei
mport
antdif
fer
ence
i
si nhowtheknowledgeisusedbyt heproceduresthatmani pul
ateit.

Heur
ist
icorDomai
nSpeci
fi
cknowl
edgecanber
epr
esent
edusi
ngPr
ocedur
alKnowl
edge.

I
ssuesi
nKnowl
edgeRepr
esent
ati
on
MODULE-
2

Bel
owar
eli
stedi
ssuest
h
atshoul
dber
aisedwhenusi
ngknowl
edger
epr
esent
ati
ont
echni
ques:

Theatt
ri
butesarecall
edavari
etyofthi
ngsi
nAIsy st
ems,butt
henamesdonotmatter
.What
doesmatteri
sthattheyr
epr
esentclassmembershipandcl
assincl
usi
onandt
hatcl
assincl
usi
oni
s
tr
ansi
ti
ve.Thepredi
catesar
eusedinLogicBasedSy st
ems.

Rel
ati
onshipamongAt tributes
 Theat tri
butest odescr i
beobject
sar ethemselvesentit
iesthatwer epresent.
 Ther elati
onshipbet weent heatt
ribut
esofanobj ect
,independentofspeci fi
cknowledget
hey
encode,mayhol dproperti
esli
ke:
Inverses,existenceinanisahierachy
,techni
quesf orreasoningaboutv al
uesandsi
ngl
e
valuedat tri
butes.
MODULE-
2

Thesecondwaycanber eal
izedusi
ngsemant
icnetandf
ramebasedsy
stems.Thi
sInv
ersesi
sused
i
nKnowl edgeAcqui
sit
ionTools.

Thi
salsopr
ovi
desinf
ormati
onaboutconst
rai
ntsont
hev
aluest
hatt
heat
tri
but
ecanhav
eand
mechani
smsforcomputi
ngthoseval
ues.
MODULE-
2

Sev
eralkindsofinfor
mat ioncanpl ayar oleinthisreasoning,including:
Informat
ionaboutthet ypeoft hevalue.
• Const r
aintsonthev alueoft
enst atedint er
msofr elatedent it
ies.
• Rul esf
orcomput ingt hev al
uewheni tisneeded.(Exampl e:ofsuchar ul
einforbatsatt
ribut
e).
Theserulesarecalledbackwar drules.Suchruleshav eal sobeencalledif
neededrules.
• Rul est
hatdescribeact i
onst hatshouldbet akenifav alueev erbecomesknown.Theser ul
es
arecal
ledforwardr ules,orsomet imesi f
-addedrules.

 Int
roduceanexplici
tnotati
onf ortemporalinterval
.Iftwodi f
ferentval
uesareeverassertedfor
thesamet emporali
nterval
,signalacontradictionautomaticall
y.
 Assumet hatt
heonl ytempor ali
ntervalt
hati sofinteresti
snow.Soi fanewv al
ueisasser t
ed,
repl
acetheoldvalue.
 Provi
denoexpl i
citsupport.Logic-basedsy stemsar ei nthi
scat egory.Buti
nthesesy stems,
knowledgebasebui l
derscanaddaxi omsthatst atethatifanat tr
ibut
ehasonev al
uet henitis
knownnott ohaveallothervalues.
MODULE-
2

Choosingt heGranular
it
yofRepr esentat
ionPr i
miti
vesar
efundamentalconceptssuchasholdi
ng,
seei
ng, play i
ngandasEngl i
shi sav er
yrichlanguagewit
hoverhalfamill
ionwor dsi
tiscl
earwewill
fi
nddifficultyindecidi
nguponwhi chwor dst ochooseasourpri
miti
vesinaseriesofsit
uati
ons.
Separatel evelsofunderst
andingrequiredif
ferentl
evel
sofpri
miti
vesandt heseneedmanyr ul
esto
l
inktoget hersimilarpr
imit
ives.
MODULE-
2
 MODULE-
2

TheFr
amePr
obl
em
 MODULE-
2

Whenr epresenti
ngoper at
orswemaket heassumpt i
ont hatt
heonl yef
fectsouroperatorhasont heworl
dare
thosespecifi
edbyt headdanddel etel
ists.Inreal-
wor l
dpl anningthisi
sahar dassumpt i
ontomakeaswecan
neverbeabsol ut
elycertai
noft heextentoft heef f
ectsofanact i
on.ThisisknowninAIast heFr ameProbl
em.Real
-Worldsystems,suchasShakey ,arenotoriouslydiff
iculttoplanforbecauseofthisproblem.Plansmust
constant
lyadaptbasedoni ncomi ngsensor yinfor
mat ionaboutt henewst at
eofthewor ldotherwiset
heoper
ator
precondi
tionswillnolongerapply.Thepl anningdomai nswewi l
lbeworkinginourToy-Wor l
dssowecanassume
thatourframingassumpt i
onsar eaccur ate.
 MODULE-
2

Usi
ngPr
edi
cat
eLogi
c

I
ntr
oduct
ion
Predi
cat
elogi
cisusedtor
epresentKnowledge.Predi
cat
elogicwi
ll
bemetinKnowl
edgeRepr
esent
ati
on
Schemesandreasoni
ngmethods.Thereareotherwaysbutthi
sfor
mispopul
ar.

Repr
esent
ingSi
mpl
eFact
sinLogi
c
Pr
oposit
ionalLogi
c
I
tissi
mpl etodealwi
thanddeci
sionpr
ocedur
eforitexi
sts.Wecanrepr
esentr
eal-
worl
dfact
saslogi
cal
pr
oposit
ionswrit
tenaswell
-f
ormedfor
mulas.
Toexpl
oretheuseofpredi
catelogi
casawayofrepresenti
ngknowl
edgebylooki
ngataspeci
fi
cexample.

Theabovet
wost at
ementsbecomestot
all
ysepar
ateassert
ion,
wewoul
dnotbeabl
etodr
awany
concl
usi
onsaboutsimi
l
arit
iesbet
weenSocrat
esandPlato.

Theserepresent
ati
onsr
efl
ectt
hest
ruct
ureoft
heknowl
edgei
tsel
f.Theseusepr
edi
cat
esappl
i
edt
o
arguments.

I
tfai
l
stocapt
uret
her
elat
ionshi
pbet
weenanyi
ndi
vi
dual
bei
ngamanandt
hati
ndi
vi
dual
bei
nga
mort
al.

Weneedv
ari
abl
esandquant
if
icat
ionunl
esswear
ewi
l
li
ngt
owr
it
esepar
atest
atement
s.

Predicate:
APr edicat
eisat
rut
hassignmentgi
venforapar
ti
cul
arst
atementwhi
chisei
thert
rueorf
alse.Tosol
ve
commonsensepr oblemsbycomputersyst
em,weusepredi
cat
elogi
c.

Logi
cSy
mbol
susedi
npr
edi
cat
elogi
c
MODULE-
2

Pr
edi
cat
eLogi
c
• Termsr epr esentspeci f i
cobj ectsinthewor ldandcanbeconst ants,
v ari
ablesorfuncti
ons.
• PredicateSy mbol srefert oapar ticul
arrelati
onamongobj ects.
• Sentencesr epresentf acts,andar emadeoft erms,quant
if
ier
sandpr edicatesymbols.
• Functionsal lowust or efertoobj ectsindi
rectly(v
iasomer el
ati
onshi
p) .
• Quant i
fier sandv ariabl
esal lowust orefertoacol l
ecti
onofobject
swi thoutexpl
ici
tlynaming
eachobj ect.
• SomeExampl es
o Pr edicates: Brother ,
Sister,Mother, Father
o Obj ect s:Bil
l,Hil
lary,Chelsea, Roger
o Fact sexpr essedasat omi csentencesa. k.
a.
l
iterals:
o Fat her(Bill
,Chelsea)
o Mot her(Hill
ary,Chelsea)
o Br
other
(Bi
l
l,
Roger
)
o Fat
her
(Bi
l
l,
Chel
sea)

Var
iablesandUniver
salQuant
if
icat
ion
Uni
versalQuant
if
icat
ionall
owsustomakeast
atementaboutacol
l
ect
ionofobj
ect
s:

Var
iablesandExi
stent
ialQuant
if
icat
ion
Exi
stenti
alQuant
if
icat
ionall
owsustostat
ethatanobj
ectdoesexi
st(
wit
houtnami
ngi
t)
:

Nest
edQuant
if
icat
ion
MODULE-
2

Funct
ions
• Functi
onsareterms-t
heyref
ertoaspecifi
cobject.
• Wecanusef uncti
onst
osy mbol
i
call
yrefertoobject
swi t
houtnami
ngt
hem.
• Examples:
fat
herof
(x) age(x) times(x,
y) succ(
x)
• Usi
ngf
uncti
ons

I
fweusel ogicalstatementsasawayofrepr
esent
ingknowledge,
thenwehav
eav
ail
abl
eagoodway
ofreasoningwi t
ht hatknowledge.
Representingfactswi t
hPredicat
eLogi
c
1)Mar cuswasaman man(
Markus)
2)Mar cuswasaPompei an pompeian(
Markus)

3)Al
lPompeianswereRomans
4)Caeserwasarul
er. rul
er(caeser
)
5)Al
lromanswereeit
herl
oyal
tocaeserorhatedhi
m.

6) Ever
yonel
oyalt
osomeone.
7) Peopl
eonl
ytrytoassassi
nat
erul
erst
heyar
enotl
oyal
to.

8) Mar
cust
ryt
oassassi
nat
eCeaser

Q.Pr
ovet
hatMar
cusi
snotl
oyalt
oCeaserbybackwar
dsubst
it
uti
on
MODULE-
2

Repr
esent
ingI
nst
anceandI
saRel
ati
onshi
ps
Twoatt
ribut
esisaandinst
anceplayani mportantroleinmanyaspect sofknowledger
epr
esent
ati
on.
Ther
easonf ort
hisi
sthattheysupportpropertyinheri
tance.
isa-usedtoshowcl assi
nclusi
on,e.g.isa(mega_ star
,r
ich)
.instance-
usedt oshowclassmember ship,
e.g.instance(pri
nce,
mega_ star)
.

I
nthefi
gureabov e,
 The f i
rst f i
ve sentences of t he r epresent t he pur e pr edicatel ogic. Int hese
represent ati
ons,class member shipi sr epr esented with unar y predi
cat es (such as
Roman) ,eachofwhi chcor respondst oacl ass.Asser t
ingthatP( x)istrueisequi val
entt o
asser ti
ngt hatxisani nst
anceofP.
 Thesecondpar tofthef i
gur econt ai
nsr epr esentati
onst hatuset heinstancepr edicate
explicit
ly.Thepr edi
cat ei
nst ancei sabi naryone,whosef ir
star gumenti sanobj ectand
whose second ar gument i s a cl ass t o whi ch t he object bel ongs.But t hese
represent ati
onsdonotuseanexpl icitisapr edicat
e.
 Thet hi
rdpar tcontainsr epresentat i
onst hatusebot ht hei nstanceandi sapr edicates
explicit
ly.Theuseoft heisapr edi
catesi mpl if
iestherepresent ati
onofsent ence3,buti t
requirest hatoneaddi ti
onalaxi om bepr ovided.Thi sadditi
onalaxi om descr i
beshowan
inst
ancer elati
onandani sar elati
oncanbecombi nedt oderiveanewi nstancer el
ation.
MODULE-
2
MODULE-
2

Comput
abl
eFunct
ionsandPr
edi
cat
es

Thi
sisfineifthenumberoffact
sisnotv er
ylargeorifthefact
sthemsel
vesaresuf
fici
entl
y
unstr
uctur
edt hatt
her
eislit
tl
ealt
ernat
ive.Butsupposewewantt oexpresssi
mplefacts,
such
asthefoll
owinggreat
er-
thanandless-
thanrelati
onships:
gt
(1,
0) I
t(
0,1)
gt
(2,
1) I
t(
1,2)
gt
(3,
2) I
t(2,
3)
Clearlywedonotwantt ohav etowr i
teoutt herepr
esentati
onofeachofthesefactsindividual
ly.
Foronet hi
ng,
ther eareinf
ini
tel
ymanyoft hem.Butev enifweonlyconsi
derthefinit
enumberof
them t hatcanber epr
esented,say,usingasi ngl
emachi newordpernumber ,itwoul dbe
extremelyineff
icienttostoreexplici
tl
yal argesetofst at
ementswhenwecoul d,i
nst ead,so
easilycomputeeachoneasweneedi t
.Thusi tbecomesusef ult
oaugmentourr epresentati
on
bythesecomput ablepredi
cates.
MODULE-
2

Resol
uti
on:
Apr oceduret oproveast at
ement ,Resol
uti
onattempt stoshow t hatNegat
ionofSt atement
gi
v esCont r
adict
ionwit
hknownst atement
s.I
tsimpli
f i
esproofprocedurebyfi
rstconv
er t
ingthe
statementsi nt
ocanonicalform.Si mpl
eiter
ati
vepr ocess;ateachst ep,2clausescall
edt he
parentclausesarecompared,yiel
dinganewclausethathasbeeni nf
erredfr
om them.

Resol
uti
onr efutati
on:
• Conv ertallsentencestoCNF( conjuncti
venormal
for
m)
• Negat ethedesi redconcl
usion(conv er
tedtoCNF)
Applyr esol
ut i
onr ul
eunti
lei
ther
– Der ivefalse(acontr
adicti
on)
– Can’ tappl yanymore
Resol
uti
onr efutati
oni ssoundand
complet
e
• Ifweder iveacont r
adi
cti
on,thentheconclusionfol
l
owsf r
om theaxi
oms
• Ifwecan’ tapplyanymor e,t
hent heconclusioncannotbeprov
edf r
om t
heaxi
oms.

Sometimesfrom thecollecti
onoft hestat
ement swehav e,wewantt oknowt heansweroft
his
questi
on-"Isitpossibl
etopr ovesomeot herstatementsfrom whatweact uall
yknow?"Inor
der
toprovethi
sweneedt omakesomei nfer
encesandt hoseot herstat
ement scanbeshowntrue
usi
ngRef ut
ationproofmet hodi.
e.proofbycontradi
ctionusingResolut
ion.Sofort
heaskedgoal
wewi l
lnegatethegoalandwi ll
addi tt
othegivenstatementst oprovethecontr
adi
cti
on.

Soresol
utionref
utati
onforproposi
ti
onall
ogici
sacomplet
eproofprocedur
e.Soift
het
hingt
hat
you'
retr
yingtoproveis,
infact,ent
ail
edbythet
hingst
hatyou'
veassumed,theny
oucanprov
eit
usi
ngresoluti
onrefut
ati
on.

Cl
auses:
 Resolut
ioncanbeappl
i
edtocer
taincl
assofwf fcal
ledcl
auses.
 Aclauseisdefi
nedasawf
fconsist
ingofdi
sjuncti
onofli
ter
als.

Conjuncti
veNormalForm orClauseNormalForm:
ClauseformisanapproachtoBooleanlogi
cthatexpressesformulasasconj
unct
ionsofcl
auses
withanANDorOR.Eachcl auseconnectedbyaconj unctionorANDmustbewi therali
teralor
contai
nadi sj
unct
ionorORoper at
or.I
nclausefor
m, astatementisaseri
esofORsconnectedby
ANDs.

Astat
ementisinconj
unctiv
enormalformifitisaconj
unct
ion(sequenceofANDs)consisti
ngof
oneormoreconjunct
s,eachofwhichisadisjunct
ion(
OR)ofoneormor eli
ter
als(
i.
e.,
statement
l
ett
ersandnegati
onsofstatementl
ett
ers)
.

Al
loft
hef
oll
owi
ngf
ormul
asi
nthev
ari
abl
esA,
B,C,
D,andEar
einconj
unct
ivenor
mal
for
m:
MODULE-
2

Conv
ersi
ont
oCl
auseFor
m:

 Cl
auseFor
m:

Al
gor
it
hm:
Conv
ertt
oCl
auseFor
m
1.El
i
minat
eimpl
i
esr
elat
ion()Usi
ngt
hef
actt
hatabi
sequi
val
entt
o~aVb.

2.Reducet
hescopeofeach t
oasi
ngl
eter
m

3. St
andar
dizev
ari
abl
essot
hateachquant
if
ierbi
ndsauni
quev
ari
abl
e.

4.Mov
eal
lquant
if
ier
stot
hel
eftoft
hef
ormul
aswi
thoutchangi
ngt
hei
rrel
ati
veor
der
.

5.El
i
mi nat
eexi
stenti
alquant
ifi
ers.Wecaneli
minatet
hequant
if
ierbysubsti
tut
ingfort
hevari
abl
e
aref
erencet
oaf uncti
onthatproducest
hedesir
edval
ue. y:Presi
dent
(y)=>Presi
dent
(S1)

I
ngener alt
hefuncti
onmusthav ethesamenumberofar gumentsast henumberofuni v
ersal
quanti
fier
sinthecurr
entscope.
Skolemizetoremoveexist
entialquant
if
ier
s.Thisstepr
eplacesexi
stenti
all
yquant
if
ied
var
iablesbySkolem f
uncti
ons.Forexample,conver
t( x)P(x)toP(c)wherecisabr and
MODULE-
2

new constantsy mbolthatisnotusedi nanyot hersentence( ciscall

edaSkol em
constant)
.Mor egeneral
ly
,iftheexi
stent
ialquantif
ieri
swithinthescopeofauniversal
quantif
iedvari
able,thenintr
oduceaSkol em functi
onthatdependsont heuni
versal
ly
quantif
iedvari
able.Forexample,"xyP( x,y
)isconv er
tedto"xP( x,f
(x)
).fi
scalleda
Skolem funct
ion,andmustbeabr andnew f uncti
onnamet hatdoesnotoccurinany
otherpartoft
helogicsentence.

6.Dr
opt
hepr
efi
x.Att
hispoi
nt,
all
remai
ningv
ari
abl
esar
euni
ver
sal
l
yquant
if
ied.

7.Conv
ertt
hemat
ri
xint
oaconj
unct
ionofdi
sjunct
ions.

8.Createaseparat
eclausecorrespondi
ngtoeachconjuncti
norderf
orawellf
ormedformulato
betrue,
allthecl
ausesthataregenerat
edfr
om itmustbet r
ue.
9.Standar
dizeapartt
hev ar
iabl
esinsetofcl
ausesgeneratedinst
ep8.Renamethevar
iabl
es.So
thatnotwoclausesmaker ef
erencetosamev ar
iabl
e.

Conver
tthestatement stoclausef or
m
1.man( mar cus)
2.pompei an(mar cus)
3. pompei an(x) roman( x)
4.ruler
(caeser)
5. x: r
oman( x) l oy
alto(
x,caeser
)Vhat
e(x,
caeser
)
MODULE-
2

Ther
esul
tantcl
ausef
ormi
s

BasisofResolution:
Resoluti
onprocessi sappliedt opai
rofparentclausestopr oduceader i
vedclause.Resol ut
ion
procedureoperatesbyt aki
ng2cl ausest
hateachcont ainthesamel i
ter
al.Thelit
eralmustoccur
inthepositi
vef orminonecl auseandnegat i
veformi ntheot her.Theresolventisobt ai
nedby
combi ni
ngalloft heli
teral
soft woparentclausesexceptonest hatcancel.I
fthecl ausethatis
producedinanempt yclause,thenacontr
adicti
onhasbeenf ound.
Eg:winterand wi nt
erwi l
lproducetheemptyclause.

I
facont radicti
onexist
s,theneventual
l
yitwil
lbefound.Ofcour
se,
ifnocontr
adi
cti
onexi
sts,
iti
s
possibl
et hattheprocedurewil
lneverter
minat
e,alt
houghaswewillsee,
ther
eareoft
enwaysof
detecti
ngt hatnocontradi
cti
onexists.

Resol
uti
oni
nPr
oposi
ti
onal
Logi
c:

Exampl
e:Consi
dert
hef
oll
owi
ngaxi
oms
P PQ)→ R
( ST)→ QT
(
Conv
ertt
hem i
ntocl
ausef
orm andpr
ovet
hatRi
str
ue
MODULE-
2

Uni
fi
cat
ionAl gori
thm
• Inproposi t
ional l
ogicitiseasyt odet er
mi net hattwol iteralscannotbothbet r
ueatthesame
ti
me.
• Simpl ylookforLand~L.I npr edicatelogic,thismat chi ngprocessismor ecompl i
cated,
since
bindingsofv ari
abl esmustbeconsi dered.
• Inordert odetermi necont r
adictionsweneedamat chingpr ocedurethatcompar estwoli
teral
s
anddi scoverswhet herther
eex i
stasetofsubst i
tuti
onst hatmakest hem i
dentical
.
• Therei sar ecursi
v eproceduret hatdoest hismat chi ng.I ti
scalledUnif
icat
ionalgori
thm.
• Thepr ocessoff i
ndingasubst i
tutionforpr edicat
epar amet ersiscal
ledunifi
cati
on.
• Weneedt oknow:
– t hat2l i
teralscanbemat ched.
– t hesubst it
utionisthatmakest hel i
teralsidentical .
• Therei sasi mpleal gori
thm calledt heunifi
cat i
onalgor ithm thatdoesthis.

TheUnifi
cationAl gorithm
1.I
nit
ialpredicatesy mbol smustmat ch.
2.Foreachpai rofpr edicatearguments:
– Di fferentconstantscannotmatch.
– Av ariablemayber epl
acedbyaconstant.
– Av ariablemayber epl
acedbyanothervar
iable.
– Av ariablemayber epl
acedbyafuncti
onasl ongast
hef
unct
iondoesnotcont
ainan
instanceoft hev ar
iabl
e.

• Whenat
tempt
ingt
omat
ch2l
i
ter
als,
all
subst
it
uti
onsmustbemadet
otheent
ir
eli
ter
al.
MODULE-
2

• Ther
emaybemanysubst
it
uti
onst
hatuni
fy2l
i
ter
als;
themostgener
aluni
fi
eri
sal
way
s
desi
red.

Uni
fi
cat
ionExampl
e:
Theobjectoft
heUnifi
cati
onprocedur
eistodiscov
eratleastonesubst
it
uti
ont
hatcausest
wol
i
ter
als
tomatch.Usual
ly
,ift
hereisonesuchsubsti
tuti
onther
earemany

In
Unifi
cational gori
thm eachl i
teralisrepresentedasal ist
,wher ef i
rstelementi sthenameofa
predicateandt her emaini ngel ementsar eargument s.Thear gumentmaybeasi ngleel ement
(atom)ormaybeanot herl ist.
Theuni ficat
ional gori
thm r ecursiv
elymat chespai rsofel ement s,onepai ratat i
me.Themat chi
ng
rul
esar e:
• Di f
ferentconst ant s,functi
onsorpr edi cat
escannotmat ch,wher easi denti
cal onescan.
• Av ariabl ecanmat chanotherv ari
able,anyconst antoraf uncti
onorpr edicate
expression, subjecttothecondi tionthatthef unct
ionor[ pr
edi cateexpr essionmust
notcont ainanyi nstanceoft hev ari
ablebeingmat ched( ot herwiseitwillleadt o
infini
te
r
ecur si
on) .
MODULE-
2

• Thesubst i
tut
ionmustbeconsi
stent.Subst
it
uti
ngyf
orxnowandt
henzf
orxl
ater
i
sinconsi
stent
.(asubst
it
uti
onyforxwr i
ttenasy/x)

Exampl e:
Supposewewantt ouni fyp(X,Y,Y)wi
thp(a,
Z,b).I
nit
i yEi
al
l s
{p(X,
Y,Y)=p( a,
Z,b)}.
Thef i
rstt i
met hrought hewhi leloop,Ebecomes{ X=a,
Y=Z,Y=b}.SupposeX=a
i
ssel ectednext .
ThenSbecomes{ X/a}andEbecomes{ Y=Z,Y=b}.
SupposeY=Zi sselected.
ThenYi sr eplacedbyZi nSandE.
Sbecomes{ X/a,
Y/Z}andEbecomes{ Z=b}.
Final
lyZ=bi sselected,Zi sreplacedbyb,Sbecomes{ X/
a,Y/b,
Z/b},and
Ebecomesempt y.
Thesubst i
tuton{
i X/a,Y/b,Z/
b}i sret
urnedasanMGU.
Unif
ication:
MODULE-
2

Resolut
ioni nPredicat
eLogi c
• Twol i
teralsarecont r
adictor
yifonecanbeuni fi
edwiththenegati
onoftheot her
.
• Forexampl eman( x)andman( Himalayas)ar
econtradi
ctor
ysinceman( x)andman( Himal
ay as
)canbeuni f
ied.
• I npredicatelogicunifi
cati
onalgori
thm isusedtolocat
epairsofli
ter
alsthatcancel
out.
• I ti
simpor tantthatiftwoinstancesofthesamev ari
ableoccur
,thentheymustbegi venident
ical
substi
tutions

Pr
ovet
hatMar
cushat
esceaserusi
ngr
esol
uti
on.
MODULE-
2

Exampl
e:
(
a)Convertallt
heabov estatement
sinto
Johnlikesallki
ndsoffood.
predi
catelogic
Applesarefood.
(
b)Showt hatJohnl i
kespeanutsusi
ngbackchaining
Chickenisfood.
(
c)Convertthestatementsintocl
auseform
Anythinganyoneeatsanditisnotki
l
ledi
s (
d)UsingResoluti
onshowt hat“
Johnli
kespeanuts” f
ood.
Bil
leatspeanutsandissti
llal
ive.
Sheeat sever
y t
hingbi
l
leats
Answer:
(a)Pr
edicat
eLogi
c:

(
b)Backwar
dChai
ningPr
oof
:
 MODULE-
2

(
c)Cl
auseFor
m:

(
d) Resol
uti
onPr
oof
:

Quest
ionsAnswer
ing
Wecanalsouset
hepr oofpr
ocedur
etoanswerquest
ionssuchas“
whot
ri
edt
oassassi
nat
eCaesar
”
bypr
ovi
ng:
– Tryassassi
nat
e(y,
Caesar
).
 MODULE-
2

– Oncet hepr oofi

scompl eteweneedt ofindoutwhatwassubst i
tut
ionwasmade
fory.
Weshowhowr esol ut
ioncanbeusedt oanswerfil
l-
in-
the-
blankquesti
ons,suchas"Whendid
Marcusdie?"or"Whot r
iedtoassassinatearul
er?”Answeringthesequest
ionsinv
olvesfi
ndi
nga
knownstatementt hatmat chesthetermsgiveninthequestionandthenrespondi
ngwi t
h
anot
herpieceoft hesamest at
ementt hatf
il
lst
hesl otdemandedbyt hequesti
on.

Natur
alDeducti
on:
Refer
(5.
5)pageno.164-
165
MODULE-
2

Repr
esent
ingKnowl
edgeusi
ngRul
es

Pr
ocedur
alv
ersusDecl
arat
ionKnowl
edge

Decl
arat
iveKnowl
edge Pr
ocedur
alKnowl
edge
Fact
ual i
nfor
mationstor
edinmemor
yand theknowl edgeofhowt oper f
orm, orhowt o
knownt obestati
cinnatur
e. operate
knowledgeoffactsorconcept
s askilloract i
onthaty ouar ecapabl eof
performi ng
knowledgeaboutt hatsomet hi
ngt r
ueorfalse Knowl edgeabouthowt odosomet hi
ngto
reachapar ti
cul
arobj ectiveorgoal
knowledgeisspecifiedbuthowt ouseto control i
nformati
oni .
e.,necessar ytousethe
whichthatknowledgei stobeputi snotgiv
en knowl edgei sconsideredt obeembeddedi n
theknowl edgeit
self
E.g.
:concepts,f
acts, pr
opositi
ons,asser
ti
ons, E.g.
: procedures,rules,strategies,agendas,
semanticnets… model s
Iti
sexpli
citknowledge( descri
bing) Iti
st acitknowledge( doi ng)

Thedecl
arativerepresentat i
oni soneinwhicht heknowl edgeisspeci
fi
edbuthowtousetowhicht
hat
knowl
edgei stobeputi snotgi ven.
• Decl arati
veknowl edgeanswer sthequest ion'Whatdoyouknow? '
• Iti syourunder standingoft hi
ngs,ideas,orconcepts.
• Inot herwor ds, declarati
veknowledgecanbet houghtofasthewho,what
,when,and
wher eofinformat ion.
• Decl arati
veknowl edgei snormall
ydi scussedusingnouns,l
iket
henamesofpeople,
places,orthingsordat esthateventsoccur r
ed.

Thepr
oceduralr
epresentati
onisonei nwhichthecont r
olinf
or mati
oni.e.
,necessar
ytouset
he
knowl
edgeisconsideredtobeembeddedi ntheknowledgeitself.
• Pr oceduralknowledgeanswerst hequest
ion'Whatcany oudo?'
• Whi ledeclarati
veknowledgeisdemonst r
atedusingnouns,
• Pr oceduralknowledgereli
esonact i
onwor ds,orverbs.
• Itisaper son'sabil
i
tytocarryoutacti
onstocompl eteatask.

Thereal
diff
erencebetweendecl
arat
iveandpr
ocedur
alv
iewsofknowl
edgel
i
esi
nwhi
cht
hecont
rol
i
nfor
mat i
onpresides.

Exampl
e:
MODULE-
2

Thest
at s1,
ement 2and3ar
epr
ocedur
alknowl
edgeand4i
sadecl
arat
iveknowl
edge.

For
war
d&Backwar
dReasoni
ng
Theobj ectofasearchprocedureistodi scoverapaththroughaprobl
em spacef
rom ani
nit
ial
confi
gur at
iont
oagoalst ate.Thereareact ual
lyt
wodi recti
onsi
nwhichsuchasearchcould
proceed:
• ForwardReasoning,
 f r
om t hestar
tstat
es
 LHSr ulemustmat chwi t
hini
ti
alst
at e
 Eg: A→ B, B→C=>A→C
• Backwar
dReasoning,
 fr
om thegoalstat
es
 RHSrulesmustmat chwi
thgoal
stat
e
 Eg:8-
Puzzl
ePr obl
em

I
nbot hthecases,t
hecontr
olstrategyi
sitmustcausemot
ionandsyst
emati
c.Thepr
oduct
ion
system modelofthesear
chpr ocessprovi
desaneasywayofviewi
ngfor
wardandbackward
reasoni
ngassymmet r
icpr
ocesses.

Consi
dertheprobl
em ofsol
vi
ngaparti
cul
arinst
anceoft
he8-
puzzl
epr
obl
em.Ther
ulest
obe
usedforsol
vi
ngthepuzzl
ecanbewr
it
tenas:

Reasoni
ngFor war dfrom I
niti
alState:
 Begi nbuildingatreeofmov esequencest hatmightbesol vedwithiniti
alconfi
gur
ati
onatroot
ofthetree.
 Gener atethenex tlevelofthetreebyf indingallt
her ul
eswhosel eftsidesmat cht
heroot
nodeandusi ngtheirr
ightsidest ocreatet henewconf i
gurati
ons.
 Gener atethenex tlevelbytakingeachnodegener at
edatthepr evi
ousl evelandappl
yi
ngtoit
al
lofther uleswhosel eftsidesmat chi t
.
 Cont i
nueunt i
laconf i
gurati
ont hatmat chest hegoalstat
eisgener ated.

Reasoni
ngBackwardf
rom Goal
Stat
e:
 Beginbui
ldi
ngatr
eeofmov esequencest
hatmi
ghtbesol
vedwi
thgoal
conf
igur
ati
onatr
oot
oft
hetr
ee.
MODULE-
2

 Gener at
ethenextl eveloft het r
eebyf i
ndingal lt
heruleswhoser i
ghtsidesmat cht heroot
node.Thesear eallther ul
est hat,i
fonlywecoul dapplythem,woul dgener atet
hest atewe
want.Uset hel
eftsidesoft her ul
estogener atethenodesatt hi
ssecondl ev
el oft
het r
ee.
 Gener at
ethenextlevelofthet reebytakingeachnodeatt heprevi
ousl ev
elandf i
ndingallthe
rul
eswhoser i
ghtsidesmat chi t
.Thenuset hecorr
espondingleftsidestogeneratet henew
nodes.
 Continueunti
lanodet hatmat chestheini
ti
al stat
eisgenerated.
 Thismet hodofreasoni ngbackwar dfrom thedesi r
edfinalstateisoftencalledgoaldir
ected
reasoning.

Toreasonforward,t
hel ef
tsides(precondi
t i
ons)arematchedagainstthecurr
entstat
eandthe
ri
ghtsides(resul
ts)areusedt ogener at
enew nodesunt i
lt hegoalisreached.Toreason
backward,t
her i
ghtsidesaremat chedagai nstthecur
rentnodeandt heleftsi
desareusedto
generat
enewnodesr epresenti
ngnewgoal stat
estobeachieved.

Thefol
l
owing4f actorsinfluencewhet heri ti
sbet t
ertoreasonFor wardorBackwar d:
1.Aret heremor epossi bl
est artst atesorgoalst at
es?Wewoul dliket omov ef r
om t he
smal l
ersetofst at est othelarger( andt huseasiertofind)setofstates.
2.Inwhi chdi rect
ionbr anchingf actor( i.
e,aver
agenumberofnodest hatcanber eached
dir
ect l
yf r
om asi nglenode)i sgr eater?Wewoul dliketopr oceedi nthedirecti
onwi th
lowerbr anchingf actor.
3.Willthepr ogram beusedt ojusti
fyi tsreasoni
ngpr ocesst oauser?Ifso, i
tisi
mpor tantto
proceedi nt hedirecti
ont hatcor respondsmor ecloselywiththewayt heuserwi l
lthi
nk.
4.Whatki ndofev enti sgoi ngt otriggerapr oblem-solvingepisode?Ifitisarri
valofanew
fact,forwar dreasoni ngmakessense.I fiti
saquer ytowhi char esponseisdesi r
ed,
backwar dr easoningi smor enat ur al.

Backward-
ChainingRul eSy stems
 Backwar d-chai ningr ul
esyst
emsar egoodforgoal-
dir
ectedproblem solving.
 Forexampl e,aquer ysyst
em wouldprobablyusebackwardchainingt oreasonaboutand
answeruserquest i
ons.
 Uni f
icati
ont r
iest of indasetofbi
ndingsforvari
abl
estoequatea( sub)goalwit
htheheadof
somer ul
e.
 Medi calexper tsy st
em, di
agnosti
cproblems

For
ward-Chai ningRuleSy stems
 Insteadofbei ngdirectedbygoals,wesomet i
meswantt obedi r
ectedbyi ncomi
ngdat a.
 Forexampl e,supposey ousenseseari
ngheatneary ourhand.Youar el
ikelytoj
erkyourhand
away .
 Rul est hatmat chdumpt hei
rri
ght-
handsideassert
ionsintothestateandt hepr
ocessr epeat
s.
 Mat chingisty pi
call
ymor ecomplexforforward-
chaini
ngsy st
emst hanbackwardones. 
Sy nthesi ssystems–Desi gn/
Confi
gurat
ion
MODULE-
2

ExampleofTypical For
wardChaining
Rules
1)Ifhotandsmokyt henADDf i
re
2)Ifalarm_ beepst
henADDsmoky
3)Iffi
rethenADDswi tchon_spr
inkl
es
Facts
1)alarm_ beeps(gi
ven)
2)hot( gi
v en)
………

(
3)smoky(from F1byR2)
(
4)fi
re(f
rom F2,F4byR1)
(
5)swit
ch_on_spri
nkl
ers(
from F2byR3)

Exampl
eofTypi
cal
BackwardChai
ningGoal
:
Shoul
dIswi
tchonspri
nkl
ers?

Combi ni
ngForwar dandBackwar dReasoni ng
Somet i
mescer tainaspect sofapr oblem ar ebesthandl edv i
af orwardchai ningandot her
aspectsbybackwar dchai ni
ng.Consideraf or
ward-chai
ningmedicaldiagnosi
spr ogram.Itmight
accepttwentyorsof actsaboutapat i
ent’scondi t
ionthenforwar
dchainont hoseconcept stotry
todeducet henatureand/orcauseoft hedi sease.
Nowsupposet hatatsomepoi nt
,theleftsideofar ulewasnearl
ysat i
sfi
ed–ni neoutoft enofit
s
precondit
ionsweremet .I
tmightbeef f
icienttoapplybackwar dr
easoningtosatisfythetenth
precondit
ioninadirectedmanner ,r
athert hanwaitforforwar
dchainingtosupplyt hefactbyacci
dent
.

Whetheritispossi bletouset hesamerulesforbot hforwardandbackwar dreasoningalso

dependsont hef or
m ofther ulesthemsel
ves.Ifbot hl
eftsidesandr i
ghtsidescontainpure
assert
ions,t
henf orwardchainingcanmatchassertionsontheleftsi
deofar uleandaddt othe
stat
edescr i
ptiontheassert
ionsont heri
ghtside.Butifarbi
tr
aryprocedur
esar eal
lowedast he
ri
ghtsidesofr ul
esthentheruleswill
notbereversi
ble.

Logi
cPr
ogr
ammi
ng
 Logi
cProgr
ammi ngisaprogrammingl
anguageparadigm i
nwhi chlogi
cal
assert
ionsare
vi
ewedasprograms.
 Ther
eareseverallogi
cprogrammingsy
stemsinuset oday,
themostpopul arofwhichi
s
PROLOG.
 APROLOGpr ogram isdescr
ibedasaseri
esoflogi
calassert
ions,eachofwhichisaHorn
cl
ause.
 AHornclausei
sacl
auset
hathasatmostoneposi
ti
vel
i
ter
al.Thusp,p q,
p qar
eal
l
Hor
nclauses.
MODULE-
2

Pr
ogramswritt
eni npur
ePROLOGar ecomposedonl yofHor
nClauses.
Sy
ntact
icDi
fferencebetweent helogi
candt hePROLOGr epr
esent
ati
ons,i
ncludi
ng:
 Inl ogic,v
ari
ablesar eexpli
citl
yquanti
fi
ed.InPROLOG,quanti
fi
cati
onispr
ovi
dedi
mpl
i
cit
ly
bythewayt hev ar
iablesareinter
pret
ed.
oThedist
inct
ionbet
weenvari
ablesandconst
ant
sismadeinPROLOGbyhav
ingall
vari
abl
esbeginwi t
huppercaselet
ter
sandallconst
ant
sbegi
nwit
hlowercase
let
ter
s.
 Inlogi
c,ther
eareexpl
ici
tsy
mbolsf
orand()andor()
.InPROLOG,t
her
eisanexpl
i
cit
symbolforand(
,)
,butt
herei
snonef
oror
.
 I
nlogi
c,impli
cat
ionsoftheform“pimpli
esq”aswr
it
tenaspq.I
nPROLOG,t
hesame
i
mpli
cat
ioniswri
tten“
backward”asq:-
p.

Exampl
e:

Thefi
rsttwooft hesedi ff
erencesari
senatural
lyfrom thefactt
hatPROLOGprogr amsar eactual
l
y
set
sofHor nCl ausest hathavebeentransf
ormedasf oll
ows:
1.IftheHor nCl ausecont ai
nsnonegativeli
terals(i
.e.
,i
tcont
ainsasi
ngl
eliteralwhichis
posit
ive),t
henl eaveitasiti
s.
2.Ot herwise,returntheHornclauseasani mplicati
on,combi
ningal
loft
henegat iveli
ter
als
i
ntotheant ecedentoft heimpli
cati
onandl eavingthesi
ngl
eposit
ivel
i
teral (
ift
hereisone)
astheconsequent .

Thi
sprocedur
ecausesacl ause,whi
chor iginal
lyconsist
edofadi
sjunct
ionofl
i
terals(al
lbut
oneofwhichwerenegati
ve),tobetransformedt osinglei
mpli
cat
ionwhoseantecedenti
sa
conj
unct
ionof(whatarenowposi t
ive)li
terals.
MODULE-
2

Mat
chi
ng
Wedescr i
bedtheprocessofusi ngsear
chtosol
veprobl
emsastheappli
cat
ionofappr
opri
ate
rul
est
oi ndiv
idualpr
oblem st
atestogenerat
enewst
atestowhi
chther
ulescanthenbeappl
ied
andsoforthunti
lasoluti
onisfound.

Howweex t
ractfr
om theent
ir
ecoll
ect
ionofrulesthoset
hatcanbeappl
iedatagivenpoint
?To
dosor equi
ressomeki ndofmatchi
ngbetweent hecurr
entstat
eandtheprecondit
ionsofthe
rul
es.Howshoul dthi
sbedone?Theanswert othi
squesti
oncanbecrit
icalt
othesuccessofa
rul
ebasedsy st
em.
MODULE-
2

Amor ecompl exmat chi

ngi sr equi
redwhent hepreconditi
onsofr ulespeci
fyrequir
edpropert
ies
thatarenotstatedexpli
cit
lyint hedescr i
pti
onoft hecurrentstate.Int
hiscase,aseparatesetof
rul
esmustbeusedt odescr ibehowsomepr opertiescanbei nferredfr
om others.Anevenmor e
complexmat chi
ngpr ocessi sr equiredifrulesshoul dbeappl iedandi ftheirprecondit
ion
approximatel
ymat chthecur rentsituati
on.Thisisoftenthecasei nsi
tuati
onsinvolv
ingphysi
cal
descri
ptionsofthewor l
d.

I
ndexi
ng
Onewayt oselectappl i
cabler ul
esi st
odoasi mplesearchthoughal
ltherul
escompar i
ngeach
one’sprecondi
tiontot hecur rentstateandextr
acti
ngal lt
heone’sthatmatch.Therearetwo
probl
emswi ththissi
mpl esol uti
on:
i
. Thel argenumberofr uleswi l
lbenecessaryandscanningthroughal
loft hem atever
yst
ep
wouldbeineffi
cient.
i
i.It’
snotalway sobv i
ouswhet herarul
e’
sprecondi
ti
onsaresati
sfi
edbyapar t
icul
arst
ate.

Sol
uti
on:Inst
eadofsear
chi
ngt
hroughrul
esuset
hecur
rentst
ateasani
ndexi
ntot
her
ulesand
sel
ectthematchi
ngone’
simmediat
ely
.

Matchingprocessi
seasybutatthepr i
ceofcomplet
elackofgener
ali
tyi
nthest
atementoft
he
rul
es.Despi
tesomel i
mitat
ionsofthisappr
oach,I
ndexi
nginsomeformisver
yimport
antint
he
eff
ici
entoperati
onofr
ulebasedsystems.

Mat
chi
ngwi
thVar
iabl
es
Thepr oblem ofsel
ecti
ngapplicabl
er ulesi smademor edi
ff
icultwhenpr econdi
ti
onsar enot
stat
edasexactdescr i
pti
onsofpar ticularsituati
onsbutr at
herdescr ibepropert
iesthatthe
si
tuati
onsmusthav e.I
toftenturnsoutt hatdiscoveri
ngwhethert her
ei samat chbet weena
parti
cularsi
tuat
ionandtheprecondit
ionsofagi venr ul
emustitselfinv
olveasignif
icantsear
ch
process.

Backwar
d-chai
ningsystemsusuall
yusedepth-
fi
rstbackt
racki
ngtosel
ectindiv
idualrules,but
for
ward-
chaini
ng systems gener
all
y empl
oy sophi
sti
cat
ed conf
li
ctresol
ution str
ategies to
chooseamongt heappli
cabl
erul
es.

Whilei
tispossi
blet
oapplyuni
fi
cati
onrepeat
edlyovert
hecrossproductofpr
econdi
ti
onsandst
ate
descri
pti
onelement
s,i
tismoreeff
ici
enttoconsi
derthemany-manymat chpr
oblem,
inwhichmany
MODULE-
2

r
ulesar
ematchedagai
nstmanyel
ement
sint
hest
atedescr
ipt
ionsi
mul
taneousl
y.Oneef
fi
cientmany
-
manymatchalgor
it
hm i
sRETE.

RETEMat chingAl
gori
thm
Thematchingconsist
sof3parts
1.Rul es&Producti
ons
2.Wor ki
ngMemor y
3.InferenceEngi
ne
Theinf
erenceEngineisacycl
eofpr
oduct
ionsy
stem whi
chi
smat
ch,
sel
ect
,execut
e.

INFERENCEENGI NE
Theabov ecyclei
sr epeatedunti
lnor ul
esareputintheconfl
i
ctsetoruntilstoppi
ngcondit
ionis
reached.Inordertov er
if
ysev er
alconditi
ons,iti
sat i
meconsumi ngprocess.Toeliminat
et he
needt operf
ormt housandsofmat chesofcyclesoneff
ecti
vematchingalgori
thm i
scall
edRETE.

TheAlgor
it
hm consi
stsoftwoSteps.
1.Wor ki
ngmemor ychangesneedtobeexamined.
2.Groupingrul
eswhichsharethesamecondi
ti
on&l i
nki
ngt
hem t
othei
rcommont
erms.

RETEAl gorit
hm i smany -matchal gorithm ( I
nwhi chmanyr ulesar emat chedagai nstmany
el
ements) .RETE uses f orward chai ning systems whi ch gener all
y empl oy ee sophi sti
cated
confl
i
ctr esol
utionst rategiest ochooseamongappl icabler ules.RETEgai nsef f
ici
encyf r
om 3
majorsources.
1.RETEmai ntai
nsanet wor kofr ulecondi tionandi tuseschangesi nt hest ate
descriptiont odet erminewhi chnew r ulesmi ghtappl y.Ful lmat chingi sonl y
pursuedf orcandidatest hatcouldbeaf fectedbyi ncomi ng/out goingdat a.
2.St r
uct uralSimilari
tyinrul es:RETEstorest her ul
essot hattheyshar estructuresin
memor y,setofcondi ti
onst hatappearinsev er
al r
ulesaremat chedoncef orcy cle.
3.Per sistenceofv ari
ablebi ndingconsist
ency .Whi l
ealltheindiv idualprecondi t
ions
ofther ulemi ghtbemet ,theremaybev ariabl
ebi ndingconf l
ict sthatprev entthe
rul
ef rom f i
ri
ng.
MODULE-
2

canbemini
mized.RETEr
emember si
tspr
evi
ouscal
cul
ati
onsandi
sabl
etomer
ge
newbi
ndi
nginf
ormati
onef
fi
cient
ly.

Appr
oxi
mat
eMat
chi
ng:
Rulesshouldbeappli
edifthei
rprecondit
ionsappr
oximatel
ymatchtothecur
rent
si
tuati
onEg: Speechunderst
andingprogram
Rules:Adescri
pti
onofaphy sicalwavef
ormt ophones
Phy si
calSi
gnal:
diff
erenceinthewayindi
vidual
sspeak,
resul
tofbackgr
oundnoi
se.

Confli
ctResol
ution:
Whensev eral
rulesmat chedatoncesuchasi tuati
oniscal
ledconfl
ictr
esoluti
on.Ther
ear
e3
approachestothepr obl
em ofconf l
ictresol
uti
oni npr
oducti
onsy st
em.
1.Pr efer
encebasedonr ul
emat ch:
a.Phy si
calorderofrulesinwhicht heyar
epresentedtothesystem
b.Pr iori
tyisgivent
or ulesintheorderinwhichtheyappear

2.Pr
efer
encebasedont heobj ectsmatch:
a.Considersimpor t
anceofobjectst hataremat ched
b.Considerstheposi ti
onoft hemat chabl eobjectsi
ntermsofLongTer m
Memor y(LTM)&Shor tTerm Memor y(STM)
LTM: Storesasetofr ul
es
STM ( WorkingMemor y):Ser
vesasst orageareaforthefact
sdeducedbyr ul
esinlong
ter
m memor y
3.Pr
efer
encebasedont heAct ion:
a.Onewayt odoi sf i
ndal lt
herulest empor ar
il
yandexami netheresul
tsofeach.Usi
nga
Heuristi
cFunct ionthatcanev al
uat eeachoft heresul
ti
ngstatescomparethemer i
tsof
theresultandt henselecttheprefer r
edone.

Sear
chCont
rolKnowledge:
 I
tisknowledgeaboutwhichpathsaremostl
ikel
ytoleadqui
ckl
ytoagoal
stat
e
 Sear
chCont r
olKnowledgerequi
resMetaKnowledge.
 I
tcantakemanyf or
ms.Knowl edgeabout
whi
chstat
esar
emor
epr
efer
abl
e
t
oother
s.
whi
chr
ulet
oappl
yinagi
vensi
tuat
ion
t
heOr
deri
nwhi
cht
opur
suesubgoal
s
usef
ulSequencesofr
ulest
oappl
y.