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

冯伟森冯伟森Email：：fws365@Tel: 1380819227504 八月八月 20242024/8/42024/8/4计算机学院计算机学院2 22024/8/42024/8/4计算机学院计算机学院3 3基本要求基本要求1.1.正确理解正确理解幂集、笛卡尔集幂集、笛卡尔集和和关系关系的定义；的定义；2.2.能能正正确确使使用用集集合合表表达达式式，，关关系系矩矩阵阵，，关关系系图图表示给定的二元关系；表示给定的二元关系；3.熟熟练练掌掌握握关关系系的的各各种种运运算算，，特特别别是是复复合合运运算算和逆运算和逆运算；；4.4.牢牢记记关关系系的的5 5个个性性质质的的定定义义，，对对给给定定A A上上的的关关系系R R，，能能用用三三种种方方式式（（集集合合、、矩矩阵阵、、图图））判判断断该关系该关系R R所具有的性质；所具有的性质；2024/8/42024/8/4计算机学院计算机学院4 4基本要求基本要求5.5.正确理解关系运算的性质正确理解关系运算的性质6.熟练熟练掌握关系的掌握关系的闭包闭包的概念和性质；的概念和性质；7.7.掌握用矩阵计算传递闭包的掌握用矩阵计算传递闭包的Warshall(1962)Warshall(1962)算法；算法； 8.8.能正确理解闭包运算；能正确理解闭包运算；9.9.熟练掌握熟练掌握等价关系等价关系、、等价类等价类的定义；的定义；10.10.正确理解集合的划分正确理解集合的划分( (分划分划) )；；11.11.熟练掌握熟练掌握偏序关系偏序关系、、偏序集偏序集、、哈斯图哈斯图等概念；等概念； 12.12.熟练掌握由关系图得到哈斯图的方法；熟练掌握由关系图得到哈斯图的方法；2024/8/42024/8/4计算机学院计算机学院5 5基本要求基本要求13.13.熟练掌握偏序集中特定元素的计算；熟练掌握偏序集中特定元素的计算；14.14.掌握全序关系、良序关系、良序集等概念；掌握全序关系、良序关系、良序集等概念；15.15.掌掌握握对对给给定定的的有有限限偏偏序序集集构构造造全全序序集集的的拓拓扑扑排序算法；排序算法；16.16.能能正正确确使使用用按按定定义义证证明明的的方方法法进进行行关关系系的的性性质和特殊关系的证明质和特殊关系的证明 。

2024/8/42024/8/4计算机学院计算机学院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 1＝＝R R，，R R2 2＝＝R R R R＝＝{,,,,,}{,,,,,}，，　　R R3 3＝＝R R R R R R＝＝R R2 2 R R＝＝{,,,,,}{,,,,,}，，　　R R4 4＝＝R R3 3 R R＝＝{,,,,,}{,,,,,}，，　　R R5 5＝＝R R4 4 R R＝＝{,,,,,}{,,,,,}，，　　R R6 6＝＝R R5 5 R R＝＝{,,,,,}{,,,,,}＝＝R R5 5，，　　R R7 7＝＝R R6 6 R R＝＝R R5 5，，…，，R Rn n＝＝R R5 5　　(n(n＞＞5)5)。

2024/8/42024/8/4计算机学院计算机学院7 7　　S S1 1＝＝S=S={<{,<>,,<>,,<>,,<>,}>}, ,例例1(1(续续) )　　S S2 2＝＝S S S S＝＝{,,,}{,,,}，，　　S S3 3＝＝S S S S S S＝＝S S2 2 S S＝＝{,,}{,,}，，　　S S4 4＝＝S S3 3 S S＝＝{,}{,}，，　　S S5 5＝＝S S4 4 S S＝＝{}{}，，　　S S6 6＝＝S S5 5 S S＝＝ΦΦ，，　　S S7 7＝＝ΦΦ，，…，，　　S Sn n＝＝ΦΦ　　(n(n＞＞5)5)2024/8/42024/8/4计算机学院计算机学院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 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个或更多的物体个或更多的物体2024/8/42024/8/4计算机学院计算机学院9 9例例3解解先求先求A 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 bc ca ab bc c2024/8/42024/8/4计算机学院计算机学院1010例例4 4解：解：R R1 1＝＝{1,2,3}{1,2,3}××{1,2,3}∪{4,5}{1,2,3}∪{4,5}××{4,5}∪{6}{4,5}∪{6}××{6}{6}＝＝{<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,{<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>}<2,3>,<3,2>,<4,4>,<5,5>,<4,5>,<5,4>,<6,6>}；；R R2 2＝＝{1,2,3}{1,2,3}××{1,2,3}∪{4,5,6}{1,2,3}∪{4,5,6}××{4,5,6}{4,5,6} ＝＝{<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,{<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>,<4,4>,<5,5>,<6,6>,<3,1>,<2,3>,<3,2>,<4,4>,<5,5>,<6,6>,<4,5>,<5,4>,<4,6>,<6,4>,<5,6>,<6,5>}<4,5>,<5,4>,<4,6>,<6,4>,<5,6>,<6,5>}。

设集合设集合A A＝＝{1,2,3,4,5,6}{1,2,3,4,5,6}的两个划分如下：的两个划分如下：ПП1 1(A)(A)＝＝{{1,2,3},{4,5},{6}}{{1,2,3},{4,5},{6}}；；ПП2 2(A)(A)＝＝{{1,2,3},{4,5,6}}.{{1,2,3},{4,5,6}}.求其相应的等价关系求其相应的等价关系2024/8/42024/8/4计算机学院计算机学院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＝＝ { { [1][1]R R，， [2][2]R R ，， [3][3]R R} }，， 这这 里里 [1][1]R R={1,4,7,10}, ={1,4,7,10}, [2][2]R R={2,5, 8}, ={2,5, 8}, [3][3]R R={3,6,9} ={3,6,9} 2024/8/42024/8/4计算机学院计算机学院1212例例5 5 设设R R是是集集合合A A上上的的一一个个传传递递关关系系和和自自反反关关系系，，S S是是A A上上的的一一个个关关系系，，使使得得对对任任意意a,b∈Aa,b∈A，，< ∈S>∈S当当且且仅仅当当< ∈R>∈R且且< ∈R>∈R，，试试证证明明S S是是A A上的一个等价关系。

上的一个等价关系证明：证明：1 1））对对任任意意a∈Aa∈A，，因因R R是是自自反反的的，，所所以以< ∈R>∈R由由< ∈R>∈R并并且且< ∈R>∈R，，有有< ∈S>∈S，，即即S S是是自自反的2 2））对对任任意意a,b∈Aa,b∈A，，若若< ∈S>∈S，，则则由由已已知知条条件件有有< ∈R>∈R并并 且且 < ∈R>∈R，， 即即 有有 < ∈R>∈R并并 且且< ∈R>∈R，，所以，所以，< ∈S>∈S，即，即S S是对称的是对称的2024/8/42024/8/4计算机学院计算机学院13133 3））对对任任意意a,b,c∈Aa,b,c∈A，，若若< ∈S>∈S，，< ∈S>∈S，，则则由由已已知知条条件件有有：：< ∈R>∈R并并且且< ∈R>∈R和和< ∈R>∈R并并且且< ∈R>∈R所所以以，，由由< ∈R>∈R并并且且< ∈R>∈R，，有有< ∈R>∈R；；由由< ∈R>∈R并并且且< ∈R>∈R，，有有< ∈R>∈R；；由由：：< ∈R>∈R并并且且< ∈R>∈R，有，有< ∈S>∈S，即，即S S是传递的。

是传递的§由由1),2),3)1),2),3)知，知，S S是是A A上的一个等价关系上的一个等价关系■■2024/8/42024/8/4计算机学院计算机学院1414例例6 6证明：证明：“” 若若R R是等价关系是等价关系1 1））显然显然R R是自反的是自反的2 2））对任意对任意a,b,c∈Aa,b,c∈A，若，若< ∈R,<>∈R,∈R>∈R，则由，则由R R是对称的，有是对称的，有< ∈R>∈R并且并且< ∈R>∈R，由，由R R是传递是传递的，所以，的，所以，< ∈R>∈R即R R是循环的关系是循环的关系由由1)1)，，2)2)知知R R是自反的和循环的是自反的和循环的 设设R R是集合是集合A A上的一个关系，对上的一个关系，对 a,b,c∈Aa,b,c∈A，若，若< ∈R>∈R并且并且< ∈R>∈R，则有：，则有：< ∈R>∈R，则，则R R称称为为A A上的上的循环关系循环关系试证明R R是是A A上的一个等价关系上的一个等价关系的充要条件是的充要条件是R R是循环关系和自反关系。

是循环关系和自反关系2024/8/42024/8/4计算机学院计算机学院1515“” 若若R R是自反的和循环的是自反的和循环的1 1））显然显然R R是是自反性自反性的；的；2 2））对任意对任意a,b∈a,b∈A,A,若若< >∈∈R,R,则由则由R R是自反的是自反的, ,有有< >∈∈R R，因，因R R是循环的，所以，是循环的，所以，< >∈∈R R且且< >∈∈R R  < >∈∈R R，，即即R R是对称的是对称的3 3））对任意对任意a,b,ca,b,c∈∈A A，若，若< >∈∈R R，，< >∈∈R R，则，则由由R R对称的，有对称的，有< ∈R>∈R并且并且< ∈R>∈R；由；由R R是是循环的，所以循环的，所以< ∈R>∈R且且< ∈R>∈R< ∈R>∈R，即，即R R是传递的是传递的由由1),2),3)1),2),3)知，知，R R是是A A上的一个等价关系。

上的一个等价关系■■例例6(6(续续) )2024/8/42024/8/4计算机学院计算机学院1616例例7 7设集合设集合A A＝＝{a}{a}，，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={={ ，，{a}}{a}}2 2B B={={ ，， {a}, {b}, {{a}, {b}, {a,ba,b}}}}2 2C C={={ ，，{ {a},{b},{c},{a,b},{a,c},{b,c},{a,b,ca},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}}}<2<2A A, , > > {a}{a}<2<2B B, , > > {a}{a}{b}{b}{ {a,ba,b} }<2<2C C, , > > {a}{a}{b}{b}{c}{c}{ {a,ba,b} }{ {a,ca,c} }{ {b,cb,c} }{ {a,b,ca,b,c} }2024/8/42024/8/4计算机学院计算机学院1717例例8 8 设集合设集合A A＝＝{ {a,b,ca,b,c} }，考虑，考虑2 2A A 上的关系上的关系“ ”，则，则<2<2A A, , > >是偏序集。

求是偏序集求2 2A A的子集：的子集：B B1 1＝＝{{{{a,b},{b,c},{b},{c},Φa,b},{b,c},{b},{c},Φ} }，，B B2 2＝＝{{{{a},{c},{a,ca},{c},{a,c}}}}，，B B3 3＝＝2 2A A的最大的最大( (小小) )元、极大元、极大( (小小) )元、元、最小上界、最大下界最小上界、最大下界集集合合 最大元最大元最小最小元元极大元极大元极小极小元元上界上界下界下界最小最小上界上界最大最大下界下界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},{c}{c}{ {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} } ΦΦ2024/8/42024/8/4计算机学院计算机学院1818例例9 9解：解：最大元：无；最小元：最大元：无；最小元：x x5 5；； 设设A A＝＝{x{x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5},},A A上定义偏序集上定义偏序集的哈斯图如下，求的哈斯图如下，求B B＝＝{x{x3 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 5x x5 5x x3 3x x4 4x x1 1x x2 22024/8/42024/8/4计算机学院计算机学院1919例例10 10 字典次序字典次序§计算机科学中常用的字典排序如下：设计算机科学中常用的字典排序如下：设∑∑是一是一有限的字母表有限的字母表∑∑上的字母组成的字母串叫上的字母组成的字母串叫∑∑上上的字；的字；∑∑* *是包含空字是包含空字“∧∧”的所有字组成的集合，的所有字组成的集合，建立建立∑∑* *上的字典次序关系上的字典次序关系L L：： 设设 x x＝＝x x1 1x x2 2x x3 3…x xn n，，y y＝＝y y1 1y y2 2y y3 3…y ym m, ,其中：其中：x,yx,y∈∑∈∑* *，，x xi i,y,yj j∈∑ (i∈∑ (i＝＝1,2,...n1,2,...n；；j j＝＝1,2,...m)1,2,...m)。

①①. . 当当x x1 1≠y≠y1 1时时, ,若若x x1 1≤y≤y1 1(x(x1 1、、y y1 1的大小由它们的大小由它们的的ASCIIASCII码号进行比较）码号进行比较）, ,则则xLyxLy；若；若y y1 1≤x≤x1 1, ,则则yLxyLx；；2024/8/42024/8/4计算机学院计算机学院2020 ②.②.若若存存在在最最大大的的k k且且k k＜＜min(n,mmin(n,m) )，，使使x xi i＝＝y yi i(i(i＝＝1,2,3,1,2,3,…,k),k)，，而而x xk+1k+1≠y≠yk+1k+1，，若若x xk+1k+1≤y≤yk+1k+1，则，则xLyxLy；若；若y yk+1k+1≤x≤xk+1k+1，则，则yLxyLx；； ③③. .若若存存在在最最大大的的k k且且k k＝＝min(n,mmin(n,m) )，，使使x xi i＝＝y yi i(i(i＝＝1,2,3,...,k),1,2,3,...,k),此此时时, ,若若n≤mn≤m, ,则则xLyxLy；；若若m≤nm≤n, ,则则yLxyLx 显显然然，，L L是是一一个个偏偏序序关关系系，，且且也也是是一一个个全全序关系序关系。

如如英英语语词词典典和和汉汉语语词词典典都都是是按按字字典典次次序序排排列的2024/8/42024/8/4计算机学院计算机学院2121第二类第二类StirlingStirling数数 将将n n个个不不同同的的球球放放入入r r个个相相同同的的盒盒中中去去，，并并且且要要求求无无空空盒盒，，有有多多少少种种不不同同的的放放法法？？这里要求这里要求n n r r 不不同同的的放放球球方方法法数数即即为为n n元元集集合合A A的的不不同的划分数，同的划分数， v设设 表示将表示将n n个不同的球放入个不同的球放入r r个相同的盒中个相同的盒中的方案数，称的方案数，称 为第二类为第二类StirlingStirling数数 2024/8/42024/8/4计算机学院计算机学院2222第二类第二类StirlingStirling数的性质数的性质(1)(1)2024/8/42024/8/4计算机学院计算机学院2323 (2) (2) 满足如下的递推公式满足如下的递推公式: : 2024/8/42024/8/4计算机学院计算机学院2424例例11 11 集集合合A={aA={a，，b b，，c c，，d}d}上上有有多多少少不不同同的的等价关系？等价关系？v解：不同的划分个数为解：不同的划分个数为: :不不同同的的等等价价关关系系个个数数等等于于不不同同的的划划分分个个数数，，所以不同的等价关系个数为所以不同的等价关系个数为1515。

2024/8/42024/8/4计算机学院计算机学院2525习题解答习题解答习题三习题三 17172024/8/42024/8/4计算机学院计算机学院2626习题习题 四四§13. 解：解： ，，§ 且且§∴∴ 需需3∣ ∣k，，5∣ ∣k§ ，即，即§故使故使 的最小正整数的最小正整数2024/8/42024/8/4计算机学院计算机学院272715、解：、解：2024/8/42024/8/4计算机学院计算机学院2828习题五习题五§13. 证证：：i））自自反反性性，，对对 ，，§（（R的自反性）的自反性）§显然显然§ii)反对称性，对反对称性，对§即，即，§由由R的反对称性，的反对称性，§iii)传递性，对，传递性，对，§设设 ，，2024/8/42024/8/4计算机学院计算机学院2929§则则 ，， 。

§由由R的传递性，的传递性， ，，§显然显然2024/8/42024/8/4计算机学院计算机学院3030实验二实验二§利利用用求求传传递递闭闭包包的的Warshall算算法法，，给给定定关关系系R，，编编写写求求R的的可可传传递递闭闭包包的的C语语言言程程序序并并利利用用下列数据测试下列数据测试§测试数据为：测试数据为：§1，，0，，0，，0，，§1，，1，，0，，1，，§0，，1，，1，，0，，§1，，0，，1，，1。