离散数学(第1章习题课)

1、2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院1 1陈瑜陈瑜Email：2022-3-282022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院2 2第一章小结第一章小结一、基本概念一、基本概念命题命题-具有具有确切真值确切真值的陈述句称为命题的陈述句称为命题, ,该命题可以取一个该命题可以取一个“值值”，称为真值。称为真值。命题的解释命题的解释-用一个具体的命题代入命题标识符用一个具体的命题代入命题标识符P P的过程的过程, ,称为对称为对P P的解释或赋值的解释或赋值( (指派指派) )原子命题、复合命题原子命题、复合命题逻辑联结词逻辑联

2、结词（、（、 、与非与非、或非、或非、条件否定、条件否定 c c ）：（1 1）联结词）联结词“”是自然语言中的是自然语言中的“非非”、“不不”和和“没有没有”等的逻等的逻辑抽象；辑抽象；（2 2）联结词）联结词“”是自然语言中的是自然语言中的“并且并且”、“既既又又”、“但但”、“和和”等的逻辑抽象；等的逻辑抽象；（3 3）联结词）联结词“”是自然语言中的是自然语言中的“或或”、“或者或者”等逻辑抽象；但等逻辑抽象；但“或或”有有“可兼或可兼或”、“不可兼或不可兼或 ”、“近似或近似或”三种，前两三种，前两种是联结词，后一种是非联结词；种是联结词，后一种是非联结词；2022-3-282022

3、-3-28计算机科学与工程学院计算机科学与工程学院3 3（4 4）联结词）联结词“”是自然语言中的是自然语言中的“如果如果，则，则”，“若若，才能，才能”、“除非除非，否则，否则”等的逻辑抽等的逻辑抽象。在自然语言中，前件为假，不管结论真假，整个象。在自然语言中，前件为假，不管结论真假，整个语句的意义，往往无法判断。但在数理逻辑中，当前语句的意义，往往无法判断。但在数理逻辑中，当前件件P P为假时，不管为假时，不管Q Q的真假如何，则的真假如何，则PQPQ都为真。此时都为真。此时称为称为“善意推定善意推定”；这里要特别提醒一下；这里要特别提醒一下“”的含的含义，在自然语言中，条件式中前提和结论

4、间必含有某义，在自然语言中，条件式中前提和结论间必含有某种因果关系，但在数理逻辑中可以允许种因果关系，但在数理逻辑中可以允许两者无必然因两者无必然因果关系果关系，也就是说，也就是说并不要求前件和后件有什么联系并不要求前件和后件有什么联系；（5 5）双条件联结词）双条件联结词“”是自然语言中的是自然语言中的“充分必要条充分必要条件件”、“当且仅当当且仅当”等的逻辑抽象；等的逻辑抽象；2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院4 4（6 6）联结词连接的是联结词连接的是两个命题真值两个命题真值之间的联结，而不是之间的联结，而不是命题内容命题内容之间的连接，因此复合

5、命题的真值只取决于之间的连接，因此复合命题的真值只取决于构成他们的各原子命题的真值，而与它们的内容、含构成他们的各原子命题的真值，而与它们的内容、含义无关，与联结词所连接的两原子命题之间是否有关义无关，与联结词所连接的两原子命题之间是否有关系无关；系无关；（7 7）联结词）联结词“”、“”、“”具有对称性，而联具有对称性，而联结词结词“”、“”没有；没有；（8 8）联结词）联结词“”、“”、“”同构成计算机的与同构成计算机的与门、或门和非门电路是相对应的，从而命题逻辑是计门、或门和非门电路是相对应的，从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。算机硬件电路的表示、分析和设计的重要

6、工具。2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院5 5命题公式命题公式-（1 1）命题变元（）命题变元（原子命题变元原子命题变元）本身是一个公式；）本身是一个公式；（2 2）如）如P P，Q Q是公式，则是公式，则( (P)P)、(PQ)(PQ)、(PQ)(PQ)、(PQ)(PQ)、(P(PQ)Q)也是公式；也是公式；（3 3）命题公式命题公式仅由仅由有限步有限步使用规则使用规则1-21-2后产生的结果。后产生的结果。该公式常用符号该公式常用符号G G、H H、等表示。等表示。公式的解释公式的解释-设设P P1 1、P P2 2、P Pn n是出现在公式是出现

7、在公式G G中的所中的所有命题变元有命题变元，指定指定P P1 1、P P2 2、P Pn n的的一组真值（如一组真值（如1 1，0 0，1 1，0 0，1 1），则这组真值称为），则这组真值称为G G的一个的一个解释解释, ,常常记为记为。2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院6 6永真式永真式( (重言式重言式) )永假式永假式( (矛盾式，不可满足公式矛盾式，不可满足公式) )可满足的可满足的命题公式的等价命题公式的等价-设设G G、H H是是公式，公式，如果在如果在任意解释任意解释下，下，G G与与H H的的真值相同，则称公式真值相同，则称公式G

8、G、H H是是等价的等价的 ，记作记作G GH H。替换定理替换定理-设设G G1 1是是G G的子公式的子公式( (即即 G G1 1是公式是公式G G的一部分的一部分) )，H H1 1是任意是任意的命题公式，在的命题公式，在G G中凡出现中凡出现G G1 1处都以处都以H H1 1替换后得到新的命题公式替换后得到新的命题公式H H，若若G G1 1 H H1 1，则则G G H H。对偶式对偶式- - 在给定的仅使用联结词在给定的仅使用联结词 、的命题公式的命题公式A A中，若中，若把把和和，F F和和T T互换而得的公式互换而得的公式A A* *，则称，则称A A* *为为A A的对偶

9、（公）式的对偶（公）式。对偶原理对偶原理-设设A A和和B B是两个命题公式，若是两个命题公式，若A A B B， 则则 A A* * B B* *2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院7 7基本等价式基本等价式命题定律命题定律 设设G G，H H，S S是任何的公式，则：是任何的公式，则：1:1:(G(G H) H)(GH)(HG)(GH)(HG)( (等价等价) )2 2：(GH) (GH) ( (GH) GH) ( (蕴涵蕴涵) )3 3：GG GG G G ( (幂等律幂等律) ) 4 4：GG GG G G5 5：GH GH HG HG ( (交

10、换律交换律) ) 6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S (GH)S ( (结合律结合律) ) 8:8: G(HS) G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G ( G (吸收律吸收律) ) 1010：G(GH) G(GH) G G 1111：G(HS) G(HS) (GH)(GS) (GH)(GS) (分配律分配律) ) 1212：G(HS) G(HS) (GH)(GS)(GH)(GS)1313：GF GF G G ( (同一律同一律) ) 1414：GTGT G G2022-3-282022-3-28计算机科学与工程学院计算机科学与工

11、程学院8 81515：GTGT T T( (零律零律) ) 1616：GFGF F F 1717：GGG G T T ( (矛盾律矛盾律) )1818：GGG G F F1919： ( (G) G) G G ( (双重否定律双重否定律) )2020：（GH)S GH)S G G（HSHS） （输出律）（输出律）2121：（G G H H）( (GH)(GGH)(GH) H) ( (排中律排中律) )2222：PQ PQ QQP P （逆反律）（逆反律）2323： (GH) (GH) GGH (De MorganH (De Morgan定律定律) ) 2424： (GH) (GH) GGH H。

12、范式范式全名叫规范型式全名叫规范型式normal form,normal form,又叫标准型式又叫标准型式, ,正规型正规型式。式。把公式进行标准化，正规化，就叫对公式求范式。把公式进行标准化，正规化，就叫对公式求范式。 命题变元或命题变元的命题变元或命题变元的否定否定称为称为句节句节。 有限个有限个句节句节的的析取式析取式称为称为子句子句； 有限个有限个句节句节的的合取式合取式称为称为短语短语。 有限个有限个短语短语的的析取式析取式称为称为析取范式析取范式； 有限个有限个子句子句的的合取式合取式称为称为合取范式合取范式。2022-3-282022-3-28计算机科学与工程学院计算机科学与工

13、程学院9 9 极小项极小项-在在n n个变元的基本积（个变元的基本积（短语短语）中，若每一个）中，若每一个变元与其否定变元与其否定并不同时存在并不同时存在，且，且二者之一必出现且仅二者之一必出现且仅出现一次出现一次，则称这种基本积为，则称这种基本积为极小项极小项。 主析取范式主析取范式-由有限个极小项组成的析取式由有限个极小项组成的析取式。 极大项极大项-在在n n个变元的基本和（个变元的基本和（子句子句）中，若每一个）中，若每一个变元与其否定变元与其否定并不同时存在并不同时存在，且，且二者之一必出现且仅二者之一必出现且仅出现一次出现一次，则这种基本和称为，则这种基本和称为极大项极大项。 主合

14、取范式主合取范式-由有限个极大项组成的合取式由有限个极大项组成的合取式。 命题公式的蕴涵命题公式的蕴涵-设设A A和和B B是两个合适公式，如果在是两个合适公式，如果在任何解释任何解释下，下，A A取值取值1 1时时B B也取值也取值1 1，则称公式，则称公式A A蕴涵公式蕴涵公式B B，并记，并记A A B B。2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院1010 基本蕴含（关系）式基本蕴含（关系）式I I1 1：P PPQ PQ ， Q QPQ PQ P PPQ PQ ， Q QPQ PQ 扩充法则扩充法则( (析取引入律析取引入律) )I I2 2：PQ

15、PQ P P ， PQPQQ Q （PQPQ）P P ，（，（PQPQ）Q Q 化简化简法则法则( (合取消去律合取消去律) )I I3 3：P P（PQPQ） Q Q 假言推论（分离规则）假言推论（分离规则）I I4 4：Q Q（PQPQ） P P 否定式假言推论（拒取式）否定式假言推论（拒取式）I I5 5：PP（PQPQ） Q Q 析取三段论（选言三段论）析取三段论（选言三段论）I I6 6：（：（PQPQ）（QRQR） PR PR 假言（前提条件）三段论假言（前提条件）三段论I I7 7：（：（PQPQ）（PRPR）（QRQR） R R 二难推论二难推论I I8 8：（：（PQPQ）（

16、RSRS）（PRPR）（QSQS）I I9 9：（：（P PQ Q）（Q QR R） P PR RI I1010：（：（PQPQ）（PRPR） QR QR 归结原理归结原理2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院1111 命题逻辑的推理方法命题逻辑的推理方法-设设G G是由一组命题公式组成的集合，如果存在命题公式的有限序列：是由一组命题公式组成的集合，如果存在命题公式的有限序列： H1H1，H2H2，HnHn（=H=H） 其中，其中，HiHi或者是或者是G G中的某个公式，或者是前面的某些中的某个公式，或者是前面的某些HjHj（jiji）的有）的有效结论，并

17、且效结论，并且HnHn就是就是H H，则称公式，则称公式H H是是G G的逻辑结果（有效结论），或者的逻辑结果（有效结论），或者称由称由G G演绎出结论演绎出结论H H来。来。 推理规则推理规则- P P规则（称为前提引用规则）：规则（称为前提引用规则）：在推导的过程中，可随时引入前提集在推导的过程中，可随时引入前提集合中的任意一个前提；合中的任意一个前提； 规则（逻辑结果引用规则）：规则（逻辑结果引用规则）：在推导的过程中，利用基本等价式在推导的过程中，利用基本等价式和蕴涵式，由证明过程中某些中间公式变换出新的公式，若依据的是等和蕴涵式，由证明过程中某些中间公式变换出新的公式，若依据的是等价

18、式，规则标明为价式，规则标明为TETE，若依据的是蕴涵式，规则标明为，若依据的是蕴涵式，规则标明为TI TI 。 规则（附加前提规则）：规则（附加前提规则）：如果能从给定的前提集合如果能从给定的前提集合G G与公式与公式P P推推导出导出S S，则能从此前提集合，则能从此前提集合G G推导出推导出PSPS。 即即G G1 1,G,G2 2,G,Gn n PS PS 当且仅当当且仅当 G G1 1,G,G2 2,G,Gn n，P P S S2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院1212 二、基本方法二、基本方法 1、应用基本等价式及置换规则进行等价演算应用基

19、本等价式及置换规则进行等价演算 2 2、求主析取（主合取）范式的方法求主析取（主合取）范式的方法 公式转换法公式转换法（1 1）利用等价公式中的等价式和蕴涵式将公式中的）利用等价公式中的等价式和蕴涵式将公式中的、用联用联结词结词、来取代；来取代；（2 2）利用德）利用德 摩根定律将否定号摩根定律将否定号移到各个命题变元的前端；移到各个命题变元的前端；（3 3）利用结合律、分配律、吸收律、幂等律、交换律等将公式）利用结合律、分配律、吸收律、幂等律、交换律等将公式化成其等价的析取范式和合取范式。化成其等价的析取范式和合取范式。（4 4）在析取范式的短语和合取范式的子句中，如同一命题变元在析取范式的

20、短语和合取范式的子句中，如同一命题变元出现多次，则将其化成只出现一次。出现多次，则将其化成只出现一次。（5 5）去掉析取范式中所有永假式的短语和合取范式中所有永真去掉析取范式中所有永假式的短语和合取范式中所有永真式的子句，即去掉短语中含有形如式的子句，即去掉短语中含有形如PPP P的子公式和子句中含有的子公式和子句中含有形如形如PPP P的子公式。的子公式。2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院1313（6 6）若析取范式的某一个短语中缺少该命题公式中所规定的命题）若析取范式的某一个短语中缺少该命题公式中所规定的命题变元，则可用公式：变元，则可用公式： （

21、）Q=QQ=Q将命题变元将命题变元P P补进去，并利用分配律展开，然后合并相同的短语，补进去，并利用分配律展开，然后合并相同的短语，此时得到的短语将是此时得到的短语将是标准的极小项标准的极小项；（7 7）若合取范式的某一个子句中缺少该命题公式中所规定的命题）若合取范式的某一个子句中缺少该命题公式中所规定的命题变元，则可用公式：变元，则可用公式： （）Q=QQ=Q将命题变元将命题变元P P补进去，并利用分配律展开，然后合并相同的子句，补进去，并利用分配律展开，然后合并相同的子句，此时得到的子句将是此时得到的子句将是标准的极大项标准的极大项。（8 8）利用幂等律将相同的极小项和极大项合并，同时利用

22、交换律）利用幂等律将相同的极小项和极大项合并，同时利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。进行顺序调整，由此可转换成标准的主析取范式和主合取范式。 真值表技术法真值表技术法主合取范式主合取范式-在命题公式的真值表中，使公式取值在命题公式的真值表中，使公式取值0 0时的解释所时的解释所对应的对应的全部极大项的合取式全部极大项的合取式。主析取范式主析取范式-在命题公式的真值表中，使公式取值在命题公式的真值表中，使公式取值1 1时的解释所时的解释所对应的对应的全部极小项的析取式全部极小项的析取式。2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院1

23、414（1 1）求出公式的）求出公式的真值表真值表（2）求出求出使公式取值使公式取值0 0时的解释所对应的时的解释所对应的全部极大项全部极大项 极大项取值极大项取值0“0“当且仅当当且仅当”：如果极大项中出现的是原子本：如果极大项中出现的是原子本身，则原子赋值为身，则原子赋值为0 0；如果出现的是原子的否定，则原子赋值为；如果出现的是原子的否定，则原子赋值为1 1。 （3 3）求出使公式取值）求出使公式取值1 1时的解释所对应的时的解释所对应的全部极小项全部极小项 极小项取值极小项取值1 “1 “当且仅当当且仅当”：如果极小项中出现的是原子：如果极小项中出现的是原子本身，则原子赋值为本身，则原

24、子赋值为1 1；如果出现的是原子的否定，则原子赋值；如果出现的是原子的否定，则原子赋值为为0 0。 3 3、推理的各种方法、推理的各种方法 （1 1）直接法）直接法 （2 2）利用）利用CPCP规则规则 （3 3）反证法）反证法 2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院1515 三、典型例题三、典型例题1 1、证明、证明 (PQ) (PQ) (PQ) (PQ) (P(PQ)Q)(PQ)(PQ)(PQ) (PQ) (PQ)(PQ)(P PQ) Q) (PQ)(PQ)P)P) (PQ)(PQ)Q) Q) (P(PP)(QP)(QP)P)(P(PQ)(QQ)(QQ

25、)Q) (Q(QP)P)(P(PQ)Q) (Q(QP)P)(P(PQ)Q) ( (QP)QP)( (P PQ)Q)(QP)(QP)(P(PQ)Q)(P(PQ)Q)2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院16162 2、 G=G=( ()，求主析取和主合取范式。，求主析取和主合取范式。解解：首先列出其真值表如下：首先列出其真值表如下：P Q R P Q R PQPQ（PQPQ）( (PQ)RPQ)R0 0 00 0 01 10 00 00 0 10 0 11 10 01 10 1 00 1 01 10 00 00 1 10 1 11 10 01 11 0 01

26、 0 00 01 11 11 0 11 0 10 01 11 11 1 01 1 01 10 00 01 1 11 1 11 10 01 1极大项极大项极小项极小项PQRPQRPPQRQRPPQRQRPPQRQRPQRPQRPPQQR RPPQRQRPQRPQR主析取范式主析取范式= =（PPQRQR）（PQRPQR） （PPQQR R）（PPQRQR）（PQRPQR）主合取范式主合取范式= =（ PQRPQR ）（ PPQRQR ）（PPQRQR）2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院17173 3、用公式转换法求上题中的主析取和主合取范式、用公式转换法

27、求上题中的主析取和主合取范式( ()（PQPQ）R R （PPQ Q）RR（PRPR）（QRQR）（PRPR（QQQQ）（QRQR（PPPP）（PRPRQ Q）（PRQPRQ）（QRQRP P）（QRPQRP）（PRPRQ Q）（PRQPRQ）（QRQRP P） （主合取范式）主合取范式）( ()（PQPQ）R R （PPQ Q）RR（PPQQ（RRR R）（RR（PPP P）（QQQ Q）（PPQRQR）（PPQQR R）（RPRP）（RRP P）（PPQRQR）（PPQQR R）（RPRP（QQQ Q） （RRP P（QQQ Q）（PPQRQR）（PPQQR R）（RPQRPQ） （RPR

28、PQ Q）（RRP PQQ）（RRP PQ Q）（主析取范式）（主析取范式）2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院1818 4 4、P P2525 14 14 解：根据给定的条件有下述命题公式：解：根据给定的条件有下述命题公式：（AA（C C D D）（BCBC）（CDCD）（AA（CCD D）（CDCD）（BBC C）（CCD D）（AAB B）（CCDDB B）（CDCDB B） （AAC C）（CCDDC C）（CDCDC C）（CCD D）（AAB B）（CCDDB B）（CDCDB B） （AAC C）（CDCDC C） （CCD D）（AABB

29、C C）（CCDDBBC C）（CDCDBBC C）（AACCC C）（CDCDCCC C）（AABBD D）（CCDDBBD D）（CDCDBBD D）（AACCD D）（CDCDCCD D）（由题意和矛盾律）（由题意和矛盾律）2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院1919（CDCDB B）（AAC C）（CDCD）（CCDDB B）（CDCDB BAA） （CDCDB BA A） （AACBCB） （AACCB B） （CDCDAA） （CDCDA A）（CCDDBABA）（CCDDBBA A）（CDCDB BAA） （AACBDCBD） （AACBC

30、BD D） （AACCBDBD） （AACCBBD D） （CDCDABAB） （CDCDAAB B） （CDCDABAB） （CDCDAAB B）（CCDDBABA）（CCDDBBA A）（CDCDB BAA） （AACBDCBD） （CDCDAAB B） （CDCDABAB） （CCDDBABA）（CDCDB BAA） （AACBDCBD）（CCDDBABA）所以，共有三种选派方案：所以，共有三种选派方案：A和和C，A和和D，B和和D 2022-3-282022-3-28计算机科学与工程学院计算机科学与工程学院20205 5、P P2525 18 18解：根据给定的条件有下述命题：解：根据给定的条件有下述命题：P P：珍宝藏在东厢房：珍宝藏在东厢房Q Q：藏宝的房子靠近池塘：藏宝的房子靠近池塘R R：