离散数学第1章重言式与蕴含式和其它连接词.ppt

《离散数学第1章重言式与蕴含式和其它连接词.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学DiscreteMathematics山东科技大学信息科学与工程学院1为什么要学习离散数学？李开复：给中国学生的第四封信——大学四年应该这么度过数学是理工科学生必备的基础。很多学生在高中时认为数学是最难学的，到了大学里，一旦发现本专业对数学的要求不高，就会彻底放松对数学知识的学习，而且他们看不出数学知识有什么现实的应用或就业前景。但大家不要忘记，绝大多数理工科专业的知识体系都建立在数学的基石之上。例如，要想学好计算机工程专业，那至少要把离散数学（包括集合论、图论、数理逻辑等）、线性代数、概率统计和数学分析

2、学好；要想进一步攻读计算机科学专业的硕士或博士学位，可能还需要更高的数学素养。2课程回顾第1次课：命题；5个联结词第2次课：合式公式命题的翻译命题公式等价的两种证明方法真值表利用命题定律推导3第一章命题逻辑第3讲§1—5重言式与蕴含式§1—6其他连结词重点：重言式、蕴含式难点：用推理方法证明蕴含式。4回顾PQP∧Q┐(P∧Q)┐P┐Q┐P∨┐Q┐(P∧Q）（┐P∨┐Q）TTTFFFFTTFFTFTTTFTFTTFTTFFFTTTTT表1-4.45回顾表1-4.2PQP∧Q┐P(P∧Q）∧┐PTTTFFTFFFF

3、FTFTFFFFTF6一、重言式和矛盾式定义1-5.1给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式。定义1-5.2给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式。7对于矛盾式也有类似于定理1-5.1和定理1-5.2的结果。证明由于重言式的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值仍永为T。口定理1-5.2一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。证明设A和B为两个重言式

4、，则不论A和B的分量指派任何真值，总有A为T，B为T，故A∧BT，A∨BT。口定理1-5.1任何两个重言式的合取或析取，仍然是一个重言式。8因为重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了，后面将重点研究重言式。重言式最有用，因为它有以下特点：①两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。②由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。9证明重言式的方法给定一命题公式，至少存在一个指派，公式相应确定真值为真，称为可满足式。重

5、言式必是可满足式，反之一般不真。判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。在命题逻辑中，由于任何一个命题公式的指派数目总是有限的，所以命题逻辑的判定问题是可解的。其判定方法有真值表法和公式推演法。10例题1证明((P∨S)∧R)V┐((P∨S)∧R)为重言式。证明因为PV┐PT，如以((P∨S)∧R)置换P即得((P∨S)∧R)V┐((P∨S)∧R)T11定理1-5.3设A、B为两个命题公式，AB当且仅当AB为一个重言式。证明若AB，则A、B有相同真值，即AB永为T。若AB

6、为重言式，则AB永为T，故A、B的真值相同，即AB。定理1-5.3的作用：为AB又提供了一种方法。其他方法：（1）真值表法（2）利用命题定律推导证明12例题2证明┐(P∧Q）（┐P∨┐Q）证明：据定理1-5.3，只需证：┐(P∧Q）（┐P∨┐Q）为重言式。PQP∧Q┐(P∧Q)┐P┐Q┐P∨┐Q┐(P∧Q）（┐P∨┐Q）TTTFFFFTTFFTFTTTFTFTTFTTFFFTTTTT13二、蕴含式联结词可用→来表达。由第4节例题5可知：AB(A→B)∧(B→A)下面讨论A→B的重言式。1.定义定义1-5.

7、3当且仅当P→Q是一个重言式时，我们称“P蕴含Q”，并记作PQ。14符号→和的区别与联系类似于和的关系。区别：→是逻辑联结词，属于对象语言中的符号，是公式中的符号；不是联结词，属于元语言中的符号，表示两个公式之间的关系，不是两公式中符号。152.蕴含式的证明方法：(1)列真值表法：根据定义，只需证P→Q是重言式(2)逻辑推论前真看后真后假看前假(3)等价置换16例题3证明PP∨Q证明列出真值表：从表中看出P→P∨Q是一个重言式，故PP∨Q成立。PQP∨QP→P∨QTTTTTFTTFTTTFFTT17

8、证明列出真值表：从表中看出P∨Q→P不是一个重言式，故P∨QP不成立。PQP∨QP∨Q→PTTTTTFTTFTTFFFFT例题4考察P∨QP是否成立。18由例题3和例题4可知，P→Q和Q→P不等价。对P→Q来说，Q→P称作它的逆换式；┐P→┐Q称为它的反换式；┐Q→┐P称为它的逆反式。它们之间的关系如表所示。PQ┐P┐QP→Q原式┐Q→┐P逆反式Q→P逆换式┐P→┐Q