离散数学练习(部分)解答

《离散数学练习(部分)解答》由会员分享，可在线阅读，更多相关《离散数学练习(部分)解答（9页珍藏版）》请在金锄头文库上搜索。

1、离散数学练习解答福建农林大学东方学院2009 2010 学年第二学期第一篇 数理逻辑二、解答题：1、 将下列命题符号化：（1） 明天不下雨又有空的话，我就会去打球。（2） 只要她生病了，我都会去看她（只有她生病了，我才会去看她） 。（3） 每个旅客或坐头等舱或坐二等舱。（4） 有些汽车比任何火车都慢，但并非所有的汽车都比火车慢。解 （1） 设 ：明天不下雨； ：明天我有空； ：明天我去打球。则该命题可符PQR号化为 。R（2）设 ：她生病； ：我去看她。则该命题可符号化为 。()PQ（3）设 是旅客； 坐 ； 是头等舱位； 是二:ML:FL:GL:HL等舱位。则该命题可符号化为 。()()(,

2、)()(,)xyxyHyFx（4）设 是汽车； 是火车； 比 慢。则该命题可:L:WL:L符号化为 ()()(,)()()(,)xMyFxyxMyWxy2、 求公式 的主合取范式和主析取范式，并求使 取值为GPQRG真的所有指派。解： 的主析取范式：()()()()PQRPQRQ()()()P)()(R()(PQRPPQ)()()()G RPQR练习解答第 1 页（共 9 页）所以 的主合取范式为()G()()()()PQRPQRPQR使 取值为真的所有指派为： 1,0,0注意：若没有要求用等值演算，也可采用真值表求。三、逻辑推理题1、用演绎法证明：P（ QR） ， S P， Q, R S.（

3、应注明每一步推理所采用的推理规则） 。证明：（1） （假设，否定结论引入）()S（2） （1）置换，T 规则）（3） （前提，P 规则）（4） （2） ， （3）析取三段论，T 规则）P（5） （前提，P 规则）()QR（6） （4） ， （5）假言推理，T 规则）（7） （前提，P 规则）（8） （7） ， （6）假言推理，T 规则）R（9） （前提，P 规则）（10） （8） ， （9）合取，T 规则）所以 (),PQRSRS2、找出下列推导过程中的错误，并问结论是否有效？如果是，写出正确的推导过程。（1） 规则 （前提引入）)(xPxP（2） (1) )yQ（3） 规则 （前提引入）(（

4、4） (3) ) （5） (2),(4)假言推理(y（6） (5) )xQ练习解答第 2 页（共 9 页）解 该推导过程中由（3）推出结论（4）是错误的。这是因为第（2）步中已有变元出现，因此由第（3）步中应用 规则时,不能再引入变元 。 3 分yy结论 是有效的，其正确推导过程为：)(xQ（1） 规则PP（2） (1) y（3） 规则)(xx（4） (3) ) （5） (2),(4)假言推理(yQ（6） (5) )x3、有红、黄、绿、白四队参加足球联赛，如果红队第三，则当黄队不是第二时，绿队第四。或者白队不是第一，或者红队第三。已知绿队不是第四。试证明：如果白队第一，那么黄队第二。（要求：设

5、 ：白队第一； ：黄队第二； ：红队第三； ：绿队第四。并写出前PQRS提和结论的符号化及推理过程。 ）解 前提： (),RSP结论： 证明：（1） 附加前提引入（2） 前提引入 PR（3） （1） ， （2）析取三段论（4） 前提引入()QS（5） （3） ， （4）假言推理（6） 前提引入（7） （6） ， （5）拒取第二篇 集合论二、解答题1、设集合 ， 为 上的整除关系 ，试求：12,LARA（1）画出偏序集 的 Hasse 图；)(（2）写出 中的最大元、最小元、极大元、极小元；（3）写出 的子集 的上界、下界及上、下确界。9,63B练习解答第 3 页（共 9 页）解：（1） 的 H

6、asse 图如下：),(RA11179 631224 1058（2） 中没有最大元；最小元是 1；极小元也是 1；极大元有A7，8，9，10，11，12。（3） 没有上界，也就没有上确界；下界是 1；下确界也是 1。9,61B2、 （自然映射问题）习题八（P162）第 16 题。 （屈婉玲离散数学 ，下同）设 ，R 为 上的等价关系，且,AabcA,AabIU求自然映射 。:/g解：因为 ，所以,c， ，:/(),g()gc3、 （计数问题）习题六（P99）第 21，23 题。（1）某班有 25 个学生，其中 14 人会打篮球，12 人会打排球， 6 人会打篮球和排球，5 人会打篮球和网球，还

7、有 2 人会打这三种球。已知 6 个会打网球的人都会打蓝球或排球。求不会打球的人数。解：设 S 为该班学生集合，A、B 、C 分别表示会打篮球、排球和网球的学生集合，则据题设，有， ， ， ， ， ，25142B6AB5C2AB因为会打网球的人都会打蓝球或排球，因此有 U于是由包含排斥原理知或 CAC从而不会打球的人数为()()BSBABC5（2）使用包含排斥原理求不超过 120 的素数个数。解：因为11 2=121，故不超过120的合数至少含有2、3、5或7这些素因数之一。为此，设练习解答第4页（共9页）现在先要求出不能被这4个素数整除的数的个数。由于 ，且因此，不能被2、3、5及7整除的整

8、数有又因为 2、3、5 及 7 不满足上述条件，被“筛掉”，但它们是素数，而数 1 则相反。故不超过 120 的素数有个*4、 （特征函数问题）习题八（P162）第 14 题。设 S 为集合，A，B 是 S 的子集， 表示 T 的特征函数。若，,1,0,abcd,0,1,0,1Babcd，求 。ABI*5、设 ， ，则0,AS ，cardA 2 。,10SxZ1A2,3AxS3,5x47x160A2S20A32417A123I 1305I14087AI 238AI2453I 341057I12AI 124AI 134AI234I 12340II1234AII0(617)(20853)(42)0

9、5843A 上可定义 个二元关系。其中216n(2)cardA4 个自反关系， 4 个反自反关系， 8 个对称关系，12 个反对称关系， 2 个等价关系， 3 个偏序关系。练习解答第 5 页（共 9 页）注意：A 上的二元关系是 的一个子集，若 ，则 的子集有A2ncardA个。空关系即空集既是反自反的，也是对称的，还是反对称的。应掌握本例中每一类2n关系具体的有哪些。S 中有 个函数，其中 2 个是双射。24n*6、 （哈斯图问题） （P127 例 7.19）设集合 ， 为幂集 上的包含,AabcR()PA关系 ，试求：（1）画出偏序集 的 Hasse 图；(),PAR（2）写出 中的最大元

10、、最小元、极大元、极小元；()（3）写出 的子集 的上界、下界及上、下确界。,Bab*7、 （哈斯图问题） （P127 例 7.20）已知偏序集的哈斯图如下，求关系 R 的集合表示。三、证明题1、设 是非空集合 上的等价关系，试证 的逆关系 也是 上的等价关系。RAR1A证明 1） 具有自反性： ，因为 是 上的等价关系，具有自反性，有xA，从而 ，即 具有自反性。(,)x1(,)x12） 具有对称性： ，若 ，则 。因为 具有对1R,xy1(,)xyR(,)yxR称性，因此 ，从而 ，即 具有对称性。(,)xy1()R13） 具有传递性： ，若 ，则 。1,xyzA1(,)xyz(,)zyx

11、因为 具有传递性，因此 ，从而 ，即 具有传递性。R()1R所以 是 上的等价关系。1RA2、设 是非空集合 上的偏序关系，试证 的逆关系 也是 上的偏序关系。R1A练习解答第 6 页（共 9 页）证明 1） 具有自反性： ，因为 是 上的等价关系，具有自反性，有RxA，从而 ，即 具有自反性。(,)x1(,)x1R2） 具有反对称性： ，若 ，则 。1,xy1(,)xyR(,)yxR因为 具有反对称性，因此 ，即 也具有反对称性。R1R3） 具有传递性： ，若 ，则 。1,xyzA1(,)xyz(,)zyx因为 具有传递性，因此 ，从而 ，即 具有传递性。()1R所以 是 上的偏序关系。1R

12、A3、设（0，1）和0，1为实数区间，证明： (0,),提示：参考课本第 148 页例 8.9（5）的解答。第四篇 图论三、应用及证明题：1、 （哈米尔顿回路问题）习题十五（P306）第 15 题。某工厂生产由 6 种颜色的纱织成的双色布。已知在一批双色布中，每种颜色至少与其他 3 种颜色相搭配。证明可以从这批双色布中挑出 3 种，它们由不同颜色的纱织成。解：构造无向简单图 ，使,GVE126,vL其中 表示 6 种颜色之一，而(1,2)ivL, ijij ijEvVijv与由已知条件可知， ，有 ,()ijV()36ijdV于是根据无向简单图有哈密顿回路的判定定理， 为哈密顿图。设 为G12

13、61iiCvL中的一条哈密顿回路，任何两个顶点若在 C 中相邻，则在这批布中有这两个顶点代表的G颜色搭配成的双色布。于是，在这批布中有 与 ， 与 以及 与 搭配成的 3 种1iv2i3i4iv5i6iv双色布，它们使用了全部 6 种颜色。练习解答第 7 页（共 9 页）*2、 （最短路问题）习题十五（P307）第 22 题。某工厂使用一台设备，每年年初要决定是继续使用，还是购买新的。预计该设备第一年的价格为 11 万元，以后每年涨 1 万元。使用的第 1 年，第 2 年，第 5 年的维修费分别为 5，6，8，11，18 万元。使用 1 年后的残值为 4 万元，以后每使用 1 年残值减少 1 万元。试制定购买维修该设备的 5 年计划，使总支出最小。解：第 年初购买使用到第 年初（或第 年末）所需的总费用（购买费+维修费-ijj残值）如下表；i 2 3 4 5 61234512 19 28 40 5913 20 29 4114 21 3015 2216根据上表构造有向带权图 G，其中顶点 表示第 年初（或第 年末） ， 到ivi1iiv的边表示在第 年初购买设备使用到第 年末，其权为所需的总费用。()jvii 1jj19594012 13 14 15 16v1 v2 v3 v4 v5 v620