离散数学王元元习题解答

1命题演算及其形式系统1.1命题与联结词 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 提要1.1.1命题我们把对确定的对象作出判断的陈述句称作命题（propositions），当判断正确或符合客观实际时，称该命题真（true），否则称该命题假（false）。“真、假”常被称为命题的真值。自然语言中“并非、或者、并且、如果…，那么…、当且仅当”这样的联结词称为逻辑联结词（logicalconnectives）。通常把不含有逻辑联结词的命题称为原子命题或原子（atoms），而把由原子命题和逻辑联结词共同组成的命题称为复合命题（compositivepropositions）。1.1.2联结词否定词(negation)“并非”（not），用符号┐ 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示。设p表示一命题，那么┐p表示命题p的否定。p真时┐p假，而p假时┐p真。┐p读作“并非p”或“非p”。合取词(conjunction)“并且”（and），用符号∧表示。设p，q表示两命题，那么p∧q表示合取p和q所得的命题，即p和q同时为真时p∧q真，否则p∧q为假。p∧q读作“p并且q”或“p且q”。析取词(disjunction)“或”（or）用符号∨表示。设p，q表示两命题，那么p∨q表示p和q的析取，即当p和q有一为真时，p∨q为真，只有当p和q均假时p∨q为假。p∨q读作“p或者q”、“p或q”。蕴涵词(implication)“如果……，那么……”（if…then…），用符号→表示。设p，q表示两命题，那么p→q表示命题“如果p，那么q”。当p真而q假时，命题p→q为假，否则均认为p→q为真。p→q中的p称为蕴涵前件，q称为蕴涵后件。p→q的读法较多，可读作“如果p则q”，“p蕴涵q”，“p是q的充分条件”，“q是p的必要条件”，“q当p”，“p仅当q”等等。 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 中还常把q→p，┐p→┐q，┐q→┐p分别叫做p→q的逆命题，否命题，逆否命题。双向蕴涵词(two-wayimplication)“当且仅当”（ifandonlyif），用符号表示之。设p，q为两命题，那么pq表示命题“p当且仅当q”，“p与q等价”，即当p与q同真值时pq为真，否则为假。pq读作“p双向蕴涵q”，“p当且仅当q”，“p等价于q”。由于“当且仅当”“等价”常在其它地方使用，因而用第一种读法更好些。1.1.3命题公式及其真值表我们把表示具体命题及表示常命题的p，q，r，s与f，t统称为命题常元（propositionconstant）。深入的讨论还需要引入命题变元（propositionvariable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。定义1.1以下三条款规定了命题公式（propositionformula）的意义：（1）命题常元和命题变元是命题公式，也称为原子公式或原子。（2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（AB）也是命题公式。（3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。如果公式A含有命题变元p1，p2，…，pn，记为A(p1,…,pn)，并把联结词看作真值运算符，那么公式A可以看作是p1,…,pn的真值函数。对任意给定的p1,…,pn的一种取值状况，称为指派（assignments），用希腊字母，等表示，A均有一个确定的真值。当A对取值状况为真时，称指派弄真A，或是A的成真赋值，记为(A)=1；反之称指派弄假A，或是A的成假赋值，记为(A)=0。对一切可能的指派,公式A的取值可能可用一张表来描述,这个表称为真值表（truthtable）。当A(p1,…,pn)中有k个联结词时，公式A的真值表应为2n行、k+n列（不计表头）。1.1.4语句的形式化用我们已有的符号语言，可以将许多自然语言语句形式化。语句形式化要注意以下几个方面。要善于确定原子命题，不要把一个概念硬拆成几个概念，例如“弟兄”是一个概念，不要拆成“弟”和“兄”、“我和他是弟兄”是一个原子命题。要善于识别自然语言中的联结词（有时它们被省略）。例如“风雨无阻，我去上学”一句，可理解为“不管是否刮风、是否下雨我都去上学”。否定词的位置要放准确。需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。另外要注意的是,语句的形式化未必是唯一的。习题解答练习1.11、判断下列语句是否是命题，若是命题则请将其形式化：（1）a+b（2）x>0（3）“请进！”（4）所有的人都是要死的，但有人不怕死。（5）我明天或后天去苏州。（6）我明天或后天去苏州的说法是谣传。（7）我明天或后天去北京或天津。（8）如果买不到飞机票，我哪儿也不去。（9）只要他出门，他必买书，不管他余款多不多。（10）除非你陪伴我或代我雇辆车子，否则我不去。（11）只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切论证，才能得到可靠见解。（12）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。（13）不管你和他去不去，我去。（14）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》）（15）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。（荀况：《荀子劝学》）解（1）a+b不是命题（2）x>0不是命题（x是变元）（3）“请进！”不是命题（4）所有的人都是要死的，但有人不怕死。是命题可表示为p∧┐q，其中p：所有的人都是要死的，q：所有的人都怕死（5）我明天或后天去苏州。是命题可表示为p∨q，其中p：我明天去苏州；q：我后天去苏州（6）我明天或后天去苏州的说法是谣传。是命题可表示为┐(p∨q)，其中p、q同（5）（7）我明天或后天去北京或天津。是命题可表示为p∨q∨r∨s，其中p：我明天去北京，q：我明天去天津，r：我后天去北京，s：我后天去天津（8）如果买不到飞机票，我哪儿也不去。是命题可表示为┐p→┐q，其中，p：我买到飞机票，q：我出去（9）只要他出门，他必买书，不管他余款多不多。是命题可表示为(p∧q→r)∧(┐p∧q→r)或q→r，其中p：他余款多，q：他出门，r：他买书（10）除非你陪伴我或代我雇辆车子，否则我不去。是命题可表示为(p∨q)r，其中p：你陪伴我，q：你代我雇车，r：我去（11）只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切论证，才能得到可靠见解。是命题可表示为(p→q)∧(q→p)或pq，其中p：你充分考虑了一切论证，q：你得到了可靠见解（12）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。是命题可表示为(q→p)→┐q，其中p：我懂得希腊文，q：我了解柏拉图（13）不管你和他去不去，我去。是命题可表示为(p→r)∧(q→r)∧(┐p→r)∧(┐q→r)或r，其中p：你去，q：他去，r：我去（14）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》）是命题可表示为((p∧q)→r)∧((┐p∧┐q)→┐r)，其中p：你奢侈，q：你懒惰，r：你贫困（15）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。（荀况：《荀子劝学》）是命题可表示为(p→┐q)∧(s→r)∧(m∧n→┐o)∧(m∧┐n→v)，其中p：骐骥一跃，q：骐骥一跃十步，r：驽马行千里，s：驽马不断奔跑，m：你雕刻，n：你放弃，o：将朽木折断，v：金石可雕刻2、判定下列符号串是否为公式，若是，请给出它的真值表，并请注意这些真值表的特点（公式中省略了可以省略的括号）：（1）┐(p)（p为原子命题）（2）(p∨qr)→s（3）(p∨q)→p（4）p→(p∨q)（5）┐(p∨┐p)（6）p∧(p→q)→q（7）p∧(p→q)∧(p→┐q)（8）(p→q)(┐q→┐p)（9）┐(p∨q)┐q∧┐p（10）┐p∨q(p→q)（11）(p→q)∧(q→r)→(p→r)（12）(p∨q→r)(p→r)∧(q→r)解（1）┐(p)不是公式（2）(p∨qr)→s不是公式（3）(p∨q)→p是公式 p q p∨q (p∨q)→p 0 0 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1（4）p→(p∨q)是公式（真值表见上表，恒真）（5）┐(p∨┐p)是公式（恒假） p ┐p p∨┐p ┐(p∨┐p) 0 1 1 0 1 0 1 0（6）p∧(p→q)→q是公式（恒真） p q p→q p∧(p→q) p∧(p→q)→q 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1（7）p∧(p→q)∧(p→┐q)是公式（恒假） p q ┐q p→q p∧(p→q) p→┐q p∧(p→q)∧(p→┐q) 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0（8）(p→q)(┐q→┐p)是公式（恒真） p q ┐p ┐q p→q ┐q→┐p (p→q)(┐q→┐p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 1（9）┐(p∨q)┐q∧┐p是公式（恒真） p q ┐p ┐q p∨q ┐(p∨q) ┐q∧┐p ┐(p∨q)┐q∧┐p 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1（10）┐p∨q(p→q)是公式（恒真） p q ┐p ┐p∨q p→q ┐p∨q(p→q) 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1（11）(p→q)∧(q→r)→(p→r)是公式（恒真） p q r p→q q→r p→r (p→q)∧(q→r) (p→q)∧(q→r)→(p→r) 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1（12）(p∨q→r)(p→r)∧(q→r)是公式（恒真） p q r p∨q p∨q→r p→r q→r (p→r)∧(q→r) (p∨q→r)(p→r)∧(q→r) 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1*3、A国的人只有两种，一种永远说真话，一种永远说假话。你来到A国，并在一个二叉路口不知如何走才能到达首都。守卫路口的士兵只准你问一个问题，而且他只答“是”或“不是”。你应该如何发问，才能从士兵处获知去首都的道路。解设p：你是说真话的；q：我应当向右走去首都你应当问：pq?当回答“是(真)”，你选择向右走；当回答“不（假）”时，你选择向左走。因为pq真，当且仅当p真且q真（士兵说真话且应当向右走）或p假且q假（士兵说假话且应当向左走）pq假，当且仅当p真且q假（士兵说真话且应当向左走）或p假且q假（士兵说假话且应当向右走）1.2重言式内容提要1.2.1重言式概念定义1.2命题公式A称为重言式（tautology），如果对A中命题变元的一切指派均弄真A，因而重言式又称永真式；A称为可满足式（satisfactableformula），如果至少有一个指派弄真A，否则称A为不可满足式或永假式、矛盾式。1.2.2逻辑等价式和逻辑蕴涵式定义1.3当命题公式AB为永真式时，称A逻辑等价于B，记为A┝┥B，它又称为逻辑等价式(logicallyequivalent)。以下是一些重要的逻辑等价式，其中A，B，C表示任意命题公式：E1┐┐A┝┥A双重否定律E2A∨A┝┥A幂等律E3A∧A┝┥A幂等律E4A∨B┝┥B∨A交换律E5A∧B┝┥B∧A交换律E6(A∨B)∨C┝┥A∨(B∨C)结合律E7(A∧B)∧C┝┥A∧(B∧C)结合律E8A∧(B∨C)┝┥(A∧B)∨(A∧C)分配律E9A∨(B∧C)┝┥(A∨B)∧(A∨C)分配律E10┐(A∨B)┝┥┐A∧┐B德摩根律E11┐(A∧B)┝┥┐A∨┐B德摩根律E12A∨(A∧B)┝┥A吸收律E13A∧(A∨B)┝┥A吸收律E14A→B┝┥┐A∨BE15AB┝┥(A→B)∧(B→A)E16A∨t┝┥tE17A∧t┝┥AE18A∨f┝┥AE19A∧f┝┥fE20A∨┐A┝┥tE21A∧┐A┝┥fE22┐t┝┥f,┐f┝┥tE23A∧B→C┝┥A→(B→C)E24A→B┝┥┐B→┐AE25(A→B)∧(A→┐B)┝┥┐A定义1.4当命题公式A→B为永真式时，称A逻辑蕴涵B，记为A┝B，它又称为逻辑蕴涵式(logicallyimplication)。我们也列出一些十分重要的逻辑蕴涵式：I1A┝A∨B，B┝A∨BI2A∧B┝A，A∧B┝BI3A∧(A→B)┝BI4(A→B)∧┐B┝┐AI5┐A∧(A∨B)┝B，┐B∧(A∨B)┝AI6(A→B)∧(B→C)┝A→CI7(A→B)∧(C→D)┝(A∧C)→(B∧D)I8(AB)∧(BC)┝AC逻辑等价式与逻辑蕴涵式有如下明显性质。定理1.1对任意命题公式A，B，C，A'，B'，（1）A┝┥B当且仅当┝AB（2）A┝B当且仅当┝A→B（3）若A┝┥B，则B┝┥A（4）若A┝┥B，B┝┥C，则A┝┥C（5）若A┝B，则┐B┝┐A（6）若A┝B，B┝C，则A┝C（7）若A┝B，A┝┥A'，B┝┥B'，则A'┝B'定理1.2设A为永真式，p为A中命题变元，A(B/p)表示将A中p的所有出现全部代换为公式B后所得的命题公式（称为A的一个代入实例），那么A(B/p)亦为永真式。定理1.3设A为一命题公式，C为A的子公式（A的一部分，且自身为一公式），且C┝┥D。若将A中子公式C的某些（未必全部）出现替换为D后得到公式B，那么A┝┥B。定理1.2常被称为代入原理（ruleofsubstitution），简记为RS。定理1.3常被称为替换原理（ruleofreplacement）简记为RR。△1.2.3对偶原理定义1.5设公式A仅含联结词┐，∧，∨，A*为将A中符号∧，∨，t，f分别改换为∨，∧，f，t后所得的公式，那么称A*为A的对偶（dual）。显然A与A*互为对偶，即(A*)*=A定理1.4设公式A中仅含命题变元p1,…,pn，及联结词┐，∧，∨，那么A┝┥┐A*(┐p1/p1,…,┐pn/pn)这里A*(┐p1/p1,…,┐pn/pn)表示在A*中对p1,…,pn分别作代入┐p1,…,┐pn后所得的公式。定理1.5设A，B为仅含联结词┐，∧，∨和命题变元p1,…,pn的命题公式，且满足A┝B，那么有B*┝A*。进而当A┝┥B时有A*┝┥B*。常把B*┝A*，A*┝┥B*称为A┝B和A┝┥B的对偶式。习题解答练习1.21、试判定以下各式是否为重言式：（1）(p→q)→(q→p)（2）┐p→(p→q)（3）q→(p→q)（4）p∧q→(pq)（5）(p→q)∨(r→q)→((p∨r)→q)（6）(p→q)∨(r→s)→((p∨r)→(q∨s))解（1）否（2）是（3）是（4）是（5）否（6）否2、试用真值表验证E6，E8，E10，E11，E23。证（1）E6(A∨B)∨CA∨(B∨C) A B C A∨B (A∨B)∨C B∨C A∨(B∨C) E6 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1（2）E8A∧(B∨C)(A∧B)∨(A∧C) A B C B∨C A∧(B∨C) A∧B A∧C (A∧B)∨(A∧C) E8 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1（3）E10┐(A∨B)┐A∧┐B A B A∨B ┐(A∨B) ┐A ┐B ┐A∧┐B E10 0 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 0 0 0 1（4）E11┐(A∧B)┐A∨┐B A B ┐A ┐B A∧B ┐(A∧B) ┐A∨┐B E11 0 0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 0 0 1（5）E23(A∧B→C)(A→(B→C)) A B C A∧B A∧B→C B→C A→(B→C) E23 0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 13、不用真值表，用代入、替换证明E12，E13，E24。证（1）E12：A∨(A∧B)┝┥AA∨(A∧B)┝┥(A∧t)∨(A∧B)据E17用RR┝┥A∧(t∨B)对E8用RS┝┥A∧t据E16用RR┝┥A据E17（2）E13：A∧(A∨B)┝┥AA∧(A∨B)┝┥(A∨f)∧(A∨B)据E18用RR┝┥A∨(f∧B)对E9用RS┝┥A∨f据E19用RR┝┥A据E18（3）E24：A→B┝┥┐B→┐A┐B→┐A┝┥┐┐B∨┐A对E14用RS┝┥B∨┐A据E1用RR┝┥┐A∨B对E4用RS┝┥A→B据E144、试用真值表验证I3，I4，I5，I6。证（1）I3A∧(A→B)→B A B A→B A∧(A→B) A∧(A→B)→B 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1（2）I4(A→B)∧┐B→┐A A B ┐B ┐A A→B (A→B)∧┐B I4 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 1（3）I5┐A∧(A∨B)→B┐B∧(A∨B)→A A B ┐A A∨B ┐A∧(A∨B) ┐A∧(A∨B)→B 0 0 1 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0 1 A B ┐B A∨B ┐B∧(A∨B) ┐B∧(A∨B)→A 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 1（4）I6(A→B)∧(B→C)→(A→C) A B C A→B B→C A→C (A→B)∧(B→C) I6 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 15、不用真值表，用代入、替换证明I7，I8。证（1）I7：(A→B)∧(C→D)┝(A∧C)→(B∧D)(A→B)∧(C→D)┝┥(┐A∨B)∧(┐C∨D)(A∧C)→(B∧D)┝┥(┐A∨┐C)∨(B∧D)┝┥(┐A∨┐C∨B)∧(┐A∨┐C∨D)由于(┐A∨B)∧(┐C∨D)┝(┐A∨┐C∨B)∧(┐A∨┐C∨D)故(A→B)∧(C→D)┝(A∧C)→(B∧D)。（2）I8：(AB)∧(BC)┝(AC)(AB)∧(BC)┝┥(A→B)∧(B→A)∧(B→C)∧(C→B)┝┥((A→B)∧(B→C))∧((C→B)∧(B→A))┝(A→C))∧(C→A)┝┥(AC)6、用三种不同 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 证明下列逻辑等价式：（1）AB┝┥(A∧B)∨(┐A∧┐B)（2）A→(B→C)┝┥B→(A→C)（3）A→(A→B)┝┥A→B（4）A→(B→C)┝┥(A→B)→(A→C)证（1）证法1： A B A∧B ┐A ┐B ┐A∧┐B AB (A∧B)∨(┐A∧┐B) 0 0 0 1 1 1 1 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1证法2：AB┝┥(A→B)∧(B→A)┝┥(┐A∨B)∧(┐B∨A)┝┥(┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A)┝┥(A∧B)∨(┐A∧┐B)证法3：先证AB┝(A∧B)∨(┐A∧┐B)(a)设为任一指派，使(AB)=1，那么(A)=(B)=1或(A)=(B)=0，从而(A∧B)=1或(┐A∧┐B)=1，即((A∧B)∨(┐A∧┐B))=1。(a)得证；再证(A∧B)∨(┐A∧┐B)┝AB(b)设为任一指派，使(AB)=0，那么(A)=1，(B)=0，或者(A)=0，(B)=1，从而(A∧B)=0且(┐A∧┐B)=0，即((A∧B)∨(┐A∧┐B))=0。(b)得证。（2）证法1： A B C B→C A→C A→(B→C) B→(A→C) 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1证法2：A→(B→C)┝┥┐A∨(┐B∨C)┝┥(┐A∨┐B)∨C┝┥(┐B∨┐A)∨C┝┥┐B∨(┐A∨C)┝┥B→(A→C)证法3：先证A→(B→C)┝B→(A→C)(a)设为任一指派，使(A→(B→C))=1，那么ⅰ）(A)=0，则(A→C)=1，从而(B→(A→C))=1ⅱ）(A)=1，(B)=0，则(B→(A→C))=1ⅲ）(A)=(B)=(C)=1，则(B→(A→C))=1综上，(a)得证；同理可证B→(A→C)┝A→(B→C)。（3）证法1： A B A→B A→(A→B) (A→(A→B))(A→B) 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1证法2：A→(A→B)┝┥┐A∨(┐A∨B)┝┥(┐A∨┐A)∨B┝┥┐A∨B┝┥A→B证法3：先证A→(A→B)┝A→B(a)设为任一指派，使(A→B)=0，那么(A)=1，(B)=0，从而(A→(A→B))=0。(a)得证；再证A→B┝A→(A→B)(b)设为任一指派，使(A→(A→B))=0，那么(A)=1，(A→B)=0。(b)得证。（4）证法1： A B C B→C A→B A→C A→(B→C) (A→B)→(A→C) 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 1证法2：(A→B)→(A→C)┝┥┐(┐A∨B)∨(┐A∨C)┝┥(A∧┐B)∨(┐A∨C)┝┥((A∧┐B)∨┐A)∨C┝┥((A∨┐A)∧(┐B∨┐A))∨C┝┥(t∧(┐A∨┐B))∨C┝┥(┐A∨┐B)∨C┝┥┐A∨(┐B∨C)┝┥A→(B→C)证法3：先证A→(B→C)┝(A→B)→(A→C)(a)设为任一指派，使((A→B)→(A→C))=0，那么(A→B)=1，(A→C)=0，即(A)=(B)=1，(C)=0，从而(B→C)=0，(A→(B→C))=0。(a)得证；再证(A→B)→(A→C)┝A→(B→C)(b)设为任一指派，使(A→(B→C))=0，那么(A)=1，(B→C)=0，即(B)=1，(C)=0，从而(A→B)=1，(A→C)=0，((A→B)→(A→C))=0。(b)得证。7、用三种不同方法证明下列逻辑蕴涵式：（1）A∧B┝AB（2）(A→B)→A┝A（3）A→B┝((AB)→A)→B（4）(A∨B)∧(A→C)∧(B→C)┝C证（1）证法1： A B A∧B AB (A∧B)→(AB) 0 0 0 1 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 1证法2：A∧B┝(A∧B)∨(┐A∧┐B)┝┥AB证法3：设为任一指派，使(A∧B)=1，则(A)=(B)=1，从而(AB)=1。A∧B┝AB得证。（2）证法1： A B A→B (A→B)→A ((A→B)→A)→A 0 0 1 0 1 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1证法2：(A→B)→A┝┥┐(┐A∨B)∨A┝┥(A∧┐B)∨A┝┥(A∨A)∧(┐B∨A)┝┥A∧(┐B∨A)┝A证法3：设为任一指派，使(A)=0，则(A→B)=1，从而((A→B)→A)=0。(A→B)→A┝A得证。（3）证法1： A B A→B AB (AB)→A ((AB)→A)→B (A→B)→(((AB)→A)→B) 0 0 1 1 0 1 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1证法2：A→B┝┥┐A∨B((AB)→A)→B┝┥┐((AB)→A)∨B┝┥((AB)∧┐A)∨B┝┥(((A∧B)∨(┐A∧┐B))∧┐A)∨B┝┥(┐A∧┐B)∨B┝┥┐A∨B∴A→B┝((AB)→A)→B证法3：设为任一指派，使(A→B)=1，则（ⅰ）(A)=0；（ⅱ）(B)=1。对（ⅱ）显然有(((AB)→A)→B)=1；对（ⅰ）则可令(B)=0（(B)=1的情况已证），于是(AB)=1，((AB)→A)=0，(((AB)→A)→B)=1。A→B┝((AB)→A)→B得证。（4）证法1： A B C A∨B A→C B→C (A∨B)∧(A→C)∧(B→C) ((A∨B)∧(A→C)∧(B→C))→C 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1证法2：(A∨B)∧(A→C)∧(B→C)┝┥(A∨B)∧(┐A∨C)∧(┐B∨C)┝┥(A∨B∨C)∧(A∨B∨┐C)∧(┐A∨B∨C)∧(┐A∨┐B∨C)∧(A∨┐B∨C)┝(A∨B∨C)∧(A∨┐B∨C)∧(┐A∨B∨C)∧(┐A∨┐B∨C)┝┥(A∨C)∧(┐A∨C)┝┥C证法3：设为任一指派，使((A∨B)∧(A→C)∧(B→C))=1，则(A∨B)=(A→C)=(B→C)=1。由(A∨B)=1有两种情况：（ⅰ）(A)=1，由(A→C)=1得(C)=1；（ⅱ）(B)=1，由(B→C)=1得(C)=1。(A∨B)∧(A→C)∧(B→C)┝C得证。△8、验证下列逻辑等价式和逻辑蕴涵式，并写出它们的对偶式：（1）┐(┐A∨┐B)∨┐(┐A∨B)┝┥A（2）(A∨┐B)∧(A∨B)∧(┐A∨┐B)┝┥┐(┐A∨B)（3）B∨┐((┐A∨B)∧A)┝┥t（4）┐A∨(┐B∨C)┝┐(┐A∧B)∨(┐A∨C)（5）┐(A∨B)∨C┝A∨(┐B∨C)解（1）┐(┐A∨┐B)∨┐(┐A∨B)┝┥(A∧B)∨(A∧┐B)┝┥A∧(B∨┐B)┝┥A对偶式：┐(┐A∧┐B)∧┐(┐A∧B)┝┥A（2）(A∨┐B)∧(A∨B)∧(┐A∨┐B)┝┥A∧(B∨┐B)∧(┐A∨┐B)┝┥A∧(┐A∨┐B)┝┥A∧┐B┝┥┐(┐A∨B)对偶式：(A∧┐B)∨(A∧B)∨(┐A∧┐B)┝┥┐(┐A∧B)（3）B∨┐((┐A∨B)∧A)┝┥B∨((A∧┐B)∨┐A)┝┥B∨(┐B∨┐A)┝┥t对偶式：B∧┐((┐A∧B)∨A)┝┥f（4）┐A∨(┐B∨C)┝A∨┐B∨┐A∨C┝┐(┐A∧B)∨(┐A∨C)对偶式：┐(┐A∨B)∧(┐A∧C)┝┐A∧(┐B∧C)（5）┐(A∨B)∨C┝(┐A∧┐B)∨C┝(┐A∨C)∧(┐B∨C)┝┐B∨C┝A∨(┐B∨C)对偶式：A∧(┐B∧C)┝┐(A∧B)∧C1.3范式内容提要1.3.1析取范式和合取范式文字(letters)：指命题常元、变元及它们的否定，前者又称正文字，后者则称负文字。析取子句(disjunctiveclauses)：指文字或若干文字的析取。例如,p,p∨┐q,┐p∨┐q∨r.合取子句(conjunctiveclauses)：指文字或若干文字的合取。例如,┐p,┐p∧┐q,p∧┐q∧r.互补文字对(complementalpairsofletters)：指形如L，┐L（L为文字）的一对字符。定义1.6命题公式A'称为公式A的析取范式（disjunctivenormalform），如果（1）A'┝┥A（2）A'为一合取子句或若干合取子句的析取。定义1.7命题公式A'称为公式A的合取范式（conjunctivenormalform）如果（1）A'┝┥A（2）A'为一析取子句或若干析取子句的合取。1.3.2主析取范式与主合取范式定义1.8设A为恰含命题变元p1,…,pn的公式。公式A'称为A的主析（合）取范式（majordisjunctive（conjunctive）normalform），如果A'是A的析（合）取范式，并且其每个合（析）取子句中p1,…,pn均恰出现一次。△1.3.3联结词的扩充与归约n个变元的真值表可以有张，因而可以定义个n元的真值函数或联结词。这就是说，我们可以规定=4个一元联结词，=16个二元联结词。定义1.9称n元联结词h是用m个联结词g1,g2,…,gm可表示的，如果h(p1,p2,...,pn)┝┥A而A中所含联结词仅取自g1,g2,...,gm。定义1.10当联结词组g1,g2,...,gm可表示所有一元、二元联结词时，称其为完备联结词组（completegroupofconnectives）。习题解答练习1.31、求下列公式的析取范式、合取范式及主析取范式、主合取范式，并据主析（合）取范式直接确定弄真该公式的指派和弄假该公式的指派：（1）(┐p∨┐q)→(p┐q)（2）q∧(p∨┐q)（3）p∨(┐p→(q∨(┐q→r)))（4）(p→(q∧r))∧(┐p→(┐q∧┐r))（5）p→(p∧(q→r))解（1）(┐p∨┐q)→(p┐q)┝┥┐(┐p∨┐q)∨((┐p∨┐q)∧(p∨q))┝┥(p∧q)∨(┐p∧q)∨(p∧┐q)（主析取范式）┝┥q∨(p∧┐q)（析取范式）┝┥p∨q（合取范式、主合取范式）弄真指派：p101弄假指派：p0q110q0（2）q∧(p∨┐q)┝┥q∧(p∨┐q)（合取范式）┝┥((p∧┐p)∨q)∧(p∨┐q)┝┥(p∨q)∧(┐p∨q)∧(p∨┐q)（主合取范式）┝┥p∧q（析取范式、主析取范式）弄真指派：p1弄假指派：p010q1q001（3）p∨(┐p→(q∨(┐q→r)))┝┥p∨(p∨(q∨(q∨r)))┝┥p∨q∨r（合取范式、主合取范式）┝┥(p∧(q∨┐q)∧(r∨┐r))∨(q∧(p∨┐p)∧(r∨┐r))∨(r∧(p∨┐p)∧(q∨┐q))┝┥(p∧q∧r)∨(p∧q∧┐r)∨(p∧┐q∧r)∨(p∧┐q∧┐r)∨(┐p∧q∧r)∨(┐p∧q∧┐r)∨(┐p∧┐q∧r)（析取范式、主析取范式）弄真指派：p1111000弄假指派：p0q1100110q0r1010101r0（4）(p→(q∧r))∧(┐p→(┐q∧┐r))┝┥(┐p∨(q∧r))∧(p∨(┐q∧┐r))┝┥(┐p∨q)∧(┐p∨r)∧(p∨┐q)∧(p∨┐r)（合取范式）┝┥(┐p∨q∨r)∧(┐p∨q∨┐r)∧(┐p∨┐q∨r)∧(p∨┐q∨r)∧(p∨┐q∨┐r)∧(p∨q∨┐r)（主合取范式）┝┥(┐p∧p)∨(q∧r∧p)∨(┐p∧┐q∧┐r)∨(q∧r∧┐q∧┐r)（析取范式）┝┥(p∧q∧r)∨(┐p∧┐q∧┐r)（主析取范式）弄真指派：p10弄假指派：p111000q10q001110r10r010011（5）p→(p∧(q→r))┝┥┐p∨(p∧(┐q∨r))┝┥┐p∨(p∧┐q)∨(p∧r)（析取范式）┝┥(┐p∧q∧r)∨(┐p∧q∧┐r)∨(┐p∧┐q∧r)∨(┐p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧┐q∧┐r)∨(p∧q∧r)（主析取范式）┝┥(┐p∨p)∧(┐p∨┐q∧r)（合取范式）┝┥┐p∨┐q∧r（主合取范式）弄真指派：p0000111弄假指派：p1q1100001q1r1010101r02、主析取范式的两个不同析取项可能在同一指派下均真吗？为什么？主合取范式的两个不同合取项可能在同一指派下均假吗？为什么？答主析取范式的两个不同析取项不可能在同一指派下均真。因为给定命题公式，其每个命题变元p1,…,pn在每个析取项中均恰出现一次，要使某个析取项在某指派下为真，则该指派下p1,…,pn的取值完全确定，而两个析取项又不相同，所以一个指派最多弄真一个析取项。同理可知主合取范式的两个不同合取项不可能在同一指派下均假。3、利用范式证明下列公式为永真式（证明合取范式的每一个合取项中含有互补文字、或其主析取范式中含有2n个析取项，n是公式中变元的个数）（1）(p→q)∧p→q（2）((p→q)→(┐p→┐q))→((┐q→┐p)→(q→p))（3）(pq)((p∧q)∨(┐p∧┐q))（4）(pq)((r∧p)(r∧q))∧((r∨p)(r∨q))（5）┐(pq)┐p┐q（6）┐(pq)┐p┐q证（1）(p→q)∧p→q┝┥┐((┐p∨q)∧p)∨q┝┥┐(┐p∨q)∨┐p∨q┝┥(p∧┐q)∨┐p∨q┝┥(p∨┐p∨q)∧(┐q∨┐p∨q)∵合取范式的每一个合取项中均含有互补文字∴原式为永真式（2）((p→q)→(┐p→┐q))→((┐q→┐p)→(q→p))┝┥┐(┐(┐p∨q)∨(p∨┐q))∨(┐(q∨┐p)∨(┐q∨p))┝┥((┐p∨q)∧(┐p∧q))∨((┐q∧p)∨(┐q∨p))┝┥(┐p∧┐p∧q)∨(q∧┐p∧q)∨(┐q∧p)∨(┐q∧p)∨(┐q∧┐p)∨(p∧q)∨(p∧┐q)┝┥(┐p∧q)∨(┐q∧┐p)∨(p∧q)∨(p∧┐q)∵主析取范式中含有22个析取项∴原式为永真式（3）(pq)((p∧q)∨(┐p∧┐q))┝┥(((p→q)∧(q→p))→((p∧q)∨(┐p∧┐q)))∧(((p∧q)∨(┐p∧┐q))→((p→q)∧(q→p)))┝┥(┐((┐p∨q)∧(┐q∨p))∨((p∧q)∨(┐p∧┐q)))∧(┐((p∧q)∨(┐p∧┐q))∨((┐p∨q)∧(┐q∨p)))┝┥((p∧┐q)∨(q∧┐p)∨