《离散数学(第28讲半期考试讲评).ppt》由会员分享，可在线阅读，更多相关《离散数学(第28讲半期考试讲评).ppt（41页珍藏版）》请在三一文库上搜索。
1、冯伟森,Email： Tel: 13808192275 2019年2月10日星期日,离散 数学,计算机学院,2019/2/10,计算机学院,2,主要内容,Euler图的应用(计算机鼓轮设计) 半期考试讲评,2019/2/10,计算机学院,3,Euler图的应用,计算机鼓轮设计（模数转换问题）：设有旋转鼓轮其表面被等分成16个部分，如图1所示。,其中每一部分分别用绝缘体或导体组成，绝缘体部分给出信号0，导体部分给出信号1，在图中阴影部分表示导体，空白部分表示绝缘体，根据鼓轮的位置，触点将得到信息1101，如果鼓轮沿顺时针方向旋转一个部分，触点将有信息1010。问鼓轮上16个部分怎样安排导体及绝缘
2、体，才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。,图1,2019/2/10,计算机学院,4,设有一个八个结点的有向图（图2 ），其结点分别记为三位二进制数000，001，010，011，100，101，110，111，设ai0，1，从结点a1a2a3可引出两条有向边，其终点分别是a2a30以及a2a31。该两条边分别记为a1a2a30和a1a2a31。,图2,2019/2/10,计算机学院,5,按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三位数与第二条边标号的头三位数相
3、同。,2019/2/10,计算机学院,6,因为图2中16条边被记成不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路，由回路中每条边对应码的第一个符号构成的循环序列就是所求结果。,2019/2/10,计算机学院,7,如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8是一条欧拉回路，这16个二进制数可写成对应的二进制数序列0000100110101111。把这个序列排成环状,即与所求的鼓轮相对应。,2019/2/10,计算机学院,8,上面的例子，我们可以把它推广到鼓轮具有n个触点的情况。为此，我们只要构造2n-1个结点的
4、有向图，设每个结点标记为n-1位二进制数，从结点12n出发，有一条终点为23n-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分,2019/2/10,计算机学院,9,第一大题,1、除非天下雨，否则他不开车上班
5、。 解： 设：P:天下雨 Q: 他开车上班 QP 或者 PQ 完全答对： 49人 基本答对： 0人 完全答错：10 原因分析： 分不清楚命题和逻辑谓词之间表示的区别。,2019/2/10,计算机学院,10,2、如果f（x）在点x0处可导，则f（x）在点x0处可微。反之亦然。 设：P: f（x）在点x0处可导, Q: f（x）在点x0处可微 PQ 完全答对： 52人 基本答对： 0人 完全答错：7 原因分析： 分不清楚命题和逻辑谓词之间表示的区别，没有注意到反之亦然是双条件命题。,2019/2/10,计算机学院,11,3、男人一定比女人聪明，是不对的。 解：设：P(x):x是男人；Q(y):y是
6、女人；R(x,y):x比y聪明 xy(P(x)Q(y)R(x,y) 或者 xy(P(x) Q(y) R(x,y) 完全答对： 16人 基本答对： 18人 完全答错：25 原因分析：对命题的设定不正确，逻辑混淆。,2019/2/10,计算机学院,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 原因分析： 对题意理解不清,2019/2/10,计算机学院,13,5、会叫的狗未
7、必会咬人 解：设：P(x)：x是会叫的狗，Q(x)：x是会咬人的狗 x（P(x)Q(x)）或者 x（ P(x) Q(x)） 完全答对： 42人 基本答对： 0人 完全答错：17 原因分析： 逻辑谓词的存在量词没有写，对这句话理解有偏差。,2019/2/10,计算机学院,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),2019/2/10,计算机学院,1
8、5,主合取范式为（p q r）（p q r）（p q r）（p q r）（p q r）（p q r） 又因为在主合取范式中 和 没有出现， 因而，主析取范式应为 M7 M0 ，即 (pqr) (pqr) 完全答对： 35人 基本答对： 19人 完全答错：5 原因分析：对求主析取范式与主合取范式的方法掌握不够熟练,等价变化过程中不仔细,不能完全正确地得到结果.,2019/2/10,计算机学院,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)
9、（ xP(x) yQ(y)） zR(z) x y z（P(x)Q(y)） R(z) 完全答对：28人 基本答对： 15人 完全答错：16 原因分析：没有掌握求Skolem范式的方法,2019/2/10,计算机学院,17,3、设A=1,2,3,B=a,b,求BA，并指出哪些是单射，哪些是满射，哪些是双射？,2019/2/10,计算机学院,18,解：BA=f0,f1,f2.,f7,其中 f0=, f1=, f2=, f3=, f4=, f5=, f6=, f7=, 其中，除f0 和f7外都是满射。无单射和双射。,完全答对：13人 基本答对： 5人 完全答错：41 原因分析：对概念理解不清,2019
10、/2/10,计算机学院,19,2019/2/10,计算机学院,20,4.A=1,2,3,4,R=,画出R的关系图，写出A的关系矩阵，并求r(R),s(R),t(R)。,M (R)=,M (R)=,2019/2/10,计算机学院,21,r(R)=RIA=, , s(R)=RR1=, , t(R)=RR2R3R4=, , =, , , , ， ,2019/2/10,计算机学院,22,M (r(R)=,M (s(R)=,完全答对： 27人 基本答对： 26人 完全答错：6 原因分析：没有根据图写出关系或关系矩阵R，对r（R）和s（R）错误较少，t（R）错误较多。,2019/2/10,计算机学院,23
11、,5、设A为72的因子构成的集合，R AA， x,yA, xRy x整除y。画出偏序集的哈斯图，设B=1,2,3,4,6,8,9,12，求出B中的最大元，最小元，极大元，极小元，上界，下界，最小上界，最大下界。 解：,2019/2/10,计算机学院,24,最大元无，最小元1，极大元8、9、12，极小元1，上界72，下界1，最小上界72，最大下界1,完全答对： 19人 基本答对： 35人 完全答错：5 原因分析：偏序图未能规范地画出;对最大元,最小元,极大元,极小元,上界,下界,最小上界,最大下界等概念理解混淆,2019/2/10,计算机学院,25,第三大题,1、符号化下列命题并证明其结论。 每
12、个自然数不是奇数就是偶数。自然数是偶数当且仅当它能被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),2019/2/10,计算机学院,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
13、) ) P 7 O（c） E(c) T(6)US 8 O(c) T(5)(7)I 9 xO(x) T(8)EG,2019/2/10,计算机学院,27,完全答对： 19人 基本答对： 35人 完全答错：5 原因分析：对命题的符号化不准确,证明过程不规范，逻辑不严密。,2019/2/10,计算机学院,28,2019/2/10,计算机学院,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。 任取,有AAx-y=x-y R 自反性,2019/2/1
14、0,计算机学院,30,任取，有R x-y=- -=x-y R对称性 任取，,有 RR x-y=-=s-t x-y=s-t R 传递性 (2) ,，,，, ,完全答对： 23人 基本答对： 29人 完全答错：7 原因分析：对自反性和对称性的证明大都能完成,但对传递性的证明不严密.通过等价关系求划分时候,错误较多.,2019/2/10,计算机学院,31,3、设有函数g：AB和f：BC，使得f g是一个单射，且g是满射。证明f是一个单射。 证明：(反证法) 假定f不是单射，则存在y1和y2 B, 使得y1y2时， f（y1）=f（y2）。 因g是满射，对于y1和y2B，必有x1 和x2A，使得g（x
15、1）=y1，g（x2）=y2， 因g（x1 ）=y1y2=g（x2），故x1x2。 为什么？,2019/2/10,计算机学院,32,这样就有 f g（x1 ）=fg（x1 ）=f（y1 ）=f（y2 ） =fg（x2）= f g（x2）. 这与f g是单射矛盾。 由反证法，因此f是单射。 完全答对： 9人 基本答对： 16人 完全答错：34 原因分析：对概念理解掌握不够,反证法证明不严密.题目本身不严谨.,2019/2/10,计算机学院,33,第四大题,1、在一个盗窃案中，已知如下事实： 王波或者李明是窃贼； 王波是窃贼，作案时间不会发生在夜间12点以前； 若李明的证词正确，则夜间12点时被盗
16、物品所在房间灯光未灭； 若李明的证词不正确，则作案时间发生在夜间12点以前； 夜间12点被盗房间的灯光灭了。 根据以上事实，请通过演绎推理找出偷窃者。,2019/2/10,计算机学院,34,解：设p：王波是窃贼，q：李明是窃贼，r：作案时间在12点以前，s：李明的证词正确， t：夜间12点时被盗物品所在房间灯光熄灭。 符号化为 p q, pr, st, sr, t 。 推理过程如下 1 t P 2 st P 3 s T(1)(2)IE 4 sr P,2019/2/10,计算机学院,35,5 r T(3)(4)IE 6 pr P 7 p T(5)(6)IE 8 p q P 9 q T(7)(8)
17、E 因此，李明是窃贼。 完全答对： 31人 基本答对： 25人 完全答错：3 原因分析：基本都能得到最后的正确结论,但不能按照命题逻辑的推理方法来规范严密地证明.,2019/2/10,计算机学院,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的传递闭包t(R)
18、 即可获得问题的解。,2019/2/10,计算机学院,37,2019/2/10,计算机学院,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,f t(R)a=b，c，d，e，f，g t(R)b=c,d，e，f，g t(R)c=(t(R)-IS)d= e，f t(R)d=e,f t(R)f=e t(R)g=c，e，f,2019/2/10,计算机学院,39,2019/2/10,计算机学院,40,完全答对： 37人 基本答对： 18人 完全答错：4人 原因分析：失分的主要原因是解题时，没有从关系矩阵的传递闭包角度来解答，只写出结果值，没有写出关系矩阵和正确计算传递闭包矩阵。,2019/2/10,计算机学院,41,