LOGICAL CONSIDERATIONS ON DEFAULT SEMANTICS 1

LOGICALCONSIDERATIONSONDEFAULTSEMANTICS1WilliamC.RoundsArticialIntelligenceLaboratoryUniversityofMichiganAnnArbor,[e-mail]-QiangZhangDepartmentofComputerScienceUniversityofGeorgiaAthens,[e-mail]’sdefaultrulesintoaconstructivemethodofbuildingmodels,nottheories.Toallowreasoninginrstordersystems,weequipstandardrst-orderlogicwitha(new)Kleene3-valuedpartialmodelsemantics.Then,usingourmethodology,weadddefaultstothissemanticsystem.Theresultisthatourlogicisanordinarymonotonicone,butitssemanticsisnownonmonotonic.Reiter’sextensionsnowappearinthesemantics,notinthesyntax.Asanapplication,weshowthatthissemanticsgivesapartialsolutiontotheconceptualproblemswithopendefaultspointedoutbyLifschitz[17],andBaaderandHollunder[2].Thesolutionisnotcomplete,chieybecauseinmakingthedefaultsmodel-theoretic,wecanonlyaddconjunctiveinformationtoourmodels.Thisisincontrasttodefaulttheories,whereextensionscancontaindisjunctiveformulas,andthereforedisjunctiveinformation.Ourproposaltotreattheproblemofopendefaultsusesasemanticnotionofnonmono-tonicentailmentforourlogic,relatedtotheideaof\onlyknowing.Ournotionis\onlyhav-inginformationgivenbyaformula.Wediscussthedierencesbetweenthisand\minimal-knowledgeideas.Finally,weconsidertheKraus-Lehmann-Magidor[14]axiomsforpreferentialconsequencerelations.Wendthatourconsequencerelationsatisesthemostbasicofthelaws,andtheOrlaw,butitdoesnotsatisfythelawofCut,northelawofCautiousMonotony.Wegiveintuitiveexamplesusingoursystem,ontheotherhand,whichonthesurfaceseemtoviolatethesetwolaws.Wemakesomecomparisons,usingourexamples,toprobabilisticinterpretationsforwhichtheselawsaretrue,andwecompareourmodelstothecumulativemodelsofKraus,Lehmann,andMagidor.Wealsoshowsucientconditionsforthelawstohold.Theseinvolvelimitingtheuseofdisjunctioninourformulasinonewayoranother.Weshowhowtomakeuseofthetheoryofcompletepartiallyorderedsets,ordomaintheory.WecanaugmentanyScottdomainwithadefaultset.WestateaversionofRe-iter’sextensionoperatoronarbitrarydomainsaswell.Thisversionmakesclearthebasic1VersionpresentedattheThirdInternationalSymposiumonArticialIntelligenceandMathematics,FortLauderdale,Fla,January1994.ResearchsupportedbyNSFgrantIRI-9120851.1order-theoreticnatureofReiter’sdenitions.Athree-variablefunctionisinvolved.Findingextensionscorrespondstotakingxedpointstwice,withrespecttotwoofthesevariables.Inthespecialcaseofprecondition-freedefaults,ageneralrelationonScottdomainsinducedfromthesetofdefaultsisshowntocharacterizeextensions.Weshowhowageneralnotionofdomaintheory,thelogicinducedfromtheScotttopologyonadomain,guidesustoacorrectnotionof\armablesentenceinaspeciccasesuchasourrst-ordersystems.Wealsoproveourconsequencelawsinsuchawaythattheyholdnotonlyinrst-ordersystems,butinanylogicderivedfromtheScotttopologyonanarbitrarydomain.Contentareas:Knowledgerepresentation,nonmonotonicreasoning,terminologicalrea-soning,mathematicalfoundations21IntroductionSincetheintroductionofnon-monotoniclogic(byMcDermott,Doyle,Reiter,McCarthy,Moore,andothers),mucheorthasbeenspentonndingsemanticalsystemsfordieringformsofnonmonotoniclogic.Thereisbynowconsiderableagreementthatmodelsforanonmonotoniclogicshouldbeorderedbysomecriterionof\preference,sothatformulascanbevalidinall\preferredmodelsinsteadofallmodels.Thatwayonecanbelieveinthevalidityofaformula,thoughitisnotinfactvalid.ThiswayofunifyingthesemanticsofdieringlogicswasinitiatedbyShoham[28].Onelogic,foralongtime,resistedattemptstoprovideitwithapreferentialmodelsemantics:Reiter’sdefaultlogic[22].Etherington[9]gaveapreferentialsemantics,involvingsetsofrst-ordermodelsratherthansimplemodels.Othermodeltheoriesbynowareknown.Manyofthesecomefromothernonmonotoniclogicsbymeansofatranslationofdefaulttheoriestotheotherlogics.Thearticle[26]givesagoodproposal,aswellasanoverviewofotherproposals,includingLinandShoham[19]andLifschitz[18].Ourapproachdiersfromalloftheaboveproposals.WeregardReiter’sdefaultsystemsassemantic,notsyntacticnotions.Ourpreferencerelationispurelyinformation-theoretic:themostpreferredpartialmodelsofasentencearetheonescontainingtheminimalinforma-tionarmingit.ThecentralconceptofReiter’ssystem{thatofanextension{isviewedasawaytoadddefaultinformation,viaanonmonotonicxed-pointoperator,tooneoftheseminimalpartialmodels.Thisisasimplebutradicalreconstructionofdefaultreasoning.Wehopethatitwillprovetobeaninterestingandprotableone.Havingintroduceddefaultsystemsassemanticnotions,wearefreetoadoptanyofanumberofordinarylogicsaswaystoreasonaboutthesemanticsgeneratedbydefaultstructures.Thebestanalogymaybetothesemanticsofprogramminglanguages.Scottdomaintheoryisonewaytoassignmeanings(denotations)toprograms.Inanalogy,weuseScottdomaintheorytoassignmeaningstosystemsofdefaults.Inthetheoryofprogramming,logicssuchasHoarelogic,dynamiclogic,andtemporallogicareusedtoreasonaboutprogramproperties.Inanalogy,wecouldconsiderrst-orderlogic,modallogic,orsomeotherlanguagetoreasonaboutsystemsofdefaults2