Logical considerations on default semantics

ResearchReportAI{1994-07LogicalConsiderationsonDefaultSemanticsWilliamC.RoundsArticialIntelligenceLaboratoryUniversityofMichiganGuo-QiangZhangDepartmentofComputerScienceUniversityofGeorgiaLOGICALCONSIDERATIONSONDEFAULTSEMANTICS1WilliamC.RoundsArticialIntelligenceLaboratoryUniversityofMichiganAnnArbor,[e-mail]-QiangZhangDepartmentofComputerScienceUniversityofGeorgiaAthens,[e-mail]7,1994Abstract.Weconsiderareinterpretationoftherulesofdefaultlogic.WemakeReiter’sdefaultrulesintoaconstructivemethodofbuildingmodels,nottheories.Toallowreasoninginrstordersystems,weequipstandardrst-orderlogicwitha(new)Kleene3-valuedpartialmodelsemantics.Then,usingourmethodology,weadddefaultstothissemanticsystem.Theresultisthatourlogicisanordinarymonotonicone,butitssemanticsisnownonmonotonic.Reiter’sextensionsnowappearinthesemantics,notinthesyntax.Asanapplication,weshowthatthissemanticsgivesapartialsolutiontotheconceptualproblemswithopendefaultspointedoutbyLifschitz[16],andBaaderandHollunder[2].Thesolutionisnotcomplete,chieybecauseinmakingthedefaultsmodel-theoretic,wecanonlyaddconjunctiveinformationtoourmodels.Thisisincontrasttodefaulttheories,whereextensionscancontaindisjunctiveformulas,andthereforedisjunctiveinformation.Ourproposaltotreattheproblemofopendefaultsusesasemanticnotionofnonmono-tonicentailmentforourlogic,derivingfromtheideaof\onlyknowing.Ournotionis\onlyhavinginformationgivenbyaformula.Wediscussthedierencesbetweenthisand\minimal-knowledgeideas.Finally,weconsidertheKraus-Lehmann-Magidor[14]axiomsforpreferentialconsequencerelations.Wendthatourconsequencerelationsatisesthemostbasicofthelaws,andtheOrlaw,butitdoesnotsatisfythelawofCut,northelawofCautiousMonotony.Wegiveintuitiveexamplesusingoursystem,ontheotherhand,whichonthesurfaceseemtoviolatetheselaws,nomatterhowtheyareinterpreted.Wemakesomecomparisons,usingourexamples,toprobabilisticinterpretationsforwhichthelawsaretrue,andwecompareourmodelstothecumulativemodelsofKraus,Lehmann,andMagidor.Wealsoshowsucientconditionsforthelawstohold.Theseinvolvelimitingtheuseofdisjunctioninourformulasinonewayoranother.Weshowhowtomakeuseofthetheoryofcompletepartiallyorderedsets,ordomaintheory.WecanaugmentanyScottdomainwithadefaultset.WestateaversionofRe-1VersionpresentedattheThirdInternationalSymposiumonArticialIntelligenceandMathematics,FortLauderdale,Fla,January1994.ResearchsupportedbyNSFgrantIRI-9120851.1iter’sextensionoperatoronarbitrarydomainsaswell.Thisversionmakesclearthebasicorder-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[26].Onelogic,foralongtime,resistedattemptstoprovideitwithapreferentialmodelsemantics:Reiter’sdefaultlogic[21].Etherington[9]gaveapreferentialsemantics,involvingsetsofrst-ordermodelsratherthansimplemodels.Othermodeltheoriesbynowareknown.Manyofthesecomefromothernonmonotoniclogicsbymeansofatranslationofdefaulttheoriestotheotherlogics.Thearticle[25]givesagoodproposal,aswellasanoverviewofotherproposals,includingLinandShoham[18]andLifschitz[17].Ourapproachdiersfromalloftheaboveproposals.WeregardReiter’sdefaultsystemsassemantic,notsyntacticnotions.Ourpreferencerelationispurelyinformation-theoretic:themostpreferredpartialmodelsofasentencearetheonescontainingtheminimalinforma-tionarmingit.ThecentralconceptofReiter’ssystem{thatofanextension{isviewedasawaytoadddefaultinformation,viaanonmonotonicxed-pointoperator,tooneoftheseminimalpartialmodels.Thisisasimplebutradicalreconstructionofdefaultreasoning.Wehopethatitwillprovetobeaninterestingandprotableone.Havingintroduceddefaultsystemsassemanticnotions,wearefreetoadoptanyofanumberofordinarylogicsaswaystoreasonaboutthesemanticsgeneratedbydefaultstructures.Thebestanalogymaybetothesemanticsofprogramminglanguages.Scottdomaintheoryisonewaytoassignmeanings(denotations)toprograms.Inanalogy,weuseScottdomaintheorytoassignmeaningstosyste