离散数学(第28讲半期考试讲评).ppt
《离散数学(第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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 28 讲半期 考试 讲评
链接地址:https://www.31doc.com/p-2071756.html