冯伟森 Email：fws365scu.edu.cnTel: 13808192275*计算机学院2主要内容 Euler图的应用(计算机鼓轮设计) 半期考试讲评*计算机学院3Euler图的应用计算机鼓轮设计（模数转换问题）：设有旋转 鼓轮其表面被等分成16个部分，如图1所示。 其中每一部分分别用绝缘体或 导体组成，绝缘体部分给出信号0， 导体部分给出信号1，在图中阴影部 分表示导体，空白部分表示绝缘体 ，根据鼓轮的位置，触点将得到信 息1101，如果鼓轮沿顺时针方向旋 转一个部分，触点将有信息1010。 问鼓轮上16个部分怎样安排导体及 绝缘体，才能使鼓轮每旋转一个部 分，四个触点能得到一组不同的四 位二进制数信息。图1*计算机学院4 设有一个八个结点的有 向图（图2 ），其结点分别记为三位二进制数 000，001，010，011， 100，101，110，111， 设ai0，1，从结点 a1a2a3可引出两条有向边 ，其终点分别是a2a30以 及a2a31。该两条边分别 记为a1a2a30和a1a2a31。图2*计算机学院5按照上述方法，对于八个结点的有向图共有16条边，在这种图的任一条路中，其邻接的边必是a1a2a3a4和a2a3a4a5的形式，即是第一条边标号的后三位数与第二条边标号的头三位数相同。*计算机学院6因为图2中16条边被记成不同的二进制数，可见前述鼓轮转动所得到16个不同位置触点上的二进制信息，即对应于图中的一条欧拉回路，由回路中每条边对应码的第一个符号构成的循环序列就是所求结果。*计算机学院7如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8是一条欧拉回路，这16个二进制数可写成对应的二进制数序列0000100110101111。把这个序列排成环状,即与所求的鼓轮相对应。 *计算机学院8上面的例子，我们可以把它推广到鼓轮具有n个触点的情况。为此，我们只要构造2n-1个结点的有向图，设每个结点标记为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分 *计算机学院9第一大题 1、除非天下雨，否则他不开车上班。解： 设：P:天下雨 Q: 他开车上班 QP 或者 PQ完全答对： 49人 基本答对： 0人 完全答错：10原因分析： 分不清楚命题和逻辑谓词之间表示的区别。*计算机学院102、如果f（x）在点x0处可导，则f（x）在点x0处可微。反之亦然。 设：P: f（x）在点x0处可导, Q: f（x）在点x0处可微 PQ完全答对： 52人 基本答对： 0人 完全答错：7原因分析： 分不清楚命题和逻辑谓词之间表示的区别，没有注意到反之亦然是双条件命题。*计算机学院113、男人一定比女人聪明，是不对的。 解：设：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)完全答对： 16人 基本答对： 18人 完全答错：25原因分析：对命题的设定不正确，逻辑混淆。*计算机学院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原因分析： 对题意理解不清*计算机学院135、会叫的狗未必会咬人 解：设：P(x)：x是会叫的狗，Q(x)：x是会咬人的狗 x（P(x)Q(x)）或者 x（ P(x) Q(x)）完全答对： 42人 基本答对： 0人 完全答错：17原因分析： 逻辑谓词的存在量词没有写，对这句话理解有偏差。*计算机学院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)*计算机学院15 主合取范式为（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原因分析：对求主析取范式与主合取范式的方法掌握不够熟练,等价变化过程中不仔细,不能完全正确地得到结果.*计算机学院162、求（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范式的方法*计算机学院17 3、设A=1,2,3,B=a,b,求BA，并指出哪些是单射，哪些是满射，哪些是双射？*计算机学院18解：BA=f0,f1,f2.,f7,其中 f0=, f1=, f2=, f3=, f4=, f5=, f6=, f7=, 其中，除f0 和f7外都是满射。无单射和双射。完全答对：13人 基本答对： 5人 完全答错：41原因分析：对概念理解不清*计算机学院19*计算机学院20 4.A=1,2,3,4,R=,画出R的关系图，写出A的关系矩阵，并求 r(R),s(R),t(R)。2134M (R)=M (R)=*计算机学院21r(R)=RIA=,s(R)=RR1=, ,t(R)=RR2R3R4=, , =, , , , ， *计算机学院22M (r(R)=M (s(R)=完全答对： 27人 基本答对： 26人 完全答错：6原因分析：没有根据图写出关系或关系矩阵R，对r（R）和s（R）错误较少，t（R）错误较多。*计算机学院23 5、设A为72的因子构成的集合，R AA， x,yA, xRy x整除y。画出偏序集的哈斯图，设B=1,2,3,4,6,8,9,12 ，求出B中的最大元，最小元，极大元，极小元，上界，下界，最小上界，最大下界。 解：*计算机学院24最大元无，最小 元1，极大元8、9 、12，极小元1， 上界72，下界1， 最小上界72，最 大下界1 完全答对： 19人 基本答对： 35人 完全答错：5 原因分析：偏序图未能规范地画出;对最大元,最小元,极大元,极小元,上界,下界,最小上界,最大下界等概念理解混淆*计算机学院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)*计算机学院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 *计算机学院27 完全答对： 19人 基本答对： 35人 完全答错：5 原因分析：对命题的符号化不准确,证明过程不规范，逻辑不严密。*计算机学院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。 任取,有AAx-y=x-y R 自反性 *计算机学院30 任取，有R x-y=- -=x-y R对称性 任取，,有 RR x-y=-=s -t x-y=s-t R 传递性 (2) ,， ,， , 完全答对： 23人 基本答对： 29人 完全答错：7 原因分析：对自反性和对称性的证明大都能完成,但对传递性的证明不严密.通过等价关系求划分时候,错误较多.*计算机学院31 3、设有函数g：AB和f：BC，使得f g是一个单射，且g是满射。证明f是一个单射。 证明：(反证法) 假定f不是单射，则存在y1和y2 B, 使得y1y2时 ， f（y1）=f（y2）。 因g是满射，对于y1和y2B