《离散数学(第1章习题课)汇编》由会员分享，可在线阅读，更多相关《离散数学(第1章习题课)汇编（24页珍藏版）》请在金锄头文库上搜索。
1、陈瑜,Email：chenyu.inbox 2019年11月10日星期日,离散 数学,计算机学院,2019/11/10,计算机学院,2/24,第一章小结,一、基本概念 命题-具有确切真值的陈述句称为命题,该命题可以取一个“值”，称为真值。 命题的解释-用一个具体的命题代入命题标识符P的过程,称为对P的解释或赋值(指派) 原子命题、复合命题 逻辑联结词（、与非、或非、条件否定 c ）： （1）联结词“”是自然语言中的“非”、“不”和“没有”等的逻辑抽象； （2）联结词“”是自然语言中的“并且”、“既又”、“但”、“和”等的逻辑抽象； （3）联结词“”是自然语言中的“或”、“或者”等逻辑抽象；但“
2、或”有“可兼或”、“不可兼或”、“近似或”三种，前两种是联结词，后一种是非联结词；,2019/11/10,计算机学院,3/24,（4）联结词“”是自然语言中的“如果，则”，“若，才能”、“除非，否则”等的逻辑抽象。在自然语言中，前件为假，不管结论真假，整个语句的意义，往往无法判断。但在数理逻辑中，当前件P为假时，不管Q的真假如何，则PQ都为真。此时称为“善意推定”；这里要特别提醒一下“”的含义，在自然语言中，条件式中前提和结论间必含有某种因果关系，但在数理逻辑中可以允许两者无必然因果关系，也就是说并不要求前件和后件有什么联系； （5）双条件联结词“”是自然语言中的“充分必要条件”、“当且仅当”
3、等的逻辑抽象；,2019/11/10,计算机学院,4/24,（6）联结词连接的是两个命题真值之间的联结，而不是命题内容之间的连接，因此复合命题的真值只取决于构成他们的各原子命题的真值，而与它们的内容、含义无关，与联结词所连接的两原子命题之间是否有关系无关； （7）联结词“”、“”、“”具有对称性，而联结词“”、“”没有； （8）联结词“”、“”、“”同构成计算机的与门、或门和非门电路是相对应的，从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。,2019/11/10,计算机学院,5/24,命题公式- （1）命题变元（原子命题变元）本身是一个公式； （2）如P，Q是公式，则(P)、(PQ
4、)、(PQ)、(PQ)、(PQ)也是公式； （3）命题公式仅由有限步使用规则1-2后产生的结果。该公式常用符号G、H、等表示。 公式的解释-设P1、P2、Pn是出现在公式G中的所有命题变元，指定P1、P2、Pn的一组真值（如1，0，1，0，1），则这组真值称为G的一个解释,常记为。,2019/11/10,计算机学院,6/24,永真式(重言式) 永假式(矛盾式，不可满足公式) 可满足的 命题公式的等价-设G、H是公式，如果在任意解释下，G与H的真值相同，则称公式G、H是等价的 ，记作GH。 替换定理-设G1是G的子公式(即 G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1
5、替换后得到新的命题公式H，若G1 H1，则G H。 对偶式- 在给定的仅使用联结词 、的命题公式A中，若把和，F和T互换而得的公式A*，则称A*为A的对偶（公）式。 对偶原理-设A和B是两个命题公式，若A B， 则 A* B*,2019/11/10,计算机学院,7/24,基本等价式命题定律,设G，H，S是任何的公式，则： 1:(G H)(GH)(HG) (等价) 2：(GH) (GH) (蕴涵) 3：GG G (幂等律) 4：GG G 5：GH HG (交换律) 6：GH HG 7：G(HS) (GH)S (结合律) 8: G(HS) (GH)S 9：G(GH) G (吸收律) 10：G(GH
6、) G 11：G(HS) (GH)(GS) (分配律) 12：G(HS) (GH)(GS) 13：GF G (同一律) 14：GT G,2019/11/10,计算机学院,8/24,15：GT T (零律) 16：GF F 17：GG T (矛盾律) 18：GG F 19： (G) G (双重否定律) 20：（GH)S G（HS） （输出律） 21：（GH）(GH)(GH) (排中律) 22：PQ QP （逆反律） 23： (GH) GH (De Morgan定律) 24： (GH) GH。 范式全名叫规范型式normal form,又叫标准型式,正规型式。把公式进行标准化，正规化，就叫对公式求
7、范式。 命题变元或命题变元的否定称为句节。 有限个句节的析取式称为子句； 有限个句节的合取式称为短语。 有限个短语的析取式称为析取范式； 有限个子句的合取式称为合取范式。,2019/11/10,计算机学院,9/24,极小项-在n个变元的基本积（短语）中，若每一个变元与其否定并不同时存在，且二者之一必出现且仅出现一次，则称这种基本积为极小项。 主析取范式-由有限个极小项组成的析取式。 极大项-在n个变元的基本和（子句）中，若每一个变元与其否定并不同时存在，且二者之一必出现且仅出现一次，则这种基本和称为极大项。 主合取范式-由有限个极大项组成的合取式。 命题公式的蕴涵-设A和B是两个合适公式，如果
8、在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记A B。,2019/11/10,计算机学院,10/24,基本蕴含（关系）式 I1：PPQ ， QPQ PPQ ， QPQ 扩充法则(析取引入律) I2：PQ P ， PQQ （PQ）P ，（PQ）Q 化简法则(合取消去律) I3：P（PQ） Q 假言推论（分离规则） I4：Q（PQ） P 否定式假言推论（拒取式） I5：P（PQ） Q 析取三段论（选言三段论） I6：（PQ）（QR） PR 假言（前提条件）三段论 I7：（PQ）（PR）（QR） R 二难推论 I8：（PQ）（RS）（PR）（QS） I9：（PQ）（QR） PR I1
9、0：（PQ）（PR） QR 归结原理,2019/11/10,计算机学院,11/24,命题逻辑的推理方法- 设G是由一组命题公式组成的集合，如果存在命题公式的有限序列： H1，H2，Hn（=H） 其中，Hi或者是G中的某个公式，或者是前面的某些Hj（ji）的有效结论，并且Hn就是H，则称公式H是G的逻辑结果（有效结论），或者称由G演绎出结论H来。 推理规则- P规则（称为前提引用规则）：在推导的过程中，可随时引入前提集合中的任意一个前提； 规则（逻辑结果引用规则）：在推导的过程中，利用基本等价式和蕴涵式，由证明过程中某些中间公式变换出新的公式，若依据的是等价式，规则标明为TE，若依据的是蕴涵式，
10、规则标明为TI 。 规则（附加前提规则）：如果能从给定的前提集合G与公式P推导出S，则能从此前提集合G推导出PS。 即G1,G2,Gn PS 当且仅当 G1,G2,Gn，P S,2019/11/10,计算机学院,12/24,二、基本方法 1、应用基本等价式及置换规则进行等价演算 2、求主析取（主合取）范式的方法 公式转换法 （1）利用等价公式中的等价式和蕴涵式将公式中的、用联结词、来取代； （2）利用德摩根定律将否定号移到各个命题变元的前端； （3）利用结合律、分配律、吸收律、幂等律、交换律等将公式化成其等价的析取范式和合取范式。 （4）在析取范式的短语和合取范式的子句中，如同一命题变元出现多
11、次，则将其化成只出现一次。 （5）去掉析取范式中所有永假式的短语和合取范式中所有永真式的子句，即去掉短语中含有形如PP的子公式和子句中含有形如PP的子公式。,2019/11/10,计算机学院,13/24,（6）若析取范式的某一个短语中缺少该命题公式中所规定的命题变元，则可用公式： （）Q=Q 将命题变元P补进去，并利用分配律展开，然后合并相同的短语，此时得到的短语将是标准的极小项； （7）若合取范式的某一个子句中缺少该命题公式中所规定的命题变元，则可用公式： （）Q=Q 将命题变元P补进去，并利用分配律展开，然后合并相同的子句，此时得到的子句将是标准的极大项。 （8）利用幂等律将相同的极小项和
12、极大项合并，同时利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。 真值表技术法 主合取范式-在命题公式的真值表中，使公式取值0时的解释所对应的全部极大项的合取式。 主析取范式-在命题公式的真值表中，使公式取值1时的解释所对应的全部极小项的析取式。,2019/11/10,计算机学院,14/24,（1）求出公式的真值表 （2）求出使公式取值0时的解释所对应的全部极大项 极大项取值0“当且仅当”：如果极大项中出现的是原子本身，则原子赋值为0；如果出现的是原子的否定，则原子赋值为1。 （3）求出使公式取值1时的解释所对应的全部极小项 极小项取值1 “当且仅当”：如果极小项中出现的是原
13、子本身，则原子赋值为1；如果出现的是原子的否定，则原子赋值为0。 3、推理的各种方法 （1）直接法 （2）利用CP规则 （3）反证法,2019/11/10,计算机学院,15/24,三、典型例题 1、证明 (PQ) (PQ) (PQ) (PQ)(PQ) (PQ)(PQ) (PQ)P) (PQ)Q) (PP)(QP)(PQ)(QQ) (QP)(PQ) (QP)(PQ) (QP)(PQ) (QP)(PQ) (PQ),2019/11/10,计算机学院,16/24,2、 G=()，求主析取和主合取范式。 解：首先列出其真值表如下：,极大项,极小项,PQR,PQR,PQR,PQR,PQR,PQR,PQR,
14、PQR,主析取范式=（PQR）（PQR） （PQR）（PQR）（PQR） 主合取范式=（ PQR ）（ PQR ）（PQR）,2019/11/10,计算机学院,17/24,3、用公式转换法求上题中的主析取和主合取范式 ()（PQ）R （PQ）R （PR）（QR） （PR（QQ）（QR（PP） （PRQ）（PRQ）（QRP）（QRP） （PRQ）（PRQ）（QRP） （主合取范式） ()（PQ）R （PQ）R （PQ（RR）（R（PP）（QQ） （PQR）（PQR）（RP）（RP） （PQR）（PQR）（RP（QQ） （RP（QQ） （PQR）（PQR）（RPQ） （RPQ）（RPQ）（RPQ）,（主析取范式）,2019/11/10,计算机学院,18/24,4、
