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

,单击此处编辑母版标题样式,*,计算机学院,*,单击此处编辑母版标题样式,*,计算机科学与工程学院,*,冯伟森,Email,：,28 十一月 2024,离散数学,计算机学院,2024/11/28,计算机学院,2,主要内容,Euler,图的应用,(,计算机鼓轮设计,),半期考试讲评,2024/11/28,计算机学院,3,Euler,图的应用,计算机鼓轮设计（,模数转换问题）,：设有旋转鼓轮其表面被等分成,16,个部分，如图,1,所示。,其中每一部分分别用绝缘体或导体组成，绝缘体部分给出,信号,0,，导体部分给出,信号,1,，在图中阴影部分表示导体，空白部分表示绝缘体，根据鼓轮的位置，,触点,将得到信息,1101,，如果鼓轮沿顺时针方向旋转一个部分，触点将有信息,1010,。,问鼓轮上,16,个部分怎样安排导体及绝缘体，才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。,图,1,2024/11/28,计算机学院,4,设有一个,八个结点,的有向图（,图,2,），其结点分别记为,三位二进制数,000,，,001,，,010,，,011,，,100,，,101,，,110,，,111,，设,a,i,0,，,1,，,从结点,a,1,a,2,a,3,可引出两条有向边，其终点分别是,a,2,a,3,0,以及,a,2,a,3,1,。该两条边分别记为,a,1,a,2,a,3,0,和,a,1,a,2,a,3,1,。,图,2,2024/11/28,计算机学院,5,按照上述方法，对于八个结点的有向图共有,16,条边，在这种图的任一条路中，其邻接的边必是,a,1,a,2,a,3,a,4,和,a,2,a,3,a,4,a,5,的形式，即是,第一条边标号的后三位数与第二条边标号的头三位数相同。,2024/11/28,计算机学院,6,因为图,2,中,16,条边被记成不同的二进制数，可见前述鼓轮转动所得到,16,个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路，由回路中每条边对应码的第一个符号构成的循环序列就是所求结果。,2024/11/28,计算机学院,7,如,e,0,e,1,e,2,e,4,e,9,e,3,e,6,e,13,e,10,e,5,e,11,e,7,e,15,e,14,e,12,e,8,是一条欧拉回路，这,16,个二进制数可写成对应的二进制数序列。把这个序列排成环状,即与所求的鼓轮相对应。,2024/11/28,计算机学院,8,上面的例子,，我们可以把它推广到鼓轮具有,n,个触点的情况。为此，我们只要构造,2,n-1,个结点的有向图，设每个结点标记为,n-1,位二进制数，从结点,1,2,n,出发，有一条终点为,2,3,n-1,0,的边，该边记为,1,2,n-1,0,；还有一条边的终点为,2,3,n-1,1,的边，该边记为,1,2,n-1,1,。这样构造的有向图，其每一结点的出度和入度都是,2,，故必是欧拉图。由于邻接边的标记是第一条边的后,n-1,位二进制数与第二条边的前,n-1,位二进制数相同，为此就有一种,2,n,个二进制数的环形排列与所求的鼓轮相对应。,考试情况,参加考试共,59,人。,90,分以上,3,人，,8089,分,7,人，,7079,分,9,人，,6069,分,19,人，,5059,分,7,人，,50,以下,14,人。,平均成绩,61.30,分,2024/11/28,计算机学院,9,第一大题,1,、,除非天下雨，否则他不开车上班。,解：,设：,P:,天下雨,Q:,他开车上班,Q,P,或者,P,Q,完全答对：,49,人,基本答对：,0,人,完全答错：,10,原因分析：,分不清楚命题和逻辑谓词之间表示的区别。,2024/11/28,计算机学院,10,2,、,如果,f,（,x,）在点,x,0,处可导，则,f,（,x,）在点,x,0,处可微。反之亦然,。,设：,P:f,（,x,）在点,x,0,处可导,Q:f,（,x,）在点,x,0,处可微,P,Q,完全答对：,52,人,基本答对：,0,人,完全答错：,7,原因分析：,分不清楚命题和逻辑谓词之间表示的区别，没有注意到反之亦然是双条件命题。,2024/11/28,计算机学院,11,3,、,男人一定比女人聪明，是不对的。,解：,设：,P(x):x,是男人；,Q(y):y,是女人；,R(x,y):x,比,y,聪明,x,y(P(x),Q(y),R(x,y),或者,x,y(P(x),Q(y),R(x,y),完全答对：,16,人,基本答对：,18,人,完全答错：,25,原因分析：,对命题的设定不正确，逻辑混淆。,2024/11/28,计算机学院,12,4,、,两个不相等的实数间，必存在第三个实数。,解：,设：,R(x):x,是实数；,P(x,y,z):x,z,y,；,Q(x,y):x,和,y,不相等,x,y(R(x),R(y),Q(x,y),zR(z),(P(x,y,z),P(y,x,z),完全答对：,26,人,基本答对：,0,人,完全答错：,33,原因分析：,对题意理解不清,2024/11/28,计算机学院,13,5,、,会叫的狗未必会咬人,解：,设：,P(x),：,x,是会叫的狗，,Q(x),：,x,是会咬人的狗,x,（,P(x),Q(x),）,或者,x,（,P(x),Q(x),）,完全答对：,42,人,基本答对：,0,人,完全答错：,17,原因分析：,逻辑谓词的存在量词没有写，对这句话理解有偏差。,2024/11/28,计算机学院,14,第二大题：计算题,1,、,用公式转换法求（,p,q,r,）,(,p,(,q,r),的主合取范式和主析取范式。,解：,（,p,q,r,）,(p,(q,r),(p(q,r),(p(q,r),(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),2024/11/28,计算机学院,15,主合取范式为（,p q r,）（,p q r,）（,p q r,）（,p q r,）（,p q r,）（,p q r,）,又因为在主合取范式中,和,没有出现，,因而，主析取范式应为,M,7,M,0,，即,(p,q,r)(p,q,r),完全答对：,35,人,基本答对：,19,人,完全答错：,5,原因分析：,对求主析取范式与主合取范式的方法掌握不够熟练,等价变化过程中不仔细,不能完全正确地得到结果,.,2024/11/28,计算机学院,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,范式,的方法,2024/11/28,计算机学院,17,3,、,设,A=1,2,3,B=a,b,求,B,A,，并指出哪些是单射，哪些是满射，哪些是双射？,2024/11/28,计算机学院,18,解,：,B,A,=f,0,f,1,f,2,.,f,7,其中,f,0,=,f,1,=,f,2,=,f,3,=,f,4,=,f,5,=,f,6,=,f,7,=,其中，除,f,0,和,f,7,外都是满射。无单射和双射。,完全答对：,13,人,基本答对：,5,人,完全答错：,41,原因分析：,对概念理解不清,2024/11/28,计算机学院,19,2024/11/28,计算机学院,20,4.A=1,2,3,4,R=,画出,R,的关系图，写出,A,的关系矩阵，并求,r(R),s(R),t(R),。,2,1,3,4,M,(R)=,M,(R)=,2024/11/28,计算机学院,21,r(R)=R,I,A,=,s(R)=R,R,1,=,t(R)=R,R,2,R,3,R,4,=,=,，,2024/11/28,计算机学院,22,M,(r(R)=,M,(s(R)=,完全答对：,27,人,基本答对：,26,人,完全答错：,6,原因分析：,没有根据图写出关系或关系矩阵,R,，对,r,（,R,）和,s,（,R,）错误较少，,t,（,R,）错误较多。,2024/11/28,计算机学院,23,5,、,设,A,为,72,的因子构成的集合，,R A,A,，,x,y,A,xRy,x,整除,y,。画出偏序集,的哈斯图，设,B=1,2,3,4,6,8,9,12,，求出,B,中的最大元，最小元，极大元，极小元，上界，下界，最小上界，最大下界。,解：,2024/11/28,计算机学院,24,最大元,无,，最小元,1,，极大元,8,、,9,、,12,，极小元,1,，上界,72,，下界,1,，最小上界,72,，最大下界,1,完全答对：,19,人,基本答对：,35,人,完全答错：,5,原因分析：,偏序图未能规范地画出,;,对最大元,最小元,极大元,极小元,上界,下界,最小上界,最大下界等概念理解混淆,2024/11/28,计算机学院,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),2024/11/28,计算机学院,26,1,x(N(x),F(x)P,2 N(c),F(c)T(1)ES,3,x(E(x),N(x)F(x)P,4 E(c),N(c)F(c)T(3)US,5 E(c)T(2)(4)I,6,x(N(x),(O(x),E(x)P,7 O,（,c,）,E(c)T(6)US,8 O(c)T(5)(7)I,9,xO(x)T(8)EG,2024/11/28,计算机学院,27,完全答对：,19,人,基本答对：,35,人,完全答错：,5,原因分析：,对命题的符号化不准确,证明过程不规范，逻辑不严密。,2024/11/28,计算机学院,28,2024/11/28,计算机学院,29,2.,设,A=1,2,3,4,，在,AA,上定义二元关系,R,AA,R,+y=x+,(1),证明,R,是,AA,上的等价关系。,(2),确定由,R,导出的对集合,AA,的划分。,证明：,(1),注意到,R,+y=x+,-,=x-y,。,任取,有,AA,x-y=x-y,R,自反性,2024/11/28,计算机学院,30,任取,，,有,R,x-y=,-,-,=x-y,R,对称性,任取,，,，,有,R,R,x-y=,-,-,=s-t,x-y=s-t,R,传递性,(2),，,，,完全答对：,23,人,基本答对：,29,人,完全答错：,7,原因分析：,对自反性和对称性的证明大都能完成,但对传递性的证明不严密,.,通过等价关系求划分时候,错误较多,.,2024/11/28,计算机学院,31,3,、,设有函数,g,：,A,B,和,f,：,B,C,，使得,f,g,是一个单射，且,g,是满射。证明,f,是一个单射。,证明：,(,反证法,),假定,f,不是单射，则存在,y,1,和,y,2,B,使得,y,1,y,2,时，,f,（,y,1,）,=f,（,y,2,）。,因,g,是满射，对于,y,1,和,y,2,B,，必有,x,1,和,x,2,A,，使得,g,（,x,1,）,=y,1,，,g,（,x,2,）,=y,2,，,因,g,（,x,1,）,=y,1,y,2,=g,（,x,2,），故,x,1,x,2,。,为什么？,2024/11/28,计算机学院,32,这样就有,f,g,（,x,1,）,=fg,（,x,1,）,=f,（,y,1,）,=f,（,y,