离散数学题型6.doc

《离散数学题型6.doc》由会员分享，可在线阅读，更多相关《离散数学题型6.doc（58页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date离散数学题型6离散数学集合论部分常考题离散数学常考题型梳理第6章 命题逻辑一、题型分析本章主要介绍命题、联结词的概念，命题公式与翻译，真值表与等价公式，重言式与蕴含式，范式和命题逻辑的推理理论等内容。经常涉及到的题型有：6-1 将陈述句翻译成命题公式6-2 求命题公式的真值6-3 命题公式类型的判断6-4 等价公式的证明6-5 求范式和主范式6-6判断有效结论的直接证

2、法和间接证法因此，在本章学习过程中希望大家要清楚地知道：1将陈述句翻译成命题公式命题表述为具有确定真假意义的陈述句。命题必须具备二个条件：语句是陈述句；语句有唯一确定的真假意义。因此判断一个句子是否为命题，应首先判断它是否为陈述句，再判断它是否有唯一的真值。例如，“北京是中国的首都”是陈述句，有确定的真假意义，是命题，为真命题。将陈述句翻译成命题公式关键在于陈述句的逻辑含义要与命题公式的逻辑含义保持一致。因此首先要注意陈述句中表示特殊逻辑关系的词语的含义，其次要掌握五个联结词“， ， ，”所表示的命题间的逻辑关系：“” 是唯一一元联结词，表示否定；合取联结词“”在语句中相当于“不但而且”，“既

3、又”；析取联结词“”在语句中表示“或”的含义；条件联结词“”在语句中表示“如果P则Q”或“只有Q，才P”；双条件联结词“”在语句中相当于“当且仅当”。例如，“我们不能划船，又跑步”。设P：我们划船，G：我们跑步，那么该命题符号化为：或。2求命题公式的真值一般将命题的合式公式简称为命题公式。要理解合式公式的递归定义： （1）单个命题变元本身是一个合式公式 （2）若A是合式公式，则A是合式公式 （3）若A与B是合式公式，则（AB），（AB），（AB）与（AB）是合式公式（4）当且仅当能够有限次应用（1）、（2）、（3）所得到的包含命题变元，联结词和括号的符号串是合式公式显然，如果对一个命题公式中的

4、命题变元不给以真值指派，则命题公式无真值可言。如果对命题公式中的每个命题变元都赋以真值（1或0），则命题公式就变成了一个有真值的命题，并可求出其真值。对于特殊的命题公式（永真式和永假式），对命题公式中的命题变元不给以真值指派，利用常用的等价公式也可以求出其真值（永真式为1，永假式为0）。对命题公式中的所有命题变元指派各种可能的真值组合，就可确定这个命题公式对应的取值，将命题变元的所有真值组合及命题公式对应的取值汇列成表，就得到命题公式的真值表如果一个命题公式有n个命题变元，那么命题变元的真值指派就可能出现种不同的组合。在真值表中是包含了命题变元的所有真值指派。例如，如果一个命题公式有3个命题变

5、元，那么命题变元的真值指派就有8种不同的组合，作其真值表就是将这8种真值组合及命题公式对应的真值汇列成表。要非常熟练地掌握命题公式的真值表作法，因为利用真值表可以判定命题公式类型，验证等价公式和蕴含式，求命题公式的主析取(合取)范式，在推理理论中判别有效结论。3. 命题公式类型的判断在各种真值指派下均为真的命题公式，称为重言式或永真式；在各种真值指派下均为假的命题公式，称为矛盾式或永假式；不是矛盾式的命题公式，称为可满足式。 判定命题公式类型的方法：(1) 真值表法：任给命题公式，列出其真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最

6、后一列既非全1，又非全0，则该公式是可满足式。(2) 等值演算法：利用常用的等价公式，对给定公式进行等值推导，若该公式的真值为1，则该公式为永真式；若该公式的真值为0，则该公式为永假式。既非永真，也非永假，则为非永真的可满足式。4. 等价公式的证明等价公式：给定两个命题公式A与B，设P1，P2，Pn为所有出现于A与B中的原子变元，若给P1，P2，Pn任一组真值指派，A与B的真值均相同，则称公式A与B是等价的或逻辑相等，记作AB，此公式可称为等价公式。真值表法（验证公式等价）：将两个命题公式的真值表列出，在所有的真值指派下，两个公式的真值都对应相同，则说明两个公式等价，否则，就不等价。等值演算法

7、（证明公式等价）：利用教材182页的14个基本等价式对给定公式进行等值演算，可以证明命题公式等价。5求范式和主范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：其一是准确掌握范式定义；其二是巧妙使用基本等价式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律。范式的相关定义有：合取范式：一个命题公式称为合取范式，当且仅当它具有形式： A1A2An ， （n1）其中A1，A2，An均是由命题变元或其否定所组成的析取式 析取范式：一个命题公式称为析取范式，当且仅当它具有形式：A1A2An ， （n1）其中A1，A2，An均是有命题变元或其否定所组成的合取式 布尔合取、小

8、项：n个命题变元的合取式，称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次一般n个命题变元共有个小项。布尔析取、大项：n个命题变元的析取式，称为布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次一般n个命题变元共有个大项。主析取范式：对于给定的命题公式，若有一个等价公式，它仅仅由小项的析取组成，则该等价式称为原式的主析取范式 主合取范式：对于给定的命题变元，如果有一个等价公式，它仅仅由大项的合取组成，则该等价式称为原式的主合取范式 求析取(合取)范式的步骤： 将公式中的联结词都化成，(即消去联结词，)； 将否定联结词消去或移到各命题

9、变元之前； 利用分配律、结合律等，将公式化为析取(合取)范式。求主析取范式(主合取范式)的方法：真值表法：在命题公式的真值表中，真值为1的指派所对应的小项的析取，为此命题公式的主析取范式；在命题公式的真值表中，真值为0的指派所对应的大项的合取，为此命题公式的主合取范式。等值演算法：利用等价公式，求命题公式A的主析取(合取)范式的步骤： 将公式A化为析取(合取)范式； 除去析取(合取)范式中永假(永真)的析取 (合取) 项，并将析取(合取)式中重复出现的合取项(析取项)和相同变元合并。 对于不是小项（大项）的合取（析取）式，补入没有出现的命题变元，即通过合取（析取）添加PP(PP) 式，然后利用

10、分配律展开公式。一般地，若命题公式A的主析取范式为则A的主合取范式为 由此可见，命题公式A的主析取范式的小项个数与主合取范式的大项个数之和等于。6判断有效结论的直接证法和间接证法判断有效结论的过程就是论证过程，基本方法有真值表法、直接证法和间接证法。要重点掌握后两种方法。直接证法：就是由一组给定的前提，利用一些公认的推理规则，并根据已知的等价公式和蕴含公式，推演得到有效结论的方法在证明过程中一般要用到的两个公认的推理规则，即P规则与T规则P规则：前提在推导过程中的任何时候都可以引入使用T规则：在推导中，如果有一个或多个公式重言蕴含着公式C，则公式C可以作为前提在推导引用因此要掌握直接证法，就必

11、须理解并掌握好教材第182页的14个等价公式和14个蕴含公式，并会使用P规则和T规则。将证明的过程用三列的形式表示，第一列为序号，第二列为当前得到的结论，第三列为得到当前结论的理由或根据E与I分别表示已经证明成立的等价式与蕴含式间接证法：有两种，一种为反证法，是由不相容的概念引出的一种间接证法。相容、不相容：假设公式H1，H2，Hm中的命题变元为P1，P2，Pn，对于P1，P2，Pn的一些真值指派，如果能使H1H2Hm的真值为T，则称公式H1，H2，Hm是相容的如果对于P1，P2，Pn的每一组真值指派，使得H1H2Hm的真值为F，则称公式H1，H2，Hm是不相容的其证明思路就是，如要证明，只要

12、把作为前提使用，推出矛盾的结论即可。另一种间接证法就是附加前提证明法：该方法使用的前提是有效结论以蕴含的形式出现，即具有这样的形式。则把B作为附加前提使用，只要推出结论C即可。即证明。通常将此方法称为CP规则。二、常考知识点分析常考知识点1：将陈述句翻译成命题公式（历年考核次数：6次，本课程共考过6次；重要程度：）1.（2009年10月试卷第11题）将语句“他是学生”翻译成命题公式解题过程 依据命题必须具备的二个条件，可设P：他是学生， 则该语句翻译成命题公式为： P 2.（2008年7月试卷第12题）将语句“今天没有人来”翻译成命题公式解题过程 依据命题必须具备的二个条件以及否定联结词“”的

13、定义，可设 P：今天有人来， 则语句“今天没有人来” 翻译成命题公式为 P。3.（2008年7月试卷第11题）将语句“如果所有人今天都去参加活动，则明天的会议取消”翻译成命题公式解题过程 在该语句中出现表示逻辑关系的连词“如果，则”，这样我们就很容易联想到条件联结词“”在语句中表示“如果，则”，但要注意的是，似乎PQ是“因果关系”，但是不一定总有因果关系，只要P，Q是命题，那么PQ就是命题(即有真值)，不管P，Q是否有无因果关系。因此，设P：所有人今天都去参加活动，Q：明天的会议取消，于是该语句可翻译成命题公式为： P Q 4.（2009年1月试卷第12题）（2010年1月试卷第12题）将语句

14、“我去旅游，仅当我有时间”翻译成命题公式解题过程 PQ表示的基本逻辑关系是，Q是P的必要条件，P是Q的充分条件，因此复合命题“只要P，就Q”，“P仅当Q”，“只有Q才P”等都可以符号化为PQ的形式。因此可设P：我去旅游，Q：我有时间，则语句“我去旅游，仅当我有时间”翻译成命题公式为：PQ 5.（2008年9月试卷第12题）将语句“小王去旅游，小李也去旅游”翻译成命题公式解题过程 合取联结词“”在语句中相当于“并且”，“不但而且”，“既又”。但要注意“”与 “并且”等是有区别的，“并且”等要考虑语义，而“合取”只考虑命题之间的关系以及复合命题的取值情况，不考虑语义。因此，可设P：小王去旅游，Q：

15、小李去旅游，则语句“小王去旅游，小李也去旅游”翻译成命题公式为：PQ常考知识点2：求命题公式的真值（历年考核次数：1次，本课程共考过6次；重要程度：）1.（2009年 1月试卷第6题）命题公式的真值是 解题过程 依次利用蕴含等价式、结合律和零律，可将该命题公式化为：，因此该公式的真值是1。常考知识点3：命题公式类型的判断（历年考核次数：2次，本课程共考过6次；重要程度：）1.（2008年 7月试卷第14题）判断说明题（判断下列各题正误，并说明理由）为永真式 解题过程 正确因为联结词运算的优先次序为：，再利用等价公式中的蕴含等价式，吸收律和否定律，对给定公式进行等值推导如下：因此该公式是永真式。

16、以上是利用等值演算法判断公式的类型，也可利用如下真值表法。PQPQPQP (PQ)P (PQ) P 1100001 1001101 01101110011111由真值表可见该公式在任意真值指派下的真值都是1，因此该公式是永真式。2.（2009年1月试卷第5题）下列公式 ( )为重言式APQPQ B(Q(PQ) (Q(PQ) C(P(QP)(P(PQ) D(P(PQ) Q解题过程 C选A错误.因为利用蕴含等价式，可将PQ化为(PQ)，即PQ (PQ)，依据等价联结词的定义可知(PQ)PQ为矛盾式。选B错误.因为利用蕴含等价式、分配律和结合律，可将(Q(PQ)化为(Q(PQ) (Q(PQ) (QQ

17、)P) (1 P) 1 而用分配律和否定律得(Q(PQ) (QP)(QQ) (QP)0) (QP)依据等价联结词的定义可知1(QP)为可满足式。选C正确.因为利用蕴含等价式可将(P(QP)(P(PQ)化为(P(QP)(P (PQ)，再利用结合律得(P (QP)( P (Q P)。再依据等价联结词的定义可知该式为重言式。选D错误.因为利用分配律可将(P(PQ)化为(P(PQ) (PP)(PQ) (1 (PQ) (PQ)依据等价联结词的定义可知(PQ)Q为可满足式。常考知识点4：等价公式的证明（历年考核次数：2次，本课程共考过6次；重要程度：）1.（2008年 9月试卷第5题）下列等价公式成立的为

18、( )APQPQ BP(QP) P(PQ) CQ(PQ) Q(PQ) DP(PQ) Q解题过程 B选A错误.因为依据德摩根律，PQ(PQ)，所以PQ与PQ不等价。选B正确.因为依次利用蕴含等价式、分配律和蕴含等价式可得，P(QP) P(QP) P (Q P) P ( P Q) P (PQ) P (PQ)。选C错误.因为依次利用蕴含等价式、结合律、否定律和零律可得，Q(PQ) Q (PQ) 1，而 Q(PQ) (QP) (Q Q) (QP) 0(QP) ，其真值不等于1。选D错误.因为依次利用分配律、否定律和同一律可得，P(PQ) (PP)(PQ) 1(PQ) (PQ)，显然与Q不等价。2.（2

19、010年 1月试卷第5题）下列公式成立的为( )APQ PQ BPQ PQ CQP P DP(PQ)Q解题过程 D选A错误.因为依据德摩根律，PQ (PQ)，显然与PQ不等价。选B错误.因为利用蕴含等价式可得，PQ PQ，同理，PQ PQ，显然PQ与PQ不等价。选C错误.因为QP P是一个蕴含式，依据蕴含的定义，该蕴含式成立只需证明(QP) P为重言式即可。依次利用蕴含等价式、分配律、否定律和同一律，(QP) P (QP) P (QP) P (QP) P (QP) ( P P) (QP) 1 (QP)，显然结果不是重言式，因此QP P不成立。选D正确.也可以利用直接证法来证明该蕴含式，思路是：

20、证明P(PQ)为真时，Q一定为真。假定P(PQ)为T，则P为T，且PQ为T，由P为F，PQ为T，知Q为T。则P(PQ)Q成立。常考知识点5：求范式和主范式（历年考核次数：6次，本课程共考过6次；重要程度：）1.（2008年7月试卷第17题）求PQR的析取范式、合取范式、主析取范式、主合取范式 解题过程 依据求析取(合取)范式的步骤可得，P（RQ）P(RQ) PQR （析取范式、合取范式、主合取范式）因此该公式的主析取范式对应的小项为：，故该公式的主析取范式为： (PQR)(PQR) (PQR) (PQR) (PQR) (PQR) (PQR) 。此外，我们也可利用真值表法求该命题公式的主析取范式

21、和主合取范式 PQRPQR小项大项0001PQR0011PQR0101PQR0111PQR1000PQR1011PQR110 1 PQR1111PQR表中所有小项的析取就是公式的主析取范式，所有大项的合取就是公式的主合取范式，从真值表中可以看出所得结果与用上述等值演算法所得结果相同。2.（2008年9月试卷第3题）命题公式（PQ）R的析取范式是 ( ) A（PQ）R B（PQ）R C（PQ）R D（PQ）R解题过程 D 依据求析取范式的步骤可得，（PQ）R(PQ）R (PQ)R，这就是命题公式（PQ）R的析取范式，虽然命题公式的析取范式不唯一，但这个结论与选项D相同，故选择D。3.（2009年

22、1月试卷第16题）试求出（PQ）R的析取范式，合取范式，主合取范式解题过程 （PQ）R(PQ)R (PQ)R（析取范式） (PR) (QR)（合取范式） (PR)(QQ) (QR)(PP) (PRQ)(PRQ) (QRP)(QRP) (PQR)(PQR) (PQR) （主合取范式） 常考知识点6：判断有效结论的直接证法和间接证法（历年考核次数：0次，本课程共考过6次）1. 试证明（）， 。判断有效结论的直接证法和间接证法，它的理论根据是14个等价公式（P167），14个蕴含式(P170-171)，三个规则(P规则、T规则和CP规则)。在这些公式中，我们并不需要全部记住，记住最基本的即可，在这些

23、公式中，下列这些式子是最基本的和最常用，其它公式有的可以根据它推导出来。14个蕴含式中最常用和最基本的式子有(1)，(2)，(3)，(8)，(10)，(11)。14个等价式中（12）,（14）式用得较少。利用直接证明法和间接证明法来证明，一个关键问题就是在多个前提条件下，不知道按什么顺序来引入前提？一般的来说是根据析取三段论（或假言推理）（即教材P170第（9）、（10）式），即一个前提中含有A，再引入一个含有A的前提，就可以去掉A了。这样我们可以先从远离结论的前提入手，逐步推导出结论。分析：结论是，先从远离结论的前提（或者）出发引入第一个前提，然后根据析取三段论再引入一个含有的前提（或者），

24、这样就可以去掉了，只剩下了，再引入一个含有的前提（），就又可以去掉了，只剩下含有、了，这正是结论所需要的。证明：(直接证法) P P T I () P () TI () TI TE 三、模拟练习练习1。（2009年1月试卷第11题）将语句“他不去学校”翻译成命题公式解析：依据命题和否定联结词的定义，可设P：他去学校， 则语句“他不去学校”翻译成命题公式为 P 练习2。（2009年7月试卷第12题）将语句“今天没有下雨”翻译成命题公式解析：依据命题和否定连接词的定义，可设P：今天下雨， 则语句“今天没有下雨”翻译成命题公式为 P练习3。（2008年9月试卷第11题）将语句“如果你去了，那么他就不

25、去”翻译成命题公式解析：条件联结词“”在语句中表示“如果，则”，与本语句中的“如果，那么”，语意相同，再依据否定联结词的定义，则可设P：你去，Q：他去，于是语句“如果你去了，那么他就不去”翻译成命题公式为PQ练习4。（2009年10月试卷第12题）将语句“如果明天不下雨，我们就去郊游”翻译成命题公式解析：依据条件联结词“”在语句中表示“如果，则”，以及否定联结词的定义，可设P：明天下雨，Q：我们就去郊游，则该语句可翻译成命题公式为 P Q 练习5。（2009年7月试卷第11题）将语句“尽管他接受了这个任务，但他没有完成好”翻译成命题公式解析：依据合取联结词“”在语句中相当于“并且”，“不但而且

26、”，“既又”，以及否定联结词的定义，可设P：他接受了这个任务，Q：他完成好了这个任务。则该语句可翻译成命题公式为 P Q练习6。（2010年1月试卷第11题）将语句“今天考试，明天放假”翻译成命题公式解析：合取联结词“”只考虑命题之间的关系以及复合命题的取值情况等。因此，可设P：今天考试，Q：明天放假则该语句可翻译成命题公式为 PQ练习7。将语句“如果天不下雪，我有时间，那么我就去市里”翻译成命题公式解析：依据合取联结词“”，在语句中相当于“并且”，“不但而且”，条件联结词“” 在语句中表示“如果，则”。因此，可设P：天下雪，Q：我去市里，R：我有时间，则该语句可翻译成命题公式为：PRQ练习8

27、。命题公式的真值是 解析：该命题公式的真值为1。依据蕴含等价式、结合律和零律，可将该命题公式化为：练习9。命题公式（PQ）Q为（ ）A. 矛盾式 B可满足式C重言式 D合取范式解析：B因为利用蕴含等价式可将（PQ）Q化为（PQ）Q，利用德摩根律得（PQ）Q，利用分配律得（PQ ）(QQ)，利用否定律得（PQ）1，再利用同一律得PQ，因此该命题公式为可满足式。练习10。判断命题公式(QP)P的类型（重言式、矛盾式或可满足式），说明理由。解析：(QP)P(QP)P (QP)PQPPQ(PP)Q00所以(QP)P是矛盾式。练习11。证明命题公式是永真式证明：1练习12。下列命题公式等值的是为（ ）。

28、A. B. C. D. 解析：C因为利用蕴含等价式可得，练习13。化简命题公式解析：因为 练习14。证明命题公式(P(QR)PQ与（PQ）等值 证明 (P(QR)PQ(P(QR)PQ (PPQ)(QPQ)(RPQ) (PQ)(PQ)(PQR) PQ (PQ) 练习15。（2009年7月试卷第15题）求（PQ）（RQ）的合取范式解析：（PQ）（RQ） （PQ）（RQ） (PQ)（RQ） (PRQ)(QRQ)(PRQ) R 合取范式 练习16。（2009年10月试卷第15题）求（PQ）R的析取范式与合取范式解析：（PQ）R （PQ）R (PQ)R （析取范式） (PR)(QR) （合取范式）练习1

29、7。（2010年1月试卷第2题）命题公式（PQ）的合取范式是 ( ) A（PQ） B（PQ）（PQ） C（PQ） D（PQ）解析：C因为，选项A，B与命题公式（PQ）不等价，选项D中的“”没有移到各命题变元之前，选项C是命题公式（PQ）只由一个析取项组成的合取范式。故选项C正确。练习18。试证明： 解析： (附加前提证明法)(1) S CP规则(2) SP P(3) P T(1)(2)I(4) P(QR) P(5)QR T(3)(4)I(6)Q P(7)R T(5)(6)I练习19。构造下面推理的证明前提 R Q，RS，S Q，P Q 结论P解析：(用反证法)（1） P CP (结论之否定作为附加前提)（2） P Q P （3） Q T （1）（2）I （4） S Q P （5） S T （3）（4）I（6） R Q P （7） R T （3）（6）I （8） RS T（5）（7）I （9） （RS） T （8）E （10） RS P （11） （RS）（RS） T （9）（10）I （12） P -