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

2、1 1 1 0 1 1 1 0 1 1 1 1 1 (PQ)R)P(PQ)R)P(1分)(PQ)R)P(1分)(PR)(QR)PP(QR)(P(QQ)(RR)(PP)(QR)(1分)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(1分)- 1 - (PQR)(PQR)(PQR)(PQR)(PQR) m2m4m5m6m7(这是主析取范式)(1分)M0M1M3(这是主合取范式)(PQR)(PQR)(PQR)(1分)3判断命题公式 (PQ)(PR)与 (PQR)是否等价。解：A=(PQ)(PR)(PQ)(PR) B=P(QR)P(QR)(PQ)(PR) 等价四证明题用CP规则证

3、明P(QR),Q(RS),PQS； 1. P P 6. (RS) T(4,5) I 2. P(QR) P 7. R T(3,4) I 3. QR T(1, 2) I 8. S T(6,7) I 4. Q P(附加前提) 9. (QS) CP 5. Q(RS) P ,(CB),CSA用归谬法证明 AB 证: 1 A P(附加前提) 2 AB P 3 B T1,2I 4 CB P 5 C T3,4I 6 CS P 7 C T6I 8 CC T5,7I 由8得出了矛盾，根据归谬法说明原推理正确 3公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下：营业员A或B盗窃了钻石项链若B作案，则作

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

5、 P T(3)，(4) I 天津理工大学离散数学第二章检测题答案一、填空题 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) 3P(a)P(b)P(c)(Q(a)Q(b)Q(c) 4(P(a)P(b)P(c)(P(a)P(b)P(c) 5P(x),(x)($y)P(x,y) 6 7(P(x)$yR(x,y) 8($x)(F(x)G(x) 二、单项选择题 1 A 2 A 3 B 4 D 5 C 6 A 7 C 8 C 9 B 10 D 得分 - 3 - 三、简答题

6、 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)四证明

7、题 1用谓词演算的推理规则证明: x(P(x)Q(x)，x(Q(x)R(x)S(x)，P(a)R(a)S(a) x(P(x)Q(x) P P(a)Q(a) US(1) P(a)R(a) P Q(a) T(2)(3)I x(Q(x)R(x)S(x) P Q(a)R(a)S(a) US(5) R(a) T(3) I Q(a)R(a) T(4)(7)I S(a) T(6)(8)I 2(10分) 指出下面推理证明过程中的错误，并给出正确的证明用谓词演算的推理规则证明： - 4 - 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

8、) 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) 的顺序颠倒了，应该先指定存在后指定全称。正确的证明是： (1) $x(Q(x)Z(x) P (6) Z(a) T(2) I (2) Q(a)Z(a) ES (1) (7) R(a) T(4),(5) I (3) x(Q(x)R(x) P (8)

9、 R(a)Z(a) T(6),(7) I (4) Q(a)R(a) US (3) (9) $x(R(x)Z(x) EG(8) (5) Q(a) T(2) I 3符号化下列命题并推证其结论任何人如果他喜欢音乐,他就不喜欢体育每个人或者喜欢体育，或者喜欢美术有的人不喜欢美术因而有的人不喜欢音乐该推理符号化为： S(x)x(S(x)A(x)$xA(x)$(x 或M x (x(M(x)前提：x(M(x)S(x),x(S(x)A(x),$xA(x) 结论：$xM(x) 证： $xA(x) P A(a) ES x(S(x)A(x) P S(a)A(a) US S(a) TI x(M(x)S(x) P

10、- 5 - M(a)S(a) US S(a)M(a) TE M(a) TI $xM(x) EG 天津理工大学离散数学第三、四章检测题答案一、填空题 1 n2 F,F,F,F,F,F 3n F,a,b,c 0L01L0或单位矩阵 MMM0L110-1i4反对称，传递。 5RUR；UR 6 IA，Mi=108 f1=f,0,f,1, f2=f,1,f,0。 9单射，满射；既是单射又是满射； IB； IA 7 4,6 ， 2,3 ，无，无， 12 ， 1 。二、单项选择题 1 (1) 2 (2) 3 (1) 4 (3) 5 6 7 (1) 8 (3) 9 (3) 10 (1) 得分三、

11、简答题 1设A=1,2,3,5,6,10,15,30 ， “” 为集合A上的整除关系。A，是否为偏序集? 若是，画出其哈斯图；解：A，是偏序集。其哈斯图为： 2对下图所给的偏序集A,，求下表所列集合的上界，上确界，并将结果填入表中。子集上界下界上确界下确界 - 6 - a,b,c a a,c d 无无 a c a d 无无 c,d,e A a 3设 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。画出R的关系图，并求它的关系矩阵；求r(R),S(R)及 t(R)。解：R的关系图为 R的关系矩阵为

12、 000000MR=000000101000100000 011001001001r(R)=RU1,1,2,2,3,3,5,5， S(R)=RU3,1,5,1,5,2 , t(R)=R , 5 U1,4,2,4, 5 4设Z是整数集，R是Z上的模3同余关系，即R=x,yx,yZ,xy(mod3)，试根据等价关系R决定Z的一个划分。答案：由R决定的Z的划分为：0R,1R,2R，其中： 0R=L,-9,-6,-3,0,3,6,9,L 1R=L,-8,-5,-2,1,4,7,L 2R=L,-7,-4,-1,2,5,8,L- 7 - 四证明题设a,bR,ab, 定义f:a,b0,1为 f(x)

13、=其逆映射。证：1）先证明f是入射对任意的x1,x2a,b,若f(x1)=f(x2),则有故f是入射。 2) 再证明f是满射对任意的y0,1,都存在x=(b-a)y+aa,b,使得f(x)=y,从而f是满射。综合、知f是双射。 f-1x-a，证明：f是双射，并求出b-ax1-ax2-a=，从而有x1=x2，b-ab-a :0,1a,b为 f-1(x)=(b-a)x+a，对任意x0,1。天津理工大学离散数学第五章检测题答案一、填空题 1. b*a 2a 3F,S,S,F 4a；1 5S关于+运算不封闭 -1-16 2，a-1=4-a 7循环群，生成元 8 * 1 2 129B关于*封闭

14、 1 1 1 2 二、单项选择题 1 B 2 C 3 A 4 A 5 B 6 D 7 D 8 C 9 B 10 D 得分三、简答题 1设*是实数集R上的二元运算，其定义如下： a*b=a+b+2ab 求2*3， 3*(-5)和7*1/2 。 - 8 - R,*是半群吗？*可交换吗？求R中关于*的单位元。 R中哪些元素有逆元素，其逆元素是什么？答案：17，-32，14.5 。 2）R,*是半群，*可交换。 0。 -1当aR,a-1/2时，a有逆元素，a=-a/(1+2a)。 2设A=a,b,c,d，A,*是交换群，a是A,*的单位元。*的运算表如下： * a b c d ab cda b

15、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乘法，问G,*是循环群吗？若是，试找出它的生成元。答： G,*的运算表如下表所示。 * 1 3 4 5 9 1 3 4 5 9 1 3 4 5 9 3 9 1 4 5 4 1 5 9 3 5 4 9 3 1 9 5 3 1 4 从运算表可知，*在G上封闭、有幺元1，且1=35,3=31,4=34,5

16、=33,9=32，再由*是可结合的得G,*是循环群，3，4，5和9均为其生成元。 - 9 - 四证明题设G,*是独异点，e为其幺元，且对aG，有a*a=e，证明 G,*是一个交换群。证明：对aG，由于a*a=e，则 a素,故-1=a，即G中的每一个元素a都有逆元G,*是一个群。又对a,bG，有 a*b=a-1*b-1=(b*a)-1=b*a，所以G,*是一个Abel群。设G,*是一个群，aG，f:GG，xG，有 f(x)=a*x*a-1 试证明f是G,*一个自同构证：首先证明f是入射。对x1,x2G,若f(x1)=f(x2),则有a*x1*a-1=a*x2*a-1,该式两边同

17、时左乘a及右乘a,得x1=x2,故f为入射f.其次证明f是满射。 -1对yG,都存在x=a*y*aG,使得y=f(x),因此f是满射. 综合以上两点，知f是双射。 -1最后,对x1,x2G,都有f(x1*x2)=a*x1*x2*a-1=(a*x1*a-1)*(a*x2*a-1)=f(x1)*f(x2),从而f是G到G的自同构.天津理工大学离散数学第六章检测题答案一、填空题 1. 上确界和下确界，a，b 2至少有一个补元素，不一定 30，1；1，0 - 10 - 4aa=1,aa=0 5ab；ab 6 AAn，A2n二、单项选择题 1 D 2 C 3 B 4 C 5 A 6 D 7 A 8

18、B 9 D 10 D 得分三、简答题 1下面哈斯图表示的格中哪个元素无补元？对有补元的元素求出它们的补元解：c无补元，a的补元为e，b的补元为d，d的补元为b、e，e的补元为a、d，0与1互为补元。 2设B,0,1是一个布尔代数且B=0,a,b,1，求布尔表达式 f(x1,x2,x3)=(ax1x2)(x1(x3b) 1a)的值。的析取范式和合取范式并计算f(b,解：f(x1,x2,x3)的析取范式为： (x1x2x3)(x1x2x3)(x1x2x3)(bx1x2x3) f(x1,x2,x3)的合取范式为： (x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(bx1x2x3

19、) f(b,1a)=b 3设A=1,2,3,5,6,10,15,30 ， “” 为集合A上的整除关系。 (1)A，是否为偏序集? 若是，画出其哈斯图； (2)A，是否构成格？为什么？ (3)A，是否构成布尔代数？为什么？解：(1)A，是偏序集。其哈斯图为： (2)A，构成格。因为其任意两个元素都有上确界和下确界。 (3)A，构成布尔代数。因为它是有界分配格，且其任意元素都有唯一补元素。四证明题设G,*是独异点，e为其幺元，且对aG，有a*a=e，证明 G,*是一个交换群。证明：对aG，由于a*a=e，则 a-1=a，即G中的每一个元素a都有逆元素,故- 11 - G,*是一个群

20、。又对a,bG，有 a*b=a-1*b-1=(b*a)-1=b*a，所以G,*是一个Abel群。设G,*是一个群，aG，f:GG，xG，有 f(x)=a*x*a-1 试证明f是G,*一个自同构证：首先证明f是入射。对x1,x2G,若f(x1)=f(x2),则有a*x1*a-1=a*x2*a-1,该式两边同时左乘a及右乘a,得x1=x2,故f为入射f.其次证明f是满射。 -1对yG,都存在x=a-1*y*aG,使得y=f(x),因此f是满射. 综合以上两点，知f是双射。最后,对x1,x2G,都有f(x1*x2)=a*x1*x2*a-1=(a*x1*a-1)*(a*x2*a-1)=f(

21、x1)*f(x2),从而f是G到G的自同构.离散数学第七章检测题答案一、单项选择题 1 2 2 4 3 2 4 4 5 3 6 2 7 4 8 2 9 1 10 3 得分二、填空题 1 4 ， 3 。 2 _0_， _1_。 _0_， _0_。 3(V2V1,V2=V1 4 2 E ，偶数。5_5_； _9_。 6 3 ， 1 。7 7 。三、简答题 - 12 - 1对有向图G=V,E求解下列问题：写出邻接矩阵A； G=V,E中长度为3的不同的路有几条？其中不同的回路有几条？解：邻接矩阵为： 00A=010100101000001， 10000010011011000001

22、30010,A=11110100100001001010000 111101002A=001则，G=V,E中长度为3的不同的路有10条，其中有1条不同的回路。 2设有盏灯，拟公用一个电源，求至少需要插头的接线板的数目。解：设至少需要4插头的接线板i个，则有 i=28-1 故 i=9 即至少需要9个4插头的接线板。 3设有6个城市V1，V2，V6，它们之间有输油管连通，其布置如下图,Si(数字)中Si为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?输油管道总长度越短，士兵越好防守。求他们看守

23、的最短管道的长度。(要求写出求解过程) 解：为保证每个城市石油的正常供应最少需 5连士兵看守.求看守的最短管道相当于求图的最小生成树问题，此图的最小生成树为：因此看守的最短管道的长度为： 1222 - 13 - 4以给定权1, 4, 9, 16, 25, 36, 49, 64, 81, 100构造一棵最优二叉树。 5一次学术会议的理事会共有20个人参加，他们之间有的相互认识，但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20，说明能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什么？解：可以把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人。

24、根据是：分别用20个结点代表这20个人，将相互认识的人之间连一条线，便得到一个无向简单图G=V,E，每个结点viV的度数是与vi认识的人的数目，由题意知vi,vjV，有degv(i+)devg2于是G=V,E中存在哈密尔顿回路，设j()，C=vi1vi2Lvi20vi1是G=V,E中的一条哈密尔顿回路，按此回路安排园桌座位即符合要求。四证明与应用题 1 某次聚会的成员到会后相互握手，试用图论的知识说明与奇数个人握手的人数一定是一个偶数。证: 用结点代表成员, 握手的成员之间连一条线, 则所有聚会的成员之间的握手情况可以用一个图来表示，其中每个结点的度数就是该结点所代表的成员握手的人数,由于任一图中奇数度结点的个数为偶数,所以与奇数个人握手的人数一定是一个偶数。 - 14 -

展开阅读全文