离散数学第1章命题逻辑

《离散数学第1章命题逻辑》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章命题逻辑（PropositionLogic）命题符号化及联结词命题公式及分类等值演算联结词全功能集对偶与范式推理理论1234562简介逻辑学：研究推理的一门学科数理逻辑：用数学方法研究推理的一门数学学科——一套符号体系+一组规则3简介数理逻辑的内容：古典数理逻辑：命题逻辑、谓词逻辑现代数理逻辑：逻辑演算、公理化集合论、递归论、模型论、证明论4命题逻辑命题(Proposition)：一个有确定真或假意义的语句。命题符号化及联结词15EXAMPLE1下列句子都是命题：1.华盛顿是美国的首都。2.

2、多伦多是加拿大的首都。3.1+1=2。4.2+2=3。命题1和3是真命题，2和4是假命题。命题符号化及联结词6命题符号化及联结词EXAMPLE2考虑如下句子：1.现在几点了？2.认真阅读一下。3.x+1=2.4.x+y=z.句子1和2不是命题，因为它们都不是陈述句。句子3和4不是命题，由于x，y和z的值不确定，使得它们的真值都不唯一。7命题的语句形式：陈述句非命题语句：疑问句、命令句、感叹句、非命题陈述句：悖论语句（真值不唯一）命题符号化及联结词8命题的符号表示：大小写英文字母：P、Q、R、p、q

3、、r……命题真值(TruthValues)的表示：真：T、1假：F、0命题符号化及联结词9命题语句真值确定的几点说明：1、时间性2、区域性3、标准性命题真值间的关系表示：真值表(TruthTable)命题符号化及联结词10DEFINITION1.设p为任一命题，复合命题“非p”（或“p的否定”）称为p的否定式。记作﹁p。﹁为否定联结词。真值表见Table1。(Letpbeaproposition.Thestatement“Itisnotthecasethatp.”isanotherproposit

4、ion,calledthenegationofp.Thenegationofpisdenotedby﹁p.Theproposition﹁pisread“notp.”)p的否定命题符号化及联结词11Table1Table1否定命题的真值表p﹁p1001命题符号化及联结词12EXAMPLE3设p表示“今天是星期五”，则﹁p表示“今天不是星期五”。显然，当p的真值为0时，﹁p的真值为1。命题符号化及联结词13命题符号化及联结词设p，q为两命题，复合命题“p并且q”（或“p和q”）称作p与q的合取式。记作

5、p∧q。∧为合取联结词。真值表见Table2。(Letpandqbepropositions.Theproposition"pandq,"denotedbyp∧q,isthepropositionthatistruewhenbothpandqaretrueandisfalseotherwise.Thepropositionp∧qiscalledtheconjunctionofpandq.)p和q的合取DEFINITION2.14命题符号化及联结词Table2Table2两个命题的合取的真值表pqp

6、∧q00011011000115EXAMPLE4用p表示命题“今天是星期五”，q表示命题“今天下雨”，则命题p与q的合取式是什么？解答：p与q的合取式p∧q是“今天是星期五，而且今天下雨。”如果是星期五，又下雨，则该命题为真；如果是除星期五外的任意一天，或者虽是星期五但没下雨，则该命题为假。命题符号化及联结词16命题符号化及联结词设p，q为两命题，复合命题“p或q”称作p与q的析取式。记作p∨q。∨为析取联结词。真值表见Table3。(Letpandqbepropositions.Thepropo

7、sition"porq,"denotedbyp∨q,isthepropositionthatisfalsewhenpandqarebothfalseandtrueotherwise.Thepropositionp∨qiscalledthedisjunctionofpandq.)p和q的析取DEFINITION3.17命题符号化及联结词Table3Table3两个命题的析取的真值表pqp∨q00011011011118还是以Example4为例，命题p与q的析取式是什么？解答：p与q的析取式p∨q是

8、“今天是星期五或今天下雨。”只有今天既不是星期五，又没有下雨，则该命题为假；如果今天是星期五或者今天下雨了（包括下雨的星期五），则该命题就为真。EXAMPLE5命题符号化及联结词19命题符号化及联结词设p，q为两命题，复合命题“如果p，则q”称作p与q的蕴含式。记作p→q。称p为蕴含式的前件(hypothesis)，q为蕴含式的后件(conclusion)。→称作蕴含联结词。真值表见Table4。(Letpandqbepropositions.Theimplicationp→qis