天津理工大学《离散数学》第一章检测题答案
一、填空题（每空2分，共30分）
1． 2．
3．→，
，∧，
，
，
，
，
。
4．，
5． 6．
7．
二、单项选择题（每小题2分，共20分）
三、简答题（每小题6分，共12分）
1．构造命题公式的真值表．
2．求命题公式的主析取范式和主合取范式。
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分）
三、 简答题（每小题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分）
三、简答题（共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分）
三、简答题（共30分）
1．设是实数集
上的二元运算，其定义如下：
（1）求23， 3
(-5)和7
1/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和9均为其生成元。
四．证明题（共20分）
１．（4分）设是独异点，
为其幺元，且对
，有
，证明
是一个交换群。
证明： 对，由于
，则
， 即
中的每一个元素
都有逆元素,故
是一个群。
又对，有
，
所以是一个Abel群。
２．（6分）设是一个群，
，
，
，有
试证明是
一个自同构．
证：首先证明是入射。（3分）
其次证明是满射。
对
综合以上两点，知是双射。（3分）
天津理工大学《离散数学》第六章检测题答案
一、填空题（每空2分，共40分）
1. 上确界 和下确界，，
2．至少有一个补元素，不一定 3．0，1；1，0
4． 5．
；
6．
，
二、单项选择题（每小题2分，共20分）
三、简答题（共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分）
二、 填空题（每空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． 某次聚会的成员到会后相互握手，试用图论的知识说明与奇数个人握手的人数一定是一个偶数。
证: 用结点代表成员, 握手的成员之间连一条线, 则所有聚会的成员之间的握手情况可以用一个图来表示，其中每个结点的度数就是该结点所代表的成员握手的人数,由于任一图中奇数度结点的个数为偶数,所以与奇数个人握手的人数一定是一个偶数。
本文来源：https://www.2haoxitong.net/k/doc/1081d5cafad6195f302ba64b.html
文档为doc格式