天津理工大学离散数学魏雪丽版检测题答案.doc

《天津理工大学离散数学魏雪丽版检测题答案.doc》由会员分享，可在线阅读，更多相关《天津理工大学离散数学魏雪丽版检测题答案.doc（16页珍藏版）》请在装配图网上搜索。

1、 .天津理工大学离散数学第一章检测题答案一、填空题（每空2分，共30分）1 2 3， ， ， 。4，5 6 7二、单项选择题（每小题2分，共20分） 12345678910得分DBCBCDAACB三、简答题（每小题6分，共12分）1构造命题公式的真值表 00011001110100001111100111011111001111112求命题公式的主析取范式和主合取范式。3判断命题公式与 是否等价。解：等价四证明题（共32分） （10分）用CP规则证明；1. P 6. T(4,5) I （2分）2. P 7. T(3,4) I（2分） 3. T(1, 2) I （2分） 8. T(6,7) I（

2、2分）4. P(附加前提) 9. CP （2分）5. P （10分）用归谬法证明 证: 1 （1分） 2 3 （2分） 4 5 （2分） 6 7 （2分） 8 （2分）由8得出了矛盾，根据归谬法说明原推理正确（1分）3（12分）公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下：（1）营业员或盗窃了钻石项链（2）若作案，则作案时间不在营业时间（3）若提供的证词正确，则货柜未上锁（4）若提供的证词不正确，则作案发生在营业时间（5）货柜上了锁试问：作案者是谁？要求写出推理过程。解：令表示“营业员盗窃了钻石项链”； 表示“营业员盗窃了钻石项链”；表示“作案时间在营业时间”；表示“提供的证词正

3、确”；表示“货柜上了锁”。则侦察结果如下：， ，由此可推出作案者是（4分）推理过程如下：(1) (6) (2) (7) (5)，(6) （2分）(3) (1)，(2) （2分） (8) (4) (9) (7)，(8) （2分）(5) (3)，(4) （2分）天津理工大学离散数学第二章检测题答案一、填空题（每空3分，共30分）1或234 5 6（；） 7 8二、单项选择题（每小题2分，共20分） 12345678910得分AABDCACCBD三、 简答题（每小题6分，共12分）1求謂词公式的前束析取范式 2证明：证：四证明题（共38分） 1（12分）用谓词演算的推理规则证明:，（1） （2） （

4、2分）（3） （4） I （2分）（5） （6） （2分）（7） I （2分）（8） I （2分）（9） I （2分）2(10分) 指出下面推理证明过程中的错误，并给出正确的证明用谓词演算的推理规则证明：证:：(1) P (6) T(4) I (2) US(1) (7) T(2),(5) I (3) P (8) T(6),(7) I (4) ES(3) (9) EG(8) (5) T(4) I该证明的错误在于: (1)、 (2) 与 (3)、 (4) 的顺序颠倒了，应该先指定存在后指定全称。 （2分）正确的证明是：（4分）(1) P (6) T(2) I （1分）(2) ES (1) （2分）

5、 (7) T(4),(5) I （1分）(3) P (8) T(6),(7) I （1分）(4) US (3) （2分） (9) EG(8) （1分）(5) T(2) I 3（16分）符号化下列命题并推证其结论任何人如果他喜欢音乐,他就不喜欢体育每个人或者喜欢体育，或者喜欢美术有的人不喜欢美术因而有的人不喜欢音乐（设M(x)：x喜欢音乐，S(x)：x喜欢体育，(x)：喜欢美术）该推理符号化为： 或前提：结论： （4分）证：（1） P （2） ES（1） （2分）（3） P （4） US（3） （2分）（5） T（2）（4）I（2分） （6） P（7） US（6）（2分） （8） T（7）E （

6、1分）（9） T（5）（8）I（2分） （10） EG（9） （1分）天津理工大学离散数学第三、四章检测题答案一、填空题（每空2分，共40分）1 3 4反对称，传递。 5； 6 ，或单位矩阵7 4,6 ， 2,3 ， 无 ， 无 ， 12 ， 1 。8 , 。9单射，满射；既是单射又是满射； ； 二、单项选择题（每小题2分，共20分） 12345678910得分(1)(2)(1)(3)（2）（2）(1)(3)(3)(1)三、简答题（共30分）1（6分）设=1,2,3,5,6,10,15,30 ， “” 为集合上的整除关系。，是否为偏序集? 若是，画出其哈斯图；解：，是偏序集。其哈斯图为：2（1

7、2分）对下图所给的偏序集，求下表所列集合的上（下）界，上（下）确界，并将结果填入表中。子 集上 界下 界上 确 界下 确 界 无无无无3（6分）设 =1,2,3,4,5,6，集合上的关系=1,3,1,5,2,5,4,4,4,5,5,4,6,3,6,6。（1）画出的关系图，并求它的关系矩阵；（2）求及 。解：（1）的关系图为的关系矩阵为 （2分）（2）， （1分） （1分） （2分）4设Z是整数集，是Z上的模3同余关系，即，试根据等价关系决定Z的一个划分 。答案：由决定的Z的划分为：， 其中： 四证明题（共10分） 设 定义为 ，证明：是双射，并求出其逆映射。证：1）先证明是入射（2分） 对任意

8、的则有，从而有，故是入射。 2) 再证明是满射（2分）对任意的从而是满射。 综合（1）、（2）知是双射。 为 ，对任意。（1分）天津理工大学离散数学第五章检测题答案一、填空题（每空2分，共30分）1. 2 3 4；1 5关于运算不封闭 6 2， 7循环群，生成元 8 9关于封闭二、单项选择题（每小题2分，共20分） 12345678910得分BCAABDDCBD三、简答题（共30分）1设是实数集上的二元运算，其定义如下： （1）求23， 3(-5)和71/2 。 （2）是半群吗？可交换吗？ （3）求中关于的单位元。 （4）中哪些元素有逆元素，其逆元素是什么？答案：（1）17，-32，14.5

9、。 2）是半群，可交换。 （3）0。 （4）当时，有逆元素，。2设，是交换群，是的单位元。的运算表如下： 求，并说明道理。答案：。因为有限群的运算表中的每行、每列都是群中元素的一个置换。3设集合，是定义在上的模11乘法（即任意a,bG，有a*b=(ab)(mod11)，是普通乘法），问是循环群吗？若是，试找出它的生成元。答： 的运算表如下表所示。 1 3 4 5 913459 1 3 4 5 93 9 1 4 54 1 5 9 35 4 9 3 19 5 3 1 4从运算表可知，在上封闭、有幺元1，且，再由是可结合的得是循环群，3，4，5和9均为其生成元。四证明题（共20分） （4分）设是独异

10、点，为其幺元，且对，有，证明是一个交换群。证明： 对，由于，则 ， 即中的每一个元素都有逆元素,故是一个群。又对，有，所以是一个Abel群。（6分）设是一个群，有试证明是一个自同构证：首先证明是入射。（3分）其次证明是满射。对 综合以上两点，知是双射。（3分） 天津理工大学离散数学第六章检测题答案一、填空题（每空2分，共40分）1. 上确界 和下确界， 2至少有一个补元素，不一定 30，1；1，0 4 5； 6 ， 二、单项选择题（每小题2分，共20分） 12345678910得分D CB CADABDD三、简答题（共30分）1下面哈斯图表示的格中哪个元素无补元？对有补元的元素求出它们的补元解

11、：c无补元（1分），a的补元为e（1分），b的补元为d（1分），d的补元为b、e（1分），e的补元为a、d（1分），0与1互为补元。（1分）2设是一个布尔代数且，求布尔表达式的析取范式和合取范式并计算的值。解：的析取范式为： （4分）的合取范式为：（4分）（2分）3设=1,2,3,5,6,10,15,30 ， “” 为集合上的整除关系。(1)，是否为偏序集? 若是，画出其哈斯图；(2)，是否构成格？为什么？(3)，是否构成布尔代数？为什么？解：(1)，是偏序集。 其哈斯图为：(2)，构成格。因为其任意两个元素都有上确界和下确界。(3)，构成布尔代数。因为它是有界分配格，且其任意元素都有唯一补元

12、素。 四证明题（共10分） （4分）设是独异点，为其幺元，且对，有，证明是一个交换群。证明： 对，由于，则 ， 即中的每一个元素都有逆元素,故是一个群。又对，有，所以是一个Abel群。（6分）设是一个群，有试证明是一个自同构证：首先证明是入射。（3分）其次证明是满射。对 综合以上两点，知是双射。（3分）离散数学第七章检测题答案一、 单项选择题（每小题2分，共20分） 12345678910得分2424324213二、 填空题（每空3分，共45分）1 4 ， 3 。 2 _0_， _1_。 _0_， _0_。3( 4 2 E ， 偶数 。5_5_； _9_。6 3 ， 1 。7 7 。 三、 简

13、答题（每小题5分，共25分）1对有向图求解下列问题： （1）写出邻接矩阵； （2）中长度为3的不同的路有几条？其中不同的回路有几条？ 解：（1）邻接矩阵为：，（2）则，中长度为3的不同的路有10条，其中有1条不同的回路。2设有盏灯，拟公用一个电源，求至少需要插头的接线板的数目。解：设至少需要4插头的接线板i个，则有 （4-1）i=28-1 （3分）故 i=9即至少需要9个4插头的接线板。 （2分）3设有6个城市V1，V2，V6，它们之间有输油管连通，其布置如下图,Si(数字)中Si为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城

14、市石油的正常供应最少需多少连士兵看守?输油管道总长度越短，士兵越好防守。求他们看守的最短管道的长度。(要求写出求解过程)解：为保证每个城市石油的正常供应最少需5连士兵看守.求看守的最短管道相当于求图的最小生成树问题，此图的最小生成树为：因此看守的最短管道的长度为：（）12224以给定权1, 4, 9, 16, 25, 36, 49, 64, 81, 100构造一棵最优二叉树。5一次学术会议的理事会共有20个人参加，他们之间有的相互认识，但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20，说明能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什么？解：可以把

15、这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人。（1分）根据是：分别用20个结点代表这20个人，将相互认识的人之间连一条线，便得到一个无向简单图，每个结点的度数是与认识的人的数目，由题意知，有，于是中存在哈密尔顿回路，设是中的一条哈密尔顿回路，按此回路安排园桌座位即符合要求。（4分）四证明与应用题（10分）1 某次聚会的成员到会后相互握手，试用图论的知识说明与奇数个人握手的人数一定是一个偶数。证: 用结点代表成员, 握手的成员之间连一条线, 则所有聚会的成员之间的握手情况可以用一个图来表示，其中每个结点的度数就是该结点所代表的成员握手的人数,由于任一图中奇数度结点的个数为偶数,所以与奇数个人握手的人数一定是一个偶数。w