离散数学(第28讲半期考试讲评).ppt

《离散数学(第28讲半期考试讲评).ppt》由会员分享，可在线阅读，更多相关《离散数学(第28讲半期考试讲评).ppt（41页珍藏版）》请在三一办公上搜索。

1、冯伟森,Email：2023年9月14日星期四,离散数学,计算机学院,2023/9/14,计算机学院,2,主要内容,Euler图的应用(计算机鼓轮设计)半期考试讲评,2023/9/14,计算机学院,3,Euler图的应用,计算机鼓轮设计（模数转换问题）：设有旋转鼓轮其表面被等分成16个部分，如图1所示。,其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号0，导体部分给出信号1，在图中阴影部分表示导体，空白部分表示绝缘体，根据鼓轮的位置，触点将得到信息1101，如果鼓轮沿顺时针方向旋转一个部分，触点将有信息1010。问鼓轮上16个部分怎样安排导体及绝缘体，才能使鼓轮每旋转一个部分，四个触点能

2、得到一组不同的四位二进制数信息。,图1,2023/9/14,计算机学院,4,设有一个八个结点的有向图（图2），其结点分别记为三位二进制数000，001，010，011，100，101，110，111，设ai0，1，从结点a1a2a3可引出两条有向边，其终点分别是a2a30以及a2a31。该两条边分别记为a1a2a30和a1a2a31。,图2,2023/9/14,计算机学院,5,按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三位数与第二条边标号的头三位数相同。,2023/9/14,计算机学院,6,

3、因为图2中16条边被记成不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路，由回路中每条边对应码的第一个符号构成的循环序列就是所求结果。,2023/9/14,计算机学院,7,如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8是一条欧拉回路，这16个二进制数可写成对应的二进制数序列。把这个序列排成环状,即与所求的鼓轮相对应。,2023/9/14,计算机学院,8,上面的例子，我们可以把它推广到鼓轮具有n个触点的情况。为此，我们只要构造2n-1个结点的有向图，设每个结点标记为n-1位二进制数，从结点12n出发，有一条终点为2

4、3n-10的边，该边记为12n-10；还有一条边的终点为23n-11的边，该边记为12n-11。这样构造的有向图，其每一结点的出度和入度都是2，故必是欧拉图。由于邻接边的标记是第一条边的后n-1位二进制数与第二条边的前n-1位二进制数相同，为此就有一种2n个二进制数的环形排列与所求的鼓轮相对应。,考试情况,参加考试共59人。90分以上3人，8089分7人，7079分9人，6069分19人，5059分7人，50以下14人。平均成绩61.30分,2023/9/14,计算机学院,9,第一大题,1、除非天下雨，否则他不开车上班。解：设：P:天下雨 Q:他开车上班QP 或者 PQ完全答对：49人 基本答

5、对：0人 完全答错：10原因分析：分不清楚命题和逻辑谓词之间表示的区别。,2023/9/14,计算机学院,10,2、如果f（x）在点x0处可导，则f（x）在点x0处可微。反之亦然。设：P:f（x）在点x0处可导,Q:f（x）在点x0处可微PQ完全答对：52人 基本答对：0人 完全答错：7原因分析：分不清楚命题和逻辑谓词之间表示的区别，没有注意到反之亦然是双条件命题。,2023/9/14,计算机学院,11,3、男人一定比女人聪明，是不对的。解：设：P(x):x是男人；Q(y):y是女人；R(x,y):x比y聪明 xy(P(x)Q(y)R(x,y)或者 xy(P(x)Q(y)R(x,y)完全答对：

6、16人 基本答对：18人 完全答错：25原因分析：对命题的设定不正确，逻辑混淆。,2023/9/14,计算机学院,12,4、两个不相等的实数间，必存在第三个实数。解：设：R(x):x是实数；P(x,y,z):xzy；Q(x,y):x和y不相等xy(R(x)R(y)Q(x,y)zR(z)(P(x,y,z)P(y,x,z)完全答对：26人 基本答对：0人 完全答错：33原因分析：对题意理解不清,2023/9/14,计算机学院,13,5、会叫的狗未必会咬人解：设：P(x)：x是会叫的狗，Q(x)：x是会咬人的狗 x（P(x)Q(x)）或者 x（P(x)Q(x)）完全答对：42人 基本答对：0人 完全

7、答错：17原因分析：逻辑谓词的存在量词没有写，对这句话理解有偏差。,2023/9/14,计算机学院,14,第二大题：计算题,1、用公式转换法求（pqr）(p(qr)的主合取范式和主析取范式。解：（pqr）(p(qr)(p(qr)(p(qr)(p q)(p r)(p q)(p r)(pq r)(p q r)(p q r)(p q r)(p q r)(p q r),2023/9/14,计算机学院,15,主合取范式为（p q r）（p q r）（p q r）（p q r）（p q r）（p q r）又因为在主合取范式中 和 没有出现，因而，主析取范式应为 M7 M0，即(pqr)(pqr)完全答对：

8、35人 基本答对：19人 完全答错：5原因分析：对求主析取范式与主合取范式的方法掌握不够熟练,等价变化过程中不仔细,不能完全正确地得到结果.,2023/9/14,计算机学院,16,2、求（xP(x)yQ(y)xR(x)的Skolem范式解：（x P(x)yQ(y)）xR(x)(x P(x)yQ(y)xR(x)(x P(x)yQ(y)zR(z)（xP(x)yQ(y)）zR(z)x y z（P(x)Q(y)）R(z)完全答对：28人 基本答对：15人 完全答错：16原因分析：没有掌握求Skolem范式的方法,2023/9/14,计算机学院,17,3、设A=1,2,3,B=a,b,求BA，并指出哪些

9、是单射，哪些是满射，哪些是双射？,2023/9/14,计算机学院,18,解：BA=f0,f1,f2.,f7,其中f0=,f1=,f2=,f3=,f4=,f5=,f6=,f7=,其中，除f0 和f7外都是满射。无单射和双射。,完全答对：13人 基本答对：5人 完全答错：41原因分析：对概念理解不清,2023/9/14,计算机学院,19,2023/9/14,计算机学院,20,4.A=1,2,3,4,R=,画出R的关系图，写出A的关系矩阵，并求r(R),s(R),t(R)。,M(R)=,M(R)=,2023/9/14,计算机学院,21,r(R)=RIA=,s(R)=RR1=,t(R)=RR2R3R4

10、=,=,，,2023/9/14,计算机学院,22,M(r(R)=,M(s(R)=,完全答对：27人 基本答对：26人 完全答错：6原因分析：没有根据图写出关系或关系矩阵R，对r（R）和s（R）错误较少，t（R）错误较多。,2023/9/14,计算机学院,23,5、设A为72的因子构成的集合，R AA，x,yA,xRy x整除y。画出偏序集的哈斯图，设B=1,2,3,4,6,8,9,12，求出B中的最大元，最小元，极大元，极小元，上界，下界，最小上界，最大下界。解：,2023/9/14,计算机学院,24,最大元无，最小元1，极大元8、9、12，极小元1，上界72，下界1，最小上界72，最大下界1

11、,完全答对：19人 基本答对：35人 完全答错：5原因分析：偏序图未能规范地画出;对最大元,最小元,极大元,极小元,上界,下界,最小上界,最大下界等概念理解混淆,2023/9/14,计算机学院,25,第三大题,1、符号化下列命题并证明其结论。每个自然数不是奇数就是偶数。自然数是偶数当且仅当它能被2整除。并不是所有的自然数都能被2整除。因此，有的自然数是奇数。证明：设N（x）:x为自然数，O（x）：x为奇数，E（x）：x为偶数，F（x）：x被2整除；则本题符号化为x(N(x)(O(x)E(x)，x(E(x)N(x)F(x)），x(N(x)F(x)xO(x),2023/9/14,计算机学院,26,

12、1 x(N(x)F(x)P2 N(c)F(c)T(1)ES 3 x(E(x)N(x)F(x)P4 E(c)N(c)F(c)T(3)US5 E(c)T(2)(4)I 6 x(N(x)(O(x)E(x)P7 O（c）E(c)T(6)US8 O(c)T(5)(7)I 9 xO(x)T(8)EG,2023/9/14,计算机学院,27,完全答对：19人 基本答对：35人 完全答错：5原因分析：对命题的符号化不准确,证明过程不规范，逻辑不严密。,2023/9/14,计算机学院,28,2023/9/14,计算机学院,29,2.设A=1,2,3,4，在AA上定义二元关系R,AA,R+y=x+(1)证明R是AA

13、上的等价关系。(2)确定由R导出的对集合AA的划分。证明：(1)注意到R+y=x+-=x-y。任取,有AAx-y=x-y R 自反性,2023/9/14,计算机学院,30,任取，有R x-y=-=x-y R对称性任取，,有RR x-y=-=s-t x-y=s-t R 传递性(2),，,，,完全答对：23人 基本答对：29人 完全答错：7原因分析：对自反性和对称性的证明大都能完成,但对传递性的证明不严密.通过等价关系求划分时候,错误较多.,2023/9/14,计算机学院,31,3、设有函数g：AB和f：BC，使得f g是一个单射，且g是满射。证明f是一个单射。证明：(反证法)假定f不是单射，则存

14、在y1和y2 B,使得y1y2时，f（y1）=f（y2）。因g是满射，对于y1和y2B，必有x1 和x2A，使得g（x1）=y1，g（x2）=y2，因g（x1）=y1y2=g（x2），故x1x2。为什么？,2023/9/14,计算机学院,32,这样就有f g（x1）=fg（x1）=f（y1）=f（y2）=fg（x2）=f g（x2）.这与f g是单射矛盾。由反证法，因此f是单射。完全答对：9人 基本答对：16人 完全答错：34原因分析：对概念理解掌握不够,反证法证明不严密.题目本身不严谨.,2023/9/14,计算机学院,33,第四大题,1、在一个盗窃案中，已知如下事实：王波或者李明是窃贼；王

15、波是窃贼，作案时间不会发生在夜间12点以前；若李明的证词正确，则夜间12点时被盗物品所在房间灯光未灭；若李明的证词不正确，则作案时间发生在夜间12点以前；夜间12点被盗房间的灯光灭了。根据以上事实，请通过演绎推理找出偷窃者。,2023/9/14,计算机学院,34,解：设p：王波是窃贼，q：李明是窃贼，r：作案时间在12点以前，s：李明的证词正确，t：夜间12点时被盗物品所在房间灯光熄灭。符号化为p q,pr,st,sr,t。推理过程如下1 t P2 st P3 s T(1)(2)IE 4 sr P,2023/9/14,计算机学院,35,5 r T(3)(4)IE6 pr P7 p T(5)(6

16、)IE 8 p q P9 q T(7)(8)E 因此，李明是窃贼。完全答对：31人 基本答对：25人 完全答错：3原因分析：基本都能得到最后的正确结论,但不能按照命题逻辑的推理方法来规范严密地证明.,2023/9/14,计算机学院,36,2.道路网络上连接有7个城市，分别为a,b,c,d,e,f,g；城市之间直接连接的道路是单向的有ab,ac,bg,gc,cf,fe,bd,df。对每个城市求出从它出发能够到达的所有其它城市。解：令 S=a,b,c,d,e,f,g,定义S上的关系R 如下：x,yR 从x到y有一条直接的道路R=a,b,a,c,b,g,g,c,c,f,f,e,b,d,d,f求出R的

17、传递闭包t(R)即可获得问题的解。,2023/9/14,计算机学院,37,2023/9/14,计算机学院,38,t(R)=a,b,a,c,a,d,a,e,a,f,a,g,b,c,b,d,b,f,b,e,b,g,c,e,c,f,d,e,d,f,f,e,g,c,g,e,g,ft(R)a=b，c，d，e，f，gt(R)b=c,d，e，f，g t(R)c=(t(R)-IS)d=e，f t(R)d=e,ft(R)f=et(R)g=c，e，f,2023/9/14,计算机学院,39,2023/9/14,计算机学院,40,完全答对：37人 基本答对：18人 完全答错：4人 原因分析：失分的主要原因是解题时，没有从关系矩阵的传递闭包角度来解答，只写出结果值，没有写出关系矩阵和正确计算传递闭包矩阵。,2023/9/14,计算机学院,41,