2.1.1命题逻辑.ppt

2 12 20203 07AM discretemath PropositionLogic 1 命题逻辑PropositionLogic 命题 命题符号化合式公式 真值表 永真式逻辑等值式 推理定律形式化证明 2 12 20203 07AM discretemath PropositionLogic 2 数理逻辑 逻辑学 研究推理的一门学科数理逻辑 用数学方法研究推理的一门数学学科 一套符号体系 一组规则 2 12 20203 07AM discretemath PropositionLogic 3 数理逻辑的内容 古典数理逻辑 命题逻辑 谓词逻辑现代数理逻辑 公理化集合论 递归论 模型论 证明论 2 12 20203 07AM discretemath PropositionLogic 4 命题 命题Proposition 一个有确定真或假意义的语句 命题逻辑PropositionLogic 2 12 20203 07AM discretemath PropositionLogic 5 propositionsEXAMPLE Allthefollowingstatementsarepropositions 1 Washington D C isthecapitaloftheUnitedStatesofAmerica 2 TorontoisthecapitalofCanada 3 1 1 2 4 2 2 3 Propositions1and3aretrue whereas2and4arefalse 2 12 20203 07AM discretemath PropositionLogic 6 propositionsEXAMPLE Considerthefollowingsentences 1 Whattimeisit 2 Readthiscarefully 3 x 1 2 4 x y z Sentences1and2arenotpropositionsbecausetheyarenotstatements Sentences3and4arenotpropositionsbecausetheyareneithertruenorfalse sincethevariablesinthesesentenceshavenotbeenassignedvalues Variouswaystoformpropositionsfromsentencesofthistypewillbediscussedinfollowing 2 12 20203 07AM discretemath PropositionLogic 7 命题的语句形式 命题的语句形式陈述句非命题语句 疑问句命令句感态句非命题陈述句 悖论语句 2 12 20203 07AM discretemath PropositionLogic 8 命题的表示 命题的符号表示 大小写英文字母 P Q R p q r 命题真值 TruthValues 的表示 真 T 1假 F 0 2 12 20203 07AM discretemath PropositionLogic 9 真值确定 命题语句真值确定的几点说明 1 时间性2 区域性3 标准性命题真值间的关系表示 真值表 TruthTable 2 12 20203 07AM discretemath PropositionLogic 10 命题符号化 简单命题 p q r p1 q1 r1 联结词 否定联结词 合取联结词 析取联结词 蕴涵联结词 等价联结词 逻辑真值 0 1 2 12 20203 07AM discretemath PropositionLogic 11 否定negation Letpbeaproposition Thestatement Itisnotthecasethatp isanotherproposition calledthenegationofp Thenegationofpisdenotedbyp Thepropositionpisread notp p的否定 2 12 20203 07AM discretemath PropositionLogic 12 EXAMPLE1Negation否定 Findthenegationoftheproposition TodayisFriday andexpressthisinsimpleEnglish Thenegationis ItisnotthecasethattodayisFriday Or TodayisnotFriday ItisnotFridaytoday 2 12 20203 07AM discretemath PropositionLogic 13 Table1Negation否定 2 12 20203 07AM discretemath PropositionLogic 14 合取conjunction Letpandqbepropositions Theproposition pandq denotedbyp q isthepropositionthatistruewhenbothpandqaretrueandisfalseotherwise Thepropositionp qiscalledtheconjunctionofpandq Thetruthtableforp qisshowninTable2 p和q的合取 2 12 20203 07AM discretemath PropositionLogic 15 Table2Conjunction 2 12 20203 07AM discretemath PropositionLogic 16 EXAMPLE2Conjunction Findtheconjunctionofthepropositionspandqwherepistheproposition TodayisFriday andqistheproposition Itisrainingtoday Solution Theconjunctionofthesepropositions p q istheproposition TodayisFridayanditisrainingtoday ThispropositionistrueonrainyFridaysandisfalseonanydaythatisnotaFridayandonFridayswhenitdoesnotrain 2 12 20203 07AM discretemath PropositionLogic 17 析取Disjunction Letpandqbepropositions Theproposition porq denotedbyp q isthepropositionthatisfalsewhenpandqarebothfalseandtrueotherwise Thepropositionp qiscalledthedisjunctionofpandq Thetruthtableforp qisshowninTable3 p和q的析取 2 12 20203 07AM discretemath PropositionLogic 18 Table3Disjunction析取 2 12 20203 07AM discretemath PropositionLogic 19 EXAMPLE3Disjunction析取 WhatisthedisjunctionofthepropositionspandqwherepandqarethesamepropositionsasinExample4 Solution Thedisjunctionofpandq p q istheproposition TodayisFridayoritisrainingtoday ThispropositionistrueonanydaythatiseitheraFridayorarainyday includingrainyFridays ItisonlyfalseondaysthatarenotFridayswhenitalsodoesnotrain 2 12 20203 07AM discretemath PropositionLogic 20 exclusiveOr排斥或 异或 Letpandqbepropositions Theexclusiveorofpandq denotedbypq isthepropositionthatistruewhenexactlyoneofpandqistrueandisfalseotherwise ThetruthtablefortheexclusiveoroftwopropositionsisdisplayedinTable4 p和q的对称差 2 12 20203 07AM discretemath PropositionLogic 21 Table4Exclusive排斥或 异或 2 12 20203 07AM discretemath PropositionLogic 22 单条件 蕴涵Implication Letpandqbepropositions Theimplicationp qisthepropositionthatisfalsewhenpistrueandqisfalseandtrueotherwise Inthisimplicationpiscalledthehypothesis orantecedentorpremise andqiscalledtheconclusion orconsequence 如果p 则q 单条件 蕴涵P 前提Q 结论 2 12 20203 07AM discretemath PropositionLogic 23 Table5Implication蕴涵式 2 12 20203 07AM discretemath PropositionLogic 24 EXAMPLE5Implication蕴涵式 Whatisthevalueofthevariablexafterthestatementif2 2 4thenx x 1ifx 0beforethisstatementisencountered Thesymbol standsforassignment Thestatementx x 1meanstheassignmentofthevalueofx 1tox Solution Since2 2 4istrue theassignmentstatementx x 1isexecuted Hence xhasthevalue0 1 1afterthisstatementisencountered 2 12 20203 07AM discretemath PropositionLogic 25 Example IfIamelected thenIwilllowertaxes Ifyouget100 onthefinal thenyou llgetanA IftodayisFriday then2 3 6 Wewouldnotusetheselastimplicationsinnaturallanguage sincethereisnorelationshipbetweenthehypothesisandtheconclusionineitherimplication InmathematicalreasoningweconsiderimplicationisindependentofamoregeneralsortthanweuseinEnglish EXAMPLE6Implication蕴涵式 2 12 20203 07AM discretemath PropositionLogic 26 Converse逆Contrapositive逆反Inverse反 Therearesomerelatedimplicationsthatcanbeformedfromp q Thepropositionq piscalledtheconverseofp q Thecontrapositiveofp qistheproposition q p Theproposition p qiscalledtheinverseofp q 2 12 20203 07AM discretemath PropositionLogic 27 p q Ifitraining thenthehometeamwins q p Ifthehometeamdoesnotwin thenitisnotraining q p Ifthehometeamwins thenitisraining p q Ifitisnotraining thenthehometeamdoesnotwin EXAMPLE7Contrapositive逆反 2 12 20203 07AM discretemath PropositionLogic 28 EXAMPLE8Contrapositive逆反 Findtheconverseandthecontrapositiveoftheimplication IftodayisThursday thenIhaveatesttoday Solution Theconverseis IfIhaveatesttoday thentodayisThursday Andthecontrapositiveofthisimplicationis IfIdonothaveatesttoday thentodayisnotThursday 2 12 20203 07AM discretemath PropositionLogic 29 双条件 等价Biconditional Letpandqbepropositions Thebiconditionalpqisthepropositionthatistruewhenpandqhavethesametruthvaluesandisfalseotherwise ThetruthtableforpqisshowninTable6 P当且仅当q 双条件 等价 2 12 20203 07AM discretemath PropositionLogic 30 Table6Biconditional双条件 等价 2 12 20203 07AM discretemath PropositionLogic 31 Youcantaketheflightifandonlyifyoubuyaticket note p qhasexactlythesametruthvalueas p q q p EXAMPLE9Biconditional双条件 等价 2 12 20203 07AM discretemath PropositionLogic 32 Precedence优先级oflogicaloperators Howtouseparenthesestospecifytheorderinwhichlogicaloperatorsinacompoundproposition 2 12 20203 07AM discretemath PropositionLogic 33 TranslatingEnglishSentences TherearemanyreasonstotranslateEnglishsentencesintoexpressionsinvolvingpropositionalvariablesandlogicalconnectives Inparticular Englishisoftenambiguous Translatingsentencesintologicalexpressionsremovestheambiguity 2 12 20203 07AM discretemath PropositionLogic 34 HowtotranslatethisEnglishsentenceintoalogicalexpression YoucanaccesstheInternetfromcampusonlyifyouareacomputersciencemajororyouarenotafreshman Solution First usepropositionalvariablestorepresenteachsentencepartanddeterminetheappropriatelogicalconnectivesbetweenthem EXAMPLE10Translate 2 12 20203 07AM discretemath PropositionLogic 35 Letarepresent YoucanaccesstheInternetfromcampus Letcrepresent Youareacomputersciencemajor Letfrepresent Youareafreshman thenthesentence YoucanaccesstheInternetfromcampusonlyifyouareacomputersciencemajororyouarenotafreshman canberepresentedas a c f EXAMPLE10TranslateSolution 2 12 20203 07AM discretemath PropositionLogic 36 Translatethissentenceintoalogicalexpression Youcannotridetherollercoasterifyouareunder4feettallunlessyouareolderthan16yearsold EXAMPLE11Translate 2 12 20203 07AM discretemath PropositionLogic 37 EXAMPLE11TranslateSolution q Youcanridetherollercoaster 过山车 r Youareunder4feettall s Youareolderthan16yearsold Youcannotridetherollercoasterifyouareunder4feettallunlessyouareolderthan16yearsold canberepresentedas r s q 2 12 20203 07AM discretemath PropositionLogic 38 EXAMPLE12Translate 说离散数学是枯燥无味的或毫无价值的 那是不对的 P 离散数学是有味道的 Q 离散数学是有价值的 P Q 2 12 20203 07AM discretemath PropositionLogic 39 EXAMPLE13Translate WebPageSearching MostWebsearchenginessupportBooleansearchingtechniques whichusuallycanhelpfindWebpagesaboutparticularsubjects Forinstance usingBooleansearchingtofindWebpagesaboutuniversitiesinNewMexico wecanlookforpagesmatchingNEWANDMEXICOANDUNIVERSITIES TheresultsofthissearchwillincludethosepagesthatcontainthethreewordsNEW MEXICO andUNIVERSITIES 2 12 20203 07AM discretemath PropositionLogic 40 SystemSpecifications Systemspecificationsshouldnotcontainconflictingrequirements Consequently propositionalexpressionsrepresentingthesespecificationsneedtobeconsistent Thatis theremustbeanassignmentoftruthvaluestothevariablesintheexpressionsthatmakesalltheexpressionstrue 2 12 20203 07AM discretemath PropositionLogic 41 Determinewhetherthesesystemspecificationsareconsistent Thediagnosticmessageisstoredinthebufferoritisretransmitted Thediagnosticmessageisnotstoredinthebuffer Ifthediagnosticmessageisstoredinthebuffer thenitisretransmitted EXAMPLE14SystemSpecifications 2 12 20203 07AM discretemath PropositionLogic 42 p Thediagnosticmessageisstoredinthebuffer q Thediagnosticmessageisretransmitted Sothespecificationscanbewrittenas p q pp qThesespecificationsareconsistentsincetheyarealltruewhenpisfalseandqistrue EXAMPLE14SystemSpecifications 2 12 20203 07AM discretemath PropositionLogic 43 Inaboveexample ifthespecification Thediagnosticmessageisnotretransmitted isadded p q pp q q EXAMPLE14SystemSpecifications 2 12 20203 07AM discretemath PropositionLogic 44 LogicPuzzles Puzzlesthatcanbesolvedusinglogicalreasoningareknownaslogicpuzzles 2 12 20203 07AM discretemath PropositionLogic 45 Smullyanposedmanypuzzlesaboutanislandthathastwokindsofinhabitants 居民 knights 骑士 whoalwaystellthetruth andtheiropposites knaves 坏蛋 whoalwayslie YouencountertwopeopleAandB WhatareAandBifAsays Bisaknight andBsays Thetwoofusareoppositetypes Example15LogicPuzzles 2 12 20203 07AM discretemath PropositionLogic 46 Example16LogicPuzzles Afathertellshistwochildren aboyandagirl toplayintheirbackyardwithoutgettingdirty However whileplaying bothchildrengetmudontheirforeheads Whenthechildrenstopplaying thefathersays Atleastoneofyouhasamuddyforehead andthenasksthechildrentoanswer yes or No tothequestion Doyouknowwhetheryouhaveamuddyforehead Thefatherasksthisquestiontwice Whatwillthechildrenanswereachtimethisquestionisasked assumingthatachildcanseewhetherhisorhersiblinghasamuddyforehead butcannotseehisorherownforehead Assumethatbothchildrenarehonestandthatthechildrenanswereachquestionsimultaneously 2 12 20203 07AM discretemath PropositionLogic 47 LogiczebraPuzzlesDiscuss Solvethisfamouslogicpuzzle attributedtoAlbertEinstein andknownasthezebrapuzzle Fivemenwithdifferentnationalitiesandwithdifferentjobsliveinconsecutivehousesonastreet Thesehousesarepainteddifferentcolors Themenhavedifferentpetsandhavedifferentfavoritedrinks Determinewhoownsazebraandwhosefavoritedrinkismineralwater whichisoneofthefavoritedrinks giventheseclues TheEnglishmanlivesintheredhouse TheSpaniardownsadog TheJapanesemanisapainter TheItaliandrinkstea TheNorwegianlivesinthefirsthouseontheleft Thegreenhouseisontherightofthewhiteone Thephotographerbreedssnails Thediplomatlivesintheyellowhouse Milkisdrunkinthemiddlehouse Theownerofthegreenhousedrinkscoffee TheNorwegian shouseisnexttotheblueone Theviolinistdrinksorangejuice Thefoxisinahousenexttothatofthephysician Thehorseisinahousenexttothatofthediplomat 2 12 20203 07AM discretemath PropositionLogic 48 zebraPuzzlesSolution 2 12 20203 07AM discretemath PropositionLogic 49 PuzzlesDiscuss Fivefriendshaveaccesstoachatroom Isitpossibletodeterminewhoischattingifthefollowinginformationisknown EitherKevinorHeather orbotharechatting EitherRandyorVijay butnotboth arechatting IfAbbyischatting soisRandy VijayandKevinareeitherbothchattingorneitheris IfHeatherischatting thensoareAbbyandKevin Explainyourreasoning 2 12 20203 07AM discretemath PropositionLogic 50 PuzzlesDiscuss KevinorHeatherEitherRandyxorVijayAbby RandyVijay KevinHeather AbbyandKevin 2 12 20203 07AM discretemath PropositionLogic 51 Logicandbitoperations Computerbitoperationscorrespondtothelogicalconnectives ORANDXOR 2 12 20203 07AM discretemath PropositionLogic 52 位串bitstring Abitstringisasequenceofzeroormorebits Thelengthofthisstringisthenumberofbitsinthestring 2 12 20203 07AM discretemath PropositionLogic 53 Table7BitOperators 2 12 20203 07AM discretemath PropositionLogic 54 EXAMPLE14BitOperators FindthebitwiseOR bitwiseAND andbitwiseXORofthebitstrings0110110110and1100011101 Here bitstringswillbesplitintoblocksoffourbitstomakethemeasiertoread Solution ThebitwiseOR bitwiseAND andbitwiseXORofthesestringsareobtainedbytakingtheOR AND andXORofthecorrespondingbits respectively Thisgivesus011011011011000111011110111111bitwiseOR0100010100bitwiseAND1010101011bitwiseXOR 2 12 20203 07AM discretemath PropositionLogic 55 命题公式 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 2 12 20203 07AM discretemath PropositionLogic 56 命题公式的运算 命题公式的运算规则 逻辑联接词的优先级 命题公式的表达式的运算规律 同代数表达式命题公式的运算方法 所有公式中的命题变量用指定命题 真值 代入 或指派 得到一个公式对应的真值 2 12 20203 07AM discretemath PropositionLogic 57 命题公式分类 永真命题公式 Tautology 公式中的命题变量无论怎样代入 公式对应的真值恒为T 永假命题公式 Contradiction 公式中的命题变量无论怎样代入 公式对应的真值恒为F 可满足命题公式 Satisfaction 公式中的命题变量无论怎样代入 公式对应的真值总有一种情况为T 一般命题公式 Contingency 既不是永真公式也不是永假公式 2 12 20203 07AM discretemath PropositionLogic 58 Table1tautologiesandcontradictions 2 12 20203 07AM discretemath PropositionLogic 59 EXAMPLE12tautologiesandcontradictions Wecanconstructexamplesoftautologiesandcontradictionsusingjustoneproposition Considerthetruthtablesofp pandp p showninTable1 Sincep pisalwaystrue itisatautology Sincep pisalwaysfalse itisacontradiction 2 12 20203 07AM discretemath PropositionLogic 60 命题公式性质1 性质1 如果一个命题公式有N个互异的命题变量 则命题公式对应的真值有2的N次幂种可能分布 2 12 20203 07AM discretemath PropositionLogic 61 命题公式性质2 性质2 1 设P是永真命题公式 则P的否定公式是永假命题公式 2 设P是永假命题公式 则P的否定公式是永真命题公式 3 设P Q是永真命题公式 则P P Q P Q P Q P Q 也是永真命题公式 2 12 20203 07AM discre