离散数学(第16讲习题课3).pptxVIP

冯伟森Email：08 三月 2023离散　　数学计算机学院第一页，共三十页。 2023/3/8计算机学院2习题课三第二页，共三十页。 2023/3/8计算机学院3基本要求正确理解幂集、笛卡尔集和关系的定义；能正确使用集合表达式，关系矩阵，关系图表示给定的二元关系；熟练掌握关系的各种运算，特别是复合运算和逆运算；牢记关系的5个性质的定义，对给定A上的关系R，能用三种方式（集合、矩阵、图）判断该关系R所具有的性质；第三页，共三十页。 2023/3/8计算机学院4基本要求正确理解关系运算的性质熟练掌握关系的闭包的概念和性质；掌握用矩阵计算传递闭包的Warshall(1962)算法； 能正确理解闭包运算；熟练掌握等价关系、等价类的定义；正确理解集合的划分(分划)；熟练掌握偏序关系、偏序集、哈斯图等概念； 熟练掌握由关系图得到哈斯图的方法；第四页，共三十页。 2023/3/8计算机学院5基本要求熟练掌握偏序集中特定元素的计算；掌握全序关系、良序关系、良序集等概念；掌握对给定的有限偏序集构造全序集的拓扑排序算法；能正确使用按定义证明的方法进行关系的性质和特殊关系的证明 。第五页，共三十页。 2023/3/8计算机学院6例1设A＝{a,b,c,d,e,f},定义在A上的关系R＝{<a,a>,<a,b>,<b,c>,<c,d>,<d,e>,<e,f>}，S＝{<a,b>,<b,c>,<c,d>,<d,e>,<e,f>},求Rn和Sn。解　R1＝R， R2＝R?R＝{<a,a>,<a,b>,<a,c>,<b,d>,<c,e>,<d,f>}，　R3＝R?R?R＝R2?R＝{<a,a>,<a,b>,<a,c>,<a,d>,<b,e>,<c,f>}，　R4＝R3?R＝{<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<b,f>}，　R5＝R4?R＝{<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<a,f>}，　R6＝R5?R＝{<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<a,f>}＝R5，　R7＝R6?R＝R5，…，Rn＝R5　(n＞5)。第六页，共三十页。 2023/3/8计算机学院7　S1＝S={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>},例1(续)　S2＝S?S＝{<a,c>,<b,d>,<c,e>,<d,f>}，　S3＝S?S?S＝S2?S＝{<a,d>,<b,e>,<c,f>}，　S4＝S3?S＝{<a,e>,<b,f>}，　S5＝S4?S＝{<a,f>}，　S6＝S5?S＝Φ，　S7＝Φ，…，　Sn＝Φ　(n＞5)。第七页，共三十页。 2023/3/8计算机学院8例2 设集合A的元素数为n，R是A上二元关系，那么存在自然数i，j(0?i?j? )使得Ri=Rj。证明：由关系的特点知道，若?A?=n，则A上的关系有 个，因此，在 R0，R1，R2，…，这 +1个关系中，至少有两个是相同的（鸽巢原理），即有i,j(0?i?j? )使得Ri=Rj。 如果k+1个或更多的物体放入k个盒子，那么至少有一个盒子包含了2个或更多的物体。第八页，共三十页。 2023/3/8计算机学院9例3解先求A的划分：只有1个划分块的划分为П1，具有2个设A={a,b,c}，求A上所有的等价关系。 划分块的划分为П2、П3和П4，具有3个划分块的划分为П5，如下图所示。设Пi导出的等价关系为Пi，i=1,2,3,4,5。则有R1={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,a>,<c,b>,<c,c>}=A?A；R2={<a,a>,<b,b>,<b,c>,<c,b>,<c,c>}；R3={<a,a>,<a,c>,<b,b>,<c,a>,<c,c>}；R4={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>}；R5={<a,a>,<b,b>,<c,c>}=IA。 abcabcabcabcabc第九页，共三十页。 2023/3/8计算机学院10例4解：R1＝{1,2,3}×{1,2,3}∪{4,5}×{4,5}∪{6}×{6}＝{<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>, <2,3>,<3,2>,<4,4>,<5,5>,<4,5>,<5,4>,<6,6>}；R2＝{1,2,3}×{1,2,3}∪{4,5,6}×{4,5,6} ＝{<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>, <3,1>,<2,3>,<3,2>,<4,4>,<5,5>,<6,6>, <4,5>,<5,4>,<4,6>,<6,4>,<5,6>,<6,5>}。设集合A＝