2.1.1命题逻辑

命题逻辑PropositionLogic命题、命题符号化合式公式、真值、永真式逻辑等值式、推理定律形式化证明数理逻辑逻辑学：研究推理的一门学科数理逻辑：用数学方法研究推理的一门数学学科--------一套符号体系+一组规则数理逻辑的内容古典数理逻辑：命题逻辑、谓词逻辑现代数理逻辑：公理化集合论、递归论、模型论、证明论命题命题Proposition:一个有确定真或假意义的语句.命题逻辑PropositionLogicpropositionsEXAMPLEAllthefollowingstatementsarepropositions.1.Washington,D.C.,isthecapitaloftheUnitedStatesofAmerica.2.TorontoisthecapitalofCanada.3.1+1=2.4.2+2=3.Propositions1and3aretrue,whereas2and4arefalse.propositionsEXAMPLEConsiderthefollowingsentences.1.Whattimeisit?2.Readthiscarefully.3.x+1=2.4.x+y=z.Sentences1and2arenotpropositionsbecausetheyarenotstatements.Sentences3and4arenotpropositionsbecausetheyareneithertruenorfalse,sincethevariablesinthesesentenceshavenotbeenassignedvalues.Variouswaystoformpropositionsfromsentencesofthistypewillbediscussedinfollowing.命题的语句形式命题的语句形式陈述句非命题语句：疑问句命令句感态句非命题陈述句：悖论语句命题的表示命题的符号表示：大小写英文字母：P、Q、R、p、q、r、。。。命题真值（TruthValues）的表示：真：T、1假：F、0真值确定命题语句真值确定的几点说明：1、时间性2、区域性3、标准性命题真值间的关系表示：真值表（TruthTable)命题符号化简单命题：p,q,r,p1,q1,r1,…联结词：否定联结词：合取联结词：析取联结词：蕴涵联结词：等价联结词：逻辑真值：0，1否定negationLetpbeaproposition.Thestatement"Itisnotthecasethatp."isanotherproposition,calledthenegationofp.Thenegationofpisdenotedbyp.Theproposition pisread"notp."p的否定EXAMPLE1Negation否定Findthenegationoftheproposition"TodayisFriday"andexpressthisinsimpleEnglish.Thenegationis"ItisnotthecasethattodayisFriday."Or''TodayisnotFriday.""ItisnotFridaytoday."Table1Negation否定合取conjunctionLetpandqbepropositions.Theproposition"pandq,"denotedbyp∧q,isthepropositionthatistruewhenbothpandqaretrueandisfalseotherwise.Thepropositionp∧qiscalledtheconjunctionofpandq.Thetruthtableforp∧qisshowninTable2.p和q的合取Table2ConjunctionEXAMPLE2ConjunctionFindtheconjunctionofthepropositionspandqwherepistheproposition"TodayisFriday"andqistheproposition"Itisrainingtoday."Solution:Theconjunctionofthesepropositions,p∧q,istheproposition"TodayisFridayanditisrainingtoday."ThispropositionistrueonrainyFridaysandisfalseonanydaythatisnotaFridayandonFridayswhenitdoesnotrain.析取DisjunctionLetpandqbepropositions.Theproposition"porq,"denotedbyp∨q,isthepropositionthatisfalsewhenpandqarebothfalseandtrueotherwise.Thepropositionp∨qiscalledthedisjunctionofpandq.Thetruthtableforp∨qisshowninTable3.p和q的析取Table3Disjunction析取EXAMPLE3Disjunction析取WhatisthedisjunctionofthepropositionspandqwherepandqarethesamepropositionsasinExample4?Solution: Thedisjunctionofpandq,p∨q,istheproposition"TodayisFridayoritisrainingtoday."ThispropositionistrueonanydaythatiseitheraFridayorarainyday(includingrainyFridays).ItisonlyfalseondaysthatarenotFridayswhenitalsodoesnotrain.exclusiveOr排斥或、异或Letpandqbepropositions.Theexclusiveorofpandq,denotedbypq,isthepropositionthatistruewhenexactlyoneofpandqistrueandisfalseotherwise.ThetruthtablefortheexclusiveoroftwopropositionsisdisplayedinTable4.p和q的对称差Table4Exclusive排斥或、异或单条件,蕴涵ImplicationLetpandqbepropositions.Theimplicationp→qisthepropositionthatisfalsewhenpistrueandqisfalseandtrueotherwise.Inthisimplicationpiscalledthehypothesis(orantecedentorpremise)andqiscalledtheconclusion(orconsequence).如果p,则q单条件,蕴涵P:前提Q:结论Table5Implication蕴涵式EXAMPLE5Implication蕴涵式Whatisthevalueofthevariablexafterthestatementif2+2=4thenx:=x+1ifx=0beforethisstatementisencountered?(Thesymbol:=standsforassignment.Thestatementx:=x+1meanstheassignmentofthevalueofx+1tox.)Solution:Since2+2=4istrue,theassignmentstatementx:=x+1isexecuted.Hence,xhasthevalue0+1=1afterthisstatementisencountered.Example:“IfIamelected,thenIwilllowertaxes.”“Ifyouget100%onthefinal,thenyou’llgetanA”“IftodayisFriday,then2+3=6.”Wewouldnotusetheselastimplicationsinnaturallanguage,sincethereisnorelationshipbetweenthehypothesisandtheconclusionineitherimplication.InmathematicalreasoningweconsiderimplicationisindependentofamoregeneralsortthanweuseinEnglish.EXAMPLE6Implication蕴涵式Converse逆Contrapositive逆反Inverse反Therearesomerelatedimplicationsthatcanbeformedfromp→q.Thepropositionq→piscalledtheconverseofp→q.Thecontrapositiveofp→qistheproposition¬q→¬p.Theproposition¬p→¬qiscalledtheinverseofp→q.p→q:“Ifitraining,thenthehometeamwins.”¬q→¬p:“Ifthehometeamdoesnotwin,thenitisnotraining.”q→p:“Ifthehometeamwins,thenitisraining.”¬p→¬q:“Ifitisnotraining,thenthehometeamdoesnotwin.”EXAMPLE7Contrapositive逆反EXAMPLE8Contrapositive逆反Findtheconverseandthecontrapositiveoftheimplication"IftodayisThursday,thenIhaveatesttoday."Solution:Theconverseis"IfIhaveatesttoday,thentodayisThursday."Andthecontrapositiveofthisimplicationis"IfIdonothaveatesttoday,thentodayisnotThursday."双条件，等价BiconditionalLetpandqbepropositions,Thebiconditionalpqisthepropositionthatistruewhenpandqhavethesametruthvaluesandisfalseotherwise.ThetruthtableforpqisshowninTable6.P当且仅当q双条件，等价Table6Biconditional双条件，等价“Youcantaketheflightifandonlyifyoubuyaticket.”note:p↔qhasexactlythesametruthvalueas(p→q)∧(q→p).EXAMPLE9Biconditional双条件，等价Precedence优先级oflogicaloperatorsHowtouseparenthesestospecifytheorderinwhichlogicaloperatorsinacompoundproposition?Precedenceoflogicaloperators.operatorprecedence¬1∧∨23→↔45TranslatingEnglishSentencesTherearemanyreasonstotranslateEnglishsentencesintoexpressionsinvolvingpropositionalvariablesandlogicalconnectives.Inparticular,Englishisoftenambiguous.Translatingsentencesintologicalexpressionsremovestheambiguity.HowtotranslatethisEnglishsentenceintoalogicalexpression?“YoucanaccesstheInternetfromcampusonlyifyouareacomputersciencemajororyouarenotafreshman.”Solution:First,usepropositionalvariablestorepresenteachsentencepartanddeterminetheappropriatelogicalconnectivesbetweenthem.EXAMPLE10TranslateLetarepresent“YoucanaccesstheInternetfromcampus”Letcrepresent“Youareacomputersciencemajor”Letfrepresent“Youareafreshman”thenthesentence"YoucanaccesstheInternetfromcampusonlyifyouareacomputersciencemajororyouarenotafreshman,"canberepresentedas:a→(c∨¬f).EXAMPLE10TranslateSolutionTranslatethissentenceintoalogicalexpression“Youcannotridetherollercoasterifyouareunder4feettallunlessyouareolderthan16yearsold.”EXAMPLE11TranslateEXAMPLE11TranslateSolutionq:“Youcanridetherollercoaster(过山车),”r:“Youareunder4feettall,”s:“Youareolderthan16yearsold,”“Youcannotridetherollercoasterifyouareunder4feettallunlessyouareolderthan16yearsold.”canberepresentedas:(r∧¬s)→¬qEXAMPLE12Translate说离散数学是枯燥无味的或毫无价值的，那是不对的。P：离散数学是有味道的；Q：离散数学是有价值的；(PQ)EXAMPLE13TranslateWebPageSearching.MostWebsearchenginessupportBooleansearchingtechniques,whichusuallycanhelpfindWebpagesaboutparticularsubjects.Forinstance,usingBooleansearchingtofindWebpagesaboutuniversitiesinNewMexico,wecanlookforpagesmatchingNEWANDMEXICOANDUNIVERSITIES.TheresultsofthissearchwillincludethosepagesthatcontainthethreewordsNEW,MEXICO,andUNIVERSITIES.SystemSpecificationsSystemspecificationsshouldnotcontainconflictingrequirements.Consequently,propositionalexpressionsrepresentingthesespecificationsneedtobeconsistent.Thatis,theremustbeanassignmentoftruthvaluestothevariablesintheexpressionsthatmakesalltheexpressionstrue.Determinewhetherthesesystemspecificationsareconsistent:“Thediagnosticmessageisstoredinthebufferoritisretransmitted.”“Thediagnosticmessageisnotstoredinthebuffer.”“Ifthediagnosticmessageisstoredinthebuffer,thenitisretransmitted.”EXAMPLE14SystemSpecificationsp:“Thediagnosticmessageisstoredinthebuffer”q:“Thediagnosticmessageisretransmitted.”Sothespecificationscanbewrittenas:p∨q¬pp→qThesespecificationsareconsistentsincetheyarealltruewhenpisfalseandqistrue.EXAMPLE14SystemSpecificationsInaboveexample,ifthespecification:“Thediagnosticmessageisnotretransmitted”isadded?p∨q¬pp→q¬qEXAMPLE14SystemSpecificationsLogicPuzzlesPuzzlesthatcanbesolvedusinglogicalreasoningareknownaslogicpuzzles.Smullyanposedmanypuzzlesaboutanislandthathastwokindsofinhabitants(居民),knights(骑士),whoalwaystellthetruth,andtheiropposites,knaves(坏蛋),whoalwayslie.YouencountertwopeopleAandB.WhatareAandBifAsays“Bisaknight”andBsays“Thetwoofusareoppositetypes”?Example15LogicPuzzlesExample16LogicPuzzlesAfathertellshistwochildren,aboyandagirl,toplayintheirbackyardwithoutgettingdirty.However,whileplaying,bothchildrengetmudontheirforeheads.Whenthechildrenstopplaying,thefathersays“Atleastoneofyouhasamuddyforehead,”andthenasksthechildrentoanswer“yes”or“No”tothequestion“Doyouknowwhetheryouhaveamuddyforehead?”Thefatherasksthisquestiontwice.Whatwillthechildrenanswereachtimethisquestionisasked,assumingthatachildcanseewhetherhisorhersiblinghasamuddyforehead,butcannotseehisorherownforehead?Assumethatbothchildrenarehonestandthatthechildrenanswereachquestionsimultaneously.LogiczebraPuzzlesDiscussSolvethisfamouslogicpuzzle,attributedtoAlbertEinstein,andknownasthezebrapuzzle.Fivemenwithdifferentnationalitiesandwithdifferentjobsliveinconsecutivehousesonastreet.Thesehousesarepainteddifferentcolors.Themenhavedifferentpetsandhavedifferentfavoritedrinks.Determinewhoownsazebraandwhosefavoritedrinkismineralwater(whichisoneofthefavoritedrinks)giventheseclues:TheEnglishmanlivesintheredhouse.TheSpaniardownsadog.TheJapanesemanisapainter.TheItaliandrinkstea.TheNorwegianlivesinthefirsthouseontheleft.Thegreenhouseisontherightofthewhiteone.Thephotographerbreedssnails.Thediplomatlivesintheyellowhouse.Milkisdrunkinthemiddlehouse.Theownerofthegreenhousedrinkscoffee.TheNorwegian’shouseisnexttotheblueone.Theviolinistdrinksorangejuice.Thefoxisinahousenexttothatofthephysician.Thehorseisinahousenexttothatofthediplomat.zebraPuzzlesSolutionpersonColorOfhousejobspetsFavoritedrinksNorwegianyellowdiplomatfoxwaterItalianbluephysicianhorseteaEnglishredphotographersnailsmilkSpaniardwhiteviolinistdogorangeJapanesegreenpainterzebracoffeePuzzlesDiscussFivefriendshaveaccesstoachatroom.Isitpossibletodeterminewhoischattingifthefollowinginformationisknown?EitherKevinorHeather,orbotharechatting.EitherRandyorVijay,butnotboth,arechatting.IfAbbyischatting,soisRandy.VijayandKevinareeitherbothchattingorneitheris.IfHeatherischatting,thensoareAbbyandKevin.Explainyourreasoning.PuzzlesDiscussKevinorHeatherEitherRandyxorVijayAbbyRandyVijayKevinHeatherAbbyandKevinLogicandbitoperationsComputerbitoperationscorrespondtothelogicalconnectives.ORANDXOR位串bitstringAbitstringisasequenceofzeroormorebits.Thelengthofthisstringisthenumberofbitsinthestring.Table7BitOperatorsEXAMPLE14BitOperatorsFindthebitwiseOR,bitwiseAND,andbitwiseXORofthebitstrings0110110110and1100011101.(Here,bitstringswillbesplitintoblocksoffourbitstomakethemeasiertoread.)Solution:ThebitwiseOR,bitwiseAND,andbitwiseXORofthesestringsareobtainedbytakingtheOR,AND,andXORofthecorrespondingbits,respectively.Thisgivesus011011011011000111011110111111bitwiseOR0100010100bitwiseAND1010101011bitwiseXOR命题公式P、Q、R……称为原子命题（AtomicProposition）。原子命题或加上逻辑联结词组成的表达式成为复合命题（CompositionalProposition）。从命题常量到命题变量(PropositionalVariable)命题公式：1、原子命题是命题公式；2、设P是命题公式，则¬P也是命题公式；3、设P、Q是命题公式，则（P∧Q）、（P∨Q）、（P→Q）、（PQ）也是命题公式；4、有限次地使用1、2、3所得到的也是命题公式。PropositionFormulas,Well-FormedFormulas(wff)命题公式的运算命题公式的运算规则：逻辑联接词的优先级：¬、∧、∨、→、命题公式的表达式的运算规律：同代数表达式命题公式的运算方法：所有公式中的命题变量用指定命题（真值）代入（或指派），得到一个公式对应的真值。命题公式分类永真命题公式（Tautology）公式中的命题变量无论怎样代入，公式对应的真值恒为T。永假命题公式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。可满足命题公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。一般命题公式（Contingency）既不是永真公式也不是永假公式。Table1tautologiesandcontradictionsEXAMPLE12tautologiesandcontradictionsWecanconstructexamplesoftautologiesandcontradictionsusingjustoneproposition.Considerthetruthtablesofp∨pandp∧p,showninTable1.Sincep∨pisalwaystrue,itisatautology.Sincep∧pisalwaysfalse,itisacontradiction.命题公式性质1性质1：如果一个命题公式有N个互异的命题变量，则命题公式对应的真值有2的N次幂种可能分布。命题公式性质2性质2：（1）设P是永真命题公式，则P的否定公式是永假命题公式；（2）设P是永假命题公式，则P的否定公式是永真命题公式；（3）设P、Q是永真命题公式，则P（P∧Q）、（P∨Q）、（P→Q）、（PQ）也是永真命题公式小结1、命题的概念：定义、逻辑值、符号化表示2、从简单命题到复合命题：逻辑联接词：运算方法、运算优先级3、从命题常量到命题变量，从复合命题到命题公式：命题公式的真值描述：真值表4、命题公式的分类：永真公式、永假公式、可满足公式、一般公式进一步的思考1、从二值逻辑到多值逻辑2、从确定值到模糊值模糊逻辑（FuzzyLogic)练习pp78:2.1、2.8、2.12例题讲解例题讲解命题例１判断下列陈述是否是命题？如果是命题，是否是复合命题？3是无理数A.是命题也是复合命题B.是命题但不是复合命题C.不是命题7能被2整除 A.是命题也是复合命题B.是命题但不是复合命题C.不是命题什么时候开会呀？ A.是命题也是复合命题B.是命题但不是复合命题C.不是命题2x+3<4 A.是命题也是复合命题B.是命题但不是复合命题C.不是命题3是素数当且仅当四边形内角和为360度 A.是命题也是复合命题B.是命题但不是复合命题C.不是命题命题符号化例１将下面的命题符号化，并指出真值。苹果树和梨树都是落叶乔木。2是质数或合数。豆沙包是由面粉和红小豆做成的。解：设p：苹果树是落叶乔木，q：梨树是落叶乔木。本命题符号化为p∧q，是真命题。设p：2是质数（即素数），q：2是合数。本命题符号化为p∨q，并且为真命题。设p：豆沙包是由面粉和红小豆做成的。本命题为真命题，而且为简单命题。命题符号化例２将下面的命题符号化，并指出真值。吃一堑，长一智。n是偶数当且仅当它能被3整除。（n为一固定的自然数）解：（１）设p：吃一堑，q：长一智。符号化为p→q，为真命题。（２）设p：n是偶数，q：n能被3整除。命题符号化为pq，本命题的真值与n有关，可能为真、也可能为假。求真值例１设p：是无理数，q：北京比天津人口多，r：美国的首都是旧金山。求下列各公式的真值：    （1）(p∨q)→r   p与q是真命题，而r是假命题。于是，本题就是判断110是上列公式的成真赋值还是成假赋值。将110赋给上列公式得真值为0真值表例１注意：写公式的真值表应该按从低到高的顺序写出各层次，再计算各层次的真值，最高层次的真值就是所求公式的真值表用真值表判断下列公式的类型：　　　   p∧┐(q→p)  解：上式为永假式、矛盾式    p∧┐(q→p)的真值表：真值表例２用真值表判断下列公式的类型：　　　(p→q)→(┐q→┐p)解：上式为永真式、重言式　　　　(p→q)→(┐q→┐p)的真值表真值表例３用真值表判断下列公式的类型：　　(p→q)p 解：为可满足式(p→q)p的真值表：讨论及提问讨论及提问Anyquestion?