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

《离散数学(第28讲半期考试讲评)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、样安排导体及绝缘体，才能使鼓轮每旋转一个部分，四个触点能得到一组不同的四位二进制数信息。图12021/10/1计算机学院4设有一个八个结点的有向图（图2），其结点分别记为三位二进制数{000，001，010，011，100，101，110，111}，设ai∈{0，1>，从结点a1a2a3可引出两条有向边，其终点分别是a2a30以及a2a31。该两条边分别记为a1a2a30和a1a2a31。图22021/10/1计算机学院5按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三

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

4、此，我们只要构造2n-1个结点的有向图，设每个结点标记为n-1位二进制数，从结点12…n出发，有一条终点为23…n-10的边，该边记为12…n-10；还有一条边的终点为23…n-11的边，该边记为12…n-11。这样构造的有向图，其每一结点的出度和入度都是2，故必是欧拉图。由于邻接边的标记是第一条边的后n-1位二进制数与第二条边的前n-1位二进制数相同，为此就有一种2n个二进制数的环形排列与所求的鼓轮相对应。考试情况参加考试共59人。90分以上3人，80~89分7人，70~79分9人，60~69分19人，50~59分7人，50以下14人。

5、平均成绩61.30分2021/10/1计算机学院9第一大题1、除非天下雨，否则他不开车上班。解：设：P:天下雨Q:他开车上班Q→P或者～P→～Q完全答对：49人基本答对：0人完全答错：10原因分析：分不清楚命题和逻辑谓词之间表示的区别。2021/10/1计算机学院102、如果f（x）在点x0处可导，则f（x）在点x0处可微。反之亦然。设：P:f（x）在点x0处可导,Q:f（x）在点x0处可微PQ完全答对：52人基本答对：0人完全答错：7原因分析：分不清楚命题和逻辑谓词之间表示的区别，没有注意到反之亦然是双条件命题。2021/10/1计算机学院113、男人一定比女人聪

6、明，是不对的。解：设：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原因分析：对命题的设定不正确，逻辑混淆。2021/10/1计算机学院124、两个不相等的实数间，必存在第三个实数。解：设：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原因分

7、析：对题意理解不清2021/10/1计算机学院135、会叫的狗未必会咬人解：设：P(x)：x是会叫的狗，Q(x)：x是会咬人的狗x（P(x)∧～Q(x)）或者～x（P(x)→Q(x)）完全答对：42人基本答对：0人完全答错：17原因分析：逻辑谓词的存在量词没有写，对这句话理解有偏差。2021/10/1计算机学院14第二大题：计算题1、用公式转换法求（p→q∧r）∧(～p→(～q∧～r))的主合取范式和主析取范式。解：（p→q∧r）∧(~p→(~q∧~r))(~p(q∧r))∧(p(~q∧~r))(~pq)∧(~pr)∧(p~q)∧(p~r)(p∨