人工智能的課件CH9InferenceinFOL

IX.InferenceinFirst-orderlogic

Autumn2012Instructor:WangXiaolongHarbinInstituteofTechnology,ShenzhenGraduateSchoolIntelligentComputationResearchCenter(HITSGS)IX.InferenceinFirst-orderlOutlineReducingfirst-orderinferencetopropositionalinferenceUnificationGeneralizedModusPonensForwardchainingBackwardchainingResolutionOutlineReducingfirst-orderinUniversalinstantiation(UI)Everyinstantiationofauniversallyquantifiedsentenceisentailedbyit:v

α

Subst({v/g},α) foranyvariablevandgroundtermgE.g.,xKing(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))Universalinstantiation(UI)EvExistentialinstantiation(EI)Foranysentenceα,variablev,andconstantsymbolkthatdoesnotappearelsewhereintheknowledgebase:v

αSubst({v/k},α)E.g.,x

Crown(x)

OnHead(x,John)yields:Crown(C1)

OnHead(C1,John) providedC1isanewconstantsymbol,calledaSkolemconstantExistentialinstantiation(EI)ReductiontopropositionalinferenceSupposetheKBcontainsjustthefollowing:xKing(x)Greedy(x)Evil(x)King(John)Greedy(John)Brother(Richard,John)Instantiatingtheuniversalsentenceinallpossibleways,wehave:King(John)Greedy(John)Evil(John)King(Richard)Greedy(Richard)Evil(Richard)King(John)Greedy(John)Brother(Richard,John)ThenewKBispropositionalized:propositionsymbolsare

King(John),Greedy(John),Evil(John),King(Richard),etc.ReductiontopropositionalinfReductioncontd.EveryFOLKBcanbepropositionalizedsoastopreserveentailment(AgroundsentenceisentailedbynewKBiffentailedbyoriginalKB)Idea:propositionalizeKBandquery,applyresolution,returnresultProblem:withfunctionsymbols,thereareinfinitelymanygroundterms,e.g.,Father(Father(Father(John)))Reductioncontd.EveryFOLKBcReductioncontd.Theorem:Herbrand(1930).IfasentenceαisentailedbyanFOLKB,itisentailedbyafinitesubsetofthepropositionalizedKBIdea:Forn=0to∞docreateapropositionalKBbyinstantiatingwithdepth(n)termsseeifαisentailedbythisKBProblem:worksifαisentailed,loopsifαisnotentailedTheorem:Turing(1936),Church(1936)EntailmentforFOLis

semidecidable(algorithmsexistthatsayyestoeveryentailedsentence,butnoalgorithmexiststhatalsosaysnotoeverynonentailedsentence.)Reductioncontd.Theorem:HerbrProblemswith

propositionalizationPropositionalizationseemstogeneratelotsofirrelevantsentences.E.g.,from:xKing(x)Greedy(x)Evil(x)King(John)yGreedy(y)Brother(Richard,John)itseemsobviousthatEvil(John),butpropositionalizationproduceslotsoffactssuchasGreedy(Richard)thatareirrelevantWithpk-arypredicatesandnconstants,therearep·nkinstantiations.ProblemswithpropositionalizaUnificationWecangettheinferenceimmediatelyifwecanfindasubstitutionθsuchthatKing(x)andGreedy(x)matchKing(John)andGreedy(y)θ={x/John,y/John}worksUnify(p,q)=θifSubst

(θ,p)=Subst

(θ,q)

p q θ

Knows(John,x) Knows(John,Jane) Knows(John,x) Knows(y,OJ) Knows(John,x) Knows(y,Mother(y)) Knows(John,x) Knows(x,OJ) UnificationWecangettheinfeUnificationWecangettheinferenceimmediatelyifwecanfindasubstitutionθsuchthatKing(x)andGreedy(x)matchKing(John)andGreedy(y)θ={x/John,y/John}worksUnify(p,q)=θifSubst

(θ,p)=Subst

(θ,q)

p q θ

Knows(John,x) Knows(John,Jane){x/Jane}Knows(John,x) Knows(y,OJ) Knows(John,x) Knows(y,Mother(y)) Knows(John,x) Knows(x,OJ) UnificationWecangettheinfeUnificationWecangettheinferenceimmediatelyifwecanfindasubstitutionθsuchthatKing(x)andGreedy(x)matchKing(John)andGreedy(y)θ={x/John,y/John}worksUnify(p,q)=θifSubst

(θ,p)=Subst

(θ,q)

p q θ

Knows(John,x) Knows(John,Jane){x/Jane}Knows(John,x) Knows(y,OJ) {x/OJ,y/John}Knows(John,x) Knows(y,Mother(y)) Knows(John,x) Knows(x,OJ) UnificationWecangettheinfeUnificationWecangettheinferenceimmediatelyifwecanfindasubstitutionθsuchthatKing(x)andGreedy(x)matchKing(John)andGreedy(y)θ={x/John,y/John}worksUnify(p,q)=θifSubst

(θ,p)=Subst

(θ,q)

p q θ

Knows(John,x) Knows(John,Jane){x/Jane}Knows(John,x) Knows(y,OJ) {x/OJ,y/John}Knows(John,x)Knows(y,Mother(y)){y/John,x/Mother(John)}Knows(John,x) Knows(x,OJ) UnificationWecangettheinfeUnificationWecangettheinferenceimmediatelyifwecanfindasubstitutionθsuchthatKing(x)andGreedy(x)matchKing(John)andGreedy(y)θ={x/John,y/John}worksUnify(p,q)=θifSubst

(θ,p)=Subst

(θ,q)

p q θ

Knows(John,x) Knows(John,Jane) {x/Jane}Knows(John,x) Knows(y,OJ) {x/OJ,y/John}Knows(John,x) Knows(y,Mother(y)) {y/John,x/Mother(John)}Knows(John,x) Knows(x,OJ) {fail}Standardizingaparteliminatesoverlapofvariables,e.g.,Knows(z17,OJ)UnificationWecangettheinfeUnificationTounifyKnows(John,x)andKnows(y,z),

θ={y/John,x/z}orθ={y/John,x/John,z/John}Thefirstunifierismoregeneralthanthesecond.Thereisasinglemostgeneralunifier(MGU)thatisuniqueuptorenamingofvariables.MGU={y/John,x/z}UnificationTounifyKnows(JohnTheunificationalgorithmTheunificationalgorithmTheunificationalgorithmTheunificationalgorithmGeneralizedModusPonens(GMP)p1',p2',…,pn',(p1

p2

…

pn

q) Subst(θ,q)p1'isKing(John) p1isKing(x)p2'isGreedy(y) p2isGreedy(x)θis{x/John,y/John} qisEvil(x)Subst(θ,q)isEvil(John)GMPusedwithKBofdefiniteclauses(exactlyonepositiveliteral)AllvariablesassumeduniversallyquantifiedwhereSubst(θ,pi‘)=Subst(θ,pi)foralliGeneralizedModusPonens(GMP)SoundnessofGMPNeedtoshowthatp1',…,pn',(p1

…

pn

q)╞Subst(θ,q)

providedthatSubst(θ,pi‘)=Subst(θ,pi)foralliLemma:Foranysentencep,wehavep

╞Subst(θ,q)

byUI(p1

…pn

q)╞Subst(θ,(p1

…pn

q))=(Subst(θ,p1)

…Subst(θ,pn)

Subst(θ,q))p1',…,pn'╞p1'…pn'╞Subst(θ,p1')

…Subst(θ,pn')

From1and2,Subst(θ,q)followsbyordinaryModusPonensSoundnessofGMPNeedtoshowtFOLdefiniteclausesDisjunctionsofliteralsofwhichexactlyoneispositive.Adefiniteclauseeitherisatomicorisanimplicationwhoseantecedentisaconjunctionofpositiveliteralsandwhoseconsequentisasinglepositiveliteral.Eg. King(x)

Greedy(x)Evil(x)

King(John) Greedy(y)Unlikepropositionalliterals,FOLliteralscanincludevariables(universallyquantified).NoteveryKBcanbeconvertedintoasetofdefiniteclauses.Butmanycan.FOLdefiniteclausesDisjunctioExampleknowledgebaseThelawsaysthatitisacrimeforanAmericantosellweaponstohostilenations.ThecountryNono,anenemyofAmerica,hassomemissiles,andallofitsmissilesweresoldtoitbyColonelWest,whoisAmerican.ProvethatCol.Westisacriminal.ExampleknowledgebaseThelawExampleknowledgebasecontd....itisacrimeforanAmericantosellweaponstohostilenations:American(x)Weapon(y)Sells(x,y,z)Hostile(z)Criminal(x)Nono…h(huán)assomemissiles,i.e.,xOwns(Nono,x)Missile(x):Owns(Nono,M1)Missile(M1)…allofitsmissilesweresoldtoitbyColonelWestMissile(x)Owns(Nono,x)Sells(West,x,Nono)Missilesareweapons:Missile(x)Weapon(x)AnenemyofAmericacountsas"hostile“:Enemy(x,America)Hostile(x)West,whoisAmerican…American(West)ThecountryNono,anenemyofAmerica…Enemy(Nono,America)Exampleknowledgebasecontd..ForwardchainingalgorithmForwardchainingalgorithmForwardchainingproofForwardchainingproofForwardchainingproofMissile(x)Weapon(x)Missile(x)Owns(Nono,x)Sells(West,x,Nono)Enemy(x,America)Hostile(x)ForwardchainingproofMissile(ForwardchainingproofAmerican(x)Weapon(y)Sells(x,y,z)Hostile(z)Criminal(x)ForwardchainingproofAmericanPropertiesofforwardchainingSoundandcompleteforfirst-orderdefiniteclausesDatalog=first-orderdefiniteclauses+nofunctionsFCterminatesforDataloginfinitenumberofiterationsMaynotterminateingeneralifαisnotentailedThisisunavoidable:entailmentwithdefiniteclausesissemidecidablePropertiesofforwardchainingEfficiencyofforwardchainingIncrementalforwardchaining:noneedtomatcharuleoniterationkifapremisewasn'taddedoniterationk-1matcheachrulewhosepremisecontainsanewlyaddedpositiveliteralForwardchainingiswidelyusedindeductivedatabasesEfficiencyofforwardchainingHardmatchingexampleColorable()isinferredifftheCSPhasasolutionCSPsinclude3SATasaspecialcase,hencematchingisNP-hardNote:Referenceto:JohnE.Hopcroft,RajeevMotwani,JeffereyD.Ullman,“Introductiontoautomatatheory,language,andcomputation”(2nd),Tsinghuauniversitypress,Addison-Wesley.Diff(wa,nt)Diff(wa,sa)Diff(nt,q)Diff(nt,sa)Diff(q,nsw)Diff(q,sa)

Diff(nsw,v)Diff(nsw,sa)

Diff(v,sa)Colorable()Diff(Red,Blue) Diff(Red,Green)Diff(Green,Red)Diff(Green,Blue)Diff(Blue,Red) Diff(Blue,Green)HardmatchingexampleColorable

Examplesoflongdistancerestriction

Examplesoflongdistancer

Inthew-n-grammodel,findingcharacterorwordscorrespondingtothespeechsyllableinput yi(一,疑,以,已,衣,億,依,易,醫(yī),...) zhi(只,之,直,知,制,指,紙,支,芝,...) piaoliangde(漂亮的) xiao(小,笑,消,削,銷,蕭,效,宵,曉,...) hua(話,花,化,畫,華,劃,滑,嘩,猾,...) mao(毛,冒,帽,貓,矛,卯,貌,茂,貿(mào),...).Inthew-n-grammodel,findiandtherelevantrules花

plant貓

animal一

number小

adj漂亮的

adj花

adjadj+animalanimaladj+plantplantnumber+只+animalanimalnumber+枝+plantplant.andtherelevantrules

Agoodexampleofrecursivenatureisnumber.AgroupofsimplifiedrulesfordescribingChinesenumberaregivenbelow:MX={一，二，三，四，五，六，七，八，九}MX0={零}MW={十,百,千,萬,億,兆}MWW={萬,億,兆}MH={好些,許多,若干,幾,兩}MX->MX0 (r1)MX0+MX0->MMX (r2)MX0+MMX->MMX (r3)MX+MW+MX->MX (r4)MX+MW+零+MX->MX (r5)MW+MWW->MW (r6)MWW->MW (r7)MX+MW->M (r8)

Agoodexampleofrecursive

十+MX->MS (r9)MS+MWW->M (r10)MS+MWW+MX->MX (r11)MX0+點(diǎn)+MX->M (r12)MX0+點(diǎn)+MMX->M (r13)MS+點(diǎn)+MX->M (r14)MS+點(diǎn)+MMX->M (r15)M+倍->MB (r16)MX0->M (r17)MMX->M (r18)MW->M (r19)MB->M (r20)MH->M (r21)MS->M (r22)

十+MX->MS (r9)BackwardchainingalgorithmSUBST(COMPOSE(θ1,θ2),p)=SUBST(θ2,SUBST(θ1,p))BackwardchainingalgorithmBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexamplePropertiesofbackwardchainingDepth-firstrecursiveproofsearch:spaceislinearinsizeofproofIncompleteduetoinfiniteloopsfixbycheckingcurrentgoalagainsteverygoalonstackInefficientduetorepeatedsubgoals(bothsuccessandfailure)fixusingcachingofpreviousresults(extraspace)WidelyusedforlogicprogrammingPropertiesofbackwardchaininLogicprogramming:PrologAlgorithm=Logic+ControlProgram=setofclauses=head:-literal1,…literaln.criminal(X):-american(X),weapon(Y),sells(X,Y,Z),hostile(Z).Depth-first,left-to-rightbackwardchainingAsetofbuilt-infunctionsforarithmeticetc.,e.g.,XisY*Z+3Built-inpredicatesthathavesideeffects(e.g.,inputandoutput predicates,assert/retractpredicates)Closed-worldassumption("negationasfailure")e.g.,givenalive(X):-notdead(X).alive(joe)succeedsifdead(joe)failsLogicprogramming:PrologAlgorPrologAppendingtwoliststoproduceathird: append([],Y,Y). append([X|L],Y,[X|Z]):-append(L,Y,Z).query: append(A,B,[1,2])?

answers: A=[]B=[1,2] A=[1]B=[2] A=[1,2]B=[]PrologAppendingtwoliststopResolution:briefsummaryFullfirst-orderversion:l1

···

lk,m1

···

mnSubst(θ,

l1

···

li-1

li+1

···

lk

m1

···

mj-1

mj+1

···

mn) whereUnify(li,mj)=θ.Thetwoclausesareassumedtobestandardizedapartsothattheysharenovariables.Forexample,Rich(x)

Unhappy(x)

Rich(Ken)Unhappy(Ken) withθ={x/Ken}ApplyresolutionstepstoCNF(KB

α);completeforFOLResolution:briefsummaryFullConversiontoCNFEveryonewholovesallanimalsislovedbysomeone:x[yAnimal(y)

Loves(x,y)][yLoves(y,x)]1.Eliminatebiconditionalsandimplicationsx[yAnimal(y)

Loves(x,y)][y

Loves(y,x)]2.Moveinwards:xp≡

xp,xp≡

xpx[y(Animal(y)

Loves(x,y))][yLoves(y,x)]x[yAnimal(y)

Loves(x,y)][yLoves(y,x)]x[yAnimal(y)

Loves(x,y)][yLoves(y,x)]ConversiontoCNFEveryonewhoConversiontoCNFcontd.Standardizevariables:eachquantifiershoulduseadifferentonex[yAnimal(y)

Loves(x,y)][zLoves(z,x)]

Skolemize:amoregeneralformofexistentialinstantiation.EachexistentialvariableisreplacedbyaSkolemfunctionoftheenclosinguniversallyquantifiedvariables:

x[Animal(F(x))

Loves(x,F(x))]

Loves(G(x),x)Dropuniversalquantifiers:[Animal(F(x))

Loves(x,F(x))]

Loves(G(x),x)Distributeover:[Animal(F(x))

Loves(G(x),x)][Loves(x,F(x))

Loves(G(x),x)]ConversiontoCNFcontd.StandaResolutionproof:definiteclausesResolutionproof:definiteclaResolutionproofexample2Theproblemis:

Everyonewholovesallanimalsislovedbysomeone. Anyonewhokillsananimalislovedbynoone. Jacklovesallanimals. EitherJackorCuriositykilledthecat,whoisnamedTuna. DidCuriositykillthecat?Resolutionproofexample2TheResolutionproofexample2contd.First,weexpresstheoriginalsentences,somebackgroundknowledge,andthenegatedgoalGinFOL: A. x[yAnimal(y)

Loves(x,y)][yLoves(y,x)] B. x[yAnimal(y)kills(x,y)][zLoves(z,x)] C. xAnimal(x)Loves(Jack,x) D. kills(Jack,Tuna)kills(Curiosity,Tuna) E. Cat(Tuna) F. xCat(x)Animal(x) G. kills(Curiosity,Tuna)Resolutionproofexample2conResolutionproofexample2contd.Second,converteachsentencetoCNF

A1. Animal(F(x))

Loves(G(x),x) A2. Loves(x,F(x))

Loves(G(x),x) B. Animal(y)

kills(x,y)

Loves(z,x) C. Animal(x)

Loves(Jack,x) D. kills(Jack,Tuna)kills(Curiosity,Tuna) E. Cat(Tuna) F. Cat(x)Animal(x) G. kills(Curiosity,Tuna)Resolutionproofexample2conResolutionproofexample2contd.TheresolutionproofthatCuriositykilledthecatisgivenbelow.Resolutionproofexample2conAssignmentsEx9.11AssignmentsEx9.11IX.InferenceinFirst-orderlogic

Autumn2012Instructor:WangXiaolongHarbinInstituteofTechnology,ShenzhenGraduateSchoolIntelligentComputationResearchCenter(HITSGS)IX.InferenceinFirst-orderlOutlineReducingfirst-orderinferencetopropositionalinferenceUnificationGeneralizedModusPonensForwardchainingBackwardchainingResolutionOutlineReducingfirst-orderinUniversalinstantiation(UI)Everyinstantiationofauniversallyquantifiedsentenceisentailedbyit:v

α

Subst({v/g},α) foranyvariablevandgroundtermgE.g.,xKing(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))Universalinstantiation(UI)EvExistentialinstantiation(EI)Foranysentenceα,variablev,andconstantsymbolkthatdoesnotappearelsewhereintheknowledgebase:v

αSubst({v/k},α)E.g.,x

Crown(x)

OnHead(x,John)yields:Crown(C1)

OnHead(C1,John) providedC1isanewconstantsymbol,calledaSkolemconstantExistentialinstantiation(EI)ReductiontopropositionalinferenceSupposetheKBcontainsjustthefollowing:xKing(x)Greedy(x)Evil(x)King(John)Greedy(John)Brother(Richard,John)Instantiatingtheuniversalsentenceinallpossibleways,wehave:King(John)Greedy(John)Evil(John)King(Richard)Greedy(Richard)Evil(Richard)King(John)Greedy(John)Brother(Richard,John)ThenewKBispropositionalized:propositionsymbolsare

King(John),Greedy(John),Evil(John),King(Richard),etc.ReductiontopropositionalinfReductioncontd.EveryFOLKBcanbepropositionalizedsoastopreserveentailment(AgroundsentenceisentailedbynewKBiffentailedbyoriginalKB)Idea:propositionalizeKBandquery,applyresolution,returnresultProblem:withfunctionsymbols,thereareinfinitelymanygroundterms,e.g.,Father(Father(Father(John)))Reductioncontd.EveryFOLKBcReductioncontd.Theorem:Herbrand(1930).IfasentenceαisentailedbyanFOLKB,itisentailedbyafinitesubsetofthepropositionalizedKBIdea:Forn=0to∞docreateapropositionalKBbyinstantiatingwithdepth(n)termsseeifαisentailedbythisKBProblem:worksifαisentailed,loopsifαisnotentailedTheorem:Turing(1936),Church(1936)EntailmentforFOLis

semidecidable(algorithmsexistthatsayyestoeveryentailedsentence,butnoalgorithmexiststhatalsosaysnotoeverynonentailedsentence.)Reductioncontd.Theorem:HerbrProblemswith

propositionalizationPropositionalizationseemstogeneratelotsofirrelevantsentences.E.g.,from:xKing(x)Greedy(x)Evil(x)King(John)yGreedy(y)Brother(Richard,John)itseemsobviousthatEvil(John),butpropositionalizationproduceslotsoffactssuchasGreedy(Richard)thatareirrelevantWithpk-arypredicatesandnconstants,therearep·nkinstantiations.ProblemswithpropositionalizaUnificationWecangettheinferenceimmediatelyifwecanfindasubstitutionθsuchthatKing(x)andGreedy(x)matchKing(John)andGreedy(y)θ={x/John,y/John}worksUnify(p,q)=θifSubst

(θ,p)=Subst

(θ,q)

p q θ

Knows(John,x) Knows(John,Jane) Knows(John,x) Knows(y,OJ) Knows(John,x) Knows(y,Mother(y)) Knows(John,x) Knows(x,OJ) UnificationWecangettheinfeUnificationWecangettheinferenceimmediatelyifwecanfindasubstitutionθsuchthatKing(x)andGreedy(x)matchKing(John)andGreedy(y)θ={x/John,y/John}worksUnify(p,q)=θifSubst

(θ,p)=Subst

(θ,q)

p q θ

Knows(John,x) Knows(John,Jane){x/Jane}Knows(John,x) Knows(y,OJ) Knows(John,x) Knows(y,Mother(y)) Knows(John,x) Knows(x,OJ) UnificationWecangettheinfeUnificationWecangettheinferenceimmediatelyifwecanfindasubstitutionθsuchthatKing(x)andGreedy(x)matchKing(John)andGreedy(y)θ={x/John,y/John}worksUnify(p,q)=θifSubst

(θ,p)=Subst

(θ,q)

p q θ

Knows(John,x) Knows(John,Jane){x/Jane}Knows(John,x) Knows(y,OJ) {x/OJ,y/John}Knows(John,x) Knows(y,Mother(y)) Knows(John,x) Knows(x,OJ) UnificationWecangettheinfeUnificationWecangettheinferenceimmediatelyifwecanfindasubstitutionθsuchthatKing(x)andGreedy(x)matchKing(John)andGreedy(y)θ={x/John,y/John}worksUnify(p,q)=θifSubst

(θ,p)=Subst

(θ,q)

p q θ

Knows(John,x) Knows(John,Jane){x/Jane}Knows(John,x) Knows(y,OJ) {x/OJ,y/John}Knows(John,x)Knows(y,Mother(y)){y/John,x/Mother(John)}Knows(John,x) Knows(x,OJ) UnificationWecangettheinfeUnificationWecangettheinferenceimmediatelyifwecanfindasubstitutionθsuchthatKing(x)andGreedy(x)matchKing(John)andGreedy(y)θ={x/John,y/John}worksUnify(p,q)=θifSubst

(θ,p)=Subst

(θ,q)

p q θ

Knows(John,x) Knows(John,Jane) {x/Jane}Knows(John,x) Knows(y,OJ) {x/OJ,y/John}Knows(John,x) Knows(y,Mother(y)) {y/John,x/Mother(John)}Knows(John,x) Knows(x,OJ) {fail}Standardizingaparteliminatesoverlapofvariables,e.g.,Knows(z17,OJ)UnificationWecangettheinfeUnificationTounifyKnows(John,x)andKnows(y,z),

θ={y/John,x/z}orθ={y/John,x/John,z/John}Thefirstunifierismoregeneralthanthesecond.Thereisasinglemostgeneralunifier(MGU)thatisuniqueuptorenamingofvariables.MGU={y/John,x/z}UnificationTounifyKnows(JohnTheunificationalgorithmTheunificationalgorithmTheunificationalgorithmTheunificationalgorithmGeneralizedModusPonens(GMP)p1',p2',…,pn',(p1

p2

…

pn

q) Subst(θ,q)p1'isKing(John) p1isKing(x)p2'isGreedy(y) p2isGreedy(x)θis{x/John,y/John} qisEvil(x)Subst(θ,q)isEvil(John)GMPusedwithKBofdefiniteclauses(exactlyonepositiveliteral)AllvariablesassumeduniversallyquantifiedwhereSubst(θ,pi‘)=Subst(θ,pi)foralliGeneralizedModusPonens(GMP)SoundnessofGMPNeedtoshowthatp1',…,pn',(p1

…

pn

q)╞Subst(θ,q)

providedthatSubst(θ,pi‘)=Subst(θ,pi)foralliLemma:Foranysentencep,wehavep

╞Subst(θ,q)

byUI(p1

…pn

q)╞Subst(θ,(p1

…pn

q))=(Subst(θ,p1)

…Subst(θ,pn)

Subst(θ,q))p1',…,pn'╞p1'…pn'╞Subst(θ,p1')

…Subst(θ,pn')

From1and2,Subst(θ,q)followsbyordinaryModusPonensSoundnessofGMPNeedtoshowtFOLdefiniteclausesDisjunctionsofliteralsofwhichexactlyoneispositive.Adefiniteclauseeitherisatomicorisanimplicationwhoseantecedentisaconjunctionofpositiveliteralsandwhoseconsequentisasinglepositiveliteral.Eg. King(x)

Greedy(x)Evil(x)

King(John) Greedy(y)Unlikepropositionalliterals,FOLliteralscanincludevariables(universallyquantified).NoteveryKBcanbeconvertedintoasetofdefiniteclauses.Butmanycan.FOLdefiniteclausesDisjunctioExampleknowledgebaseThelawsaysthatitisacrimeforanAmericantosellweaponstohostilenations.ThecountryNono,anenemyofAmerica,hassomemissiles,andallofitsmissilesweresoldtoitbyColonelWest,whoisAmerican.ProvethatCol.Westisacriminal.ExampleknowledgebaseThelawExampleknowledgebasecontd....itisacrimeforanAmericantosellweaponstohostilenations:American(x)Weapon(y)Sells(x,y,z)Hostile(z)Criminal(x)Nono…h(huán)assomemissiles,i.e.,xOwns(Nono,x)Missile(x):Owns(Nono,M1)Missile(M1)…allofitsmissilesweresoldtoitbyColonelWestMissile(x)Owns(Nono,x)Sells(West,x,Nono)Missilesareweapons:Missile(x)Weapon(x)AnenemyofAmericacountsas"hostile“:Enemy(x,America)Hostile(x)West,whoisAmerican…American(West)ThecountryNono,anenemyofAmerica…Enemy(Nono,America)Exampleknowledgebasecontd..ForwardchainingalgorithmForwardchainingalgorithmForwardchainingproofForwardchainingproofForwardchainingproofMissile(x)Weapon(x)Missile(x)Owns(Nono,x)Sells(West,x,Nono)Enemy(x,America)Hostile(x)ForwardchainingproofMissile(ForwardchainingproofAmerican(x)Weapon(y)Sells(x,y,z)Hostile(z)Criminal(x)ForwardchainingproofAmericanPropertiesofforwardchainingSoundandcompleteforfirst-orderdefiniteclausesDatalog=first-orderdefiniteclauses+nofunctionsFCterminatesforDataloginfinitenumberofiterationsMaynotterminateingeneralifαisnotentailedThisisunavoidable:entailmentwithdefiniteclausesissemidecidablePropertiesofforwardchainingEfficiencyofforwardchainingIncrementalforwardchaining:noneedtomatcharuleoniterationkifapremisewasn'taddedoniterationk-1matcheachrulewhosepremisecontainsanewlyaddedpositiveliteralForwardchainingiswidelyusedindeductivedatabasesEfficiencyofforwardchainingHardmatchingexampleColorable()isinferredifftheCSPhasasolutionCSPsinclude3SATasaspecialcase,hencematchingisNP-hardNote:Referenceto:JohnE.Hopcroft,RajeevMotwani,JeffereyD.Ullman,“Introductiontoautomatatheory,language,andcomputation”(2nd),Tsinghuauniversitypress,Addison-Wesley.Diff(wa,nt)Diff(wa,sa)Diff(nt,q)Diff(nt,sa)Diff(q,nsw)Diff(q,sa)

Diff(nsw,v)Diff(nsw,sa)

Diff(v,sa)Colorable()Diff(Red,Blue) Diff(Red,Green)Diff(Green,Red)Diff(Green,Blue)Diff(Blue,Red) Diff(Blue,Green)HardmatchingexampleColorable

Examplesoflongd