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

冯伟森 Email fws365 Tel 138081922752020年4月1日星期三 离散数学 计算机学院 2020 4 1 计算机学院 2 主要内容 Euler图的应用 计算机鼓轮设计 半期考试讲评 2020 4 1 计算机学院 3 Euler图的应用 计算机鼓轮设计 模数转换问题 设有旋转鼓轮其表面被等分成16个部分 如图1所示 其中每一部分分别用绝缘体或导体组成 绝缘体部分给出信号0 导体部分给出信号1 在图中阴影部分表示导体 空白部分表示绝缘体 根据鼓轮的位置 触点将得到信息1101 如果鼓轮沿顺时针方向旋转一个部分 触点将有信息1010 问鼓轮上16个部分怎样安排导体及绝缘体 才能使鼓轮每旋转一个部分 四个触点能得到一组不同的四位二进制数信息 图1 2020 4 1 计算机学院 4 设有一个八个结点的有向图 图2 其结点分别记为三位二进制数 000 001 010 011 100 101 110 111 设ai 0 1 从结点a1a2a3可引出两条有向边 其终点分别是a2a30以及a2a31 该两条边分别记为a1a2a30和a1a2a31 图2 2020 4 1 计算机学院 5 按照上述方法 对于八个结点的有向图共有16条边 在这种图的任一条路中 其邻接的边必是a1a2a3a4和a2a3a4a5的形式 即是第一条边标号的后三位数与第二条边标号的头三位数相同 2020 4 1 计算机学院 6 因为图2中16条边被记成不同的二进制数 可见前述鼓轮转动所得到16个不同位置触点上的二进制信息 即对应于图中的一条欧拉回路 由回路中每条边对应码的第一个符号构成的循环序列就是所求结果 2020 4 1 计算机学院 7 如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8是一条欧拉回路 这16个二进制数可写成对应的二进制数序列0000100110101111 把这个序列排成环状 即与所求的鼓轮相对应 2020 4 1 计算机学院 8 上面的例子 我们可以把它推广到鼓轮具有n个触点的情况 为此 我们只要构造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人 平均成绩61 30分 2020 4 1 计算机学院 9 第一大题 1 除非天下雨 否则他不开车上班 解 设 P 天下雨Q 他开车上班Q P或者 P Q完全答对 49人基本答对 0人完全答错 10原因分析 分不清楚命题和逻辑谓词之间表示的区别 2020 4 1 计算机学院 10 2 如果f x 在点x0处可导 则f x 在点x0处可微 反之亦然 设 P f x 在点x0处可导 Q f x 在点x0处可微P Q完全答对 52人基本答对 0人完全答错 7原因分析 分不清楚命题和逻辑谓词之间表示的区别 没有注意到反之亦然是双条件命题 2020 4 1 计算机学院 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原因分析 对命题的设定不正确 逻辑混淆 2020 4 1 计算机学院 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原因分析 对题意理解不清 2020 4 1 计算机学院 13 5 会叫的狗未必会咬人解 设 P x x是会叫的狗 Q x x是会咬人的狗 x P x Q x 或者 x P x Q x 完全答对 42人基本答对 0人完全答错 17原因分析 逻辑谓词的存在量词没有写 对这句话理解有偏差 2020 4 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 q r p q r p q r p q r p q r p q r 2020 4 1 计算机学院 15 主合取范式为 p q r p q r p q r p q r p q r p q r 又因为在主合取范式中和没有出现 因而 主析取范式应为M7 M0 即 p q r p q r 完全答对 35人基本答对 19人完全答错 5原因分析 对求主析取范式与主合取范式的方法掌握不够熟练 等价变化过程中不仔细 不能完全正确地得到结果 2020 4 1 计算机学院 16 2 求 xP x yQ y xR x 的Skolem范式解 xP x yQ y xR x xP x yQ y xR x xP x yQ y zR z x P x y Q y zR z x y z P x Q y R z 完全答对 28人基本答对 15人完全答错 16原因分析 没有掌握求Skolem范式的方法 2020 4 1 计算机学院 17 3 设A 1 2 3 B a b 求BA 并指出哪些是单射 哪些是满射 哪些是双射 2020 4 1 计算机学院 18 解 BA f0 f1 f2 f7 其中f0 f1 f2 f3 f4 f5 f6 f7 其中 除f0和f7外都是满射 无单射和双射 完全答对 13人基本答对 5人完全答错 41原因分析 对概念理解不清 2020 4 1 计算机学院 19 2020 4 1 计算机学院 20 4 A 1 2 3 4 R 画出R的关系图 写出A的关系矩阵 并求r R s R t R M R M R 2020 4 1 计算机学院 21 r R R IA s R R R1 t R R R2 R3 R4 2020 4 1 计算机学院 22 M r R M s R 完全答对 27人基本答对 26人完全答错 6原因分析 没有根据图写出关系或关系矩阵R 对r R 和s R 错误较少 t R 错误较多 2020 4 1 计算机学院 23 5 设A为72的因子构成的集合 RA A x y A xRyx整除y 画出偏序集的哈斯图 设B 1 2 3 4 6 8 9 12 求出B中的最大元 最小元 极大元 极小元 上界 下界 最小上界 最大下界 解 2020 4 1 计算机学院 24 最大元无 最小元1 极大元8 9 12 极小元1 上界72 下界1 最小上界72 最大下界1 完全答对 19人基本答对 35人完全答错 5原因分析 偏序图未能规范地画出 对最大元 最小元 极大元 极小元 上界 下界 最小上界 最大下界等概念理解混淆 2020 4 1 计算机学院 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 2020 4 1 计算机学院 26 1 x N x F x P2N c F c T 1 ES3 x E x N x F x P4E c N c F c T 3 US5 E c T 2 4 I6 x N x O x E x P7O c E c T 6 US8O c T 5 7 I9 xO x T 8 EG 2020 4 1 计算机学院 27 完全答对 19人基本答对 35人完全答错 5原因分析 对命题的符号化不准确 证明过程不规范 逻辑不严密 2020 4 1 计算机学院 28 2020 4 1 计算机学院 29 2 设A 1 2 3 4 在A A上定义二元关系R A A R y x 1 证明R是A A上的等价关系 2 确定由R导出的对集合A A的划分 证明 1 注意到R y x x y 任取 有 A A x y x y R自反性 2020 4 1 计算机学院 30 任取 有R x y x y R对称性任取 有R R x y s t x y s t R传递性 2 完全答对 23人基本答对 29人完全答错 7原因分析 对自反性和对称性的证明大都能完成 但对传递性的证明不严密 通过等价关系求划分时候 错误较多 2020 4 1 计算机学院 31 3 设有函数g A B和f B C 使得f g是一个单射 且g是满射 证明f是一个单射 证明 反证法 假定f不是单射 则存在y1和y2 B 使得y1 y2时 f y1 f y2 因g是满射 对于y1和y2 B 必有x1和x2 A 使得g x1 y1 g x2 y2 因g x1 y1 y2 g x2 故x1 x2 为什么 2020 4 1 计算机学院 32 这样就有f g x1 f g x1 f y1 f y2 f g x2 f g x2 这与f g是单射矛盾 由反证法 因此f是单射 完全答对 9人基本答对 16人完全答错 34原因分析 对概念理解掌握不够 反证法证明不严密 题目本身不严谨 2020 4 1 计算机学院 33 第四大题 1 在一个盗窃案中 已知如下事实 王波或者李明是窃贼 王波是窃贼 作案时间不会发生在夜间12点以前 若李明的证词正确 则夜间12点时被盗物品所在房间灯光未灭 若李明的证词不正确 则作案时间发生在夜间12点以前 夜间12点被盗房间的灯光灭了 根据以上事实 请通过演绎推理找出偷窃者 2020 4 1 计算机学院 34 解 设p 王波是窃贼 q 李明是窃贼 r 作案时间在12点以前 s 李明的证词正确 t 夜间12点时被盗物品所在房间灯光熄灭 符号化为p q p r s t s r t 推理过程如下1tP2s tP3 sT 1 2 IE4 s rP 2020 4 1 计算机学院 35 5rT 3 4 IE6p rP7 pT 5 6 IE8p qP9qT 7 8 E因此 李明是窃贼 完全答对 31人基本答对 25人完全答错 3原因分析 基本都能得到最后的正确结论 但不能按照命题逻辑的推理方法来规范严密地证明 2020 4 1 计算机学院 36 2 道路网络上连接有7个城市 分别为a b c d e f g 城市之间直接连接的道路是单向的有a b a c b g g c c f f e b d d f 对每个城市求出从它出发能够到达的所有其它城市 解 令S a b c d e f g 定义S上的关系R如下 x y R 从x到y有一条直接的道路R a b a c b g g c c f f e b d d f 求出R的传递闭包t R 即可获得问题的解 2020 4 1 计算机学院 37 2020 4 1 计算机学院 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