天津理工大学离散数学(魏雪丽版)检测题答案汇总

1、-1-天津理工大学离散数学第一章检测题答案、填空题（每空 2 分，共 30 分）4.(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 -P7.(P -Q)(Q -P)、单项选择题（每小题 2 分，共 20 分）12345678910得分DnBCBnCDAACB二、简答题（每小题 6 分，共 12 分）1.构造命题公式P （Q R）的真值表.PQRQTRPM(QTR)00011001110100001111100111011111001111112.求命题公式(P Q)；R)；P

2、的主析取范式和主合取范式。(P Q) R)P= -(一(P Q) R) P 1 分二(P Q) R) P 1 分 二(P一 R) (Q 一 R)P= P (Q 一 R)=(P(QQ)(RR) (P一卩)(QR) 1 分(P Q R) (P_Q R) (P Q_R) (P_Q_R)(P Q R)(-卩Q R) 1 分二（P Q R） （P_Q R） （P Q R） （P_Q_R）（一P Q -R）：=m2m4m5m6m7（这是主析取范式）1 分1 .PQ2 .- P r Q-2-二 M0M,M3（这是主合取范式）二（P Q R） （P Q R） （P Q R） 1 分3.判断命题公式（PQ） （

3、P R）与（PQ R）是否等价。 解：A=（P Q） （PR）= （-P Q）（一P R）B=P （Q R）二-P （Q R）二（一P Q）（一P R）等价四.证明题（共 32 分）1.（10 分）用 CP 规则证明 一P （-Q R）,Q （RS）, P= Q S；1.PP6.（R S）T（4,5）I（2分）2._P（一Q R）P7.RT（3,4）I（2 分）3.-QRT（1,2） I （2 分）8.ST（6,7）I（2 分）4.QP（附加前提）9.（Q S）CP （2 分）5.Q （R S）P2.（10分）用归谬法证明ATB （C yB）, C_S二TA证: :1AP（附加前提）（1 分）

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

5、R表示 货柜上 了锁”。则侦察结果如下：A B，B P，Q -R，-Q P，R由此可推出作案者是A. (4 分) 推理过程如下：(1)RPB -P PQ _RP(7)-BT(5)，(6)I(2 分)-QT，(2)I(2 分)(8)A BPQ；PP(9)AT(7) ,(8)I(2 分)PT(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

6、.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)&( x)(_F(x)_G(x)、单项选择题(每小题 2 分，共 20 分)12345678910得分A nABD nCACCBD二、 简答题(每小题 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)-4-二(-x)

7、(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.证明：Tx(P(x)r Q(x)：= -xP(x)- _xQ(x)证：左式二.x(P(x) Q(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)

8、 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)l（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 分）指出下面推理证明过程中的错误，并给出正确的证明. 用谓词演算的推理规则证明：-5-x(Q(x)R(x)八二X(Q(x) Z(x)= x(R(x) Z(x)该证明的错误在于

9、：、与、的顺序颠倒了，应该先指定存在后 指定全称。(2 分)正确的证明是：(4 分)(1)x(Q(x) Z(x)P(6)Z(a)T(2) I(1 分)Q(a) Z(a)ES (1)(2 分)R(a)T(4), (5) I(1 分)-x(Q(x)r R(x)P(8)R(a) Z(a)T(6)， I(1 分)Q(a) R(a)US (3)(2 分)(9)x(R(x) Z(x)EG(8)(1 分)Q(a)T(2) I3.(16 分)符号化下列命题并推证其结论.任何人如果他喜欢音乐，他就不喜欢体育.每个人或者喜欢体育，或者喜欢美 术.有的人不喜欢美术.因而有的人不喜欢音乐.(设 M(x) : x 喜欢

10、音乐，S(x): x 喜欢体育，A(x):x喜欢美术.)该推理符号化为：(x(M(x)S(x)-xS(x) A( R(x)PQ(a) R(a)US(1)x(Q(x) Z(x)PQ(a) Z(a)ES(3)Q(a)TIZ(a)TIR(a)T(2) ,(5) I(8)R(a) Z(a)T(6)，I(9)x(R(x) Z(x)EG(8)-6-(5)S(a)T (2) (4) I (2 分)(6)-x(M (x)；S(x)P-7-(7)M(a) S(a)US (6) (2 分)(8)S(a) M (a)T (7) E (1 分)2. （12 分）对下图所给的偏序集 人-， 求下表所列集合的上（下）界，

11、上（下）确界，并将结果填入表中。子集上界下界上确界下确界(9) M (a)T (5) (8) I (2 分)(10) xM (x)EG(9)(1 分)天津理工大学离散数学第三、四章检测题答案、填空题（每空 2 分，共 40 分）1.n 2n2.”,：,3.：， a,b,c4.反对称，传递。QQ5.RI 丨口 6.i=1广 10 川 00 1 川 0IA,*.川.或单位矩阵+FF4；+rt耳（00 川 17. 46_,2,3 , 无 ， 无 ，12,18.fb ,0. ,1,5,2,5 ,4,4 ,4,5 ,5,4 ,6,3 ,6,6 。 (1)画出R的关系图，并求它的关系矩阵；(2)求r(R)

12、,S(R)及t(R)。(2)r(R)二RU1,1,：2,2,；3,3, 5,5，( 1 分)S(R)二R 3, 1 ,；5：, 1 :, 5,2 ,(16分)t(R)二R 1,4 , 2,4 , 5,5 (2 分)4.设 Z 是整数集，R是 Z 上的模 3 同余关系，即R二：X, y x,y Z,x三y(mod3)，试根据等价关系R决定 Z 的一个划分。答案：由R决定的 Z 的划分为：0L,1】R,2L,其中：0R二,一9,七,30,3,6,9, 1R珂,一8,-5,21,4,7, 2R二,-7,叫-1,2,5,8, R的关系矩阵为 0010 1010000 10M R =00000 0000

13、1 1000010 000100 1 _(2分)解：(1)R的关系图为-9-四.证明题（共 10 分）x _ a1.设a,bR,a :：: b,定义f :a,b 0,1为f（x），证明：f是双射，并求出b a其逆映射。证：1）先证明f是入射（2 分）对任意的x1,x2- la, bl 若 f （xj = f （x2）,则有xi一a=x2一a，从而有捲=x2，b -a b -a故f是入射。2）再证明f是满射（2 分）对任意的0,1丨都存在 x = （b - a）y a a,b使得 f（x） = y,从而f是满射。综合（1）、（ 2）知f是双射。f1:0,1 a,b为f（X）=（b-a）x a，对

14、任意x b,1 L（ 1 分）天津理工大学离散数学第五章检测题答案一、填空题（每空 2 分，共 30 分）1.b a2.a3. ：,S,S“4.a； 1 5.S关于-运算不圭寸闭6. 2,a =4-a7 循环群，生成元8.9.B关于”圭寸闭二、单项选择题（每小题 2 分，共 20 分）12345678910得分BCAABDDCBD二、简答题（共 30 分）1.设”是实数集R上的二元运算，其定义如下：a b = a b 2ab（1）求23,3 （-5）和 71/2。-10-(2)R, “；，是半群吗？ “可交换吗？(3)求 R 中关于”的单位元。(4)R 中哪些元素有逆元素，其逆元素是什么?答案

15、：(1)17,-32，14.5。2)R,是半群，“可交换。(4)当a R, -1/2时，a有逆元素，aJa/(1 2a)。设A二a,b,c,d,.是交换群，a是 的单位元。”的运算表如下:ab cdaab cdbbaX1X2ccX4a X3ddX5X6a求为公2必，&,%5,冷，并说明道理。答案：为=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=(ab)(mod11), 是普通乘法)，问：G,“是循环群吗？若是，试找出它的生

16、 成兀。答：，G,”；的运算表如下表所示。13459113459339145441593554931995314从运算表可知，”在G上圭寸闭、有幺兀 1,且 1 = 35,3 = 3 勺,4 = 34,5 二 33,9 = 32，再由“是可结合的得：:G,T 是循环群，3, 4, 5 和 9 均为其生成元。四.证明题(共 20 分)(3)0。2.-11-1.(4 分)设：G, “是独异点，e为其幺元，且对G，有a a = e，证明；G是一个交换群。证明： 对-a G，由于a“a=e，贝V aJ=a，即G中的每一个元素a都有逆元 素,故G,是一个群。又对- a,b G，有1 1 1a b = a

17、 b (b a) b a,所以G,是一个 Abel 群。2.(6 分)设G, ”:是一个群，aG,f:GrG，- xG，有f (x)二 a x a试证明f是G,个自同构.证：首先证明f是入射。(3 分)对-x-!,x G,若 f(xj = f (x2),则有 a ” a 二 a ” x2a，该式两边同时左乘 a及右乘 a,得 x x2,故 f 为入射 f.其次证明f是满射。对_yG,都存在 x 二 a，y a G,使得 y 二 f(x)，因此 f 是满射.综合以上两点，知f是双射。(3 分)最后,对-x-!, xG,都有 f (x x2) = a ”x2a二(ax G,- xG，有f (x)

18、= a x a 试证明f是一个自同构.证：首先证明f是入射。(3 分)对-为， G,若 f(xj = f (x2),则有 a “ 咅 “ a二 a “ x2a， 该式两边同时左乘 a及右乘 a,得 Xi = X2,故 f 为入射 f.其次证明f是满射。对_yG,都存在 x=a y a G,使得 y = f(x)，因此 f 是满射.综合以上两点，知f是双射。(3 分)最后,对x, ,x2 G,都有 f( x2)二 a “ x2“ a二(a “ 捲 “ a)“(a“ x2“ a-1) 二 f(xjf(x2),从而 f 是 G 到 G 的自同构.离散数学第七章检测题答案一、单项选择题(每小题2分，共

19、20分)12345678910得分2424324213二、填空题（每空 3 分，共 45 分）1.4，3。2._0_ ， _1_。_0_ ，_0_ 。3.（V,V2=V14.2 | E | , 偶数 。5._5_ ; _9_6. _ 3_ , _ 1_。7.7 。-15-则，G = V, E；中长度为 3 的不同的路有10 条，其中有 1 条不同的回路。2.设有 28 盏灯， 拟公用一个电源， 求至少需要 4 插头的接线板的数目。解：设至少需要 4 插头的接线板 i 个，则有（4-1） i=28-1（3 分）故i=9即至少需要 9 个 4 插头的接线板。（2 分）3.设有 6 个城市 V1,

20、V2,，V6，它们之间有输油管连通，其布置如下图，S（数字）中Si为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守？输油管道总长度越短，士兵越好防守。求他们看守的最短管道的长度。（要求写出求解过程）解：为保证每个城市石油的正常供应最少需5 连士兵看守求看守的最短管道相当于求图的最小生成树问题，此图的最小生成树为：因此看守的最短管道的长度为：W（T）=1 +1+ 2 + 2 + 2=8.1 对有向图G =：V, E.求解下列问题：（1）写出邻接矩阵A;（2）G=fV,E中长度为 3 的不同的路有几条？其中不同的回路有几