Interpretability and Equivalence in Quantified Equilibrium Logic
- 格式:pdf
- 大小:111.56 KB
- 文档页数:12
InterpretabilityandEquivalenceinQuantifiedEquilibriumLogic
DavidPearce1⋆andAgust´ınValverde2⋆⋆1ComputingScienceandArtificialIntelligence,
Univ.ReyJuanCarlos,(M´ostoles,Madrid),Spain.davidandrew.pearce@urjc.es2Dept.ofAppliedMathematics,Univ.ofM´alaga,Spain.
a
⋆PartiallysupportedbyCICyTprojectsTIC-2003-9001-C02andTIN2006-15455-CO3.
⋆⋆PartiallysupportedbyCICyTprojectTIC-2003-9001-C01,TIN2006-15455-CO1andJunta
deAndaluciaprojectTIC-11550DavidPearceandAgust´ınValverdeworktotheoriesformulatedinfirst-orderlogicbyusingquantifiedequilibriumlogic.Westartfollowing[36]byconsideringformalandinformaldesideratathataconceptofsynonymyshouldfulfil.WethenintroduceQELasalogicalfoundationforASPandextensions,andpresentthemaincharacterisationofstrongequivalencefrom[23].In§4weproposeastrongconceptofequivalenceorsynonymyfortheoriesinquanti-fiedequilibriumlogic,givedifferentcharacterisationsofit,andshowthatitfulfilstheadequacyconditionsdiscussedin2.Themaincharacteristicsofthisconceptareasfol-lows.TheoriesΠ1andΠ2indistinctlanguagesaresaidtobesynonymousifeachisbijectivelyinterpretableintheother.Inparticular,thismeansthatthereisfaithfulinter-pretationofeachtheoryintheotherandaone-onecorrespondencebetweenthemodelsofthetwotheories.Thiscorrespondencepreservesthepropertyofbeinganequilib-riummodeloranswerset.Inaddition,Π1hasadefinitionalextensionsthatisstronglyequivalenttoadefinitionalextensionofΠ2.Moreover,inasuitablesense,Π1andΠ2
remainequivalentorsynonymouswhenextendedbytheadditionofnewformulas.
2SynonymousTheoriesWhatdoesitmeantosaythattwoprogramsortheories,Π1andΠ2,indifferentlan-guages,L1andL2,aresynonymous?WeconsidersixdesiderataD1-D6thatwebelieveshouldbesatisfiedbyanybasicconceptofsynonymy.D1-D3andD5-D6arequitegen-eralandseemtobeapplicabletoanytheoriesdescribingormodellingsomeknowledgedomain;D4takesaccountofthespecialnatureofanonmonotonicorlogicprogram-mingsystem.
D1.Translatability.ThelanguageL1ofΠ1shouldbetranslatable,viaamapping,sayτ,intothelanguageL2ofΠ2.Thetranslationτshouldbeuniform,sowerequireittoberecursive.D2.Semanticcorrespondence.ThereshouldbeacorrespondingcorrelationbetweenthestructuresofL1andL2,inparticularamappingFfromL2-structurestoL1-structuresthatrespectsthetranslationτinthesensethatforanyL2-structureIandL1-formulaϕ,F(I)|=ϕ⇔I|=τ(ϕ).
D3.Equivalence.Undertranslation,Π1andΠ2shouldbeinanobvioussenseequiva-lent.D4.Intendedmodels.Thesemanticcorrelationshouldrespecttheintendedmodelsofthetwotheories.Inthepresentcasethismeanspreservingthepropertyofbeinganequilibriummodeloranswerset:MisananswersetΠ2iffF(M)isananswersetofΠ1.D5.Idempotence.IfΠ1issynonymouswithΠ2underthepreviousmappings,thenundercorrespondingmappings,sayτ′andF′,Π2shouldbesynonymouswithΠ1.D6.Robustness.Π1andΠ2shouldremainsynonymousundertheadditionofnewformulas,ie.foranyΣ,Π1∪ΣshouldbesynonymouswithΠ2∪τ(Σ),similarlyΠ2∪ΠwithΠ1∪τ′(Π).
Thefirsttwoconditionsprovidethecornerstoneofanyformalapproachtointerthe-oryrelations.DifferentkindsofrelationsbetweentheoriesareobtainedbyspecifyingInterpretabilityandEquivalenceinQuantifiedEquilibriumLogic51additionalconditionsthatthemappingsshouldsatisfy(seeeg[30,34,41]).Inthiscasewerequire(D3,D5)thattheoriesareinanobvioussenseequivalentoncethetranslationmapsaremadeavailable.Sincewearedealingherewithlogicprogramsandtheirgen-eralisationsintheASPframework,wecanunderstandthiseitherintheweakersenseofhavingthesameanswersets,orinthesenseofstrongequivalenceexplainedearlier.TheproblemisthatifwechoosetheweakervariantthenwehavevirtuallynohopetofulfilconditionD6whichrequiresthatthetheoriesremainequivalentwhenembeddedinanyrichercontext.Ontheotherhand,ifweinterpretD3tomeanthatundersuitabletranslationmanuals,Π1andΠ2arestronglyequivalent,thenwemayexpectthatΠ1
andΠ2remainsynonymouswhenextendedwithnewrules.
Perhapssomewhatsurprisinglyweshallapproachtheproblemofsynonymyviatheclassicaltheoryofinterpretations.Brieflyweshallsaythattheoriesaresynonymousifeachisfaithfullyinterpretedintheotherinsuchawaythattheinterpretationsareidempotent(seebelow);thisisbasicallythestandardapproachfollowedinclassicalpredicatelogic,seeeg.[4,40].Weadaptitheretothecaseofanonmonotonicsystembasedonanon-classicallogic.
3QuantifiedEquilibriumLogic(QEL)Equilibriumlogicforpropositionaltheoriesandlogicprogramswaspresentedin[31]asafoundationforanswersetsemanticsandextendedtothefirst-ordercasein[37,38]andinslightlymoregeneral,modifiedformin[39].Forasurveyofthemainpropertiesofequilibriumlogic,see[32].Usuallyinquantifiedequilibriumlogicweconsiderafullfirst-orderlanguageallowingfunctionsymbolsandweincludeasecond,strongnegationoperatorasoccursinseveralASPdialects.Forthepresentpurposeweconsiderthefunction-freelanguagewithasinglenegationsymbol,‘¬’.So,inparticular,weshallworkwithaquantifiedversionofthelogicHTofhere-and-there.Inotherrespectswefollowthetreatmentof[39].