离散数学第4章-关系

1第4章关系24-1.关系及其运算关系的基本概念“关系”是一个很基本的概念,为了用数学的方法来研究和讨论各种关系,下面从集合论的观点来描述关系.例:设A={a,b,c,d,e,f},a,b,c,d,e,f分别表示６个男人,其中a是b和c的父亲,b是d的父亲,c是e和f的父亲.则这6个人中所有符合父子关系的两个人可分别用有序偶(a,b),(a,c),(b,d),(c,e),(c,f)来表示，则集合Ｒ＝｛(a,b),(a,c),(b,d),(c,e),(c,f)｝可完整地描述出集合Ａ中元素的父子关系．称R为集合上的一个关系(父子关系).例:Ａ＝｛１，２，３｝上的小于关系可表示为Ｒ＝｛(1,2),(1,3),(2,3)}3两个集合之间的关系设A={a,b,c,d},B={m,p,e},A中的元素a,b,c,d分别表示4位中学教师,B中的元素m,p,e分别表示数学课程、物理课程和英语课程。如果a和b是数学教师，c是物理教师，d是英语教师。则有序偶:(a,m),(b,m)(c,p),(d,e)表示了这4位教师和他们所讲授课程的关系。由这些有序偶作为元素构成的集合R={（a,m),(b,m)(c,p),(d,e)}称为A到B的二元关系。二元关系的实质是什么？4关系的实质由于二元关系就是符合某种特定要求的有序偶的集合.因此A到B的二元关系应是笛卡儿乘积A×B的子集A上的二元关系应是A上的笛卡儿乘积A×A的子集。为了便于对二元关系进行一般性的讨论，下面把二元关系的概念抽象化，即抽象地把二元关系看做是笛卡儿乘积的子集。5二元关系的定义定义设A,B是集合，R是笛卡儿乘积A×B的子集，则称R为A到B的一个二元关系。例如:设A={a,b,c,d},B={x,y,z},令R={(a,y),(b,x),(b,y),(d,x)}由于R是A×B的子集，所以R是A到B的一个二元关系。类似,可定义n元关系.6n元关系的定义定义.,,,2121的一个子集是元关系所确定的由集合nnXXXnXXX7二元关系的定义对于二元关系R,如果(a,b)∈R，也可记作aRb，并称a与b有关系R。如果(a,b)R，也可记作aRb，并称a与b没有关系R。定义设A是集合，R是A上的笛卡儿乘积A×A的子集，则称R为A上的一个二元关系。例如:设A={1，2，3，4，5},R={（1，1）,（2，5）,（3，1）,（4,3）,(4,5)}，由于R是A×A的子集，所以R为A上的一个二元关系。8二元关系的定义域和值域定义设S是A到B的二元关系，使(x,y)∈S的所有x组成的集合称为S的定义域，记作D(S)；使(x,y)∈S的所有y组成的集合称为S的值域，记作C(S)或R(S)。易知:D(S)就是S的所有有序偶的第一个元素构成的集合,C(S)就是S的所有有序偶的第二个元素构成的集合.9求关系的定义域和值域例如:设则R的定义域D(R)，值域C(R))}b,a(),b,a(),b,a{(R},b,b,b{B},a,a,a,{aA3433113214321}a,a,{a431},{31bb10例1例1:设A={2，4，6，8}，R是A上的小于关系，即当a,b∈A且ab时，（a,b）∈R，求R及D(R),C(R)解:R={（2，4）,（2，6）,（2，8）,（4，6）,（4，8）,（6，8）}.R的定义域D(R)={2，4，6}，R的值域C(R)={4，6，8}。11例2例2:设A={2，3，4，6，12}，R是A上的整除关系，即当a,b∈A且a能整除b时，（a,b）∈R，求R及D(R),C(R)解:A上有整除关系为R={（2，2）,（2，4）,（2，6）,（2，12）,（3，3）,（3，6）,（3，12）,（4，4）,（4，12）,（6，6）,（6，12）,（12，12）}，R的定义域D(R)={2，3，4，6，12}，R的值域C(R)={2，3，4，6，12}。12例3例3设A={a,b}，B={x，y}，写出所有A到B的二元关系。，13例3例3设A={a,b}，B={x，y}，写出所有A到B的二元关系。解:由于，所以，由此可知，A×B共有子集数为=16，即共有16种A到B的二元关系：2B,2A4BA，42)},(),,{()},(),,{()},(),,{()},{()},{()})},{(76543210ybxaRybxbRyaxaRybRxbRy{(a,RxaRR)}y,b(),x,b(),y,a(),x,a{(R)}y,b(),x(b,),y,a{(R)}y,b(),x,b(),x,a{(R)}y,b(),y(a,),x,a{(R)}x,b(),y,a(),x,a{(R)}y,b(),y(a,{R)}x,b(),x,a{(R)}y,a(),x,b{(R1514131211109814例3的说明此例说明，当时，A到B共可定义种不同的二元关系。问:在一个有n个元素的集合A上，可以有多少种不同的二元关系？答：共有种．mBn,Amn22n215三种特殊的关系对于任意集合，空集和集合本身都是它的子集，常称这两种子集为平凡子集。定义笛卡儿乘积A×B的两个平凡子集，空集和A×B本身称为集合A到B的空关系和全域关系。定义设R是A上的二元关系且满足则称R为A上的恒等关系，并记作。})a,a{(RAaAI16例子例4:设集合A={1，2，3}，R是A上的二元关系，当a,b∈A且a×b0时，（a,b）∈R。则R={（1，1）,（1，2）,（1，3）,（2，2）,（2，1）,（2，3）,（3，1）,（3，2）,（3，3）}所以R是A上的全域关系。若令当a,b∈A且a×b0时，（a,b）∈R，则R=即R是A上的空关系。例5:设A={a,b,c,d},则A上的恒等关系={(a,a),(b,b),(c,c),(d,d)}。AI练习172关系的表示方法1.关系矩阵设集合，R是A到B的二元关系，令则称为R的关系矩阵.}b,,b,b{B},a,,a,{aAm2121nR)b,a(0R)b,a(1cjijiijnm2n1nm22221m11211ijRccccccccccM18关系的表示方法例1:设R是A到B的二元关系，且则R的关系矩阵为}b,b,b,b,b{B},a,a,a,a,a,{aA54321654321)}b,a(),b,a(),b,a(),b,a(),b,a(),b,a(),b,a(),b,a({R5646255433322111110000001010000001000010000011MRA是行，B是列19关系的表示方法设,R为A上的二元关系,令则n阶方阵称为R的关系矩阵}a,,a,a{A21nR)a,(a0R)a,(a1ajijiijnn2n1nn22221n11211RaaaaaaaaaMija20关系的表示方法例2设A={1,2,3,4,5},R是A上的小于等于关系,即当a≤b时,(a,b)∈R。求R的关系矩阵。解:易知A上的小于等于关系为R={（1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)}其关系矩阵为1000011000111001111011111MR21关系的表示方法2.关系图设集合，R是A到B的二元关系。R的图形表示是在平面上用n个点分别表示A中的元素；再在平面上画出m个点分别表示B中元素；当时，从点至画一条有向边，其箭头指向，否则就不画边。例3:R是A到B的二元关系，且则R的关系图为？}b,,b,b{B},a,,a,{aAm2121nna,,a,a21m21b,,b,bR)b,(jiaiajbjb}b,b,b,b{B},a,a,a,a,{aA432154321)}b,a(),b,a(),b,a(),b,a(),b,a({R4524133211a2a1a3a4a5b1b2b3b422关系的表示方法当R是A上的二元关系时，经常采用如下的图形表示方法：在平面上仅仅画n个点分别表示A中的元素，当时，从点至画一条有向边，箭头指向。例如，，R是A上的二元关系，且则R的关系图为na,,a,a21R),(jaaiiajaja}a,a,a,a,{aA54321)},a),(a,a),(a,a),(a,a),(a,a),(a,a),(a,a{(aR4535434232211123小结二元关系的表示方法（它们可唯一相互确定）集合表达式关系矩阵（用矩阵表示关系，便于在计算机中对关系进行存储和计算，并可充分利用矩阵的结论）关系图（关系图直观清晰，是分析关系性质的方便形式，但它不便于进行运算）练习243.关系的运算关系的交、并、差、对称差、补设R和S是集合A上的两个二元关系,则R∩S,R∪S,R-S,R+S,～R仍是A上的二元关系.25关系的运算例：X={a,b,c}，Y={1，2}，关系R={(a,1),(b,2),(c,1)}S={(a,1),(b,1),(c,1)}则：R∪S={(a,1),(b,1),(b,2),(c,1)}R∩S={(a,1),(c,1)}E={(a,1),(a,2),(b,1),(b,2),(c,1),(c,2),}R=E-R={(a,2),(b,1),(c,2)}练习26复合关系1.复合关系的定义定义R是A到B的二元关系，S是B到C的二元关系，R和S的复合记作RοS，它是A到C的二元关系，仅当(a,b)∈R，且(b,c)∈S时，(a,c)∈RοS。例:设，R是A到B的二元关系，S是B到C的二元关系，且则R和S的复合}c,c,c{C},b,b,b,{bB},a,a,{aA3214321321)}c,b(),c,b(),c,b(),c,b({S)}b,a(),b,a(),b,a(),b,a{(R2332211143232211)}c,a(),c,a(),c,a(),,a{(SR33322111c27用关系图法求复合关系RSABCa1b1c1a2b2c2a3b3c3b4)}c,a(),c,a(),c,a(),,a{(SR33322111c)}c,b(),c,b(),c,b(),c,b({S)}b,a(),b,a(),b,a(),b,a{(R233221114323221128用关系图法求复合关系由R和S的关系图得，复合关系RSAAAa1a1a1a2a2a2a3a3a3a4a4a4a5a5a5)}a,a(),a,a(),a,a(),a,a(),a,a{(S)},a,a(),a,a(),a,a(),a,a({R},a,a,a,a,{aA24433322215443322154321)}a,a(),a,a(),a,a(),a,a({SR2342322129复合关系的矩阵表示定理R是A到B的二元关系，其关系矩阵为，S是B到C的二元关系，其关系矩阵为，复合关系RοS是A到C的二元关系，其关系矩阵为，则注意:按普通矩阵乘法求,只不过是将乘法改为布尔乘,加法改为布尔加.RMSMSRMSRSRMMMSRMM30例1设A={1，2，3}，B={a,b,c,d},C={x,y,z}，R是A到B的二元关系，R={(1,a),(1,b),(2,b),(3,c)}，S是B到C的二元关系，S={(a,x),(b,x),(b,y),(b,z)}。求复合关系RοS的关系矩阵.解:因为所以000000111001M,010000100011SRM