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

1,离 散 数 学 Discrete Mathematics,山东科技大学 信息科学与工程学院,2,为什么要学习离散数学？,李开复：给中国学生的第四封信大学四年应该这么度过 数学是理工科学生必备的基础。很多学生在高中时认为数学是最难学的，到了大学里，一旦发现本专业对数学的要求不高，就会彻底放松对数学知识的学习，而且他们看不出数学知识有什么现实的应用或就业前景。但大家不要忘记，绝大多数理工科专业的知识体系都建立在数学的基石之上。例如，要想学好计算机工程专业，那至少要把离散数学（包括集合论、图论、数理逻辑等）、线性代数、概率统计和数学分析学好；要想进一步攻读计算机科学专业的硕士或博士学位，可能还需要更高的数学素养。,3,课程回顾,第1次课： 命题；5个联结词 第2次课： 合式公式 命题的翻译 命题公式等价的两种证明方法 真值表 利用命题定律推导,第一章 命题逻辑 第3讲15 重言式与蕴含式 16 其他连结词,重点：重言式、蕴含式 难点：用推理方法证明蕴含式。,5,回顾,表1-4.4,6,回顾,表 1-4.2,7,一、重言式和矛盾式 定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式。,定义1-5.2 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式。,对于矛盾式也有类似于定理1-5.1和定理1-5.2的结果。,证明 由于重言式的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值仍永为T。 口,定理1-5.2 一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。,证明 设A和B为两个重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故ABT，ABT。 口,定理1-5.1 任何两个重言式的合取或析取，仍然是一个重言式。,因为重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了，后面将重点研究重言式。重言式最有用，因为它有以下特点： 两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。 由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。,10,证明重言式的方法,给定一命题公式，至少存在一个指派，公式相应确定真值为真，称为可满足式。 重言式必是可满足式，反之一般不真。 判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。 在命题逻辑中，由于任何一个命题公式的指派数目总是有限的，所以命题逻辑的判定问题是可解的。其判定方法有真值表法和公式推演法。,例题1 证明(PS)R)V(PS)R)为重言式。,证明 因为PVPT， 如以(PS)R)置换P即得 (PS)R)V(PS)R) T,定理1-5.3 设A、B为两个命题公式，A B当且仅当A B为一个重言式。 证明 若AB，则A、B有相同真值，即A B永为T。 若A B为重言式，则A B永为T，故A、B的真值相同，即AB。,定理1-5.3的作用：为A B又提供了一种方法。 其他方法： （1）真值表法 （2）利用命题定律推导证明,13,例题2 证明(PQ）（PQ）,证明：据定理1-5.3 ，只需证：(PQ） （PQ）为重言式。,二、蕴含式 联结词 可用来表达。由第4节例题5可知： A B (AB)(BA) 下面讨论AB的重言式。 1.定义 定义1-5.3 当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并记作P Q。,符号和的区别与联系类似于和的关系。区别： 是逻辑联结词，属于对象语言中的符号，是公式中的符号； 不是联结词，属于元语言中的符号，表示两个公式之间的关系，不是两公式中符号。,2. 蕴含式的证明方法： (1)列真值表法： 根据定义， 只需证PQ是重言式 (2)逻辑推论 前真看后真 后假看前假 (3)等价置换,例题3 证明P PQ 证明 列出真值表： 从表中看出PPQ是一个重言式，故P PQ成立。,证明 列出真值表： 从表中看出PQP 不是一个重言式，故 PQ P不成立。,例题4 考察PQ P是否成立。,由例题3和例题4可知，PQ和QP不等价。 对PQ来说， QP称作它的逆换式； PQ称为它的反换式； QP称为它的逆反式。 它们之间的关系如表所示。,从表1-5.1中看出：(PQ）（QP） (QP）（PQ） 因此要证明P Q，只需证明Q P，反之亦然。 要证明P Q，即证PQ是重言式。 对于PQ来说，除P的真值取T，Q的真值取F这样一种指派时，PQ的真值为F外，其余情况，PQ的真值为T。 要证PQ是重言式： （1）只要对条件命题PQ的前件P，指定真值为T，若由此推出Q的真值也为T，则PQ是重言式，即P Q成立(前真看后真)； （2）同理，如条件命题PQ中，假定后件Q的真值取F，若由此推出P的真值为F，即推证了Q P 故P Q成立(后假看前假)。,例题1 推证Q(PQ） P,证法2 (后假看前假) 假定P为F，则P为T。 (a）：若Q为F，则PQ为F，Q(PQ）为F。 (b）：若Q为T，则Q为F，Q(PQ）为F。 所以Q(PQ) P成立。,证法1 (前真看后真) 假定Q(PQ）为T，则Q为T，且(PQ）为T。由Q为F，则必须P为F，故P为T。,表 1-5.2 常用的蕴含重言式,三、等价式和蕴含式的关系 就象联结词 和的关系一样，等价式与蕴含式之间也有紧密的联系。 定理1-5.4 设P、Q为任意两个命题公式，PQ的充分必要条件是P Q且Q P。,证明 若PQ，则P Q为重言式，因为 P Q (PQ)(QP)，故PQ为T且QP为T，即P Q，Q P成立。反之，若P Q且Q P，则，PQ为T且QP为T，因此P Q为T，P Q是重言式，即PQ。 这个定理也可作为两个公式等价的定义。,蕴含有下面几个常用的性质： (1)设A、B、C为合式公式，若A B且A是重言式，则B必是重言式。 证明 因为AB永为T，所以，当A为T时，B必永为T。 (2)若A B，且B C则A C，即蕴含关系是传递的。 证明 由A B，B C，即AB，BC为重言式。所以(AB)(BC)为重言式。 由表l-5.2的(11)式，(AB)(BC) AC，故由性质(1)，AC为重言式，即A C。,(3)若A B，且A C，则A (BC)。 证明 由假设AB，AC为重言式。设A为T，则B、C为T，故BC为T。因此，A(BC)为T。 若A为F，则BC不论有怎样的真值，A(BC)为T。 所以， A (BC) (4)若A B，且C B，则AC B。 证明 因为AB为T，CB为T，故(AB)(CB)为T。 即(AC)B)为T或ACB为T。 所以 AC B,四、小结 本节主要内容 1. 深刻理解以下概念 重言式 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式。 矛盾式 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式。 蕴含式 当且仅当PQ是一个重言式时，称P蕴含Q，并记作P Q。 逆换式 对PQ来说，QP称作它的逆换式。 反换式 对PQ来说， PQ称为它的反换式。 逆反式 对PQ来说， QP称为它的逆反式。,2. 掌握以下定理 定理1-5.1 任何两个重言式的合取或析取，仍然是一个重言式。 定理1-5.2 一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。 定理1-5.3 设A、B为两个命题公式，A B当且仅当A B为一个重言式。 定理1-5.4 设P、Q为任意两个命题公式，P Q的充分必要条件是P Q且Q P。 3. 会证明重言式、蕴含式,28,前面已经定义了5种联结词：，和 ，但这些联结词还不能广泛地直接表达命题间的联系，下面再定义4种命题联结词：,16 其他连结词,29,一、不可兼析取（异析取）,表1-6.1,30,31,4. 定理,证明,则,32,二、条件否定 定义 定义1-6.2 设P和Q是两个命题公式，复合命题P Q称作命题P和Q的条件否定，P Q的真值为T，当且仅当P的真值为T，Q的真值为F，否则的P Q的真值为F。,表1-6.2,2. 真值表 联结词 的定义如表1-6.2所示。,从定义可知,33,三、与非 定义,表1-6.3,2. 真值表,从表1-6.3 可以看出,2、真值表,34,3. 性质,联结词“”有如下几个性质： (a) PQQP (b) PP P (c) (PQ)(PQ)PQ (d) (PP)(QQ)PQ,35,表1-6.4,从表1-6.4可以看出,2. 真值表,1. 定义,四、或非,36,3. 性质,联结词“”有如下几个性质： (a) PQQP (b) PPP (c) (PQ)(PQ)PQ (d) (PP)(QQ)PQ,37,38,五、联结词完备集 定义 设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。 根据需要，人们还可构造形式上更为简单的联结词完备集。例如，在计算机硬件设计中，用与非门或者或非门来设计逻辑线路时，就需要构造新联结词完备集。,39,定理： ，都是联结词完备集。,证 已知,为联结词完备集，因而只需证明其中的每个联结词都可以由定义即可。,而 p pq (pp) ( pq) pp (1) (pq) pq （定义） (pp)(qq)由(1) (3) pq ( pq) ( pq) （定义） (pq)(pq) 由(1) (2),由（1）(3)可知是联结词完备集，类似可证是联结词完备集。,40,五、最小联结词组 我们一共给出了九个联结词的定义，是否还需要定义其他联结词呢？下面列出两个命题变元可构成的所有不等价的命题公式（共有16个）。,41,由上述分析，除常量及命题变元本身外，命题联结词一共有九个就够了。,42,实际上这九个联结词并非都是必要的。因为包含某些联结词的公式可以用另外一些联结词的公式等价代换。 下面考虑最小联结词组，对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。,43,所以,44,六、小结 本节所讲内容如下： 不可兼析取 设P和Q是两个命题公式，复合命题 称作P和Q的不可兼析取。 的真值为T，当且仅当P与Q的真值不同时为T，否则 的真值为F。 逆条件 设P和Q是两个命题公式，复合命题P Q 称作命题P和Q的条件否定，P Q的真值为T，当且仅当P的真值为T，Q的真值为F，否则的P Q的真值为F。 与非 设P和Q是两个命题公式，复合命题 称作命题P和Q的“与非”，当且仅当P和Q真值都是T时， 为F，否则 的真值都为T。 或非 设P和Q是两个命题公式，复合命题 称作命题P和Q的“或非”，当且仅当P和Q的真值都为F时， 的真值为T，否则 的真值都为F。,45,作业,P23：2.a)(3种方法)，8 P29：3,46,离 散 数 学 Discrete Mathematics,山东科技大学 信息科学与工程学院,第一章 命题逻辑 第4讲17 对偶与范式,要求：掌握对偶与范式，会求命题公式的主析取范式和主合取范式。 重点和难点：求命题公式的主析取范式和主合取范式。,一、对偶式 1. 复习命题定律。见15页表1-4.8,我们从表1-4.8可以看到命题定律除对合律外都是成对出现的，其不同的只是和互换。我们把这样的公式称作具有对偶规律。 定义1-7.1 在给定的命题公式中，将联结词换成，将换成 ，若有特殊变元F和T亦相互取代，所得公式A*称作A的对偶式。 显然A也是A*的对偶式。,2. 对偶式的定义,例题1 写出下列表达式的对偶式。,(P Q) R (P Q) F (P Q) (P (Q S),（a）(PQ) R （b）(PQ) T （c）(P Q) (P (Q S),A,A*,定理1-7.1 设A和A*是对偶式，P1， P2 ，Pn是出现在A和A*中的原子变元，则 A（ P1， P2 ，Pn ） A*（ P1， P2 ，Pn ） A（ P1， P2 ，Pn ） A*（ P1， P2 ，Pn ）,证明 由德摩根定律 (PQ) (P Q)， P Q (P Q) 故 A（ P1， P2 ，Pn ） A*（ P1， P2 ，Pn ） 同理 A*（ P1， P2 ，Pn ） A（ P1， P2 ，Pn ）,例题3 设A*（S，W，R）是 S (W R) ，证明 A*（S， W， R） A（S，W，R）,.所以 A*（S， W， R） A（S，W，R）,证明 由于A*（S，W，R）是 S (W R) ，,则 A*（S， W， R）是 S (W