2.1.1命题逻辑

命题逻辑PropositionLogic命题、命题符号化合式公式、真值表、永真式逻辑等值式、推理定律形式化证明8/25/20211discretemath--PropositionLogic 数理逻辑逻辑学：研究推理的一门学科数理逻辑：用数学方法研究推理的一门数学学科--------一套符号体系+一组规则8/25/20212discretemath--PropositionLogic 数理逻辑的内容古典数理逻辑：命题逻辑、谓词逻辑现代数理逻辑：公理化集合论、递归论、模型论、证明论8/25/20213discretemath--PropositionLogic 命题命题Proposition:一个有确定真或假意义的语句.命题逻辑PropositionLogic8/25/20214discretemath--PropositionLogic propositionsEXAMPLEAllthefollowingstatementsarepropositions.1.Washington,D.C.,isthecapitaloftheUnitedStatesofAmerica.2.TorontoisthecapitalofCanada.3.1+1=2.4.2+2=3.Propositions1and3aretrue,whereas2and4arefalse.8/25/20215discretemath--PropositionLogic propositionsEXAMPLEConsiderthefollowingsentences.1.Whattimeisit?2.Readthiscarefully.3.x+1=2.4.x+y=z.Sentences1and2arenotpropositionsbecausetheyarenotstatements.Sentences3and4arenotpropositionsbecausetheyareneithertruenorfalse,sincethevariablesinthesesentenceshavenotbeenassignedvalues.Variouswaystoformpropositionsfromsentencesofthistypewillbediscussedinfollowing.8/25/20216discretemath--PropositionLogic 命题的语句形式命题的语句形式陈述句非命题语句：疑问句命令句感态句非命题陈述句：悖论语句8/25/20217discretemath--PropositionLogic 命题的表示命题的符号表示：大小写英文字母：P、Q、R、p、q、r、。。。命题真值（TruthValues）的表示：真：T、1假：F、08/25/20218discretemath--PropositionLogic 真值确定命题语句真值确定的几点说明：1、时间性2、区域性3、标准性命题真值间的关系表示：真值表（TruthTable)8/25/20219discretemath--PropositionLogic 命题符号化简单命题：p,q,r,p1,q1,r1,…联结词：否定联结词：合取联结词：析取联结词：蕴涵联结词：等价联结词：逻辑真值：0，18/25/202110discretemath--PropositionLogic 否定negationLetpbeaproposition.Thestatement"Itisnotthecasethatp."isanotherproposition,calledthenegationofp.Thenegationofpisdenotedbyp.Thepropositionpisread"notp."p的否定8/25/202111discretemath--PropositionLogic EXAMPLE1Negation否定Findthenegationoftheproposition"TodayisFriday"andexpressthisinsimpleEnglish.Thenegationis"ItisnotthecasethattodayisFriday."Or''TodayisnotFriday.""ItisnotFridaytoday."8/25/202112discretemath--PropositionLogic Table1Negation否定8/25/202113discretemath--PropositionLogic 合取conjunctionLetpandqbepropositions.Theproposition"pandq,"denotedbyp∧q,isthepropositionthatistruewhenbothpandqaretrueandisfalseotherwise.Thepropositionp∧qiscalledtheconjunctionofpandq.Thetruthtableforp∧qisshowninTable2.p和q的合取8/25/202114discretemath--PropositionLogic Table2Conjunction8/25/202115discretemath--PropositionLogic EXAMPLE2ConjunctionFindtheconjunctionofthepropositionspandqwherepistheproposition"TodayisFriday"andqistheproposition"Itisrainingtoday."Solution:Theconjunctionofthesepropositions,p∧q,istheproposition"TodayisFridayanditisrainingtoday."ThispropositionistrueonrainyFridaysandisfalseonanydaythatisnotaFridayandonFridayswhenitdoesnotrain.8/25/202116discretemath--PropositionLogic 析取DisjunctionLetpandqbepropositions.Theproposition"porq,"denotedbyp∨q,isthepropositionthatisfalsewhenpandqarebothfalseandtrueotherwise.Thepropositionp∨qiscalledthedisjunctionofpandq.Thetruthtableforp∨qisshowninTable3.p和q的析取8/25/202117discretemath--PropositionLogic Table3Disjunction析取8/25/202118discretemath--PropositionLogic EXAMPLE3Disjunction析取WhatisthedisjunctionofthepropositionspandqwherepandqarethesamepropositionsasinExample4?Solution:Thedisjunctionofpandq,p∨q,istheproposition"TodayisFridayoritisrainingtoday."ThispropositionistrueonanydaythatiseitheraFridayorarainyday(includingrainyFridays).ItisonlyfalseondaysthatarenotFridayswhenitalsodoesnotrain.8/25/202119discretemath--PropositionLogic exclusiveOr排斥或、异或Letpandqbepropositions.Theexclusiveorofpandq,denotedbypq,isthepropositionthatistruewhenexactlyoneofpandqistrueandisfalseotherwise.ThetruthtablefortheexclusiveoroftwopropositionsisdisplayedinTable4.p和q的对称差8/25/202120discretemath--PropositionLogic Table4Exclusive排斥或、异或8/25/202121discretemath--PropositionLogic 单条件,蕴涵ImplicationLetpandqbepropositions.Theimplicationp→qisthepropositionthatisfalsewhenpistrueandqisfalseandtrueotherwise.Inthisimplicationpiscalledthehypothesis(orantecedentorpremise)andqiscalledtheconclusion(orconsequence).如果p,则q单条件,蕴涵P:前提Q:结论8/25/202122discretemath--PropositionLogic Table5Implication蕴涵式8/25/202123discretemath--PropositionLogic EXAMPLE5Implication蕴涵式Whatisthevalueofthevariablexafterthestatementif2+2=4thenx:=x+1ifx=0beforethisstatementisencountered?(Thesymbol:=standsforassignment.Thestatementx:=x+1meanstheassignmentofthevalueofx+1tox.)Solution:Since2+2=4istrue,theassignmentstatementx:=x+1isexecuted.Hence,xhasthevalue0+1=1afterthisstatementisencountered.8/25/202124discretemath--PropositionLogic Example:“IfIamelected,thenIwilllowertaxes.”“Ifyouget100%onthefinal,thenyou’llgetanA”“IftodayisFriday,then2+3=6.”Wewouldnotusetheselastimplicationsinnaturallanguage,sincethereisnorelationshipbetweenthehypothesisandtheconclusionineitherimplication.InmathematicalreasoningweconsiderimplicationisindependentofamoregeneralsortthanweuseinEnglish.EXAMPLE6Implication蕴涵式8/25/202125discretemath--PropositionLogic Converse逆Contrapositive逆反Inverse反Therearesomerelatedimplicationsthatcanbeformedfromp→q.Thepropositionq→piscalledtheconverseofp→q.Thecontrapositiveofp→qistheproposition¬q→¬p.Theproposition¬p→¬qiscalledtheinverseofp→q.8/25/202126discretemath--PropositionLogic p→q:“Ifitraining,thenthehometeamwins.”¬q→¬p:“Ifthehometeamdoesnotwin,thenitisnotraining.”q→p:“Ifthehometeamwins,thenitisraining.”¬p→¬q:“Ifitisnotraining,thenthehometeamdoesnotwin.”EXAMPLE7Contrapositive逆反8/25/202127discretemath--PropositionLogic EXAMPLE8Contrapositive逆反Findtheconverseandthecontrapositiveoftheimplication"IftodayisThursday,thenIhaveatesttoday."Solution:Theconverseis"IfIhaveatesttoday,thentodayisThursday."Andthecontrapositiveofthisimplicationis"IfIdonothaveatesttoday,thentodayisnotThursday."8/25/202128discretemath--PropositionLogic 双条件，等价BiconditionalLetpandqbepropositions,Thebiconditionalpqisthepropositionthatistruewhenpandqhavethesametruthvaluesandisfalseotherwise.ThetruthtableforpqisshowninTable6.P当且仅当q双条件，等价8/25/202129discretemath--PropositionLogic Table6Biconditional双条件，等价8/25/202130discretemath--PropositionLogic “Youcantaketheflightifandonlyifyoubuyaticket.”note:p↔qhasexactlythesametruthvalueas(p→q)∧(q→p).EXAMPLE9Biconditional双条件，等价8/25/202131discretemath--PropositionLogic Precedence优先级oflogicaloperatorsHowtouseparenthesestospecifytheorderinwhichlogicaloperatorsinacompoundproposition?Precedenceoflogicaloperators.operatorprecedence¬1∧∨23→↔458/25/202132discretemath--PropositionLogic TranslatingEnglishSentencesTherearemanyreasonstotranslateEnglishsentencesintoexpressionsinvolvingpropositionalvariablesandlogicalconnectives.Inparticular,Englishisoftenambiguous.Translatingsentencesintologicalexpressionsremovestheambiguity.8/25/202133discretemath--PropositionLogic HowtotranslatethisEnglishsentenceintoalogicalexpression?“YoucanaccesstheInternetfromcampusonlyifyouareacomputersciencemajororyouarenotafreshman.”Solution:First,usepropositionalvariablestorepresenteachsentencepartanddeterminetheappropriatelogicalconnectivesbetweenthem.EXAMPLE10Translate8/25/202134discretemath--PropositionLogic Letarepresent“YoucanaccesstheInternetfromcampus”Letcrepresent“Youareacomputersciencemajor”Letfrepresent“Youareafreshman”thenthesentence"YoucanaccesstheInternetfromcampusonlyifyouareacomputersciencemajororyouarenotafreshman,"canberepresentedas:a→(c∨¬f).EXAMPLE10TranslateSolution8/25/202135discretemath--PropositionLogic Translatethissentenceintoalogicalexpression“Youcannotridetherollercoasterifyouareunder4feettallunlessyouareolderthan16yearsold.”EXAMPLE11Translate8/25/202136discretemath--PropositionLogic EXAMPLE11TranslateSolutionq:“Youcanridetherollercoaster(过山车),”r:“Youareunder4feettall,”s:“Youareolderthan16yearsold,”“Youcannotridetherollercoasterifyouareunder4feettallunlessyouareolderthan16yearsold.”canberepresentedas:(r∧¬s)→¬q8/25/202137discretemath--PropositionLogic EXAMPLE12Translate说离散数学是枯燥无味的或毫无价值的，那是不对的。P：离散数学是有味道的；Q：离散数学是有价值的；(PQ)8/25/202138discretemath--PropositionLogic EXAMPLE13TranslateWebPageSearching.MostWebsearchenginessupportBooleansearchingtechniques,whichusuallycanhelpfindWebpagesaboutparticularsubjects.Forinstance,usingBooleansearchingtofindWebpagesaboutuniversitiesinNewMexico,wecanlookforpagesmatchingNEWANDMEXICOANDUNIVERSITIES.TheresultsofthissearchwillincludethosepagesthatcontainthethreewordsNEW,MEXICO,andUNIVERSITIES.8/25/202139discretemath--PropositionLogic SystemSpecificationsSystemspecificationsshouldnotcontainconflictingrequirements.Consequently,propositionalexpressionsrepresentingthesespecificationsneedtobeconsistent.Thatis,theremustbeanassignmentoftruthvaluestothevariablesintheexpressionsthatmakesalltheexpressionstrue.8/25/202140discretemath--PropositionLogic Determinewhetherthesesystemspecificationsareconsistent:“Thediagnosticmessageisstoredinthebufferoritisretransmitted.”“Thediagnosticmessageisnotstoredinthebuffer.”“Ifthediagnosticmessageisstoredinthebuffer,thenitisretransmitted.”EXAMPLE14SystemSpecifications8/25/202141discretemath--PropositionLogic p:“Thediagnosticmessageisstoredinthebuffer”q:“Thediagnosticmessageisretransmitted.”Sothespecificationscanbewrittenas:p∨q¬pp→qThesespecificationsareconsistentsincetheyarealltruewhenpisfalseandqistrue.EXAMPLE14SystemSpecifications8/25/202142discretemath--PropositionLogic Inaboveexample,ifthespecification:“Thediagnosticmessageisnotretransmitted”isadded?p∨q¬pp→q¬qEXAMPLE14SystemSpecifications8/25/202143discretemath--PropositionLogic LogicPuzzlesPuzzlesthatcanbesolvedusinglogicalreasoningareknownaslogicpuzzles.8/25/202144discretemath--PropositionLogic Smullyanposedmanypuzzlesaboutanislandthathastwokindsofinhabitants(居民),knights(骑士),whoalwaystellthetruth,andtheiropposites,knaves(坏蛋),whoalwayslie.YouencountertwopeopleAandB.WhatareAandBifAsays“Bisaknight”andBsays“Thetwoofusareoppositetypes”?Example15LogicPuzzles8/25/202145discretemath--PropositionLogic Example16LogicPuzzlesAfathertellshistwochildren,aboyandagirl,toplayintheirbackyardwithoutgettingdirty.However,whileplaying,bothchildrengetmudontheirforeheads.Whenthechildrenstopplaying,thefathersays“Atleastoneofyouhasamuddyforehead,”andthenasksthechildrentoanswer“yes”or“No”tothequestion“Doyouknowwhetheryouhaveamuddyforehead?”Thefatherasksthisquestiontwice.Whatwillthechildrenanswereachtimethisquestionisasked,assumingthatachildcanseewhetherhisorhersiblinghasamuddyforehead,butcannotseehisorherownforehead?Assumethatbothchildrenarehonestandthatthechildrenanswereachquestionsimultaneously.8/25/202146discretemath--PropositionLogic LogiczebraPuzzlesDiscussSolvethisfamouslogicpuzzle,attributedtoAlbertEinstein,andknownasthezebrapuzzle.Fivemenwithdifferentnationalitiesandwithdifferentjobsliveinconsecutivehousesonastreet.Thesehousesarepainteddifferentcolors.Themenhavedifferentpetsandhavedifferentfavoritedrinks.Determinewhoownsazebraandwhosefavoritedrinkismineralwater(whichisoneofthefavoritedrinks)giventheseclues:TheEnglishmanlivesintheredhouse.TheSpaniardownsadog.TheJapanesemanisapainter.TheItaliandrinkstea.TheNorwegianlivesinthefirsthouseontheleft.Thegreenhouseisontherightofthewhiteone.Thephotographerbreedssnails.Thediplomatlivesintheyellowhouse.Milkisdrunkinthemiddlehouse.Theownerofthegreenhousedrinkscoffee.TheNorwegian’shouseisnexttotheblueone.Theviolinistdrinksorangejuice.Thefoxisinahousenexttothatofthephysician.Thehorseisinahousenexttothatofthediplomat.8/25/202147discretemath--PropositionLogic zebraPuzzlesSolutionpersonColorOfhousejobspetsFavoritedrinksNorwegianyellowdiplomatfoxwaterItalianbluephysicianhorseteaEnglishredphotographersnailsmilkSpaniardwhiteviolinistdogorangeJapanesegreenpainterzebracoffee8/25/202148discretemath--PropositionLogic PuzzlesDiscussFivefriendshaveaccesstoachatroom.Isitpossibletodeterminewhoischattingifthefollowinginformationisknown?EitherKevinorHeather,orbotharechatting.EitherRandyorVijay,butnotboth,arechatting.IfAbbyischatting,soisRandy.VijayandKevinareeitherbothchattingorneitheris.IfHeatherischatting,thensoareAbbyandKevin.Explainyourreasoning.8/25/202149discretemath--PropositionLogic PuzzlesDiscussKevinorHeatherEitherRandyxorVijayAbbyRandyVijayKevinHeatherAbbyandKevin8/25/202150discretemath--PropositionLogic LogicandbitoperationsComputerbitoperationscorrespondtothelogicalconnectives.ORANDXOR8/25/202151discretemath--PropositionLogic 位串bitstringAbitstringisasequenceofzeroormorebits.Thelengthofthisstringisthenumberofbitsinthestring.8/25/202152discretemath--PropositionLogic Table7BitOperators8/25/202153discretemath--PropositionLogic EXAMPLE14BitOperatorsFindthebitwiseOR,bitwiseAND,andbitwiseXORofthebitstrings0110110110and1100011101.(Here,bitstringswillbesplitintoblocksoffourbitstomakethemeasiertoread.)Solution:ThebitwiseOR,bitwiseAND,andbitwiseXORofthesestringsareobtainedbytakingtheOR,AND,andXORofthecorrespondingbits,respectively.Thisgivesus011011011011000111011110111111bitwiseOR0100010100bitwiseAND1010101011bitwiseXOR8/25/202154discretemath--PropositionLogic 命题公式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)8/25/202155discretemath--PropositionLogic 命题公式的运算命题公式的运算规则：逻辑联接词的优先级：¬、∧、∨、→、命题公式的表达式的运算规律：同代数表达式命题公式的运算方法：所有公式中的命题变量用指定命题（真值）代入（或指派），得到一个公式对应的真值。8/25/202156discretemath--PropositionLogic 命题公式分类永真命题公式（Tautology）公式中的命题变量无论怎样代入，公式对应的真值恒为T。永假命题公式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。可满足命题公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。一般命题公式（Contingency）既不是永真公式也不是永假公式。8/25/202157discretemath--PropositionLogic Table1tautologiesandcontradictions8/25/202158discretemath--PropositionLogic EXAMPLE12tautologiesandcontradictionsWecanconstructexamplesoftautologiesandcontradictionsusingjustoneproposition.Considerthetruthtablesofp∨pandp∧p,showninTable1.Sincep∨pisalwaystrue,itisatautology.Sincep∧pisalwaysfalse,itisacontradiction.8/25/202159discretemath--PropositionLogic 命题公式性质1性质1：如果一个命题公式有N个互异的命题变量，则命题公式对应的真值有2的N次幂种可能分布。8/25/202160discretemath--PropositionLogic 命题公式性质2性质2：（1）设P是永真命题公式，则P的否定公式是永假命题公式；（2）设P是永假命题公式，则P的否定公式是永真命题公式；（3）设P、Q是永真命题公式，则P（P∧Q）、（P∨Q）、（P→Q）、（PQ）也是永真命题公式8/25/202161discretemath--PropositionLogic 小结1、命题的概念：定义、逻辑值、符号化表示2、从简单命题到复合命题：逻辑联接词：运算方法、运算优先级3、从命题常量到命题变量，从复合命题到命题公式：命题公式的真值描述：真值表4、命题公式的分类：永真公式、永假公式、可满足公式、一般公式8/25/202162discretemath--PropositionLogic 进一步的思考1、从二值逻辑到多值逻辑2、从确定值到模糊值模糊逻辑（FuzzyLogic)练习pp78:2.1、2.8、2.128/25/202163discretemath--PropositionLogic 例题讲解例题讲解8/25/202164discretemath--PropositionLogic 命题例１判断下列陈述是否是命题？如果是命题，是否是复合命题？3是无理数A.是命题也是复合命题B.是命题但不是复合命题C.不是命题7能被2整除A.是命题也是复合命题B.是命题但不是复合命题C.不是命题什么时候开会呀？A.是命题也是复合命题B.是命题但不是复合命题C.不是命题2x+3