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

1、冯伟森冯伟森Email：Tel: 138081922752021年年10月月26日星期二日星期二2021-10-262021-10-26计算机学院计算机学院2 2主要内容主要内容第一大题第一大题1、只有不怕困难，才能战胜困难；、只有不怕困难，才能战胜困难；解：解： p：怕困难，：怕困难， q：战胜困难：战胜困难 q p or p q完全答对：完全答对： 37人人 基本答对：基本答对： 7人人 完全答错：完全答错：0原因分析：原因分析： 分不清楚命题和逻辑谓词之间表示的分不清楚命题和逻辑谓词之间表示的区别。区别。2021-10-262021-10-26计算机学院计算机学院3 32、整数、整数n

2、是偶数当且仅当是偶数当且仅当n能被能被2整除整除.；解：解：p:整数整数n是偶数，是偶数，q:整数整数n能被能被2整除整除 pq完全答对：完全答对： 26人人 基本答对：基本答对： 17人人 完全答错：完全答错：1原因分析：原因分析： 分不清楚命题和逻辑谓词之间表示的分不清楚命题和逻辑谓词之间表示的区别，没有注意到当且仅当是双条件命题。区别，没有注意到当且仅当是双条件命题。2021-10-262021-10-26计算机学院计算机学院4 43、发明家都是聪明的并且是勤劳的，王前进是、发明家都是聪明的并且是勤劳的，王前进是发明家，所以王前进是聪明的并且是勤劳的；发明家，所以王前进是聪明的并且是勤劳

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原因分析：原因分析： 逻辑谓词的全称量词没有写，或者逻辑谓词的全称量词没有写，或者逻辑混淆。逻辑混淆。2021-10-262021-10-26计算机学院计算机学院5 54、若、若x与与y都是实数，且都是实数，且 xy，则，则 x+2y+2；解：解： F(x)：x是实数，是实数，H(x，y)：xy x y(F(x)F(y)H(x

4、,y)H(x+2，x+2)完全答对：完全答对： 20人人 基本答对：基本答对： 22人人 完全答错：完全答错：2原因分析：原因分析： 逻辑谓词的全称量词没有写。逻辑谓词的全称量词没有写。2021-10-262021-10-26计算机学院计算机学院6 65、不存在最大的自然数。、不存在最大的自然数。解：解： 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原因分析：原因分析： 逻辑谓词的存在量词和全称量词没逻辑谓词的存在量词

5、和全称量词没有写，对这句话理解很多人不是很清楚。有写，对这句话理解很多人不是很清楚。2021-10-262021-10-26计算机学院计算机学院7 7第二大题第二大题1、用等价变换法求下列公式的主析取范式和主、用等价变换法求下列公式的主析取范式和主合取范式合取范式2021-10-262021-10-26计算机学院计算机学院8 8)pq()qp()qp(主合取式主析取式 )pq()pq()qp()pp(q()qp( )qp(q)qp()q)pq()pq(q()pq(q)pq()qp()qp(完全答对：完全答对： 27人人 基本答对：基本答对： 5人人 完全答错：完全答错：12原因分析：原因分析：

6、对命题公式不熟悉，计算错误。对命题公式不熟悉，计算错误。2021-10-262021-10-26计算机学院计算机学院9 92、求、求2A，其中，其中A=，a，b；解：解：2A=，,a,b,a，,b,a，b,A完全答对：完全答对： 35人人 基本答对：基本答对： 0人人 完全答错：完全答错：9原因分析：原因分析：典型错误是少写一个典型错误是少写一个，或，或。2021-10-262021-10-26计算机学院计算机学院10103、假设、假设R的关系图如图所示，试给出的关系图如图所示，试给出r（R）、）、s（R）、）、t（R）的关系矩阵）的关系矩阵M（r（R）、）、M（s（R）、）、M（t（R）。）

7、。2021-10-262021-10-26计算机学院计算机学院11111 0 0 0 00 0 1 0 00 1 0 0 01 0 1 0 00 0 0 1 0R2021-10-262021-10-26计算机学院计算机学院12121 0 0 0 00 1 1 0 00 1 1 0 01 0 1 1 00 0 0 1 1)R(r(M1 0 0 1 00 0 1 0 00 1 0 1 01 0 1 0 10 0 0 1 0)R(s(M1 0 0 0 00 1 1 0 00 1 1 0 01 1 1 0 01 1 1 1 0)R(t(M完全答对：完全答对： 14人人 基本答对：基本答对： 26人人

8、完全答错：完全答错：4原因分析：原因分析：没有根据图写出关系或关系矩阵没有根据图写出关系或关系矩阵R，对对r（R）和）和s（R）错误较少，）错误较少，t（R）错误较）错误较多，可能是对多，可能是对warshall算法不了解或不熟悉。算法不了解或不熟悉。2021-10-262021-10-26计算机学院计算机学院13134、如图是偏序集、如图是偏序集 的哈斯图，求的哈斯图，求X和和的集的集合表达式，合表达式， 并指出该偏序集的极大元、极小并指出该偏序集的极大元、极小元、最大元、最小元。元、最大元、最小元。 解：解：X=a,b,c,d,e,f =a,b, a,c, a,d, a,e, a,f, b

9、,e, c,e, c,f, d,fIX 极大元极大元e,f；极小元；极小元a；最大元不存在，最小元；最大元不存在，最小元a；2021-10-262021-10-26计算机学院计算机学院1414,X 完全答对：完全答对： 6人人 基本答对：基本答对： 33人人 完全答错：完全答错：5 原因分析：原因分析：偏序关系写对的人很少，大部分写偏序关系写对的人很少，大部分写的是的是 =a,b, a,c, a,d, a,e, a,f, b,e, c,e, c,f, d,f缺少缺少Ix2021-10-262021-10-26计算机学院计算机学院1515 5、设、设 求求2021-10-262021-10-26

10、计算机学院计算机学院16162,3:,( ), :, ( )22,3xxRRxRRxxx, 3 x, 03x, 2x)x(1 x, 21x,)2x()x(22 完全答对：完全答对： 32人人 基本答对：基本答对： 5人人 完全答错：完全答错：7 原因分析：原因分析：如果按函数的算对的比较多，按关如果按函数的算对的比较多，按关系的有一个，其他的错误是按函数算，但定义系的有一个，其他的错误是按函数算，但定义域没写对。域没写对。2021-10-262021-10-26计算机学院计算机学院1717第三大题第三大题 1、用、用CP规则证明下面推理规则证明下面推理前提前提: 结论结论: 2021-10-2

11、62021-10-26计算机学院计算机学院1818() ,pqrspqrs P )rq(p)6 T4)E )rq()5 Morgan) De )qr()4I2T1 qr)3P q)2 P r)1（）（附加前提） 完全答对：完全答对： 27人人 基本答对：基本答对： 11人人 完全答错：完全答错：6 原因分析：原因分析：采用采用CP规则推理时，没有严格的按规则推理时，没有严格的按逻辑推理，有些关键步骤被省略，对推理中使逻辑推理，有些关键步骤被省略，对推理中使用的规则使用不当。有些不了解规则。用的规则使用不当。有些不了解规则。2021-10-262021-10-26计算机学院计算机学院1919规则

12、拒取式）基本等价式、拒取式） CP sr)10I(8T7 s)9P ps )8T5)6)I( p)7 2、用反证法证明下面推理、用反证法证明下面推理 前提前提: 结论结论: 2021-10-262021-10-26计算机学院计算机学院2020(),pqrpqrs（假言推理）（简化法则）（附加前提） I5T4 rq)6P )rq(p)5IT3 p)4P qp)3ET1 sr)2P )sr()1 完全答对：完全答对： 22人人 基本答对：基本答对： 20人人 完全答错：完全答错：2 原因分析原因分析：没有严格的按逻辑推理，有些关键：没有严格的按逻辑推理，有些关键步骤被省略。步骤被省略。2021-1

13、0-262021-10-26计算机学院计算机学院2121（矛盾式）（简化法则）（假言推理）（简化法则）F)10IT2 r)9 I7T6 r )8 IT3 q)7 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) x y (F(x) (G(y)H(x) 3）辖域扩张）辖域扩张 5) y (F(c) (G(y)H(c) 4）UI 6) F(c) (G(c)H(c)

14、5）UI 2021-10-262021-10-26计算机学院计算机学院2222 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 原因分析：原因分析：对含有谓词公式的推理，错的人比对含有谓词公式的推理，错的人比较多，主要是对规则的不熟悉，规则使用时应较多，主要是对规则的不熟悉，规则使用时应该注意的条件没有注意。该注意的条件没有注意。2021-10-262021-10-26计算机学院计算机学院2323 4、设

15、、设R是是A 上的自反和传递关系，如下定义上的自反和传递关系，如下定义A上的关系上的关系T，使得，使得 x,yA TRR 证明证明T是是A上的等价关系。上的等价关系。 证明：证明：1）R是自反的是自反的 ， R ，即，即T，T是自反的是自反的 2） 显然，显然，T是对称的是对称的 3） 设设T，T,由由T的定义有的定义有 RR2021-10-262021-10-26计算机学院计算机学院2424 RR，由，由R的传递性，有的传递性，有RR 即即T，T是传递的是传递的 故故T是是A上的等价关系上的等价关系 完全答对：完全答对： 24人人 基本答对：基本答对： 9人人 完全答错：完全答错：11原因分

16、析：原因分析：这道题的正确率比较高，错的人主要这道题的正确率比较高，错的人主要是传递性证明出错，对传递性的定义不了解。是传递性证明出错，对传递性的定义不了解。2021-10-262021-10-26计算机学院计算机学院2525 5、设、设f:A B 为单射函数，为单射函数， 为为X 在在f 下的像。证明下的像。证明 G也是单射的。也是单射的。 解：假设解：假设 A1，A2 2A ，A1 A2， 不妨设存在不妨设存在x使得使得x A1x A2， 所以所以 f(x) f(A1) 且且f(x) f(A2) 于是于是 f（A1） f(A2) 故故 G(A1) G(A2) 2021-10-262021-

17、10-26计算机学院计算机学院2626 完全答对：完全答对： 6人人 基本答对：基本答对： 15人人 完全答错：完全答错：23 原因分析：这道题错误率比较高，对原因分析：这道题错误率比较高，对G（X）为为X在在f下的像理解不清楚，没有注意到，下的像理解不清楚，没有注意到，f(x) f(A1) 且且f(x) f(A2)。2021-10-262021-10-26计算机学院计算机学院2727第四大题第四大题 在一个道路网络上连接有在一个道路网络上连接有8个城市，分别标记为个城市，分别标记为a,b,c,d,e,f,g,h；城市之间的直接连接的道路有；城市之间的直接连接的道路有ab,ac,bg,gb,c

18、f,fe,bd,df。对每。对每个城市求出从它出发能够到达的所有其它城市个城市求出从它出发能够到达的所有其它城市。 解：令解：令 S=a,b,c,d,e,f,g,h 定义定义S上的关系上的关系R 如如下下:x,y R 从从a到到b有一条直接的道路有一条直接的道路2021-10-262021-10-26计算机学院计算机学院2828 R=a,b,a,c, b,g, g,b, c,f, f,e, b,d, d,f, 求出求出R的传递闭包的传递闭包t(R) 即可获得问题的解。即可获得问题的解。2021-10-262021-10-26计算机学院计算机学院2929000 000010000 0100000000010 1100 0000 0000000010000110MR100 111010000 0100000000011 1111 1111 0000000010101110M)R( t (t(R)-IS)a=b，c，d，e，f，g (t(R)