Exogenous semantics approach to enriching logics

ExogenousSemanticsApproachtoEnrichingLogicsPauloMateus,AmílcarSernadas,andCristinaSernadasAbstract.Theexogenoussemanticsapproachtoenrichingalogicconsistsindefin-ingeachmodelintheenrichmentasasetofmodelsintheoriginallogicplussomerelevantstructure.Weillustratetheapproachbyprobabilizingclassicalpropositionallogic,includinganovelglobalpropositionallogic.Amodeloftheprobabilitylogicisaprobabilityspacewheretheoutcomesareclassicalvaluations.Amodeloftheglobalpropositionallogicissimplyasetofclassicalvaluations.Syntactically,probabilitiesap-pearasconstructorsofnewtermsfromclassicalformulas.Soundnessandcompletenessresultsareprovedforthecalculiofbothlogics.Asimplezero-knowledgeprotocolisusedtoillustratethecapabilitiesoftheproposedprobabilitylogic.1IntroductionTheexogenoussemanticsapproachtoenrichingalogicconsistsindefiningeachmodelintheenrichmentasasetofmodelsintheoriginallogicplussomerele-vantstructure.Weillustratetheapproachbyprobabilizingclassicalpropositionallogic.Addingprobabilityfeaturestoabaselogicisarecurrentresearchtopic[2,11,23,24].Carnap,[4],wasoneofthefirstattemptingtocombinelogicandprobability.Theissueisnotaneasyonesincethereistheneedtoaccommodatethecontinuousnatureofprobabilities(namelydealingwithprobabilityspacesandtherealnumbers)inthediscretesettingoflogic.Threemainissuesmustbedealt.Thefirstisofasyntacticnaturerelatedtotheintroductionofprobabilitiesinthelanguage.Thesecondisthechoiceofthemodelsandhowtheyarerelatedwiththemodelsofthebaselogic.Finally,acalculusshouldbedefinedtoworkhandinhandwiththesemantics,thatis,itshouldbesoundandcomplete.166PauloMateus,AmílcarSernadas,andCristinaSernadasPropositionallogic,first-orderlogicsandmodallogichavebeenthemainbaselogics.Alsomany-sortedfirst-orderlogichasbeenthebaselogicasinthecaseofthesituationcalculus.Noworkcanbefoundansweringthequestionofhowtoenrichageneralbaselogicinordertogetaprobabilitylogicaswellasonthegeneralrequirementsforthebaselogics.Language-wise,inmanyapproaches,aprobabilityoperatorisintroducedwhichallowstheconstructionofnewformulas/termsfromthebaseformulas.Inthecaseofthesocalledqualitativereasoning(usualinthecontextofmodallogic),seeforinstance[3],thereisanoperatorthatwhenappliedtoaformulastatesthattheformulashouldbemoreprobablethantherespectivenegation.Alsointhisdirectionsee[7].Lately,theprobabilityoperatorsappearasmodaloperators.In[21],abinarymodaloperator≤wasadopted:ϕ1≤ϕ2statesthatformulaϕ1islessprobablethanformulaϕ2.Yetanotherapproachhasbeenusedinknowledgerepresentation,see[5,1],wheremodaloperatorsofthekindw(φ)≥bexpressingthataccordingtoanagentformulaφholdswithprobabilityatleastb.Seealso[18,19].Morerecently,thequalitativeapproachwasinvestigatedthroughanewmodaloperator:thatis,thefactthataformulashouldbemoreprobablethanitsnegationisintroducedviaaunarymodaloperator,see[22].Thisoperatordoesnotdistributewithconjunctionswhichmeansthatitisnotanormalmodaloperator.Inthecontextofprobabilitysituationcalculus[12]probabilitieswereaddedtothereactions.Fromasyntacticpointofview,ourapproachisasfollows.Westartwiththebaselanguage,defineaprobabilitylanguagebytakingthebaseformulasastermsandtheprobabilityasatermconstructor.Themainprimitiveistheprobabilityformula((Rϕ)≤p)indicatingthattheprobabilityoftheformulaϕshouldbelessthanorequaltop.Theseatomicprobabilityassertionsarethencombinedusingwhatwecallaglobalpropositionallogic.Anormalmodalityisintroducedasanabbreviation:(2ϕ)for((Rϕ)=1).Fromasemanticpointpointofview,therearetwobasicapproaches.Ei-therthemodelsofthebaselogicaremodifiedsothattheyaccommodatetheprobabilitycomponent(endogenousapproach)orthemodelsarekeptastheyareandtheprobabilitiesareassignedoutsidethemodels(exogenousapproach).TheendogenousapproachwasadoptedinthecontextofmodallogicendowedwithKripkesemantics(recallthataKripkeframeisapairhW,RiwhereWisanonemptysetandR⊆W×Wisarelation).Mostoftheapproachesintro-ducingprobabilitiestomodallogicconsisteitheringivingprobabilitiestotheelementsofW,see[5],orgivingprobabilitiestoeachhw1,w2i∈R,see[8,22].Theexogenousapproachwasadoptedforinstancein[16,17].Semantically,weillustratetwicetheexogenousapproach(someaspectsoftheexogenousapproachappearin[16,17]).Westartbydefiningaglobalproposi-tionallogicwhosemodelsaresetsofpropositionalvaluations(nomorestructureisneeded)andthenwedefineaprobabilitylogicwhosemodelsareprobabilityspaceswheretheoutcomesetisasetofpropositionalvaluations(wheremorestructureisneededtorepresentprobabilities).G.Sica(ed.)EssaysontheFoundationsofMathematicsandLogic©2005PolimetricaInternationalScientificPublisherMonza/ItalyExogenousSemanticsApproachtoEnrichingLogics167Theinterestinprobabilitylogichasrecentlyincreasedduetothegrowingimportanceofprobabilityinsecurity[10],andinquantumlogic.Anessentialissueinquantumlogicistoaccommodatethefourthpostulateofquantumme-chanics(whenaphysicalquantityismeasuredusinganobservableonasysteminagivenstate,theresultingoutcomesareruledbyaprobabilitymeasure).Formoredetailsonaquantumlogicencompassingtheprobabilityaspectsofthefourthpostulatesee[13,14].Notethekeyroleoftheexogenousapproachinthedesignofthatqu