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

1、,email： tel:2020年7月5日星期日,离散数学,计算机学院,2020/7/5,计算机学院,2,主要内容,半 期 考 试 讲 评,2020/7/5,计算机学院,3,第一大题,1、只有不怕困难，才能战胜困难； 解： p：怕困难， q：战胜困难 qp or pq 完全答对： 37人 基本答对： 7人 完全答错：0 原因分析： 分不清楚命题和逻辑谓词之间表示的区别。,2020/7/5,计算机学院,4,2、整数n 是偶数当且仅当n能被2整除.； 解：p:整数n是偶数，q:整数n能被2整除 pq 完全答对： 26人 基本答对： 17人 完全答错：1 原因分析： 分不清

2、楚命题和逻辑谓词之间表示的区别，没有注意到当且仅当是双条件命题。,2020/7/5,计算机学院,5,3、发明家都是聪明的并且是勤劳的，王前进是发明家，所以王前进是聪明的并且是勤劳的； 解： f(x)：x是发明家，g(x)：x是聪明的，h(x)：x是勤劳的，a：王前进 (x(f(x)(g(x)h(x) f(a)g(a)h(a) 完全答对： 7人 基本答对： 31人 完全答错：5 原因分析： 逻辑谓词的全称量词没有写，或者逻辑混淆。,2020/7/5,计算机学院,6,4、若x与y都是实数，且 xy，则 x+2y+2； 解： f(x)：x是实数，h(x，y)：xy xy(f(x)f(y)h(x,y)

3、h(x+2，x+2) 完全答对： 20人 基本答对： 22人 完全答错：2 原因分析： 逻辑谓词的全称量词没有写。,2020/7/5,计算机学院,7,5、不存在最大的自然数。 解： f(x)：x是实数，h(x，y)： xy x (f(x)y(f(y)h(x,y) 或 x(f(x) y(f(y)h(x,y) 完全答对： 5人 基本答对： 24人 完全答错：15 原因分析： 逻辑谓词的存在量词和全称量词没有写，对这句话理解很多人不是很清楚。,2020/7/5,计算机学院,8,第二大题,1、用等价变换法求下列公式的主析取范式和主合取范式,2020/7/5,计算机学院,9,完全答对： 27人 基本答对

4、： 5人 完全答错：12 原因分析：对命题公式不熟悉，计算错误。,2020/7/5,计算机学院,10,2、求2a，其中a=，a，b； 解：2a= ，,a,b,a，,b,a，b,a 完全答对： 35人 基本答对： 0人 完全答错：9 原因分析：典型错误是少写一个，或。,2020/7/5,计算机学院,11,3、假设r的关系图如图所示，试给出r（r）、s（r）、t（r）的关系矩阵m（r（r）、m（s（r）、m（t（r）。,2020/7/5,计算机学院,12,2020/7/5,计算机学院,13,完全答对： 14人 基本答对： 26人 完全答错：4 原因分析：没有根据图写出关系或关系矩阵r，对r（r）和

5、s（r）错误较少，t（r）错误较多，可能是对warshall算法不了解或不熟悉。,2020/7/5,计算机学院,14,4、如图是偏序集 的哈斯图，求x和的集合表达式， 并指出该偏序集的极大元、极小元、最大元、最小元。 解：x=a,b,c,d,e,f =a,b, a,c, a,d, a,e, a,f, b,e, c,e, c,f, d,fix 极大元e,f；极小元a；最大元不存在，最小元a；,2020/7/5,计算机学院,15,完全答对： 6人 基本答对： 33人 完全答错：5 原因分析：偏序关系写对的人很少，大部分写的是 =a,b, a,c, a,d, a,e, a,f, b,e, c,e,

6、c,f, d,f缺少ix,2020/7/5,计算机学院,16,5、设 求,2020/7/5,计算机学院,17,完全答对： 32人 基本答对： 5人 完全答错：7 原因分析：如果按函数的算对的比较多，按关系的有一个，其他的错误是按函数算，但定义域没写对。,2020/7/5,计算机学院,18,第三大题,1、用cp规则证明下面推理 前提: 结论:,2020/7/5,计算机学院,19,完全答对： 27人 基本答对： 11人 完全答错：6 原因分析：采用cp规则推理时，没有严格的按逻辑推理，有些关键步骤被省略，对推理中使用的规则使用不当。有些不了解规则。,2020/7/5,计算机学院,20,2、用反证法

7、证明下面推理 前提: 结论:,2020/7/5,计算机学院,21,完全答对： 22人 基本答对： 20人 完全答错：2 原因分析：没有严格的按逻辑推理，有些关键步骤被省略。,2020/7/5,计算机学院,22,3、构造下面推理的证明 前提: x(f(x)y(g(y)h(x) ， xf(x) 结论: x(f(x)g(x)h(x) 解：1）xf(x) 前提引入 2) f(c) 1）ei 3) x(f(x)y(g(y)h(x) 前提引入 4) xy (f(x) (g(y)h(x) 3）辖域扩张 5) y (f(c) (g(y)h(c) 4）ui 6) f(c) (g(c)h(c) 5）ui,2020

8、/7/5,计算机学院,23,7) g(c)h(c) 2）6）假言推理 8) f(c)g(c)h(c) 2）7）合取 9) x(f(x)g(x)h(x) 8）eg 完全答对： 13人 基本答对： 10人 完全答错：21 原因分析：对含有谓词公式的推理，错的人比较多，主要是对规则的不熟悉，规则使用时应该注意的条件没有注意。,2020/7/5,计算机学院,24,4、设r是a 上的自反和传递关系，如下定义a上的关系t，使得x,ya trr 证明t是a上的等价关系。 证明：1）r是自反的 ， r ，即t，t是自反的 2） 显然，t是对称的 3） 设t，t,由t的定义有 rr,2020/7/5,计算机学院

9、,25,rr，由r的传递性，有rr 即t，t是传递的 故t是a上的等价关系 完全答对： 24人 基本答对： 9人 完全答错：11 原因分析：这道题的正确率比较高，错的人主要是传递性证明出错，对传递性的定义不了解。,2020/7/5,计算机学院,26,5、设f:a b 为单射函数， 为x 在f 下的像。证明 g也是单射的。 解：假设 a1，a2 2a ，a1a2， 不妨设存在x使得xa1xa2， 所以 f(x)f(a1) 且f(x)f(a2) 于是 f（a1）f(a2) 故 g(a1)g(a2),2020/7/5,计算机学院,27,完全答对： 6人 基本答对： 15人 完全答错：23 原因分析：

10、这道题错误率比较高，对g（x）为x在f下的像理解不清楚，没有注意到，f(x)f(a1) 且f(x)f(a2)。,2020/7/5,计算机学院,28,第四大题,在一个道路网络上连接有8个城市，分别标记为a,b,c,d,e,f,g,h；城市之间的直接连接的道路有ab,ac,bg,gb,cf,fe,bd,df。对每个城市求出从它出发能够到达的所有其它城市。 解：令 s=a,b,c,d,e,f,g,h 定义s上的关系r 如下:x,yr 从a到b有一条直接的道路,2020/7/5,计算机学院,29,r=a,b,a,c, b,g, g,b, c,f, f,e, b,d, d,f, 求出r的传递闭包t(r) 即可获得问题的解。,2020/7/5,计算机学院,30,(t(r)-is)a=b，c，d，e，f，g (t(r)-is)b=d，e，f，g