资源描述
1Discrete Mathematics2为什么要学习离散数学？李开复：给中国学生的第四封信给中国学生的第四封信大学四年应该这么度过大学四年应该这么度过数学是理工科学生必备的基础。很多学生在高中时认为数学是最难学的，到了大学里，一旦发现本专业对数学的要求不高，就会彻底放松对数学知识的学习，而且他们看不出数学知识有什么现实的应用或就业前景。但大家不要忘记，绝大多数理工科专业的知识体系都建立在数学的基石之上。例如，要例如，要想学好计算机工程专业，那至少要把离散数学（包括集合论、想学好计算机工程专业，那至少要把离散数学（包括集合论、图论、数理逻辑等）、图论、数理逻辑等）、线性代数、概率统计和数学分析学好；要想进一步攻读计算机科学专业的硕士或博士学位，可能还需要更高的数学素养。3课程回顾第1次课：命题；5个联结词第2次课：合式公式命题的翻译命题公式等价的两种证明方法真值表利用命题定律推导第一章 命题逻辑 第3讲15 重言式与蕴含式 16 其他连结词重点：重言式、蕴含式难点：用推理方法证明蕴含式。5回顾PQPQ(PQ)PQPQ(PQ）（PQ）TT T F F F F TTF F T F T T TFT F T T F T TFF F T T T T T表1-4.46回顾 表 1-4.2 P Q PQ P(PQ）PT T T F FT F F F FF T F T FF F F T F7一、重言式和矛盾式一、重言式和矛盾式 定义定义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证明重言式的方法证明重言式的方法v给定一命题公式，至少存在一个指派，公式相应确定真值为真，称为可满足式。v重言式必是可满足式，反之一般不真。v判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。v在命题逻辑中，由于任何一个命题公式的指派数目总是有限的，所以命题逻辑的判定问题是可解的。其判定方法有真值表法和公式推演法。例题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）为重言式。PQPQ(PQ)PQPQ(PQ）（PQ）TT T F F F F TTF F T F T T TFT F T T F T TFF F T T T T T二、蕴含式二、蕴含式 联结词 可用来表达。由第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成立。P Q PQPPQT T T TT F T TF T T TF F T T 证明 列出真值表：从表中看出PQP 不是一个重言式，故 PQ P不成立。P Q PQPQPT T T TT F T TF T T FF F F T例题4 考察PQ P是否成立。由例题3和例题4可知，PQ和QP不等价。对PQ来说，vQP称作它的逆换式逆换式；vPQ称为它的反换式反换式；vQP称为它的逆反式逆反式。它们之间的关系如表所示。P Q PQPQ原式原式Q P 逆反式逆反式QP逆换式逆换式PQ 反换式反换式T T F F T T T TT F F T F F T TF T T F T T F FF F T T T T T T从表1-5.1中看出：(PQ）（QP）(QP）（PQ）因此要证明P Q，只需证明Q P，反之亦然。v要证明P Q，即证PQ是重言式。v对于PQ来说，除P的真值取T，Q的真值取F这样一种指派时，PQ的真值为F外，其余情况，PQ的真值为T。v要证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 常用的蕴含重言式 PQ P1 PQ Q2 P PQ3 P PQ4 Q PQ5 (PQ）P6 (PQ）Q7 P(PQ）Q8 Q(PQ）P9 P(PQ）Q10 (PQ）(QR）PR11 (PQ）(PR）(QR）R12 (PQ）(RS）(PR)(QS)13 (P Q)(Q R)(P R)14三、等价式和蕴含式的关系三、等价式和蕴含式的关系 就象联结词 和的关系一样，等价式与蕴含式之间也有紧密的联系。定理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 P QTT FTF TFT TFF F一、不可兼析取（异析取）一、不可兼析取（异析取）表1-6.1QP30(1)P QQ P(2)()()P QRPQ R(3)()()()PQ RPQPR(4)()()()P QPQPQ 6P PFF PPT PP（），(5)(P Q)(P Q)314.定理P RP P QF QQ Q RQ P QF PP P Q RR RF 证明则 如果PQ 32二、条件否定定义定义1-6.2 设P和Q是两个命题公式，复合命题P Q称作命题P和Q的条件否定，P Q的真值为T，当且仅当P的真值为T，Q的真值为F，否则的P Q的真值为F。PQP Q TT FTF TFT FFF F表1-6.22.真值表联结词 的定义如表1-6.2所示。从定义可知cPQPQ （）33三、与非定义 PQTT FTF TFT TFF T表1-6.32.真值表从表1-6.3 可以看出PQPQ（）PQ2、真值表343.性质联结词“”有如下几个性质：(a)PQQP(b)PP P(c)(PQ)(PQ)PQ(d)(PP)(QQ)PQ 35 PQTT FTF FFT FFF T表1-6.4从表1-6.4可以看出2.真值表1.定义四、或非PQ()PQPQ 363.性质联结词“”有如下几个性质：(a)PQQP(b)PPP(c)(PQ)(PQ)PQ(d)(PP)(QQ)PQ3738五、联结词完备集五、联结词完备集定义定义 设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个）。41PQ12345678910 1112 13 14 15 16TTTFTTFFTFTFTFTFTFTFTFTFFTFTTFFTFTTFFTTFFTTFFTTFTFFTFTFFTFFFTTFTFTTFTFTFPQ永真永假PQ非P非Q合取与非析取或非若P则Q逆条件双条件不可兼析取若Q则P逆条件由上述分析，除常量及命题变元本身外，命题联结词一共有九个就够了。42实际上这九个联结词并非都是必要的。因为包含某些联结词的公式可以用另外一些联结词的公式等价代换。下面考虑最小联结词组，对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。43P Q（）(PQ)()cPQPQ ()PQPQ()PQPQ 所以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。QPQPQPPQPQPQPQPQPQ45作业P23：2.a)(3种方法)，8P29：346Discrete Mathematics山东科技大学山东科技大学信息科学与工程学院信息科学与工程学院第一章 命题逻辑第4讲17 对偶与范式 要求：掌握对偶与范式，会求命题公式的主析取范式和主合取范式。重点和难点：求命题公式的主析取范式和主合取范式。一、对偶式一、对偶式1.复习命题定律。见15页表1-4.8对合律P P1幂等律PP P，PP P2结合律(PQ）R P（QR）(PQ）R P（QR）3交换律PQ QPPQ QP4分配律P（QR）（PQ）（PR）P（QR）（PQ）（PR）5吸收律P（PQ）PP（PQ）P6德摩根律(PQ)PQ(PQ)PQ7同一律PF P，PT P8零律PT T，PF F9否定律PP T，PP F10 我们从表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)AA*定理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 R)，但 A（S，W，R）是 S (W R)，故 A（S，W，R）是(S (W R)S(W R)定理1-7.2 设P1，P2，Pn是出现在公式A和B中的所有原子变元，如果A B，则A*B*。证明 因为A B，即1212(,)(,)nnApppBppp1212*(,)*(,)nnAp ppBp pp 是一个重言式，故也是一个重言式。即由定理1-7.1得因此 A*B*A(p1,p2,pn)B(p1,p2,pn)A(p1,p2,pn)B(p1,p2,pn)定理定理1-7.2的作用：为的作用：为A B又提供了一种方法。又提供了一种方法。其他方法：其他方法：（1）真值表法）真值表法（2）利用命题定律推导证明）利用命题定律推导证明（3）证明）证明AB为永真式为永真式
展开阅读全文