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

冯伟森,Email：fws365Tel:138081922752020年6月8日星期一,离散数学,计算机学院,2020/6/8,计算机学院,2,主要内容,半期考试讲评,第一大题,1、只有不怕困难，才能战胜困难；解：p：怕困难，q：战胜困难qporpq完全答对：37人基本答对：7人完全答错：0原因分析：分不清楚命题和逻辑谓词之间表示的区别。,2020/6/8,计算机学院,3,2、整数n是偶数当且仅当n能被2整除.；解：p:整数n是偶数，q:整数n能被2整除pq完全答对：26人基本答对：17人完全答错：1原因分析：分不清楚命题和逻辑谓词之间表示的区别，没有注意到当且仅当是双条件命题。,2020/6/8,计算机学院,4,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/6/8,计算机学院,5,4、若x与y都是实数，且xy，则x+2y+2；解：F(x)：x是实数，H(x，y)：xyxy(F(x)F(y)H(x,y)H(x+2，x+2)完全答对：20人基本答对：22人完全答错：2原因分析：逻辑谓词的全称量词没有写。,2020/6/8,计算机学院,6,5、不存在最大的自然数。解：F(x)：x是实数，H(x，y)：xyx(F(x)y(F(y)H(x,y)或x(F(x)y(F(y)H(x,y)完全答对：5人基本答对：24人完全答错：15原因分析：逻辑谓词的存在量词和全称量词没有写，对这句话理解很多人不是很清楚。,2020/6/8,计算机学院,7,第二大题,1、用等价变换法求下列公式的主析取范式和主合取范式,2020/6/8,计算机学院,8,完全答对：27人基本答对：5人完全答错：12原因分析：对命题公式不熟悉，计算错误。,2020/6/8,计算机学院,9,2、求2A，其中A=，a，b；解：2A=，,a,b,a，,b,a，b,A完全答对：35人基本答对：0人完全答错：9原因分析：典型错误是少写一个，或。,2020/6/8,计算机学院,10,3、假设R的关系图如图所示，试给出r（R）、s（R）、t（R）的关系矩阵M（r（R）、M（s（R）、M（t（R）。,2020/6/8,计算机学院,11,2020/6/8,计算机学院,12,完全答对：14人基本答对：26人完全答错：4原因分析：没有根据图写出关系或关系矩阵R，对r（R）和s（R）错误较少，t（R）错误较多，可能是对warshall算法不了解或不熟悉。,2020/6/8,计算机学院,13,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/6/8,计算机学院,14,完全答对：6人基本答对：33人完全答错：5原因分析：偏序关系写对的人很少，大部分写的是=a,b,a,c,a,d,a,e,a,f,b,e,c,e,c,f,d,f缺少Ix,2020/6/8,计算机学院,15,5、设求,2020/6/8,计算机学院,16,完全答对：32人基本答对：5人完全答错：7原因分析：如果按函数的算对的比较多，按关系的有一个，其他的错误是按函数算，但定义域没写对。,2020/6/8,计算机学院,17,第三大题,1、用CP规则证明下面推理前提:结论:,2020/6/8,计算机学院,18,完全答对：27人基本答对：11人完全答错：6原因分析：采用CP规则推理时，没有严格的按逻辑推理，有些关键步骤被省略，对推理中使用的规则使用不当。有些不了解规则。,2020/6/8,计算机学院,19,2、用反证法证明下面推理前提:结论:,2020/6/8,计算机学院,20,完全答对：22人基本答对：20人完全答错：2原因分析：没有严格的按逻辑推理，有些关键步骤被省略。,2020/6/8,计算机学院,21,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）EI3)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）UI6)F(c)(G(c)H(c)5）UI,2020/6/8,计算机学院,22,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/6/8,计算机学院,23,4、设R是A上的自反和传递关系，如下定义A上的关系T，使得x,yATRR证明T是A上的等价关系。证明：1）R是自反的，R，即T，T是自反的2）显然，T是对称的3）设T，T,由T的定义有RR,2020/6/8,计算机学院,24,RR，由R的传递性，有RR即T，T是传递的故T是A上的等价关系完全答对：24人基本答对：9人完全答错：11原因分析：这道题的正确率比较高，错的人主要是传递性证明出错，对传递性的定义不了解。,2020/6/8,计算机学院,25,5、设f:AB为单射函数，为X在f下的像。证明G也是单射的。解：假设A1，A22A，A1A2，不妨设存在x使得xA1xA2，所以f(x)f(A1)且f(x)f(A2)于是f（A1）f(A2)故G(A1)G(A2),2020/6/8,计算机学院,26,完全答对：6人基本答对：15人完全答错：23原因分析：这道题错误率比较高，对G（X）为X在f下的像理解不清楚，没有注意到，f(x)f(A1)且f(x)f(A2)。,2020/6/8,计算机学院,27,第四大题,在一个道路网络上连接有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/6/8,计算机学院,28,R=a,b,a,c,b,g,g,b,c,f,f,e,b,d,d,f,求出R的传递闭包t(R)即可获得问题的解。,2020/6/8,计算机学院,29,(t(R)-IS)a=b，c，d，e，f，g(t(R)-IS)b=d，e，f，g(t(R)-IS)c=(t(R)-IS)