离散数学_集合与关系_关系

12第三章集合与关系—关系关系（主要是二元关系），它仍然是一种集合，但它是比前面更为复杂的集合。它的元素是有序二元组的形式，这些有序二元组中的两个元素来自于两个不同或者相同的集合。因此，关系是建立在其它集合基础之上的集合。关系中的有序二元组反映了不同集合中元素与元素之间的关系，或者同一集合中元素之间的关系。这里讨论这些关系的表示方法、关系的运算以及关系的性质，最后讨论集合A上几类特殊的关系。主要内容如下：笛卡尔积与关系等价关系关系的表示关系的复合运算偏序关系关系的性质与闭包3笛卡尔积与关系一、有序n元组与笛卡尔积1.有序n元组定义3-13由n个具有给定次序的个体组成的序列称为有序n元组，记作（）。naaa,,,21naaa,,,214定义3-14设和是两个有序n元组，若,则称这两个有序n元组相等，并记作),,,(21naaa),,,(21nbbbnnbababa,,,2211),,,(),,,(2121nnbbbaaa当n=2时，有序二元组(a,b)又称为序偶。52.笛卡尔积(1)笛卡尔积的定义定义3-15设A,B为任意集合，A和B的笛卡尔积用表示，定义为BA},|),{(BbAabaBA例1设则但},,{},1,0{cbabA)},1(),,1(),,1(),,0(),,0(),,0{(cbacbaBA)}1,(),1,(),1,(),0,(),0,(),0,{(cbacbaAB笛卡尔积我们常记作AA2A},|),{(AaAaaaAjiji2例2设则}1,0{A)},(),,(),,(),,{(110110002AAA6BABA二、关系1.关系的定义定义3-16笛卡尔积的任意一个子集称为是由A到B的一个二元关系，当时，称是A上的二元关系。7若，则称a与b有关系，又记作。若，则称a与b没有关系，又记作。),(baba),(baba8)2,1(),1,1(),2,0(),1,0(1.设,。则{}{}},{},{2110BABABB)2,2(),1,2(),2,1(),1,1(9关系的表示一、集合表示法用表示集合的列举法或描述法来表示关系。},,{751B},,,{8432A例1设,,用描述法定义由A到B的关系，试用列举法将表示出来。}|),{(baba解),,(),,{(7252),(),,(7353)},(),,(745410例2有王、张、李、何是某校的老师，该校有三门课程：语文、数学和英语，已知王可以教语文和数学，张可以教语文和英语，李可以教数学，何可以教英语，若记A={王，张，李，何}，B={语文，数学，英语}。那么这些老师与课程之间的对应关系就可以用由A到B的一个关系中的序偶来表示。={(王,语文),(王,数学),(张,语文),(张,英语),(李,数学),(何,英语)}11二、矩阵表示法ijrM定义3-18设A、B都是有限集，,，由A到B的关系可以用一个的矩阵来表示，的第i行第j列的元素取值如下：矩阵称为的关系矩阵。},,,{naaaA21},,,{21mbbbBmnMjijiijbabar若若01M例1中由A到B的关系可以用一个的矩阵来表示。340001101101108432M15712例3设，A上的关系解},,,{4321A}|),{(的整数倍是xyyx)},(),,(),,(),,(),,(),,(),,(),,{(4433422241312111则可以用一个的矩阵来表示。4410000100101011114321M123413三、关系图表示法关系图由结点和边组成例如例1中的，,}8,4,3,2{A},,{751B)},(),,(),,(),,(),,(),,{(745473537252则ρ的关系图如下AB14例如例3中的，},,,{4321A)},(),,(),,(),,(),,(),,(),,(),,{(4433422241312111的关系图如下：15},,{210A},,{420B)},(),,(),,(),,(),,(),,{(022101402000练习3-61.设，，A到B的关系试构造出的关系矩阵024210M00101111116122.设，A上的关系试画出和的关系图。},,,,,{654321A}|),{(jiji整除1}|),{(是素数jiji217关系的复合运算一、关系的并、交、补运算例1设，)},(),,(),,{(3342211)},(),,(),,{(2442312则)},(),,(),,(),,(),,{(243133422121)},{(4221)},(),,{(332121若和都是由集合A到B的关系，则，。于是，，因此，和也都是由A到B的关系。12BA1BA2BA21BA21BA2121212118若将看作是全集U，则也都是由A到B的关系。BA}),(|),{(11baba}),(|),{(22baba例2设，},{32A},,{984B这里.)},(),,(),,(),,(),,(),,{(938343928242BA设由A到B的关系,)},(),,{(82421)},{(932则；；)},(),,(),,{(9382422121)},(),,{(824221)},(),,(),,(),,{(938343921均是由A到B的关系。19二、求逆关系的运算定义3-19设A、B是任意集合，是由A到B的关系，定义由B到A的关系称为关系的逆关系。}),(|),{(~baab~解由的定义知),,(),,(),,{(1026242于是)},(),,(),,(),,(),,{(~510362102624),,(63)},(105例3设，，定义由A到B的关系：当且仅当a整除b时，有，试求的逆关系。},,{532A},,{1064Bba~20三、关系的复合运算1.复合关系的定义21定义3-20设是由A到B的关系，是由B到C的关系，则和的复合关系是一个由A到C的关系，用表示，定义为：当且仅当存在元素，使得，时，有。这种由和求复合关系的运算称为关系的复合运算。12Bbba1cb2ca)(2112211221例4设是由到的关系。是由B到的关系。分别定义为：1},,,,{4321A},,{432B2},,{653C)},(),,(),,{(}|),{(24334261baba)},(),,(),,{(}|),{(6333622cbcb整除于是复合关系)},(),,(),,{(64633321223.求复合关系的几种方法（1）根据复合关系的定义求复合关系例6中求复合关系采用的就是这种方法。12又例如下面的关系图给出了从集合A到B的关系和从B到C的关系)},(),,(),,{(1332222123（2）运用关系矩阵的运算求复合关系•布尔运算其加法和乘法运算定义如下00011101101110000110,,例如11100011110001)()()()()(24•关系矩阵的乘积对两个关系矩阵求其乘积时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。00101010100121MM则例7设和是两个关系矩阵0010101000011M1010100012M1M2M25•复合关系的关系矩阵定理3-5设A、B、C均是有限集，是一由A到B的关系,是一由B到C的关系，它们的关系矩阵分别为和，则复合关系的关系矩阵121M2M212121MMM26例8设有集合，，A到B的关系B到C的关系则},,,{4321A},,{432B}3,2,1{C)},(),,(),,(),,{(341423122)},(),,(),,(),,{(243342211)},(),,(),,(),,(),,{(14233212112123412312300101010000143211M1010100014322M001010101001432121M与例7比较得2121MMM27例9设，A上的关系试求和。},,,{dcbaA)},(),,(),,(),,(),,{(cbdcccabba23解作出的关系矩阵abcd0000110001010010dcbaM0000110011100101000011000101001000001100010100102MMM因此)},(),,(),,(),,(),,(),,(),,{(2dcccdbcbbbcaaa根据定理3-528又，所以2300001100110111100000110011100101000011000101001023MMM因此)},(),,(),,(),,(),,(),,(),,(),,{(3dcccdbcbabdacaba29（3）利用关系图求复合关系n设是有限集A上的关系，则复合关系也是A上的关系，由复合关系的定义，对于任意的，当且仅当存在，使得，时，有。2Aaaji,Aakkiaajkaajiaa2反映在关系图上，这意味着，当且仅当在的关系图中有某一结点存在，使得有边由指向，且有边由指向时，在的关系图中有边从指向。kaiakaka2iajajajakaiajaia230类似地，对于任意正整数n，当且仅当在的关系图中存在n-1个结点,使得有边由指向,由指向，…由指向时，在的关系图中，有边由结点指向。121nkkkaaa,,,ia1ka1ka2ka1nkajaniaja根据的关系图构造出的关系图：n对于的关系图中的每一结点，找出从经过长为n的路能够到达的结点，这些结点在的关系图中，边必须由指向它们。iaiania31例10试利用构造和的关系图的方法求例9中的和。例中2323)},(),,(),,(),,(),,{(cbdcccabba（4）根据和的关系图直接写出和中的序偶.2323解（1）先作出的关系图（2）构造的关系图。在的关系图中寻找长为2的路。2（3）构造的关系图。在的关系图中寻找长为3的路.332)3,3(),3,2(),2,2(),3,1(),2,1(),1,1(练习3-71.设，A上的关系则用列举法表示}3,2,1{A}|),{(yxyx1}|),{(yxyx2}{1}{2}{~1}{11AA}{21)2,3(),1,3(),3,2(),1,2)(3,1(),2,1()3,2(),3,1(),2,3(),2,1(),1,3(),1,2()2,3(),1,3(),1,2()3,3(),2,2(),1,1(33则复合关系2.设，A上的关系},,,{3210A)},(),,(),,(),,(),,{(00123221101)},(),,{(13022}{21}{12}{21}{121)1,2(),0,