离散数学(习题课).ppt

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn Tel:* * 计算机学院 * * 计算机学院 * 基本要求 正确理解幂集、笛卡尔集和关系的定义； 能正确使用集合表达式，关系矩阵，关系图表示给定的二元关系； 熟练掌握关系的各种运算，特别是复合运算和逆运算； 牢记关系的5个性质的定义，对给定A上的关系R，能用三种方式（集合、矩阵、图）判断该关系R所具有的性质； * 计算机学院 * 基本要求 正确理解关系运算的性质 熟练掌握关系的闭包的概念和性质； 掌握用矩阵计算传递闭包的Warshall(1962)算法； 能正确理解闭包运算； 熟练掌握等价关系、等价类的定义； 正确理解集合的划分(分划)； 熟练掌握偏序关系、偏序集、哈斯图等概念； 熟练掌握由关系图得到哈斯图的方法； * 计算机学院 * 基本要求 熟练掌握偏序集中特定元素的计算； 掌握全序关系、良序关系、良序集等概念； 掌握对给定的有限偏序集构造全序集的拓扑排序算法； 能正确使用按定义证明的方法进行关系的性质和特殊关系的证明 。 * 计算机学院 * 例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)。 * 计算机学院 * 　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)。 * 计算机学院 * 例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个或更多的物体。 * 计算机学院 * 例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。 a b c a b c a b c a b c a b c * 计算机学院 * 例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＝{1,2,3,4,5,6}的两个划分如下：П1(A)＝{{1,2,3},{4,5},{6}}；П2(A)＝{{1,2,3},{4,5,6}}.求其相应的等价关系。 * 计算机学院 * 商集(quotient set) 设R是非空集合A上的等价关系，以R的所有不同等价类为元素作成的集合称为A的商集，简称A的商集，记作A/R。 A/R恰是集合Ａ的一个划分。 设集合A={1,2,3,?,10}，R是模3同余关系，则A/R＝{ [1]R，[2]R ，[