Logic programming and knowledge representation

LogicProgrammingandKnowledgeRepresentationChittaBaralandMichaelGelfondComputerScienceDepartmentUniversityofTexasatElPasoElPaso,Texas79968fchitta,[e-mail]24,1994AbstractInthispaper,wereviewrecentworkaimedattheapplicationofdeclarativelogicprogrammingtoknowledgerepresentationinarticialintelligence.Weconsiderexten-sionsofthelanguageofdenitelogicprogramsbyclassical(strong)negation,disjunc-tion,andsomemodaloperatorsandshowhoweachoftheaddedfeaturesextendstherepresentationalpowerofthelanguage.Wealsodiscussextensionsoflogicprogrammingallowingabductivereasoning,meta-reasoningandreasoninginopendomains.Weinvestigatethemethodologyofusingtheselanguagesforrepresentingvariousformsofnonmonotonicreasoningandfordescribingknowledgeinspecicdomains.Wealsoaddressrecentworkonpropertiesofprogramsneededforsucessfulapplicationsofthismethodologysuchasconsistency,categoricityandcomplexity.1Contents1Introduction11.1HistoricalPerspective:::::::::::::::::::::::::::::::11.2StructureofthePaper::::::::::::::::::::::::::::::32GeneralLogicPrograms52.1Preliminaries:::::::::::::::::::::::::::::::::::52.2RepresentingKnowledgeinGeneralLogicPrograms::::::::::::::82.3AnsweringQueries::::::::::::::::::::::::::::::::122.4OtherSemanticsofGeneralLogicPrograms::::::::::::::::::143ExtendedLogicPrograms203.1RepresentingKnowledgeUsingExtendedLogicPrograms:::::::::::223.2OtherSemanticsofExtendedLogicPrograms:::::::::::::::::304DisjunctiveLogicPrograms334.1RepresentingKnowledgeUsingDisjunctiveLogicPrograms::::::::::354.2AnsweringQueries::::::::::::::::::::::::::::::::384.3OtherApproachestoDisjunctiveLogicPrograms:::::::::::::::405EpistemicLogicPrograms436Meta-logicProgramming477ReasoninginOpenDomains537.1TheSemantics:::::::::::::::::::::::::::::::::::537.2Applications::::::::::::::::::::::::::::::::::::548Abduction578.1AbductionforExplainingObservations:::::::::::::::::::::578.2AbductionandNegationasFailure:::::::::::::::::::::::598.3CombiningExplanationandDeduction:::::::::::::::::::::609Relatinglogicprogrammingandothernonmonotonicformalisms649.1AutoepistemicLogicandLogicProgramming:::::::::::::::::659.2DefaultsandLogicProgramming::::::::::::::::::::::::659.3TruthMaintenanceSystemsandLogicProgramming:::::::::::::6710Expressivenessandcomplexityresults6811Conclusion7121IntroductionInthispaper,wereviewrecentworkaimedattheapplicationoflogicprogrammingtoknowledgerepresentationinarticialintelligence(AI).Weconsidervariousextensionsof\pureProlog(denitelogicprograms)andshowhoweachoftheaddedfeaturesextendstherepresentationalpowerofthelanguage.1.1HistoricalPerspectiveKnowledgerepresentationisoneofthemostimportantsubareasofarticialintelligence.Ifwewanttodesignanentity(amachineoraprogram)capableofbehavingintelligentlyinsomeenvironment,thenweneedtosupplythisentitywithsucientknowledgeaboutthisenvironment.Todothat,weneedanunambiguouslanguagecapableofexpressingthisknowledge,togetherwithsomepreciseandwellunderstoodwayofmanipulatingsetsofsentencesofthelanguagewhichwillallowustodrawinferences,answerqueries,andtoupdateboththeknowledgebaseandthedesiredprogrambehavior.Around1960,McCarthy[McC59]rstproposedtheuseoflogicalformulasasabasisforaknowledgerepresentationlanguageofthistype.Thisishowheexplainstheadvantagesofsucharepresentation:Expressinginformationindeclarativesentencesisfarmoremodularthanex-pressingitinsegmentsofcomputerprogramsorintables.Sentencescanbetrueinamuchwidercontextthanspecicprogramscanbeused.Thesupplierofafactdoesnothavetounderstandmuchabouthowthereceiverfunctionsorhoworwhetherthereceiverwilluseit.Thesamefactcanbeusedformanypurposes,becausethelogicalconsequencesofcollectionsoffactscanbeavailable.Thisideahasbeenfurtherdevelopedbymanyresearcherswithvariousbackgroundsandinterests.First,theclassicallogicofpredicatecalculusservedasthemaintechnicaltoolfortherepresentationofknowledge.Ithasawell-denedsemanticsandawell-understoodandpowerfulinferencemechanism,anditprovedtobesucientlyexpressivefortherepresenta-tionofmathematicalknowledge.Itwassoonrealized,however,thatfortherepresentationofcommonsenseknowledge,thistoolisinadequate.Thedicultyisratherdeepandrelatedtotheso-called\monotonicityoftheoriesbasedonpredicatecalculus.Alogiciscalledmonotoniciftheadditionofnewaxiomstoatheorybasedonitneverleadstothelossofanytheoremsprovedinthistheory.Commonsensereasoningisnonmonotonic:newin-formationconstantlyforcesustowithdrawpreviousconclusions.Thisobservationhasledtothedevelopmentandinvestigationofnewlogicalformalisms,nonmonotoniclogics.Thebestknownofthemarecircumscription[McC80,McC86,Lif85b],defaultlogic[Rei80b],andnonmonotonicmodallogics[MD80,McD82,Moo85].Acollectionofimportantpapersonnonmonotonicreasoningpublishedbefore1987appearsin[Gin87].Asurveycanbefoundin[Rei87a].Muchtechnicalworkhasbeendonetoinvestigatethemathematicalpropertiesoftheselogics,aswellastheirapplicabilitytotheformalizationofcommonsensereason-inginvariousspecicdomains.Thisworkhassubstantiallydeepenedourunderstanding1ofthepropertiesofnonmonotonicreasoningandofthetechnicalproblemsi