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

《离散数学(第16讲习题课3)》由会员分享，可在线阅读，更多相关《离散数学(第16讲习题课3)（30页珍藏版）》请在装配图网上搜索。

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

2、关关系系R R，能能用用三三种种方方式式（集集合合、矩矩阵阵、图图）判判断断该关系该关系R R所具有的性质；所具有的性质；2023/8/302023/8/30计算机学院计算机学院4 4基本要求基本要求5.5.正确理解关系运算的性质正确理解关系运算的性质6.熟练熟练掌握关系的掌握关系的闭包闭包的概念和性质；的概念和性质；7.7.掌握用矩阵计算传递闭包的掌握用矩阵计算传递闭包的Warshall(1962)Warshall(1962)算法；算法；8.8.能正确理解闭包运算；能正确理解闭包运算；9.9.熟练掌握熟练掌握等价关系等价关系、等价类等价类的定义；的定义；10.10.正确理解集合的划分正确理解

3、集合的划分(分划分划)；11.11.熟练掌握熟练掌握偏序关系偏序关系、偏序集偏序集、哈斯图哈斯图等概念；等概念；12.12.熟练掌握由关系图得到哈斯图的方法；熟练掌握由关系图得到哈斯图的方法；2023/8/302023/8/30计算机学院计算机学院5 5基本要求基本要求13.13.熟练掌握偏序集中特定元素的计算；熟练掌握偏序集中特定元素的计算；14.14.掌握全序关系、良序关系、良序集等概念；掌握全序关系、良序关系、良序集等概念；15.15.掌掌握握对对给给定定的的有有限限偏偏序序集集构构造造全全序序集集的的拓拓扑扑排序算法；排序算法；16.16.能能正正确确使使用用按按定定义义证证明明的的方

4、方法法进进行行关关系系的的性性质和特殊关系的证明质和特殊关系的证明 。2023/8/302023/8/30计算机学院计算机学院6 6例例1 1设设A A a,b,c,d,e,fa,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、5)。2023/8/302023/8/30计算机学院计算机学院7 7S S1 1S=S=,例例1(1(续续)S S2 2S S S S,，S S3 3S S S 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/8/302023/8/30计算机学院计算机学院8 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

6、 j。证证明明：由由关关系系的的特特点点知知道道，若若 A A=n=n，则则A A上上的的关关系有系有 个，因此，在个，因此，在 R R0 0，R R1 1，R R2 2，这，这 +1+1个个关关系系中中，至至少少有有两两个个是是相相同同的的（鸽鸽巢原理巢原理），即有），即有i,j(0i,j(0 i i j j )使得使得R Ri i=R Rj j。如果如果k+1k+1个或更多的物体放入个或更多的物体放入k k个盒子，那么个盒子，那么至少有一个盒子包含了至少有一个盒子包含了2 2个或更多的物体。个或更多的物体。2023/8/302023/8/30计算机学院计算机学院9 9例例3解解先求先求A

7、A的划分：只有的划分：只有1 1个划分块的划分为个划分块的划分为1 1，具有，具有2 2个个设设A=A=a,b,ca,b,c，求，求A A上所有的等价关系。上所有的等价关系。划划分分块块的的划划分分为为2 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 b

8、c ca ab bc c2023/8/302023/8/30计算机学院计算机学院1010例例4 4解：解：R R1 11,2,31,2,31,2,34,51,2,34,54,564,5666,；R R2 21,2,31,2,31,2,34,5,61,2,34,5,64,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/8/302023/8/30计算机学

9、院计算机学院1111 商集商集(quotient setquotient set)设设R R是是非非空空集集合合A A上上的的等等价价关关系系，以以R R的的所所有有不不同同等等价价类类为为元元素素作作成成的的集集合合称称为为A 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,

10、33R R=3,6,9=3,6,9 2023/8/302023/8/30计算机学院计算机学院1212例例5 5 设设R R是是集集合合A A上上的的一一个个传传递递关关系系和和自自反反关关系系，S S是是A A上上的的一一个个关关系系，使使得得对对任任意意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，则则由由已已知知条条

11、件件有有 RR并并 且且 RR，即即 有有 RR并并 且且 RR，所以，所以，SS，即，即S S是对称的。是对称的。2023/8/302023/8/30计算机学院计算机学院13133 3）对对任任意意a,b,cAa,b,cA，若若 SS，SS，则则由由已已知知条条件件有有：RR并并且且 RR和和 RR并并且且 RR。所所以以，由由 RR并并且且 RR，有有 RR；由由 RR并并且且 RR，有有 RR；由由：RR并并且且 RR，有，有 SS，即，即S S是传递的。是传递的。由由1),2),3)1),2),3)知，知，S S是是A A上的一个等价关系。上的一个等价关系。2023/8/302023/

12、8/30计算机学院计算机学院1414例例6 6证明：证明：“”若若R R是等价关系。是等价关系。1 1）显然显然R R是自反的。是自反的。2 2）对任意对任意a,b,cAa,b,cA，若，若 R,R,RR，则由，则由R R是对称的，有是对称的，有 RR并且并且 RR，由，由R R是传递是传递的，所以，的，所以，RR。即。即R R是循环的关系。是循环的关系。由由1)1)，2)2)知知R R是自反的和循环的。是自反的和循环的。设设R R是集合是集合A A上的一个关系，对上的一个关系，对 a,b,cAa,b,cA，若，若 RR并且并且 RR，则有：，则有：RR，则，则R R称称为为A A上的上的循环

13、关系循环关系。试证明。试证明R R是是A A上的一个等价关系上的一个等价关系的充要条件是的充要条件是R R是循环关系和自反关系。是循环关系和自反关系。2023/8/302023/8/30计算机学院计算机学院1515“”若若R R是自反的和循环的。是自反的和循环的。1 1）显然显然R R是是自反性自反性的；的；2 2）对任意对任意a,ba,bA,A,若若 R,R,则由则由R R是自反的是自反的,有有 R R，因，因R R是循环的，所以，是循环的，所以，R R且且 R R R R，即即R R是对称的。是对称的。3 3）对任意对任意a,b,ca,b,cA A，若，若 R R，R R，则，则由由R R

14、对称的，有对称的，有 RR并且并且 RR；由；由R R是是循环的，所以循环的，所以 RR且且 RR RR，即，即R R是传递的。是传递的。由由1),2),3)1),2),3)知，知，R R是是A A上的一个等价关系。上的一个等价关系。例例6(6(续续)2023/8/302023/8/30计算机学院计算机学院1616例例7 7设集合设集合A Aaa，B B a,ba,b，C C a,b,ca,b,c 。分别画出集合。分别画出集合A A、B B、C C之幂集之幂集 2 2A A、2 2B B、2 2C C 上定义的上定义的“”的哈斯图。的哈斯图。2 2A A=，aa2 2B B=，a,b,a,b,

15、a,ba,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 aabb a,ba,b 2 aabbcc a,ba,b a,ca,c b,cb,c a,b,ca,b,c 2023/8/302023/8/30计算机学院计算机学院1717例例8 8 设集合设集合A A a,b,ca,b,c，考虑，考虑2 2A A 上的关系上的关系“”，则，则2 是偏序集。求是偏序集。求2 2A A的子集：的子集：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的最大的

16、最大(小小)元、极大元、极大(小小)元、元、最小上界、最大下界最小上界、最大下界。集集合合 最大元最大元最小最小元元极大元极大元极小极小元元上界上界下界下界最小最小上界上界最大最大下界下界B1B2B3无无 a,ba,b,b,cb,c a,b,ca,b,c a,b,ca,b,c a,ca,c 无无 a,ca,c a,a,cc a,ca,c,a,b,ca,b,c a,ca,c a,b,ca,b,c a,b,ca,b,c a,b,ca,b,c a,b,ca,b,c 2023/8/302023/8/30计算机学院计算机学院1818例例9 9解：解：最大元：无；最小元：最大元：无；最小元：x x5 5；

17、设设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 x5 5。x x5 5x x3 3x x4 4x x1 1x x2 22023/8/302023/8/30

18、计算机学院计算机学院1919例例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(i1,2,.n1,2,.n；j j1,2,.m)1,2,.m)。.当当x x1 1

19、yy1 1时时,若若x x1 1yy1 1(x(x1 1、y y1 1的大小由它们的大小由它们的的ASCIIASCII码号进行比较）码号进行比较）,则则xLyxLy；若；若y y1 1xx1 1,则则yLxyLx；2023/8/302023/8/30计算机学院计算机学院2020 .若若存存在在最最大大的的k k且且k kmin(n,mmin(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 yk+1k+1xxk+1k+1，则，则yLxyLx；.若若存存在

20、在最最大大的的k k且且k kmin(n,mmin(n,m)，使使x xi iy yi i(i(i1,2,3,.,k),1,2,3,.,k),此此时时,若若nmnm,则则xLyxLy；若若mnmn,则则yLxyLx 显显然然，L L是是一一个个偏偏序序关关系系，且且也也是是一一个个全全序关系序关系。如如英英语语词词典典和和汉汉语语词词典典都都是是按按字字典典次次序序排排列的。列的。2023/8/302023/8/30计算机学院计算机学院2121第二类第二类StirlingStirling数数 将将n n个个不不同同的的球球放放入入r r个个相相同同的的盒盒中中去去，并并且且要要求求无无空空盒盒

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

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

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