离散数学王元元习题解答

1、1 命题演算及其形式系统1.1 命题与联结词内容提要1.1.1 命题我们把对确定的对象作出判断的陈述句称作命题(propositions ),当判断正确或符合客观实际时，称该命题 真(true ),否则称该命题假(false )。“真、假”常被称为命题的真值。自然语言中“并非、或者、并且、如果，那么、当且仅当 ”这样的联结词称为 逻辑 联结词(logical connectives )。通常把不含有逻辑联结词的命题称为原子命题 或原子(atoms),而把由原子命题和逻辑联结词共同组成的命题称为复合命题(compositive propositions )。1.1.2 联结词否定词(negati

2、on)“并非(not),用符号i表示。设 p表示一命题，那么1p表示命题p的否定。谓时p假，而p假时p真。1p读作“并非p”或“非p”。合取词(conjunction) “并且(and),用符号A表示。设p, q表示两命题，那么pA q表示 合取p和q所得的命题，即p和q同时为真时pAq真，否则pAq为假。pAq读作“p并且q或“p 且q” 。析取词(disjunction) 或(or)用符号V表示。设p, q表示两命题，那么pVq表示p和q 的析取，即当p和q有一为真时，pVq为真，只有当p和q均假时pVq为假。pVq读作p或者q”、 p或q”。蕴涵词(implication) 如果，那么(

3、ifthen)，用符号-表示。设 p, q表示两命题，那么p-q表示命题“如果p,那么q。当p真而q假时，命题p-q为假，否则均认为p fq为真。p-q中的p称为蕴涵前件，q称为蕴涵后件。p-q的读法较多，可读作“如果 p则q”， “p蕴涵q”，“p是q的充分条件”，“ q是p的必要条件”，“ q当p”，“p仅当q”等等。数学 中还常把qfp, n 尸n q, n q-n p分别叫做p-q的逆命题，否命题，逆否命题。双向蕴涵词(two-way implication)当且仅当(if and only if ),用符号表示之。设p, q为两命题，那么p q表示命题“ p当且仅当q，“ p与q等价

4、”，即当p与q同真值时p q 为真，否则为假。p q读作“ p双向蕴涵q”，“ p当且仅当q”，“ p等价于q”。由于“当且仅 当” “等价”常在其它地方使用，因而用第一种读法更好些。1.1.3 命题公式及其真值表我们把表示具体命题及表示常命题的p, q, r , s与f, t统称为命题常元(propositionconstant )。深入的讨论还需要引入 命题变元(proposition variable )的概念，它们是以“真、 假”或“1, 0”为取值范围的变元，为简单计，命题变元仍用 p, q, r, s等表示。定义1.1以下三条款规定了 命题公式(proposition formul

5、a )的意义：(1)命题常元和命题变元是命题公式，也称为原子公式或原子。(2)如果A,B是命题公式，那么(A),(AAB),(AVB),g B),(AB)也是命题公式。(3)只有有限步引用条款(1), (2)所组成的符号串是命题公式。如果公式A含有命题变元p1 , p2,，pn,记为A(p1,p n),并把联结词看作真值运算符， 那么公式A可以看作是p1,pn的真值函数。对任意给定的p1,pn的一种取值状况，称为 指派(assignments ),用希腊字母 ，等表示，A均有一个确定的真值。当 A寸取值状况为真时，称指派弄真A,或 是A的成真赋值，记为(A) = 1 ;反之称指派弄假A,或 是

6、A勺成假赋值，记为(A) = 0。对一切可能的指派，公式A勺取值可能可用一张表来描述，这个表称为真值表(truth table )。当A(p1,p n)中有k个联结词时，公式 A的真值表应为2n行、k+n歹U (不计表头)。1.1.4 语句的形式化用我们已有的符号语言，可以将许多自然语言语句形式化。语句形式化要注意以下几个方面。要善于确定原子命题，不要把一个概念硬拆成几个概念，例如“弟兄”是一个概念，不要 拆成“弟”和“兄”、“我和他是弟兄”是一个原子命题。要善于识别自然语言中的联结词(有时它们被省略)。例如“风雨无阻，我去上学” 一句,可理解为“不管是否刮风、是否下雨我都去上学”。否定词的位

7、置要放准确。需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。另外要注意的是，语句的形式化未必是唯一的。习题解答练习1.11 、判断下列语句是否是命题，若是命题则请将其形式化：(1) a+b(2) x0(3) “请进！”(4)所有的人都是要死的，但有人不怕死。(5)我明天或后天去苏州。(6)我明天或后天去苏州的说法是谣传。(7)我明天或后天去北京或天津。(8)如果买不到飞机票，我哪儿也不去。(9)只要他出门，他必买书，不管他余款多不多。(10)除非你陪伴我或代我雇辆车子，否则我不去。(11)只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切论证，才能得到可 靠见解。

8、(12)如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。(13)不管你和他去不去，我去。(14)侈而惰者贫，而力而俭者富。(韩非：韩非子 显学)(15)骐骥一跃，不能十步；弩马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金 石可镂。(荀况：荀子劝学)解 (1) a+b 不是命题(2) x0 不是命题(x是变元)(3) “请进！”不是命题(4)所有的人都是要死的，但有人不怕死。是命题可表示为pAq q,其中p：所有的人都是要死的，q：所有的人都怕死(5)我明天或后天去苏州。是命题可表示为pVq,其中p：我明天去苏州；q：我后天去苏州(6)我明天或后天去苏州的说法是谣传。是命题可表示为(p

9、 V q),其中p、q同(5)(7)我明天或后天去北京或天津。是命题可表示为pVqVrVs,其中p：我明天去北京，q：我明天去天津，r：我后天去北 京，s：我后天去天津(8)如果买不到飞机票，我哪儿也不去。是命题可表示为p-n q,其中，p：我买到飞机票，q：我出去(9)只要他出门，他必买书，不管他余款多不多。是命题可表示为(pAq-r) A (n p八4)或4-，其中p：他余款多，q:他出门，r:他 买书(10)除非你陪伴我或代我雇辆车子，否则我不去。是命题可表示为(p V q)r ,其中p：你陪伴我，q：你代我雇车，r :我去(11)只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切

10、论证，才能得到可靠见解。是命题可表示为(p -q) A(q - p )或p q,其中p：你充分考虑了一切论证，q：你得到了可靠见解(12)如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。是命题可表示为(q-p ) - n q,其中p：我懂得希腊文，q：我了解柏拉图(13)不管你和他去不去，我去。 是命题可表示为(p - r) A (q - r) A ( n p-r) A ( n q-r)或 r,其中 p：你去，q： 他去，r:我去(14)侈而惰者贫，而力而俭者富。(韩非：韩非子 显学)是命题可表示为(p Aq)-r) A ( n pAn q) - n r),其中p：你奢侈，q：你懒惰，r

11、 : 你贫困(15)骐骥一跃，不能十步；弩马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。(荀况：荀子劝学)是命题可表示为(p - n q) A(s-r) A(mAn-n o) A (m An nfv),其中 p：骐骥一 跃,q：骐骥一跃十步，r ：弩马行千里，s：弩马不断奔跑，m：你雕刻，n：你 放弃，o：将朽木折断，v:金石可雕刻2 、判定下列符号串是否为公式，若是，请给出它的真值表，并请注意这些真值表的特点(公式中省略了可以省略的括号)：(1) 1 (p) ( p为原子命题)(2) (p V qr) - s(3) (p V q)-p(4) p-(p V q)(5) n (p V

12、n p)(6) pA (p fq) -q pA (p -q) A (p - n q)(8) (p-q) ( n q-n p)(9) n (p V q) n qAn p(10) n pVq (p - q)(11) (p - q) A (q - r) (p r)(12) (pVqfr) (p - r) A(q - r)解(1) 1 (p)不是公式(2) (p V qr) - s 不是公式(3) (p V q) -p 是公式pqpVq(p v q)-9Pp 一 (pVq)0o0110i1011o1111i111(4) p-(p Vq)是公式(真值表见上表，恒真)(5) 1 (p Vq p) 是公式(

13、恒假)pn ppVn pn (p Vn p)01101010(6) pA(pq) - q 是公式(恒真)pqpfqpA (p-q)pA(p-q) 一 q00101011011000111111(7) pA(p-q)A(p 一n q) 是公式(恒假)pqn qpfqpA (p- q)尸n qpA (p-q) A (p、 q)0011010010101010100101101100(8) (p-q) ( n qn p) 是公式(恒真)pqn pn qpfqn qp(p-q) (n qp)00111110 111011110010011100111(9) (pVq) n qAn p 是公式(恒真)p

14、qn pn qpVqn (p V q)n qAn pn (p Vq) n qAn p00110111011010011001100111001001(10) n p V q (p -q) 是公式(恒真)pqn pn p V qpfqn pVq (p -q)0o11110 1111111o0001110111(11) (p- q) A (q 一。一 (p 是公式(恒真)pqrpfqq 一 rp-r(p-q) A (q- r)(p-q) A (q-r) 一 (p 一 r)0001111100111111010101010111111110001001101011011101000111111111

15、(12) (p V q一r)(p 一r) A(q - r) 是公式(恒真)pqrpVqp V qfrp-rq-r(p 一 r) A (q-r)(pVq-r)(p一 r) A (q 一 r)0000111110 1010111110101010010 111111111100100101101111111110101001111111111*3、A国的人只有两种，一种永远说真话，一种永远说假话。你来到A国，并在一个二叉路口不知如何走才能到达首都。守卫路口的士兵只准你问一个问题，而且他只答“是”或“不 是。你应该如何发问，才能从士兵处获知去首都的道路。解设p：你是说真话的；q：我应当向右走去首都你

16、应当问：p q ?当回答“是（真）”，你选择向右走；当回答“不（假）”时，你选择向左走。因为pq真，当且仅当p真且q真（士兵说真话且应当向右走）或p假且q假（士兵说假话且应当向左走）pq假，当且仅当p真且q假（士兵说真话且应当向左走）或p假且q假（士兵说假话且应当向右走）1.2 重言式内容提要1.2.1 重言式概念定义1.2 命题公式A称为重言式（tautology ），如果对A中命题变元的一切指派均弄真 A,因而重言式又称 永真式；A称为可满足式(satisfactable formula ),如果至少有一个指派弄真A,否则称A为不可满足式或永假式、矛盾式。1.2.2 逻辑等价式和逻辑蕴涵式

17、定义1.3当命题公式A B为永真式时，称型辑等价于B,记为Al B,它又称为 逻辑等价 式(logically equivalent)A, B, C表不任意命题公式: 双重否定律以下是一些重要的逻辑等价式，其中 E 1 n 1 A |- AE2 A V A I A哥等律E3AA A IA哥等律E4AV B kTBVA交换律E5AA B IBAA交换律E6(AVB)VCkTAV(BVC)结合律E7(AA B) A C kTAA(BA C)结合律E8 A A (B V C)H(A A B)V (A AC)分配律E9 A V (B A C)H(A V B)A (A VC)分配律Eio n (A V

18、B) n AA nB德摩根律Eii n (A AB)AV nB德摩根律E12AV (AA B) HA吸收律E13AA (A V B) HA吸收律曰4 A fBl n AV BE15 A B H (Af B) A (B-A)曰6 A vt H tE17 A At | A曰8 A Vf H AE19 a a f H fE20 A V n A _ tE21 A A A I_ fE22 n t f, n f tE23 A A B C H Af (B fC)E24 A f B I_ n Bf n AE25 (A f B) A (Afi B) H n A定义1.4 当命题公式A- B为永真式时，称 破辑蕴

19、涵B,记为AkB,它又称为 逻辑蕴涵式(logically implication) 。我们也列出一些十分重要的逻辑蕴涵式：I 1 A k AVB, B k A V BI 2 AAB k A,AA B k BI3 A A(A fB)卜 BI4 (A B) An B AI5 n AA (A V B)k BBA (A V B)k AI6 (A f B) A (B-C)k A -CI7 (A f B) A (C-D)卜(A A C) (BA D)18 (A B) A (B C)k A C逻辑等价式与逻辑蕴涵式有如下明显性质。定理1.1对任意命题公式 A B, C, A, B,(1) Al B当且仅当

20、kA B(2) AkB当且仅当卜A fB(3)若Al B,则 B I A(4)若Al B, Bl C,则A I C(5)若 A - B ,则B H n A(6)若A-B , BkC ,则AkC(7)若A- B, Al A, Bl B，则A k B定理1.2 设A为永真式，p为A中命题变元，A(B/p)表示将A中p的所有出现全部代换为公式B后所得的命题公式(称为 A的一个代入实例)，那么A(B/p)亦为永真式。定理1.3 设A为一命题公式，EA的子公式(A勺一部分，且自身为一公式)，且Cl d若将A中子公式C勺某些(未必全部)出现替换为所得到公式B,那么Al R定理1.2常被称为 代入原理 (r

21、ule of substitution),简记为RS定理1.3常被称为 替换原理 (rule of replacement )简记为RR 123对偶原理定义1.5 设公式A仅含联结词A, V,A*为将A中符号A , V, t, f分别改换为V,A, f, t后所得的公式，那么称 A*为A勺对偶(dual)。显然AM A*互为对偶，即(A*)*二A定理1.4 设公式A中仅含命题变元Pi,pn,及联结词,A, V,那么AI_ n A*( n p1/p 1,，n pn/p n)这里A*( n Pi/Pi,n pn/p n)表示在A*中对Pi,p n分别作代入Pi,n Pn后所得的公式。定理1.5 设

22、A, B为仅含联结词1,A , V和命题变兀p1,p n的命题公式，且满足 AkB,那么有B*A*。进而当A H B时有A* H B*。常把B*-A* , A* H B*称为AkB和A I B的对 偶式。习题解答练习1.21 、试判定以下各式是否为重言式：(1) (p-q) 一 (q-p)(2) n p一 (p 一q)(3) q(p q)(4) pAq一(p q)(5) (p-q) V (r-q) 一 (p V r) -q)(6) (p-q) V (r-s) 一(p V r) 一(q Vs)解(1)否是(3)是(4)是(5)否(6)否2、试用真值表验证 E6, E8, E10, E11, E2

23、3。证(1) E6 (A V B) V CAV (BV C)ABCAV B(A V B) V CBVCAV (B V C)E601 00000010010111101 10111110111111110011011101111111101111111111111(2) & AA (BVC) (A A B) V (A A C)ABCBVCAA (B V C)AA BAA C(A A B) V (A A C)睇0001 000001001100001010100001:011P 10r 00011100000001r 101P 110111110111011111111111(3) E10 n (

24、A V B) n AN n BABAV Bn (A V B)n An Bn AA n BE1000011111011010011010010111100001(4) E11 n (A A B) n AVn BABn An BAA Bn (A AB)n AV n BE1100110111011001111001011111001001ABCAA BAA Bf CBf CA一 (B-C)E23000011110010111101001011011r 011 111110001111101r 011111101000111111111(5) E23 (A A B-C)(A 一 (B - C)E24。

25、3、不用真值表，用代入、替换证明E12,曰3,证(1) E12： A V (A A B) H AA V (AA B) H (A A t) V (A A B) H AA (t V B) H AA t H A据曰7用RR巳用RS据E16用RR据E17(2) E13： A A (A V B) H aA A (A V B) H (A V f) A (A V B)据 E18用 RRI AV (f AB)又E9用RSH AV f据 E19用 RRI A据 El8(3) E24： A一 B In B一n An B一n Ali n BVn AXEi拥 RSH BVn A据Ei用RRH n AV BX曰用 RS

26、H A-B据曰44、试用真值表验证I3, |4, |5, I 60证(1) I 3 AN (A - B)-BABKBA A (A 一 B)AA (A - B) - B0010101P 10P111000111111(2) I 4 (A-B) An B一n AABn B n AKB(A f B) An BI 4001111101011101:10100011100101(3) I 5 n AN (AVB) - B n BA (AV B) 一 AABn AAV Bn AA (A V B)n AA (A V B) 一 B001001011111100101110101ABn BAV Bn BA (A

27、 V B)n BA (AVB) 一A001|0010110；10111101111110101(4) I 6 (A-B) A(B - C) 一 (A - C)ABCAfBBfCAfC(A-B)A (B-C)I 6000111110011111101010101011P 11111100010011010110111010001111111115、不用真值表，用代入、替换证明I 7, I 8。证 (1) I7： (A-B)A (C-D)卜(A A C) 一 (BA D)(A一 B)A(C-D)I (n AV B) A ( n CV D)(AAC) 一 (BAD) I (n AV n C) V (

28、B A D)H (n AV n CV B)A (n AV n CV D)由于(n AV B) A (n CV D)卜(n AVn CV B) A (n AVn CV D) 故(A - B)A (C - D)卜(A A C) 一 (BA D)。(2) I 8： (A B)A (B C)卜(A C)(A B)A (B C) H (A - B)A (B-A) A (B - C)A (C - B)H (A 一 B) A (B - C) A (C 一 B)A(B-A) 卜(A 一 C) A (C A) H (A C)6 、用三种不同方法证明下列逻辑等价式：(1) A Bl (A A B) V( n AA

29、 n B)(2) Z (B-C)I B 一 (A - C)(3) 2 (A-B) H A- B(4) Z (B-C)I (A - B)(A - C) 证 (1)证法1:ABAA Bn An Bn AA n BA B(AA B) V (n AAn B)00011111010100001000100011100011证法 2: A Bl (A-B)A(B-A)H (n AV B)A (n BV A)H ( n AAn B) V ( n AA A) V (BAn B) V (B A A)H (A A B) V (n AA n B)证法 3:先证 A B k(A A B) V (n AA n B) (

30、a)设为任一指派，使 (A B)=1 ,那么 (A)=(B)=1或(A)=(B)=0 ,从而 (AAB)=1 或 AA n B)=1 ,即 (A A B) V (n AA n B)=1。(a)得证； 再证(A A B) V (n AA n B)- A B (b)设为任一指派，使(A B)=0,那么(A)=1 , (B)=0,或者(A)=0 , (B)=1 , 从而 (AAB)=0且 (AA n B)=0 ,即 (A A B) V (n AA n B)=0。(b)得证。(2)证法1:ABCBf CA一 CZ (B - C)Bf(A-C)0001111001 :111111010011101111

31、111001011101111111000001111111证法 2: A一 (B-C)Ii AV (n BV C)H (n AVn B) VC H (n BVn A) VC BVAV C) H B一 (A-C)证法 3:先证 Af(B-C)- B 一 (A - C) (a)设 为任一指派，使(A一 (B - C)=1 ,那么i) (A)= 0 ,则(AC)=1,从而 (B 一 (A - C)=1ii) (A)= 1 ,(B)=0 ,则 (B 一 (A-C)=1iii) (A)=(B)=(C)=1 ,则 (B 一 (A - C)=1综上，(a)得证；同理可证 Bf(A一C)卜A一(B一C)。(

32、3)证法1 :AB2 BA一 (A-B)(A 一 (A-B)(A - B)001110 二11P 111000111111证法2: A一(A-B) H n AVAV B)H (n AV n A) V BI_ n AV BH A-B证法3:先证Af(A-B)-A - B (a)设为任一指派，使 (A B)=0,那么 (A)=1 ,(B)=0，从而 (A 一 (A 一B)=0。 (a)得证；再证KB k A一(A - B) (b)设 为任一指派，使 (A一 (A - B)=0 ,那么 (A)=1 , (A-B)=0。(b)得证。(4)证法1:ABCBfCAfBKCK(B - C)(A-B)(A -

33、 C)0001111100111111010011110111111110010011101101111100100011111111证法 2: (A-B)(A - C)Ii ( n AV B) V ( n AV C)H (AAn B) V ( n AV C)H ( (A An B) Vn A) V CH (A Vn A) A( n BV n A) ) VCH (t A (n AVn B) ) VCH (n AVn B) VCH n AV (n BVC)H 2 (B - C)证法 3:先证右(B - C)-(A-B)(A - C) (a)设 为任一指派，使 (A - B) (A-C)=0 ,那

34、么 (AB)=1 , ( A-C)=0, 即 (A)=(B)=1 ,(C)=0 ,从而 (BC)=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)得证。、用三种不同方法证明下列逻辑蕴涵式:(1) AA B k A B(2) (A-B)一A k A(3) KB 二(A B) 一A)一B(4) (A V B)A (A-C)A (B-C)- C证 (

35、1)证法1:ABAA BA B(A A B) 一 (A B)0001101 0011000111111证法 2: AA B k(A A B) V ( n AN n B)I A B证法3:设 为任一指派，使(AAB)=1,则 (A)=(B)=1，从而 (A B)=1。AA BkA B得证。(2)证法1:ABA一 B(A-B) 一 A(A - B) 一 A) 一 A00101011011001111111证法 2: (A-B)一 Al n ( n AV B) V AH (A An B) V AH (A V A) A (n BV A)H A A (n BV A)-A证法3:设 为任一指派，使 (A)

36、=0 ,则 (A B)= 1 ,从而 (AB)-A)=0。(A 一 B) 一 A卜A得证。(3)证法1:ABKBA B(A B) 一 A(AB) 一 A) 一 B(A(A-B) 一B) A) 一 B)001101101101111000101r 11 111111证法2: A- B 1n AV B(AB) 一 A) 一Bl n (A B) 一 A)VBH (A B) An A) V BH (A A B) V ( n AA n B) An A) V BH (n AA n B) V BIn AV BA - B 卜(A B)一 A) 一 B证法 3:设 为任一指派，使 (A - B)=1，则(i )

37、(A)= 0 ; (ii)(B)= 1 。对(ii)显然有(AB)-A)-B)=1;对(i)则可令 (B)= 0( (B)= 1的情况已证)，于是 (A B)=1 ,(A B)一 A)=0,(AB) 一 A) 一 B) =1 。B 卜(AB) 一 A)一 B导证。(4)证法1:ABCAV BAf CBfC(AV B) A (A-C) A (B - C)(A V B) A(A - C)A (B - C) 一 C0000110100101101010110010111111110010101101111111101000111111111证法 2: (A V B)A (A - C)A (B - C

38、) I (A V B) A (n AV C) A (n BV C)H (AV BV C)A(AVBV n C) A ( n AV BV C)A (n AV n BVC)A (A V n BV C)卜(A V BV C) A (A Vn BVC)A( n AV BV C) AAVn BV C)H (A V C) A (n AV C)I C证法 3:设 为任一指派，使 (A VB) A (A - C)A (B-C)=1，则 (AV B)=( AC)=( B -C)=1。由 (AV B)=1 有两种情况：(i )(A)=1，由 (A C)=1 得 (C)=1 ;(11) (B)= 1 ,由 (B-C

39、)=1 得 (C)=1。(A V B) A (A-C) A (B-C)k C得证。 8、验证下列逻辑等价式和逻辑蕴涵式，并写出它们的对偶式：(1) 1AVn B) Vn (n AV B) H A(2) (A Vn B) A (A V B) A (n AVn B) H n ( n AV B)(3) BVn ( n AV B) AA) I t(4) n AV (n BV C)k n (n AA B) V (n AV C)(5) n (AV B) VCk A V( n BV C)解 (1) (n AVn B) Vn (n AV B) H (A A B) V(A An B)H AA (B Vn B)I

40、I A对偶式：1 (1 AAn B) An (n AA B) |-1 A(2) (A Vn B)A(AVB)AAVn B) I AA (B Vn B) AAVn B)H AAAVn B)I_| AA n B n (n AV B)对偶式：(A Ai B) V (AA B) VAA n B) H n (n AA B)(3) BVn ( n AV B)A A) H BV (A An B) Vn A)H BV (n BV n A)II t对偶式：BA n ( n AA B) V A) H f(4) n AV (n BV C)k A Vn BVn AV Ck n (n AA B) V (n AV C)对

41、偶式：1 (1 AV B) A (n AA C)kAA (n BA C)(5) (A VB) VCk(n AA n B) V C卜(n AV C)A (n BV C)BVCk A V (n BV C)对偶式：AA (n BA C)卜1(A A B) A C1.3 范式内容提要1.3.1 析取范式和合取范式文字(letters):指命题常元、变元及它们的否定，前者又称正文字，后者则称负文字。析取子句(disjunctive clauses) :指文字或若干文字的析取。例如 ,p , p Vn q , n p Vq qV r.合取子句(conjunctive clauses):指文字或若干文字的合

42、取。例如 ，p , n pAq q , pAn qA r .互补文字对(complemental pairs of letters):指形如L, n L ( L为文字)的一对字符。te义1.6 命题公式A称为公式 A勺析取氾式 (disjunctive normal form ),如果 (D A H A定义1.9称n元联结词h是用m个联结词g, g 2,，g m可表示的，如果h(p1, p 2,. . ., pn ) H A而A中所含联结词仅取自gi, g 2,. . ., gmo定义1.10 当联结词组gi, g 2,. . ., gm可表示所有一元、二元联结词时，称其为 完备联结词组(co

43、mplete group of connectives )。习题解答练习1.31 、求下列公式的析取范式、合取范式及主析取范式、主合取范式，并据主析(合)取范式 直接确定弄真该公式的指派和弄假该公式的指派：(1) (n pVn q)-(p n q)(2) qA (p Vn q)(3) pV (n p-(q Vq-r)(4) (p-(q A r) Ap-q r)(5) p-(pA(q - r)解 (1) p V q) (p n q) H n (n pVq q) V ( n p Vq q) A (p V q)H (p A q) V (n pA q) V (p An q)(主析取范式)H q V (

44、p An q)(析取范式)H p V q(合取范式、主合取范式)弄真指派：p 1 0 1 弄假指派：p 0q 1 1 0 q 0(2) qA (p Vn q) H qA (p Vq q)(合取范式)H (p p) V q) A (p Vq q)H (p V q) A (n pV q) A (p Vn q)(主合取范式)1 p A q(析取范式、主析取范式)弄真指派：p 1弄假指派：p 0 1 0q 1q 0 0 1(3) p V (n p-(q V (n q-r) H pV (p V (q V (q V r)H pVqVr(合取范式、主合取范式)H (p A (q Vn q) A (r Vq

45、r) V (q A (p Vq p) A (r Vq r) V (r A (p Vq p) A (q V n q)I (pAqAr) V (p A q An r) V (p An qA r) V (p An q An r) V (n pAqAr) V(n pA q An r) V (n pAq qA r)(析取范式、主析取范式)弄真指派：p 1 1 1 1 0 0 0弄假指派：p 0q 1 1 0 0 1 1 0 q 0r 1 0 1 0 1 0 1r 0(4) (p-(qAr)A (n p-(n qAqr) H (n pV (q A r ) A (p V (n qAn r)(n pV q)

46、A (n p V r ) A (p Vq q) A (p Vq r) (合取范式)(n pVqVr) A (n p V q Vq r) A (n pVn q V r ) A (p Vq q V r) A (p Vq q Vq r)A(pVqVi r)(主合取范式)H (n pA p) V (q A r A p) V (n p八、qH (pAqAr) V (n pAn qAn r)弄真指派：p 1 0弄假指派：p 1q 1 0q 0 0 1 1 1 0r) V(qArA qAn r)(析取范式)(主析取范式)1 1 0 0 0 pf(pA(qr) H n pV (p A (n q V r )H

47、n p V (p An q) V (p A r ) (析取范式)H (n pAqAr)pA q An r) V (n p An q A r) V (n pAn q An r) V (p An qAr) V (p An qAn r) V (pAqAr)(主析取范式)H (n p V p) A (n pVn qAr )(合取范式)In pVq qAr(主合取范式)弄真指派：p 0 0 0 0 1 1 1弄假指派：p 1q 1 1 0 0 0 0 1q 1r 1 0 1 0 1 0 1r 02、主析取范式的两个不同析取项可能在同一指派下均真吗？为什么？主合取范式的两个不同合取项可能在同一指派下均假吗？为什么？答 主析取范式的两个不同析取项不可能在同一指派下均真。因为给定命题公式， 其每个命题变元丸 ,pn在每个析取项中均恰出现一次，要使某个析取项在某指派下为真，则该指派下 p1,p n的取值完全确定，而两个析取项又不相同，所以一个指派最多弄真一个析取项。同理 可知主合取范式的两个不同合取项不可能在同一指派下均假。3 、利用范式证明下列公式为永真式(证明合取范式的每一个合取项中含有互补文字、或其主析取范式中含有2n个析取项，n是公式中变元的个数)(1) (pfq) A p-q(