天津理工大学离散数学(魏雪丽版)检测题目解析

天津理工大学《离散数学》第一章检测题答案

一、填空题（每空2分，共30分）

1．PQ 2．PQ 3．→，，∧， 。 ，  ，，  ， c4．(PQR)(PQR)(PQR)，

(PQR)(PQR)(PQR)(PQR)(PQR)

5．(PQ)(P(RS)) 6．QP 7．(PQ)(QP)

二、单项选择题（每小题2分，共20分）

1 D

2 B 3 C 4 B 5 C 6 D 7 A 8 A 9 C 10 B 得分 三、简答题（每小题6分，共12分）

1．构造命题公式P(QR)的真值表．

P0 0 0 0 1 1 1 1

Q0 0 1 1 0 0 1 1 R0 1 0 1 0 1 0 1 QR1 1 0 1 1 1 0 1 P(QR)1 1 0 1 1 1 1 1 2．求命题公式 ((PQ)R)P的主析取范式和主合取范式。

((PQ)R)P((PQ)R)P1分((PQ)R)P1分(PR)(QR)PP(QR)

.

(P(QQ)(RR))((PP)(QR))1分(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)1分(PQR)(PQR)(PQR)(PQR)(PQR)

m2m4m5m6m7(这是主析取范式))1分M0M1M3(这是主合取范式)(PQR)(PQR)(PQR)1分3．判断命题公式 (PQ)(PR)与 (PQR)是否等价。 解：A(PQ)(PR)(PQ)(PR)

BP(QR)P(QR)(PQ)(PR)

等价

四．证明题（共32分）

１．（10分）用CP规则证明P(QR),Q(RS),PQS；

1. P P 6. (RS) T(4,5) I （2分） 2. P(QR) P 7. R T(3,4) I（2分） 3. QR T(1, 2) I （2分） 8. S T(6,7) I（2分） 4. Q P(附加前提) 9. (QS) CP （2分） 5. Q(RS) P

２．（10分）用归谬法证明 AB,(CB),CSA．

证: 1

A P(附加前提) （1分） 2 AB P

3 B T1,2I （2分） 4 CB P 5 C T3,4I （2分） 6 CS P 7 C T6I （2分） 8 CC T5,7I （2

.

分）

由8得出了矛盾，根据归谬法说明原推理正确（1分）

3．（12分）公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下： （1）营业员A或B盗窃了钻石项链 （2）若B作案，则作案时间不在营业时间 （3）若A提供的证词正确，则货柜未上锁

（4）若A提供的证词不正确，则作案发生在营业时间 （5）货柜上了锁

试问：作案者是谁？要求写出推理过程。

解：令A表示“营业员A盗窃了钻石项链”； B表示“营业员B盗窃了钻石项链”；

；Q表示“A提供的证词正确”；R表示“货P表示“作案时间在营业时间”柜上了锁”。

则侦察结果如下：

（4分） AB， BP，QR，QP，R．由此可推出作案者是A．

推理过程如下：

(1) R P (6) BP P

(2) QR P (7) B T(5)，(6) I（2分）

(3) Q T(1)，(2) I（2分） (8) AB P

(4) QP P (9) A T(7)，(8) I（2分）

.

(5) P T(3)，(4) I（2分）

天津理工大学《离散数学》第二章检测题答案

一、填空题（每空3分，共30分）

1．(x)(G(x)F(x))(x)(F(x)G(x)) 或(x)(G(x)F(x))(y)(F(y)G(y))

2．(x)(z)(w)[(P(x)R(x,w))(Q(z,y)R(x,w))] 3．P(a)P(b)P(c)(Q(a)Q(b)Q(c))

4．(P(a)P(b)P(c))(P(a)P(b)P(c)) 5．P(x),(x)(y)P(x,y) 6．（x,y；y） 7．(P(x)yR(x,y)) 8．(x)(F(x)G(x))

二、单项选择题（每小题2分，共20分）

1 A

2 A 3 B 4 D 5 C 6 A 7 C 8 C 9 B 10 D 得分 三、 简答题（每小题6分，共12分）

1．求謂词公式(x)(P(x)Q(x,y))((y)P(y)(z)Q(y,z))的前束析取范式．

(x)(P(x)Q(x,y))((y)P(y)(z)Q(y,z))

(x)(P(x)Q(x,y))((y)P(y)(z)Q(y,z))x(P(x)Q(x,y))((y)P(y)(z)Q(y,z))

x(P(x)Q(x,y))((u)P(u)(z)Q(y,z))(x)(u)(z)[(P(x)Q(x,y))(P(u)Q(y,z))]2．证明：x(P(x)Q(x))xP(x)xQ(x)

.

证：

左式x(P(x)Q(x))x(P(x)Q(x))x(P(x))xQ(x)xP(x)xQ(x)xP(x)xQ(x))

四．证明题（共38分）

1．（12分）用谓词演算的推理规则证明:

x(P(x)Q(x))，x(Q(x)R(x)S(x))，P(a)R(a)S(a)

（1）x(P(x)Q(x)) P （2）P(a)Q(a) US(1) （2分） （3）P(a)R(a) P （4）Q(a) T(2)(3)I （2分） （5）x(Q(x)R(x)S(x)) P

（6）Q(a)R(a)S(a) US(5) （2分） （7）R(a) T(3) I （2分） （8）Q(a)R(a) T(4)(7)I （2分） （9）S(a) T(6)(8)I （2分） 2．(10分) 指出下面推理证明过程中的错误，并给出正确的证明．

用谓词演算的推理规则证明：

x(Q(x)R(x))x(Q(x)Z(x))x(R(x)Z(x))

证:：(1) x(Q(x)R(x)) P (6) Z(a) T(4) I (2) Q(a)R(a) US(1) (7) R(a) T(2),(5) I (3) x(Q(x)Z(x)) P (8) R(a)Z(a) T(6),(7) I (4) Q(a)Z(a) ES(3) (9) x(R(x)Z(x)) EG(8)

.

(5) Q(a) T(4) I

该证明的错误在于: (1)、 (2) 与 (3)、 (4) 的顺序颠倒了，应该先指定存在后指定全称。 （2分）正确的证明是：（4分）

(1) x(Q(x)Z(x)) P (6) Z(a) T(2) I （1分） (2) Q(a)Z(a) ES (1) （2分） (7) R(a) T(4),(5) I （1分） (3) x(Q(x)R(x)) P (8) R(a)Z(a) T(6),(7) I （1分） (4) Q(a)R(a) US (3) （2分） (9) x(R(x)Z(x)) EG(8) （1分）

(5) Q(a) T(2) I

3．（16分）符号化下列命题并推证其结论．

任何人如果他喜欢音乐,他就不喜欢体育．每个人或者喜欢体育，或者喜欢美术．有的人不喜欢美术．因而有的人不喜欢音乐．（设M(x)：x喜欢音乐，S(x)：x喜欢体育，Ａ(x)：ｘ喜欢美术．） 该推理符号化为：

(x(M(x)S(x))x(S(x)A(x))xA(x))(xM(x)) 或 前提：x(M(x)S(x)),x(S(x)A(x)),xA(x)

结论：xM(x) （4分）证：

（1）xA(x) P （2）A(a) ES（1） （2分） （3）x(S(x)A(x)) P （4）S(a)A(a) US（3） （2分）（5）S(a) T（2）（4）I（2分） （6）x(M(x)S(x)) P

（7）M(a)S(a) US（6）（2分） （8）S(a)M(a) T（7）E （1分）

.

（9）M(a) T（5）（8）I（2分） （10）xM(x) EG（9） （1分）

天津理工大学《离散数学》第三、四章检测题答案

一、填空题（每空2分，共40分）

1． n2 ２．{{,{}},,{,{}},{}} 3．

n {,{{a,{b,c}}}}

00或单位矩阵 14．反对称，传递。 5．R10011iR；R 6． IA，i1007． 4,6 ， 2,3 ， 无 ， 无 ， 12 ， 1 。 8． f1{,0,{},1}, f2{,1,{},0}。 9．单射，满射；既是单射又是满射； IB； IA

二、单项选择题（每小题2分，共20分）

1 (1) 2 (2) 3 (1) 4 (3) 5 6 7 (1) 8 (3) 9 (3) 10 (1) 得分 （2） （2） 三、简答题（共30分）

1．（6分）设A={1,2,3,5,6,10,15,30} ， “／” 为集合A上的整除关系。〈A，／〉是否

为偏序集? 若是，画出其哈斯图；

解：〈A，／〉是偏序集。其哈斯图为：

.

2．（12分）对下图所给的偏序集A,，求下表所列集合的上（下）界，上（下）确界，并将结果填入表中。

子 集 上 界 下 界 上 确 界 下 确 界 {a,b,c} a d 无 无 a c a d 无 无 {c,d,e} a,c a A

3．（6分）设 A={1,2,3,4,5,6}，集合A上的关系

R={〈1,3〉,〈1,5〉,〈2,5〉,〈4,4〉,〈4,5〉,〈5,4〉,〈6,3〉,〈6,6〉}。

（1）画出R的关系图，并求它的关系矩阵； （2）求r(R),S(R)及 t(R)。 解：（1）R的关系图为

R的关系矩阵为

000MR000010100001000000 （2分）

001100010001001

.

（2）r(R)R{1,1,2,2,3,3,5,5}， （1分） S(R)R{3,1,5,1,5,2,3,6} （1分） t(R)R{1,4,2,4,5,5} （2分）

4．设Z是整数集，R是Z上的模3同余关系，即R{x,yx,yZ,xy(mod3)}，试根据等价关系R决定Z的一个划分 。

答案：由R决定的Z的划分为：{0R,1R,2R}， 其中：

0R{,9,6,3,0,3,6,9,} 1R{,8,5,2,1,4,7,}

2R{,7,4,1,2,5,8,}

四．证明题（共10分）

１．设a,bR,ab, 定义f:[a,b][0,1]为 f(x)其逆映射。

证：1）先证明f是入射（2分）

对任意的x1,x2a,b,若f(x1)f(x2),则有故f是入射。

2) 再证明f是满射（2分）

对任意的y0,1,都存在x(ba)yaa,b,使得f(x)y,从而f是满射。 综合（1）、（2）知f是双射。 f1xa，证明：f是双射，并求出bax1ax2a，从而有x1x2，baba:[0,1][a,b]为 f1(x)(ba)xa，对任意x0,1。（1分）

天津理工大学《离散数学》第五章检测题答案

.

一、填空题（每空2分，共30分）

1. ba 2．a 3．,S,S, 4．a；1 5．S关于运算不封闭

116． 2，a14a 7循环群，生成元 8．

 1 2 11 1 21 2 9．B关于封闭

二、单项选择题（每小题2分，共20分）

1 B 2 C 3 A 4 A 5 B 6 D 7 D 8 C 9 B 10 D 得分 三、简答题（共30分）

1．设是实数集R上的二元运算，其定义如下：

abab2ab

（1）求23， 3(-5)和71/2 。 （2）

R,是半群吗？可交换吗？

（3）求R中关于的单位元。

（4）R中哪些元素有逆元素，其逆元素是什么？ 答案：（1）17，-32，14.5 。 2）

R,是半群，可交换。 （3）0。

1（4）当aR,a1/2时，a有逆元素，aa/(12a)。

2．设A{a,b,c,d}，A,是交换群，a是A,的单位元。的运算表如下：

 a b c d

ab cda b c d b a x1 x2 c x4 a x3 d x5 x6 a .

求x1,x2,x3,x4,x5,x6，并说明道理。

答案：x1d,x2c,x3b,x4d,x5c,x6b。因为有限群的运算表中的每行、每列都是群中元素的一个置换。

3．设集合G{1,3,4,5,9}，是定义在G上的模11乘法（即任意a,b∈G，有

a*b=(a×b)(mod11)，×是普通乘法），问G,是循环群吗？若是，试找出它的生成元。

答： G,的运算表如下表所示。

 9 1 3 4 5 9 3 9 1 4 1 5 3 4 1 5 9 4 3 5 5 4 9 3 9 1 9 5 3 1 4 1 3 4 5

从运算表可知，在G上封闭、有幺元1，且135,331,434,533,932，再由是可结合的得G,是循环群，3，4，5和9均为其生成元。

.

四．证明题（共20分）

１．（4分）设

G,是独异点，e为其幺元，且对aG，有aae，证明

G,是一个交换群。

证明： 对aG，由于aae，则 a素,故

1a， 即G中的每一个元素a都有逆元

G,是一个群。

又对a,bG，有

aba1b1(ba)1ba，

所以

G,是一个Abel群。

２．（6分）设G,是一个群，aG，f:GG，xG，有

f(x)axa1

试证明f是G,一个自同构． 证：首先证明f是入射。（3分）

对x1,x2G,若f(x1)f(x2),则有ax1a1ax2a1,该式两边同时左乘a及右乘a,得x1x2,故f为入射f.其次证明f是满射。

1

对yG,都存在xayaG,使得yf(x),因此f是满射. 综合以上两点，知f是双射。（3分）

1最后,对x1,x2G,都有f(x1x2)ax1x2a1(ax1a1)(ax2a1)f(x1)f(x2),从而f是G到G的自同构.

天津理工大学《离散数学》第六章检测题答案

一、填空题（每空2分，共40分）

1. 上确界 和下确界，a，b 2．至少有一个补元素，不一定 3．0，1；1，

.

0

4．aa1,aa0 5．ab；ab 6． AAn，A2n

二、单项选择题（每小题2分，共20分）

1 D 2 C 3 B 4 C 5 A 6 D 7 A 8 B 9 D 10 D 得分 三、简答题（共30分）

1．下面哈斯图表示的格中哪个元素无补元？对有补元的元素求出它们的补元． 解：c无补元（1分），a的补元为e（1分），b的补元为d（1分），d的补元为b、e（1分），e的补元为a、d（1分），0与1互为补元。（1分）

2．设B,,,,0,1是一个布尔代数且B{0,a,b,1}，求布尔表达式

f(x1,x2,x3)(ax1x2)(x1(x3b))

1a)的值。 的析取范式和合取范式并计算f(b,,解：f(x1,x2,x3)的析取范式为：

(x1x2x3)(x1x2x3)(x1x2x3)(bx1x2x3)（4分）

f(x1,x2,x3)的合取范式为：

(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(bx1x2x3)（4分）

f(b,,1a)b（2分）

3．设A={1,2,3,5,6,10,15,30} ， “／” 为集合A上的整除关系。 (1)．〈A，／〉是否为偏序集? 若是，画出其哈斯图； (2)．〈A，／〉是否构成格？为什么？ (3)．〈A，／〉是否构成布尔代数？为什么？ 解：(1)．〈A，／〉是偏序集。 其哈斯图为：

.

(2)．〈A，／〉构成格。因为其任意两个元素都有上确界和下确界。 (3)．〈A，／〉构成布尔代数。因为它是有界分配格，且其任意 元素都有唯一补元素。

四．证明题（共10分） １．（4分）设

G,是独异点，e为其幺元，且对aG，有aae，证明

G,是一个交换群。

证明： 对aG，由于aae，则 a1a， 即G中的每一个元素a都有逆元素,故

G,是一个群。

又对a,bG，有

aba1b1(ba)1ba，

所以

G,是一个Abel群。

２．（6分）设G,是一个群，aG，f:GG，xG，有

f(x)axa1

试证明f是G,一个自同构． 证：首先证明f是入射。（3分）

对x1,x2G,若f(x1)f(x2),则有ax1a1ax2a1,该式两边同时左乘a及右乘a,得x1x2,故f为入射f.其次证明f是满射。

1

对yG,都存在xayaG,使得yf(x),因此f是满射. 综合以上两点，知f是双射。（3分）

1最后,对x1,x2G,都有f(x1x2)ax1x2a1(ax1a1)(ax2a1)f(x1)f(x2),从而f是G到G的自同构.

.

离散数学第七章检测题答案

一、 单项选择题（每小题2分，共20分）

1 2 2 4 3 2 4 4 5 3

6 2 7 4 8 2 9 1 10 3 得分 二、 填空题（每空3分，共45分）

1． 4 ， 3 。 2． __0___， _1__。 __0___， __0___。 3．(V2V1,V2V1 4． 2 │E│ ， 偶数 。5．___5__； __9___。 6． 3 ， 1 。7． 7 。

三、 简答题（每小题5分，共25分）

1．对有向图GV,E求解下列问题： （1）写出邻接矩阵A；

（2）GV,E中长度为3的不同的路有几条？其中不同的回路有几条？

解：（1）邻接矩阵为：

.

00A010100101000001，

1000001001101100000130010,A11110100100001001010000

111101002（2）A001则，GV,E中长度为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个人，将相互认识的人之间连一条线，便得到一个 无向简单图GV,E，每个结点viV的度数是与vi认识的人的数目，由题意知

vi,vjV，有deg(vi)deg(vj)20，于是GV,E中存在哈密尔顿回路，设Cvi1vi2vi20vi1是GV,E中的一条哈密尔顿回路，按此回路安排园桌座位即符合要

求。（4分）

四．证明与应用题（10分）

1． 某次聚会的成员到会后相互握手，试用图论的知识说明与奇数个人握手的人数一定是

一个偶数。

证: 用结点代表成员, 握手的成员之间连一条线, 则所有聚会的成员之间的握手

情况可以用一个图来表示，其中每个结点的度数就是该结点所代表的成员握

.

手的人数,由于任一图中奇数度结点的个数为偶数,所以与奇数个人握手的人数一定是一个偶数。