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

《离散数学(第16讲习题课3).ppt》由会员分享，可在线阅读，更多相关《离散数学(第16讲习题课3).ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、冯伟森冯伟森Email：21 五月五月 20232023/5/21计算机学院计算机学院22023/5/21计算机学院计算机学院3基本要求基本要求1.1.正确理解正确理解幂集、笛卡尔集幂集、笛卡尔集和和关系关系的定义；的定义；2.2.能能正正确确使使用用集集合合表表达达式式，关关系系矩矩阵阵，关关系系图图表示给定的二元关系；表示给定的二元关系；3.熟熟练练掌掌握握关关系系的的各各种种运运算算，特特别别是是复复合合运运算算和逆运算和逆运算；4.4.牢牢记记关关系系的的5 5个个性性质质的的定定义义，对对给给定定A A上上的的关关系系R R，能能用用三三种种方方式式（集集合合、矩矩阵阵、图图）判判断

2、断该关系该关系R R所具有的性质；所具有的性质；2023/5/21计算机学院计算机学院4基本要求基本要求5.5.正确理解关系运算的性质正确理解关系运算的性质6.熟练熟练掌握关系的掌握关系的闭包闭包的概念和性质；的概念和性质；7.7.掌握用矩阵计算传递闭包的掌握用矩阵计算传递闭包的Warshall(1962)Warshall(1962)算法；算法；8.8.能正确理解闭包运算；能正确理解闭包运算；9.9.熟练掌握熟练掌握等价关系等价关系、等价类等价类的定义；的定义；10.10.正确理解集合的划分正确理解集合的划分(分划分划)；11.11.熟练掌握熟练掌握偏序关系偏序关系、偏序集偏序集、哈斯图哈斯图

3、等概念；等概念；12.12.熟练掌握由关系图得到哈斯图的方法；熟练掌握由关系图得到哈斯图的方法；2023/5/21计算机学院计算机学院5基本要求基本要求13.13.熟练掌握偏序集中特定元素的计算；熟练掌握偏序集中特定元素的计算；14.14.掌握全序关系、良序关系、良序集等概念；掌握全序关系、良序关系、良序集等概念；15.15.掌掌握握对对给给定定的的有有限限偏偏序序集集构构造造全全序序集集的的拓拓扑扑排序算法；排序算法；16.16.能能正正确确使使用用按按定定义义证证明明的的方方法法进进行行关关系系的的性性质和特殊关系的证明质和特殊关系的证明 。2023/5/21计算机学院计算机学院6例例1

4、1设设A Aa,b,c,d,e,f,a,b,c,d,e,f,定义在定义在A A上的关系上的关系R R,，S S,求求R Rn n和和S Sn n。解解R R1 1R R，R R2 2R R R R,，R R3 3R R R R R RR R2 2 R R,，R R4 4R R3 3 R R,，R R5 5R R4 4 R R,，R R6 6R R5 5 R R,R R5 5，R R7 7R R6 6 R RR R5 5，R Rn nR R5 5(n(n5)5)。2023/5/21计算机学院计算机学院7S S1 1S=S=,例例1(1(续续)S S2 2S S S S,，S S3 3S S S

5、S S SS S2 2 S S,，S S4 4S S3 3 S S,，S S5 5S S4 4 S S，S S6 6S S5 5 S S，S S7 7，S Sn n(n(n5)5)。2023/5/21计算机学院计算机学院8例例2 2 设设集集合合A A的的元元素素数数为为n n，R R是是A A上上二二元元关关系系，那那么么存存在在自自然然数数i i，j(0j(0 i i j j )使使得得R Ri i=R=Rj j。证证明明：由由关关系系的的特特点点知知道道，若若 A A=n=n，则则A A上上的的关关系有系有 个，因此，在个，因此，在 R R0 0，R R1 1，R R2 2，这，这 +1

6、+1个个关关系系中中，至至少少有有两两个个是是相相同同的的（鸽鸽巢原理巢原理），即有），即有i,j(0i,j(0 i i j j )使得使得R Ri i=R=Rj j。如果如果k+1k+1个或更多的物体放入个或更多的物体放入k k个盒子，那么个盒子，那么至少有一个盒子包含了至少有一个盒子包含了2 2个或更多的物体。个或更多的物体。2023/5/21计算机学院计算机学院9例例3解解先求先求A A的划分：只有的划分：只有1 1个划分块的划分为个划分块的划分为1 1，具有，具有2 2个个设设A=a,b,cA=a,b,c，求，求A A上所有的等价关系。上所有的等价关系。划划分分块块的的划划分分为为2

7、2、3 3和和4 4，具具有有3 3个个划划分分块块的的划划分分为为5 5，如下图所示。，如下图所示。设设i i导出的等价关系为导出的等价关系为i i，i=1,2,3,4,5i=1,2,3,4,5。则有。则有R R1 1=,=,=A,=A A A；R R2 2=,=,；R R3 3=,=,；R R4 4=,=,；R R5 5=,=I=,=IA A。a ab bc ca ab bc ca ab bc ca ab bc ca ab bc c2023/5/21计算机学院计算机学院10例例4 4解：解：R R1 11,2,31,2,34,54,5661,2,31,2,34,54,566,；R R2 2

8、1,2,31,2,34,5,64,5,61,2,31,2,34,5,64,5,6 ,。设集合设集合A A1,2,3,4,5,61,2,3,4,5,6的两个划分如下：的两个划分如下：1 1(A)(A)1,2,3,4,5,61,2,3,4,5,6；2 2(A)(A)1,2,3,4,5,6.1,2,3,4,5,6.求其相应的等价关系。求其相应的等价关系。2023/5/21计算机学院计算机学院11 商集商集(quotient setquotient set)设设R R是是非非空空集集合合A A上上的的等等价价关关系系，以以R R的的所所有有不不同同等等价价类类为为元元素素作作成成的的集集合合称称为为A

9、 A的的商商集集，简简称称A A的商集，记作的商集，记作A/RA/R。A/RA/R恰是集合的一个划分。恰是集合的一个划分。设设集集合合A=1,2,3,A=1,2,3,10,10，R R是是模模3 3同同余余关关系系，则则 A/RA/R 11R R，22R R，33R R，这这 里里 11R R=1,4,7,10,=1,4,7,10,22R R=2,5,8,=2,5,8,33R R=3,6,9=3,6,9 2023/5/21计算机学院计算机学院12例例5 5 设设R R是是集集合合A A上上的的一一个个传传递递关关系系和和自自反反关关系系，S S是是A A上上的的一一个个关关系系，使使得得对对任

10、任意意a,bAa,bA，SS当当且且仅仅当当RR且且RR，试试证证明明S S是是A A上的一个等价关系。上的一个等价关系。证明：证明：1 1）对对任任意意aAaA，因因R R是是自自反反的的，所所以以RR。由由RR并并且且RR，有有SS，即即S S是是自自反的。反的。2 2）对对任任意意a,bAa,bA，若若SS，则则由由已已知知条条件件有有RR并并 且且 RR，即即 有有 RR并并 且且RR，所以，所以，SS，即，即S S是对称的。是对称的。2023/5/21计算机学院计算机学院133 3）对对任任意意a,b,cAa,b,cA，若若SS，SS，则则由由已已知知条条件件有有：RR并并且且RR和

11、和RR并并且且RR。所所以以，由由RR并并且且RR，有有RR；由由RR并并且且RR，有有RR；由由：RR并并且且RR，有，有SS，即，即S S是传递的。是传递的。由由1),2),3)1),2),3)知，知，S S是是A A上的一个等价关系。上的一个等价关系。2023/5/21计算机学院计算机学院14例例6 6证明：证明：“”若若R R是等价关系。是等价关系。1 1）显然显然R R是自反的。是自反的。2 2）对任意对任意a,b,cAa,b,cA，若，若R,RR,R，则由，则由R R是对称的，有是对称的，有RR并且并且RR，由，由R R是传递是传递的，所以，的，所以，RR。即。即R R是循环的关系

12、。是循环的关系。由由1)1)，2)2)知知R R是自反的和循环的。是自反的和循环的。设设R R是集合是集合A A上的一个关系，对上的一个关系，对 a,b,cAa,b,cA，若，若RR并且并且RR，则有：，则有：RR，则，则R R称称为为A A上的上的循环关系循环关系。试证明。试证明R R是是A A上的一个等价关系上的一个等价关系的充要条件是的充要条件是R R是循环关系和自反关系。是循环关系和自反关系。2023/5/21计算机学院计算机学院15“”若若R R是自反的和循环的。是自反的和循环的。1 1）显然显然R R是是自反性自反性的；的；2 2）对任意对任意a,bA,a,bA,若若R,R,则由则

13、由R R是自反的是自反的,有有RR，因，因R R是循环的，所以，是循环的，所以，RR且且R R RR，即即R R是对称的。是对称的。3 3）对任意对任意a,b,cAa,b,cA，若，若RR，RR，则，则由由R R对称的，有对称的，有RR并且并且RR；由；由R R是是循环的，所以循环的，所以RR且且RRRR，即，即R R是传递的。是传递的。由由1),2),3)1),2),3)知，知，R R是是A A上的一个等价关系。上的一个等价关系。例例6(6(续续)2023/5/21计算机学院计算机学院16例例7 7设集合设集合A Aaa，B Ba,ba,b，C Ca,b,c a,b,c。分别画出集合。分别画

14、出集合A A、B B、C C之幂集之幂集 2 2A A、2 2B B、2 2C C 上定义的上定义的“”的哈斯图。的哈斯图。2 2A A=，aa2 2B B=，a,b,a,ba,b,a,b2 2C C=，a,b,c,a,b,a,c,b,c,a,b,ca,b,c,a,b,a,c,b,c,a,b,c2 aa2 aabba,ba,b2 aabbcca,ba,ba,ca,cb,cb,ca,b,ca,b,c2023/5/21计算机学院计算机学院17例例8 8 设集合设集合A Aa,b,ca,b,c，考虑，考虑2 2A A 上的关系上的关系“”，则，则2 是偏序集。求是偏序集。求2 2A A的子集：的子集

15、：B B1 1a,b,b,c,b,c,a,b,b,c,b,c,，B B2 2a,c,a,ca,c,a,c，B B3 32 2A A的最大的最大(小小)元、极大元、极大(小小)元、元、最小上界、最大下界最小上界、最大下界。集集合合 最大元最大元最小最小元元极大元极大元极小极小元元上界上界下界下界最小最小上界上界最大最大下界下界B1B2B3无无a,b,a,b,b,cb,ca,b,ca,b,c a,b,ca,b,c a,ca,c无无a,ca,ca,a,cca,c,a,c,a,b,ca,b,c a,ca,ca,b,ca,b,c a,b,ca,b,c a,b,ca,b,c a,b,ca,b,c 2023

16、/5/21计算机学院计算机学院18例例9 9解：解：最大元：无；最小元：最大元：无；最小元：x x5 5；设设A Axx1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5,A A上定义偏序集上定义偏序集的哈斯图如下，求的哈斯图如下，求B Bxx3 3,x,x4 4,x,x5 5 的最大的最大(小小)元、极大元、极大(小小)元、上元、上(下下)界、最小上界、最大下界、最小上界、最大下界。界。极大元：极大元：x x3 3,x,x4 4；极小元：；极小元：x x5 5；上上界：界：x x1 1,x,x2 2；下；下界：界：x x5 5；最小上界：无；最大下界：最小上界：无；最大下界：x

17、x5 5。x x5 5x x3 3x x4 4x x1 1x x2 22023/5/21计算机学院计算机学院19例例10 10 字典次序字典次序计算机科学中常用的字典排序如下：设计算机科学中常用的字典排序如下：设是一是一有限的字母表。有限的字母表。上的字母组成的字母串叫上的字母组成的字母串叫上上的字；的字；*是包含空字是包含空字“”的所有字组成的集合，的所有字组成的集合，建立建立*上的字典次序关系上的字典次序关系L L：设设 x xx x1 1x x2 2x x3 3x xn n，y yy y1 1y y2 2y y3 3y ym m,其中：其中：x,yx,y*，x xi i,y,yj j(i

18、(i1,2,.n1,2,.n；j j1,2,.m)1,2,.m)。.当当x x1 1yy1 1时时,若若x x1 1yy1 1(x(x1 1、y y1 1的大小由它们的大小由它们的的ASCIIASCII码号进行比较）码号进行比较）,则则xLyxLy；若；若y y1 1xx1 1,则则yLxyLx；2023/5/21计算机学院计算机学院20 .若若存存在在最最大大的的k k且且k kmin(n,m)min(n,m)，使使x xi iy yi i(i(i1,2,3,1,2,3,k),k)，而而x xk+1k+1yyk+1k+1，若若x xk+1k+1yyk+1k+1，则，则xLyxLy；若；若y

19、yk+1k+1xxk+1k+1，则，则yLxyLx；.若若存存在在最最大大的的k k且且k kmin(n,m)min(n,m)，使使x xi iy yi i(i(i1,2,3,.,k),1,2,3,.,k),此此时时,若若nm,nm,则则xLyxLy；若若mn,mn,则则yLxyLx 显显然然，L L是是一一个个偏偏序序关关系系，且且也也是是一一个个全全序关系序关系。如如英英语语词词典典和和汉汉语语词词典典都都是是按按字字典典次次序序排排列的。列的。2023/5/21计算机学院计算机学院21第二类第二类StirlingStirling数数 将将n n个个不不同同的的球球放放入入r r个个相相同

20、同的的盒盒中中去去，并并且且要要求求无无空空盒盒，有有多多少少种种不不同同的的放放法法？这里要求这里要求n n r r。不不同同的的放放球球方方法法数数即即为为n n元元集集合合A A的的不不同的划分数，同的划分数，v设设 表示将表示将n n个不同的球放入个不同的球放入r r个相同的盒中个相同的盒中的方案数，称的方案数，称 为第二类为第二类StirlingStirling数数 。2023/5/21计算机学院计算机学院22第二类第二类StirlingStirling数的性质数的性质(1)(1)2023/5/21计算机学院计算机学院23 (2)(2)满足如下的递推公式满足如下的递推公式:2023/

21、5/21计算机学院计算机学院24例例11 11 集集合合A=aA=a，b b，c c，dd上上有有多多少少不不同同的的等价关系？等价关系？v解：不同的划分个数为解：不同的划分个数为:不不同同的的等等价价关关系系个个数数等等于于不不同同的的划划分分个个数数，所以不同的等价关系个数为所以不同的等价关系个数为1515。2023/5/21计算机学院计算机学院25习题解答习题解答习题三习题三 17172023/5/21计算机学院计算机学院26习题习题 四四13.解：解：，且且 需需3 k，5 k ，即，即故使故使 的最小正整数的最小正整数2023/5/21计算机学院计算机学院2715、解：、解：2023

22、/5/21计算机学院计算机学院28习题五习题五13.证证：i）自自反反性性，对对 ，（R的自反性）的自反性）显然显然ii)反对称性，对反对称性，对即，即，由由R的反对称性，的反对称性，iii)传递性，对，传递性，对，设设 ，2023/5/21计算机学院计算机学院29则则 ，。由由R的传递性，的传递性，显然显然2023/5/21计算机学院计算机学院30实验二实验二利利用用求求传传递递闭闭包包的的Warshall算算法法，给给定定关关系系R，编编写写求求R的的可可传传递递闭闭包包的的C语语言言程程序序并并利利用用下列数据测试。下列数据测试。测试数据为：测试数据为：1，0，0，0，1，1，0，1，0，1，1，0，1，0，1，1