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

,单击此处编辑母版标题样式,*,计算机学院,*,单击此处编辑母版标题样式,*,计算机科学与工程学院,*,冯伟森,Email,：,15 十一月 2024,离散数学,计算机学院,2024/11/15,计算机学院,2,习题课三,2024/11/15,计算机学院,3,基本要求,正确理解,幂集、笛卡尔集,和,关系,的定义；,能正确使用集合表达式，关系矩阵，关系图表示给定的二元关系；,熟练,掌握关系的各种运算，特别是,复合运算和逆运算,；,牢记关系的,5,个性质的定义，对给定,A,上的关系,R,，能用三种方式（集合、矩阵、图）判断该关系,R,所具有的性质；,2024/11/15,计算机学院,4,基本要求,正确理解关系运算的性质,熟练,掌握关系的,闭包,的概念和性质；,掌握用矩阵计算传递闭包的,Warshall(1962),算法；,能正确理解闭包运算；,熟练掌握,等价关系,、,等价类,的定义；,正确理解集合的划分,(,分划,),；,熟练掌握,偏序关系,、,偏序集,、,哈斯图,等概念；,熟练掌握由关系图得到哈斯图的方法；,2024/11/15,计算机学院,5,基本要求,熟练掌握偏序集中特定元素的计算；,掌握全序关系、良序关系、良序集等概念；,掌握对给定的有限偏序集构造全序集的拓扑排序算法；,能正确使用按定义证明的方法进行关系的性质和特殊关系的证明。,2024/11/15,计算机学院,6,例,1,设,A,a,b,c,d,e,f,定义在,A,上的关系,R,，,S,求,R,n,和,S,n,。,解,R,1,R,，,R,2,R,R,，,R,3,R,R,RR,2,R,，,R,4,R,3,R,，,R,5,R,4,R,，,R,6,R,5,R,R,5,，,R,7,R,6,RR,5,，,，,R,n,R,5,(n,5),。,2024/11/15,计算机学院,7,S,1,S=,例,1(,续,),S,2,S,S,，,S,3,S,S,SS,2,S,，,S,4,S,3,S,，,S,5,S,4,S，,S,6,S,5,S，,S,7,，,，,S,n,(n,5),。,2024/11/15,计算机学院,8,例,2,设集合,A,的元素数为,n,，,R,是,A,上二元关系，那么存在自然数,i,，,j(0,i,j,),使得,R,i,=R,j,。,证明：,由关系的特点知道，若,A,=n,，则,A,上的关系有 个，因此，在,R,0,，,R,1,，,R,2,，,，这,+1,个关系中，至少有两个是相同的（,鸽巢原理,），即有,i,j(0,i,j,),使得,R,i,=R,j,。,如果,k+1,个或更多的物体放入,k,个盒子，那么至少有一个盒子包含了,2,个或更多的物体。,2024/11/15,计算机学院,9,例,3,解,先求,A,的划分：只有,1,个划分块的划分为,1,，具有,2,个,设,A=a,b,c,，求,A,上所有的等价关系。,划分块的划分为,2,、,3,和,4,，具有,3,个划分块的划分为,5,，如下图所示。,设,i,导出的等价关系为,i,，,i=1,2,3,4,5,。则有,R,1,=,=A,A,；,R,2,=,；,R,3,=,；,R,4,=,；,R,5,=,=I,A,。,a,b,c,a,b,c,a,b,c,a,b,c,a,b,c,2024/11/15,计算机学院,10,例,4,解：,R,1,1,2,31,2,34,54,566,；,R,2,1,2,31,2,34,5,64,5,6,。,设集合,A,1,2,3,4,5,6,的两个划分如下：,1,(A),1,2,3,4,5,6,；,2,(A),1,2,3,4,5,6.,求其相应的等价关系。,2024/11/15,计算机学院,11,商集,(,quotient set,),设,R,是非空集合,A,上的等价关系，以,R,的所有不同等价类为元素作成的集合称为,A,的商集,，简称,A,的商集，记作,A/R,。,A/R,恰是集合的一个划分。,设集合,A=1,2,3,10,，,R,是模,3,同余关系，则,A/R,1,R,，,2,R,，,3,R,，这里,1,R,=1,4,7,10,2,R,=2,5,8,3,R,=3,6,9,2024/11/15,计算机学院,12,例,5,设,R,是集合,A,上的一个传递关系和自反关系，,S,是,A,上的一个关系，使得对任意,a,bA,，,S,当且仅当,R,且,R,，试证明,S,是,A,上的一个等价关系。,证明：,1,）,对任意,aA,，因,R,是自反的，所以,R,。由,R,并且,R,，有,S,，即,S,是自反的。,2,）,对任意,a,bA,，若,S,，则由已知条件有,R,并且,R,，即有,R,并且,R,，,所以，,S,，即,S,是对称的。,2024/11/15,计算机学院,13,3,）,对任意,a,b,cA,，若,S,，,S,，则由已知条件有：,R,并且,R,和,R,并且,R,。所以，由,R,并且,R,，有,R,；由,R,并且,R,，有,R,；由：,R,并且,R,，有,S,，即,S,是传递的。,由,1),2),3),知，,S,是,A,上的一个等价关系。,2024/11/15,计算机学院,14,例,6,证明：,“,”,若,R,是等价关系。,1,）,显然,R,是自反的。,2,）,对任意,a,b,cA,，若,R,R,，则由,R,是对称的，有,R,并且,R,，由,R,是传递的，所以，,R,。即,R,是循环的关系。由,1),，,2),知,R,是自反的和循环的。,设,R,是集合,A,上的一个关系，对,a,b,cA,，若,R,并且,R,，则有：,R,，则,R,称为,A,上的,循环关系,。试证明,R,是,A,上的一个等价关系的充要条件是,R,是循环关系和自反关系。,2024/11/15,计算机学院,15,“,”,若,R,是自反的和循环的。,1,）,显然R,是,自反性,的；,2,）,对任意,a,bA,若,R,则由,R,是自反的,有,R,，因,R,是循环的，所以，,R,且,R,R,，,即,R,是对称的。,3,）,对任意,a,b,cA,，若,R,，,R,，则由,R,对称的，有,R,并且,R,；由,R,是循环的，所以,R,且,R,R,，即,R,是传递的。,由,1),2),3),知，,R,是,A,上的一个等价关系。,例,6(,续,),2024/11/15,计算机学院,16,例,7,设集合,A,a,，,B,a,b,，,C,a,b,c,。分别画出集合,A,、,B,、,C,之幂集,2,A,、2,B,、2,C,上定义的,“,”,的哈斯图。,2,A,=,，,a,2,B,=,，,a,b,a,b,2,C,=,，,a,b,c,a,b,a,c,b,c,a,b,c,a,a,b,a,b,a,b,c,a,b,a,c,b,c,a,b,c,2024/11/15,计算机学院,17,例,8,设集合,A,a,b,c,，考虑,2,A,上的关系,“,”,，则,是偏序集。求,2,A,的子集：B,1,a,b,b,c,b,c,，,B,2,a,c,a,c,，,B,3,2,A,的最大(小)元、极大(小)元、,最小上界、最大下界,。,集合,最大元,最小元,极大元,极小元,上界,下界,最小,上界,最大下界,B,1,B,2,B,3,无,a,b,b,c,a,b,c,a,b,c,a,c,无,a,c,a,c,a,c,a,b,c,a,c,a,b,c,a,b,c,a,b,c,a,b,c,2024/11/15,计算机学院,18,例,9,解：,最大元：无；最小元：,x,5,；,设,A,x,1,x,2,x,3,x,4,x,5,A,上定义偏序集,的哈斯图如下，求,B,x,3,x,4,x,5,的最大,(,小,),元、极大,(,小,),元、上,(,下,),界、最小上界、最大下界。,极大元：,x,3,x,4,；极小元：,x,5,；,上界：,x,1,x,2,；下界：,x,5,；,最小上界：无；最大下界：,x,5,。,x,5,x,3,x,4,x,1,x,2,2024/11/15,计算机学院,19,例,10,字典次序,计算机科学中常用的字典排序如下：设是一有限的字母表。,上的字母组成的字母串叫上的字；,*,是包含空字,“,”,的所有字组成的集合，,建立,*,上的字典次序关系,L,：,设,x,x,1,x,2,x,3,x,n,，,y,y,1,y,2,y,3,y,m,其中：,x,y,*,，,x,i,y,j,(i,1,2,.n,；,j,1,2,.m),。,.,当,x,1,y,1,时,若,x,1,y,1,(x,1,、,y,1,的大小由它们的,ASCII,码号进行比较）,则,xLy,；若,y,1,x,1,则,yLx,；,2024/11/15,计算机学院,20,.,若存在最大的,k,且,k,min(n,m),，使,x,i,y,i,(i,1,2,3,k),，而,x,k+1,y,k+1,，若,x,k+1,y,k+1,，则,xLy,；若,y,k+1,x,k+1,，则,yLx,；,.,若存在最大的,k,且,k,min(n,m),，使,x,i,y,i,(i,1,2,3,.,k),此时,若,nm,则,xLy,；若,mn,则,yLx,显然，,L,是一个偏序关系，且也是一个全序关系,。,如英语词典和汉语词典都是按字典次序排列的。,2024/11/15,计算机学院,21,第二类,Stirling,数,将,n,个不同的球放入,r,个相同的盒中去，并且要求无空盒，有多少种不同的放法？这里要求,n,r,。,不同的放球方法数即为,n,元集合,A,的不同的划分数，,设 表示将,n,个不同的球放入,r,个相同的盒中的方案数，称 为第二类,Stirling,数。,2024/11/15,计算机学院,22,第二类,Stirling,数的性质,(1),2024/11/15,计算机学院,23,(2),满足如下的递推公式,:,2024/11/15,计算机学院,24,例,11,集合,A=a,，,b,，,c,，,d,上有多少不同的等价关系？,解：不同的划分个数为,:,不同的等价关系个数等于不同的划分个数，所以不同的等价关系个数为,15,。,2024/11/15,计算机学院,25,习题解答,习题三,17,2024/11/15,计算机学院,26,习题 四,13.,解：，,且,需,3k,，,5k,，即,故使 的最小正整数,2024/11/15,计算机学院,27,15,、解：,2024/11/15,计算机学院,28,习题五,13.,证：,i,）自反性，对 ，,（,R,的自反性）,显然,ii),反对称性，对,即，,由,R,的反对称性，,iii),传递性，对，,设 ，,2024/11/15,计算机学院,29,则 ，。,由,R,的传递性，,显然,2024/11/15,计算机学院,30,实验二,利用求传递闭包的,Warshall,算法，给定关系,R,，编写求,R,的可传递闭包的,C,语言程序并利用下列数据测试。,测试数据为：,1,，,0,，,0,，,0,，,1,，,1,，,0,，,1,，,0,，,1,，,1,，,0,，,1,，,0,，,1,，,1,