离散数学课后练习1.doc

练习1.1 1、判断下列语句是否是命题，若是命题则请将其形式化： （1）a+b （2）x0 （3）“请进！” （4）所有的人都是要死的，但有人不怕死。 （5）我明天或后天去苏州。 （6）我明天或后天去苏州的说法是谣传。 （7）我明天或后天去北京或天津。 （8）如果买不到飞机票，我哪儿也不去。 （9）只要他出门，他必买书，不管他余款多不多。 （10）除非你陪伴我或代我雇辆车子，否则我不去。 （11）只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切论证，才能得到可靠见解。 （12）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。 （13）不管你和他去不去，我去。 （14）侈而惰者贫，而力而俭者富。（韩非：韩非子显学）（15）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。（荀况：荀子劝学）解 （1）a+b 不是命题 （2）x0 不是命题（x是变元） （3）“请进！” 不是命题 （4）所有的人都是要死的，但有人不怕死。 是命题 可表示为pq，其中p：所有的人都是要死的，q：所有的人都怕死 （5）我明天或后天去苏州。 是命题 可表示为pq，其中p：我明天去苏州；q：我后天去苏州（6）我明天或后天去苏州的说法是谣传。 是命题 可表示为(pq)，其中p、q同（5）（7）我明天或后天去北京或天津。 是命题 可表示为pqrs，其中p：我明天去北京，q：我明天去天津，r：我后天去北京，s：我后天去天津（8）如果买不到飞机票，我哪儿也不去。 是命题 可表示为pq，其中，p：我买到飞机票，q：我出去（9）只要他出门，他必买书，不管他余款多不多。 是命题 可表示为(pqr)(pqr)或qr，其中p：他余款多，q：他出门，r：他买书（10）除非你陪伴我或代我雇辆车子，否则我不去。 是命题 可表示为(pq) r，其中p：你陪伴我，q：你代我雇车，r：我去（11）只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切论证，才能得到可靠见解。 是命题 可表示为(pq) (qp )或p q，其中p：你充分考虑了一切论证，q：你得到了可靠见解 （12）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。 是命题 可表示为(qp ) q，其中p：我懂得希腊文，q：我了解柏拉图 （13）不管你和他去不去，我去。 是命题可表示为(pr) (qr) ( pr) ( qr)或r，其中p：你去，q：他去，r：我去（14）侈而惰者贫，而力而俭者富。（韩非：韩非子显学） 是命题可表示为(pq)r) (pq)r)，其中p：你奢侈，q：你懒惰，r：你贫困（15）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。（荀况：荀子劝学） 是命题可表示为(pq) (sr) (mno) (mnv)，其中p：骐骥一跃，q：骐骥一跃十步，r：驽马行千里，s：驽马不断奔跑，m：你雕刻，n：你放弃，o：将朽木折断，v：金石可雕刻 2、判定下列符号串是否为公式，若是，请给出它的真值表，并请注意这些真值表的特点（公式中省略了可以省略的括号）： （1）(p)（p为原子命题） （2）(pqr)s （3）(pq)p （4）p(pq) （5）(pp) （6）p(pq)q （7）p(pq)(pq) （8）(pq) (qp) （9）(pq) qp （10）pq (pq) （11）(pq)(qr)(pr)（12）(pqr) (pr)(qr)解 （1）(p) 不是公式 （2）(pqr)s 不是公式 （3）(pq)p 是公式 pqpq(pq)pp(pq)00011011011011111111 （4）p(pq) 是公式（真值表见上表，恒真）（5）(pp) 是公式（恒假）pppp(pp)01101010（6）p(pq)q 是公式（恒真）pqpqp(pq)p(pq)q00101011011000111111（7）p(pq)(pq) 是公式（恒假）pqqpqp(pq)pqp(pq)(pq)0011010010101010100101101100（8）(pq) (qp) 是公式（恒真）pqpqpqqp(pq) (qp)0011111011011110010011100111（9）(pq) qp 是公式（恒真）pqpqpq(pq)qp(pq) qp00110111011010011001100111001001（10）pq (pq) 是公式（恒真）pqppqpqpq (pq)001111011111100001110111（11）(pq)(qr)(pr) 是公式（恒真）pqrpqqrpr(pq)(qr)(pq)(qr)(pr)0001111100111111010101010111111110001001101011011101000111111111（12）(pqr) (pr)(qr) 是公式（恒真）pqrpqpqrprqr(pr)(qr)(pqr) (pr)(qr)000011111001011111010101001011111111100100101101111111110101001111111111*3、A国的人只有两种，一种永远说真话，一种永远说假话。你来到A国，并在一个二叉路口不知如何走才能到达首都。守卫路口的士兵只准你问一个问题，而且他只答“是”或“不是”。你应该如何发问，才能从士兵处获知去首都的道路。解 设p：你是说真话的；q：我应当向右走去首都 你应当问：pq ? 当回答“是 (真)”，你选择向右走；当回答“不（假）”时，你选择向左走。因为 pq真，当且仅当p真且q真（士兵说真话且应当向右走）或p假且q假（士兵说假话且应当向左走） pq假，当且仅当p真且q假（士兵说真话且应当向左走）或p假且q假（士兵说假话且应当向右走）练习1.2 1、试判定以下各式是否为重言式： （1）(pq)(qp) （2）p(pq) （3）q(pq) （4）pq(pq) （5）(pq)(rq)(pr)q)（6）(pq)(rs)(pr)(qs)解 （1）否 （2）是 （3）是 （4）是 （5）否 （6）否2、试用真值表验证E6，E8，E10，E11，E23。证 （1）E6 (AB)C A(BC)ABCAB(AB)CBCA(BC)E60000000100101111010111110111111110011011101111111101111111111111 （2）E8 A(BC) (AB)(AC)ABCBCA(BC)ABAC(AB)(AC)E8000000001001100001010100001011100001100000001101110111110111011111111111 （3）E10 (AB) ABABAB(AB)ABABE10 00011111011010011010010111100001 （4）E11 (AB) AB ABABAB(AB)ABE1100110111011001111001011111001001 （5）E23 (ABC) (A(BC)ABCABABCBCA(BC)E2300001111001011110100101101101111100011111010111111010001111111113、不用真值表，用代入、替换证明E12，E13，E24。证 （1）E12： A(AB) A A(AB) (At)(AB) 据E17用RR A (tB) 对E8用RS At 据E16用RR A 据E17 （2）E13： A(AB) A A(AB) (Af)(AB) 据E18用RR A(fB) 对E9用RS Af 据E19用RR A 据E18 （3）E24： AB BA BABA 对E14用RS BA 据E1用RR AB 对E4用RS AB 据E14 4、试用真值表验证I3，I4，I5，I6。证 （1）I3 A(AB)BABABA(AB)A(AB)B00101011011000111111 （2）I4 (AB) BAABBAAB(AB) BI40011111010110110100011100101 （3）I5 A(AB)B B(AB)AABAABA(AB)A(AB)B001001011111100101110101ABBABB(AB)B(AB)A001001010101101111110101 （4）I6 (AB) (BC) (AC)ABCABBCAC(AB)(BC)I600011111001111110101010101111111100010011010110111010001111111115、不用真值表，用代入、替换证明I7，I8。证 （1）I7：(AB)(CD) (AC)(BD) (AB)(CD)(AB)(CD) (AC)(BD)(AC)(BD) (ACB)(ACD)由于(AB)(CD) (ACB)(ACD)故(AB)(CD) (AC)(BD)。 （2）I8：(AB)(BC) (AC) (AB)(BC)(AB)(BA)(BC)(CB) (AB)(BC) (CB)(BA) (AC) (CA) (AC) 6、用三种不同方法证明下列逻辑等价式： （1）AB(AB)(AB) （2）A(BC)B(AC) （3）A(AB)AB（4）A(BC)(AB)(AC)证 （1）证法1：ABABABABAB(AB)(AB)00011111010100001000100011100011 证法2：AB(AB)(BA) (AB)(BA) (AB)(AA)(BB)(BA) (AB)(AB) 证法3：先证AB (AB)(AB) (a) 设a为任一指派，使a(AB)=1，那么a(A)= a(B)=1或a(A)= a(B)=0，从而a(AB)=1或a(AB)=1，即a(AB)(AB)=1。(a)得证；再证(AB)(AB) AB (b)设a为任一指派，使a(AB)=0，那么a(A)=1，a(B)=0，或者a(A)=0，a(B)=1，从而a(AB)=0且a(AB)=0，即a(AB)(AB)=0。(b)得证。 （2）证法1：ABCBCACA(BC)B(AC)00011110011111010011101111111001011101111111000001111111 证法2：A(BC)A(BC) (AB)C (BA)C B(AC) B(AC) 证法3：先证A(BC) B(AC) (a) 设a为任一指派，使a(A(BC)=1，那么） a(A)= 0，则a( AC)=1，从而a( B(AC)=1） a(A)= 1，a(B)=0，则a( B(AC)=1） a(A)=a(B)=a(C)=1，则a( B(AC)=1综上，(a)得证；同理可证B(AC) A(BC)。（3）证法1：ABABA(AB)(A(AB) (AB)00111011111000111111 证法2：A(AB)A(AB) (AA)B AB AB 证法3：先证A(AB) AB (a) 设a为任一指派，使a( AB)=0，那么a(A)=1，a(B)=0，从而a( A(AB)=0。(a)得证；再证AB A(AB) (b)设a为任一指派，使a(A(AB)=0，那么a(A)=1，a(AB)=0。(b)得证。（4）证法1：ABCBCABACA(BC)(AB)(AC)0001111100111111010011110111111110010011101101111100100011111111 证法2：(AB)(AC)(AB) (AC) (AB) (AC) ( (AB)A)C (AA)(BA) )C (t(AB) )C (AB)C A(BC) A(BC) 证法3：先证A(BC) (AB)(AC) (a) 设a为任一指派，使a(AB)(AC)=0，那么a( AB)=1，a( AC)=0，即a(A)= a(B)=1，a(C)=0，从而a( BC)=0，a( A(BC)=0。(a)得证；再证(AB)(AC) A(BC) (b)设a为任一指派，使a( A(BC)=0，那么a(A)=1，a(BC)=0，即 a(B)=1，a(C)=0，从而a(AB)=1，a( AC)=0，a(AB)(AC)=0。(b)得证。 7、用三种不同方法证明下列逻辑蕴涵式： （1）AB AB （2）(AB)A A （3）AB (AB)A)B（4）(AB)(AC)(BC) C证 （1）证法1：ABABAB(AB) (AB)00011010011000111111 证法2：AB (AB) (AB) AB 证法3：设a为任一指派，使a(AB)=1，则a(A)= a(B)=1，从而a( AB)=1。AB AB得证。 （2）证法1：ABAB(AB)A(AB)A) A00101011011001111111 证法2：(AB)A (AB) A (AB) A (A A)(BA) A(BA) A 证法3：设a为任一指派，使a(A)=0，则a(AB)= 1，从而a(AB)A)=0。(AB)A A得证。 （3）证法1：ABABAB(AB)A(AB)A)B(AB)(AB)A)B)0011011011011110001011111111 证法2：ABAB (AB)A)B(AB)A)B (AB) A)B (AB)(AB)A)B (AB)B AB AB (AB)A)B 证法3：设a为任一指派，使a( AB)=1，则（）a(A)= 0；（）a(B)= 1。对（）显然有a( (AB)A)B)=1；对（）则可令a(B)= 0（a(B)= 1的情况已证），于是a(AB)=1，a(AB)A)=0，a(AB)A)B) =1。 AB (AB)A)B得证。 （4）证法1：ABCABACBC(AB)(AC)(BC)(AB)(AC)(BC)C0000110100101101010110010111111110010101101111111101000111111111 证法2：(AB)(AC)(BC)(AB)(AC)(BC) (ABC)(ABC)(ABC)(ABC)(ABC) (ABC)(ABC)(ABC)(ABC) (AC) (AC) C证法3：设a为任一指派，使a(AB)(AC)(BC)=1，则a(AB)= a( AC)= a( BC)=1。由a(AB)=1有两种情况：（）a(A)=1，由a( AC)=1得a(C)=1；（）a(B)= 1，由a( BC)=1得a(C)=1。 (AB)(AC)(BC) C得证。 8、验证下列逻辑等价式和逻辑蕴涵式，并写出它们的对偶式： （1）(AB)(AB)A （2）(AB)(AB)(AB)(AB) （3）B(AB)A)t （4）A(BC) (AB)(AC)（5）(AB)C A(BC)解 （1）(AB)(AB)(AB)(AB) A(BB) A对偶式 ：(AB)(AB)A （2）(AB)(AB)(AB)A(BB)(AB) A(AB) AB (AB)对偶式 ：(AB)(AB)(AB)(AB) （3）B(AB)A)B(AB)A) B(BA) t对偶式 ：B(AB)A)f （4）A(BC) ABAC (AB)(AC)对偶式 ：(AB)(AC) A(BC) （5）(AB)C (AB)C (AC)(BC) BC A(BC)对偶式 ：A(BC) (AB)C练习1.3 1、求下列公式的析取范式、合取范式及主析取范式、主合取范式，并据主析（合）取范式直接确定弄真该公式的指派和弄假该公式的指派：（1）(pq)(pq) （2）q(pq) （3）p(p(q(qr) （4）(p(qr)(p(qr)（5）p(p(qr)解 （1）(pq)(pq)(pq)(pq)(pq) (pq)(pq)(pq) （主析取范式） q(pq) （析取范式） pq （合取范式、主合取范式） 弄真指派：p 1 0 1 弄假指派：p 0 q 1 1 0 q 0 （2）q(pq)q(pq) （合取范式） (pp)q)(pq) (pq)(pq)(pq) （主合取范式） pq （析取范式、主析取范式） 弄真指派：p 1 弄假指派：p 0 1 0 q 1 q 0 0 1 （3）p(p(q(qr)p(p(q(qr) pqr （合取范式、主合取范式） (p(qq)(rr)(q(pp)(rr)(r(pp)(qq) (pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr) （析取范式、主析取范式） 弄真指派：p 1 1 1 1 0 0 0 弄假指派：p 0 q 1 1 0 0 1 1 0 q 0 r 1 0 1 0 1 0 1 r 0 （4）(p(qr)(p(qr)(p(qr )(p(qr) (pq)(pr )(pq)(pr) （合取范式） (pqr)(pqr)(pqr )(pqr)(pqr)(pqr) （主合取范式） (pp)(qrp)(pqr)(qrqr) （析取范式） (pqr)(pqr) （主析取范式） 弄真指派：p 1 0 弄假指派：p 1 1 1 0 0 0q 1 0 q 0 0 1 1 1 0r 1 0 r 0 1 0 0 1 1（5）p(p(qr)p(p(qr ) p(pq)(pr ) （析取范式） (pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr) （主析取范式） (pp)(pqr ) （合取范式） pqr （主合取范式） 弄真指派：p 0 0 0 0 1 1 1 弄假指派：p 1 q 1 1 0 0 0 0 1 q 1 r 1 0 1 0 1 0 1 r 0 2、主析取范式的两个不同析取项可能在同一指派下均真吗？为什么？主合取范式的两个不同合取项可能在同一指派下均假吗？为什么？答 主析取范式的两个不同析取项不可能在同一指派下均真。因为给定命题公式，其每个命题变元p1, ,pn在每个析取项中均恰出现一次，要使某个析取项在某指派下为真，则该指派下p1, ,pn的取值完全确定，而两个析取项又不相同，所以一个指派最多弄真一个析取项。同理可知主合取范式的两个不同合取项不可能在同一指派下均假。 3、利用范式证明下列公式为永真式（证明合取范式的每一个合取项中含有互补文字、或其主析取范式中含有2n个析取项，n是公式中变元的个数） （1）(pq)pq （2）(pq)(pq) ( qp) (qp) （3）(pq) (pq)(pq) （4）(pq) (rp) (rq)(rp) (rq) （5）(pq) pq（6）(pq) pq证 （1）(pq)pq(pq)p)q (pq)pq (pq)pq (ppq)(qpq) 合取范式的每一个合取项中均含有互补文字 原式为永真式 （2）(pq)(pq) ( qp) (qp) (pq)(pq) ( qp)(qp) ( (pq)(pq) (qp)(qp) (ppq)(qpq)(qp)(qp)(qp)(pq)(pq) (pq)(qp)(pq)(pq) 主析取范式中含有22个析取项 原式为永真式 （3）(pq) (pq)(pq)(pq)(qp)(pq)(pq) (pq)(pq)(pq)(qp)(pq)(qp) (pq)(pq) (pq)(pq) (pq)(qp)(pq)(qp)(pq)(pq) (pq)(pq) (pq)(qp)(pq)(qp)(pq)(pq) (pqpq)(pqpq)(pqqp)(pqqp)(pq)(qp)(pq)(pq) 主析取范式中含有22个析取项 原式为永真式（4）(pq) (rp) (rq)(rp) (rq) (pq)(qp) (rp)(rq)(rq)(rp)(rp)(rq)(rq)(rp) (pq)(qp) (rp)(rq)(rq)(rp)(rp) (rq)(rq)(rp) (pq)(pq) (pqr)(pqr)(pqr)(pq