天津理工大学《离散数学》第一章检测题答案一、填空题（每空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分）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）货柜上了锁试问：作案者是谁？要求写出推理过程。
解：令表示“营业员盗窃了钻石项链”； 表示“营业员盗窃了钻石项链”；表示“作案时间在营业时间”；表示“提供的证词正确”；表示“货柜上了锁”则侦察结果如下：， ，，，．由此可推出作案者是．（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．或2．3．4． 5． 6．（；） 7． 8．二、单项选择题（每小题2分，共20分） 12345678910得分AABDCACCBD三、 简答题（每小题6分，共12分）1．求謂词公式的前束析取范式． 2．证明：证：四．证明题（共38分） 1．（12分）用谓词演算的推理规则证明:，，（1） （2） （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分） (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 （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．（12分）对下图所给的偏序集，求下表所列集合的上（下）界，上（下）确界，并将结果填入表中子 集上 界下 界上 确 界下 确 界 无无无无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分） 对任意的则有，从而有，故是入射 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 2）是半群，可交换 （3）0 （4）当时，有逆元素，2．设，是交换群，是的单位元的运算表如下： 求，并说明道理。
答案：因为有限群的运算表中的每行、每列都是群中元素的一个置换3．设集合，是定义在上的模11乘法（即任意a,b∈G，有a*b=(a×b)(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分）设是独异点，为其幺元，且对，有，证明是一个交换群证明： 对，由于，则 ， 即中的每一个元素都有逆元素,故是一个群又对，有，所以是一个Abel群２．（6分）设是一个群，，，，有试证明是一个自同构．证：首先证明是入射3分）其次证明是满射对 综合以上两点，知是双射3分） 天津理工大学《离散数学》第六章检测题答案一、填空题（每空2分，共40分）1. 上确界 和下确界，， 2．至少有一个补元素，不一定 3．0，1；1，0 4． 5．； 6． ， 二、单项选择题（每小题2分，共20分） 12345678910得分D CB CADABDD三、简答题（共30分）1．下面哈斯图表示的格中哪个元素无补元？对有补元的元素求出它们的补元．解：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)．〈，／〉构成布尔代数因为它是有界分配格，且其任意元素都有唯一补元素 四．证明题（共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 三、 简答题（每小题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为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?输油管道总长度越短，士兵越好防守求他们看守的最短管道的长度要求写出求解过程)解：为保证每个城市石油的正常供应最少需5连士兵看守.求看守的最短管道相当于求图的最小生成树问题，此图的最小生成树为： 因此看守的最短管道的长度为： Ｗ（Ｔ）＝１＋1＋2＋2＋2＝８．4．以给定权1, 4, 9, 16, 25, 36, 49, 64, 81, 100构造一棵最优二叉树。
5．一次学术会议的理事会共有20个人参加，他们之间有的相互认识，但有的相互不认识但对任意两个人，他们各自认识的人的数目之和不小于20，说明能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什么？解：可以把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人1分）根据是：分别用20个结点代表这20个人，将相互认识的人之间连一条线，便得到一个无向简单图，每个结点的度数是与认识的人的数目，由题意知，有，于是中存在哈密尔顿回路，设是中的一条哈密尔顿回路，按此回路安排园桌座位即符合要求4分）四．证明与应用题（10分）1． 某次聚会的成员到会后相互握手，试用图论的知识说明与奇数个人握手的人数一定是一个偶数证: 用结点代表成员, 握手的成员之间连一条线, 则所有聚会的成员之间的握手情况可以用一个图来表示，其中每个结点的度数就是该结点所代表的成员握手的人数,由于任一图中奇数度结点的个数为偶数,所以与奇数个人握手的人数一定是一个偶数 15 -。