天津理工大学离散数学检测题答案

1、精品文档天津理工大学离散数学第一章检测题答案一、填空题 （每空 2 分，共30 分）1 PQ2PQ3 ，c。4(PQR) (PQR) (PQ R)，(PQR)(PQR) (PQR)(PQR)(PQR)5( PQ)(P(R S)6QP7 (PQ)(QP)二、单项选择题 （每小题2 分，共 20 分）12345678910得分DBCBCDAACB三、简答题 （每小题6 分，共 12 分）1构造命题公式 P(QR) 的真值表PQRQRP(Q R)00011001110100001111100111011111001111112求命题公式(PQ )R)P 的主析取范式和主合取范式。(PQ)R)P( (

2、PQ) R)分(P分P 1Q)R) P1( PR)(QR)PP(QR)( P(QQ)(RR)( PP)(Q分R) 1( PQR)(PQR)(PQR) (PQR)(P QR)( PQ分R) 1.精品文档(PQR)(PQR)(PQR) (PQR)(PQR)m2m4m5m6m7 (这是主析取范式 )分1M 0M 1M 3 (这是主合取范式 )( PQR)(PQR)(PQ分R) 13判断命题公式 (PQ )( PR) 与(PQR) 是否等价。解：A (P Q) (PR)(PQ)(PR)BP(QR)P(QR)(PQ)(PR)等价四证明题 （共 32 分）（ 10 分）用 CP 规则证明P (QR), Q

3、( RS), PQ S ；1.PP6.( RS)T(4,5) I （ 2 分）2.P(QR)P7.RT(3,4) I （2 分）3.QRT(1, 2) I（2分）8.ST(6,7) I （2 分）4.QP(附加前提 )9. (QS)CP（2 分）5. Q( RS)P（ 10 分）用归谬法证明AB,(CB),CSA证 : 1AP(附加前提) （1 分） 2ABP3BT1,2 I（2 分）4CBP5CT3,4 I（2 分）6CSP7CT6 I（2 分）8CCT5,7I （2 分）由 8 得出了矛盾，根据归谬法说明原推理正确（1 分）3（12 分）公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结

4、果如下：（ 1）营业员 A 或 B 盗窃了钻石项链（ 2）若 B 作案，则作案时间不在营业时间.精品文档（ 3）若 A 提供的证词正确，则货柜未上锁（ 4）若 A 提供的证词不正确，则作案发生在营业时间（ 5）货柜上了锁试问：作案者是谁？要求写出推理过程。解：令 A 表示 “营业员 A 盗窃了钻石项链 ”； B 表示 “营业员 B 盗窃了钻石项链 ”；P 表示 “作案时间在营业时间 ”；Q 表示 “A 提供的证词正确 ”；R 表示 “货柜上了锁 ”。则侦察结果如下：AB，BP ， QR ， QP ， R 由此可推出作案者是 A （4 分）推理过程如下：(1)RP(6)BP P(2)QRP(7)

5、BT (5)，(6)I（2 分）(3)QT (1)，(2)I （2 分） (8)A BP(4)QPP(9)AT (7)，(8)I（2 分）(5)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 P(a)P(b)P( c)(Q(a) Q(b)Q(c)4( P(a)P(b)P(c)(P(a)P(b)P(

6、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 分）12345678910得分AABDCACCBD.精品文档三、简答题 （每小题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)(

7、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

8、（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

9、(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

10、)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)I3（16 分）符号化下列命题并推证其结论任何人如果他喜欢音乐 ,他就不喜欢体育 每个人或者喜欢体育， 或者喜欢美术有的人不喜欢美术因而有的人不喜欢音乐 （设 M(x) ：x 喜欢音乐，S(x)：x 喜欢体育， (x) ：喜欢美术）该推理符号化为：(x( M ( x)S( x)x( S( x)A( x)xA( x)( xM ( x)或前提：x( M ( x)S( x),x( S( x)A( x),xA( x)结论：x

11、M ( x)（ 4 分）证：（ 1）xA( 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 n2n , , 3, a, b, c 10L05RUR1；

12、 U Ri6 IA，01L04 反对称，传递。或单位矩阵M MMMi100L17 4,6，2,3，无，无，12，1。8 f1,0, ,1 ,f 2,1, ,0 。9 单射，满射 ；既是单射又是满射；IB； IA二、单项选择题 （每小题2 分，共20 分）12345678910得分(1)(2)(1)(3)（ 2）（ 2）(1)(3)(3)(1)三、简答题 （共 30 分）1（ 6 分）设 A =1,2,3,5,6,10,15,30 ， “ ”为集合 A 上的整除关系。 A ，是否为偏序集 ? 若是，画出其哈斯图；解： A ，是偏序集。其哈斯图为：2（ 12 分）对下图所给的偏序集A,，求下表所列

13、集合的上（下）界，上（下）确界，并将结果填入表中。子集上界下界上确界下确界.精品文档 a,b, cadada, c无c无 c,d ,eAa无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 的关系矩阵为001010000010000000M R0011（2 分）00000100001001（ 2） r (R) RU 1,1, 2,2 , 3,3

14、 , 5,5 ， （ 1 分）S(R)RU 3,1, 5,1 , 5,2 , 3,6 （1 分）t(R)RU 1,4 , 2,4 , 5,5（2 分）4设 Z 是整数集，R 是 Z 上的模 3 同余关系，即R x, yx, yZ , xy(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, ab,定义 f : a, b0,1 为xa，证明： f 是双

15、射，并求出f (x)ab其逆映射。证： 1）先证明 f是入射（ 2 分）对任意的 x1 , x2a, b , 若 f ( x1 )f ( x2 ), 则有 x1ax2a ，从而有 x1x2 ，baba故 f 是入射。2) 再证明 f是满射（ 2 分）对任意的 y0,1 ,都存在 x(ba) ya a, b ,使得 f ( x)y, 从而 f 是满射。综合（ 1）、（ 2）知 f 是双射。f1 : 0,1a, b 为f 1 ( x)(ba) xa ，对任意 x0,1 。（ 1 分）天津理工大学离散数学第五章检测题答案一、填空题 （每空 2 分，共 30 分）1. b 1 a 12 a3 ,S,

16、S,4 a ； 15 S关于运算不封闭6 2， a 14 a7 循环群，生成元8121 1 12 1 29B关于封闭二、单项选择题 （每小题 2 分，共 20 分）12345678910得分BCAABDDCBD三、简答题 （共 30 分）1设是实数集 R 上的二元运算，其定义如下：abab2ab（1）求 23， 3(-5)和 71/2 。.精品文档（ 2） R, 是半群吗？ 可交换吗？（ 3）求 R中关于 的单位元。（ 4） R 中哪些元素有逆元素，其逆元素是什么？答案：（ 1）17， -32， 14.5 。2） R,是半群，可交换。（3） 0。（ 4）当 a R,a1/ 2时， a 有逆元素

17、， a 1a /(1 2a) 。2设 A a, b, c, d ， A,是交换群， a 是 A,的单位元。的运算表如下：abcdaabcdbbax1x2ccx4ax3ddx5x6a求 x1 , x2 , x3 , x4 , x5 , x6 ，并说明道理。答案： x1d , x2c, x3b, x4d , x5c, x6b 。因为有限群的运算表中的每行、每列都是群中元素的一个置换。3 设集合 G1,3,4,5,9 ，是定义在 G 上的模11 乘法（即任意a,bG，有a* b=(ab)(mod11)， 是普通乘法），问 G,是循环群吗？若是，试找出它的生成元。答：G,的运算表如下表所示。13459

18、113459339145441593554931995314从运算表可知，在 G 上封闭、有幺元1，且 135,3 31, 4 34 ,5 33 ,9 32 ，再由 是可结合的得G, 是循环群， 3，4，5 和 9 均为其生成元。.精品文档四证明题 （共 20 分）（ 4 分）设G,是独异点，e 为其幺元，且对aG ，有 aae ，证明G,是一个交换群。证明：对aG ，由于 a ae ，则a 1a ， 即 G 中的每一个元素a 都有逆元素,故 G, 是一个群。又对 a,b G ，有aba 1b 1(ba) 1ba ，所以 G,是一个 Abel 群。（ 6 分）设G,是一个群，aG ， f :

19、GG ，xG ，有f (x)axa 1试证明f 是 G,一个自同构证：首先证明f 是入射。（ 3 分）对 x1 , x2 G,若 f ( x1 ) f ( x2 ), 则有 a x1 a 1 a x2 a 1, 该式两边同时左乘 a 1及右乘 a, 得x1 x2 , 故 f 为入射 f .其次证明f 是满射。对yG ,都存在 xa 1yaG , 使得 yf ( x),因此 f 是满射.综合以上两点，知f 是双射。（ 3 分）最后, 对x1 , x2G,都有 f ( x1x2 )ax1x2a 1(ax1a 1)(ax2a 1)f (x1)f (x2 ), 从而 f 是 G到 G的自同构 .天津理

20、工大学离散数学第六章检测题答案一、填空题 （每空 2 分，共 40 分）.上确界 和下确界， a ， b2至少有一个补元素，不一定3 0，1；1，01.精品文档4 a a 1,aa0 5 ab ； ab6A n， A2nA二、单项选择题 （每小题 2 分，共 20 分）12345678910得分DCBCADABDD三、简答题 （共 30 分）1下面哈斯图表示的格中哪个元素无补元？对有补元的元素求出它们的补元解： c 无补元（ 1 分）， a 的补元为 e（ 1 分），b 的补元为 d（ 1 分）， d 的补元为 b、e（1 分）， e 的补元为 a、 d（ 1 分）， 0 与 1 互为补元。（

21、 1 分）2设 B, ,0,1 是一个布尔代数且B0, a,b,1 ，求布尔表达式f ( x1, x2 , x3 )(ax1x2 )( x1(x3b)的析取范式和合取范式并计算f (b,1 a) 的值。解： f ( x1, x2 , x3 ) 的析取范式为：(x1x2x3 )(x1x2x3 )( x1x2x3 )(bx1x2x3 ) （4分）f ( x1 , x2 , x3 ) 的合取范式为：(x1x2x3 ) (x1 x2 x3 ) ( x1x2 x3 ) ( x1 x2 x3 ) (b x1 x2x3 ) （ 分）4f (b,1 a)b （2 分）3设 A =1,2,3,5,6,10,15

22、,30 ， “ ”为集合 A 上的整除关系。(1) A ，是否为偏序集 ?若是，画出其哈斯图；(2) A ，是否构成格？为什么？(3) A ，是否构成布尔代数？为什么？解： (1) A ，是偏序集。其哈斯图为：(2) A ，构成格。因为其任意两个元素都有上确界和下确界。(3) A ，构成布尔代数。因为它是有界分配格，且其任意元素都有唯一补元素。四证明题 （共 10 分）（ 4 分）设G,是独异点，e 为其幺元，且对aG ，有 aae ，证明G,是一个交换群。证明：对aG ，由于 aae ，则a 1a ， 即 G 中的每一个元素a 都有逆元素 ,故.精品文档G,是一个群。又对a,bG ，有aba

23、 1b 1(ba) 1ba ，所以 G,是一个 Abel 群。（ 6 分）设G,是一个群，aG ， f : GG ，xG ，有f (x)axa 1试证明f 是 G,一个自同构证：首先证明f 是入射。（ 3 分）对 x1 , x2 G,若 f ( x1 ) f ( x2 ), 则有 a x1 a 1 a x2 a 1, 该式两边同时左乘 a 1及右乘 a, 得x1 x2 , 故 f 为入射 f .其次证明f 是满射。对yG ,都存在 xa 1yaG , 使得 yf ( x),因此 f 是满射.综合以上两点，知f 是双射。（ 3 分）最后 ,对x1 , x2G, 都有 f ( x1x2 )ax1x

24、2a 1( ax1a 1)(ax2a 1)f ( x1 )f ( x2 ), 从而 f 是G到 G的自同构 .离散数学第七章检测题答案一、单项选择题 （每小题2 分，共 20 分）12345678910得分2424324213二、填空题 （每空 3分，共 45 分）14，3 。2 _0_， _1_。_0_， _0_。3 (V2V1,V2V14 2E，偶数。 5 _5_； _9_。63，1。77 。三、简答题 （每小题5 分，共 25 分）.精品文档1对有向图GV , E 求解下列问题：（ 1）写出邻接矩阵 A ；（ 2） G V , E 中长度为 3 的不同的路有几条？其中不同的回路有几条？解：（ 1）邻接矩阵为：0100100100A00001，110000001000110110010000100010（2） A200010,A31100001101001111100001101则， GV,E 中长度为3 的不同的路有 10 条，其中有1 条不同的回路。2设有盏灯，拟公用一个电源，求至少需要插头的接线板的数目。解：设至少需要 4 插头的接线板i 个，则有（ 4-1） i=28-1（3 分）故i=9即至少需要 9 个 4 插头的接线板。（2 分）3设有126ii6个城市 V，V， ， V