第四章二元关系.

第四章二元关系第四章二元关系•4.1关系的基本概念•4.2关系的性质•4.3关系的表示•4.4关系的运算•4.5特殊关系4.1关系的基本概念定义：设且为n个任意集合，nI12nAAA,,,1niiRXA(a)称R为间的n元关系；12,,,nAAA(b)若n=2，则称R为A1到A2的二元关系；(c)若，则称R为空关系；若，则称R为全关系；R1niiRXA(d)若，则称R为A上的n元关系。12nAAAA一、关系的定义一、关系的定义例：令则称R1是N上的一元关系，R2是N上的二元关系，R3是N上的三元关系。如无特殊指定，“关系”概指二元关系。1{2|}RnnN2{,2|}RnnnN2223{,,|,,}RnmknmkNnmk若序偶属于R，则记作或，否则，记作或。,xy,xyRxRy,xyRxRy一、关系的定义例：设集合A={a,b},B={2,5,8}则{,2,,5,,8,,2,,5,,8}ABaaabbb令1{,2,,2,,8}abb2{,5}a则均是由A到B的关系。12,同理，3{2,,5,}abBA则是由B到A的关系。3同理，4{2,2,5,8}BB则是由B到B的关系。4一、关系的定义例：设集合A={2,3,5,9}，试给出集合A上的小于或等于关系，大于或等于关系。解：令集合A上的小于或等于关系为R1，大于或等于关系为R2，根据定义有：12{2,2,3,3,5,5,9,9,2,3,2,5,2,9,3,5,3,9,5,9}{2,2,3,3,5,5,9,9,3,2,5,2,9,2,5,3,9,3,9,5}RR二、关系的相等定义：设R1为A1,A2,…,An间的n元关系，R2为B1,B2,…,Bm间的m元关系，如果：（1）n=m（2）若，则（3）把R1和R2作为集合看，R1=R2。则称n元关系R1和m元关系R2相等，记作R1=R21iniiAB二、关系的相等例：设R1为从Z到I+的二元关系，R2和R3都是I上的二元关系123{,|1}{,1|0}{||,||1|}RnmnZmImnRnnnInRnnnI从集合的观点来看，R1=R2=R3。但是就二元关系来说，R2=R3，不等于R1。三、关系的定义域和值域关系R(从A到B的关系)的定义域(简称为域)定义为：关系R的值域定义为：D(R)={x|(y)(,R)}xyR(R)={y|()(,R)}xxy显然，有(),()DRARRB例：设A={2,3,5},B={2,6,7,8,9}，由A到B的关系R定义为：当且仅当a整除b时，有aRb。可得:{2,2,2,6,2,8,3,6,3,9}RD(R)={2,3}R(R)={2,6,8,9}AB第四章二元关系•4.1关系的基本概念•4.2关系的性质•4.3关系的表示•4.4关系的运算•4.5特殊关系4.2关系的性质定义：设R为A上的二元关系(1)若对每个，皆有，则称R为自反的。用式子来表述即是：R是自反的xA,xxR(x)(xA,R)xx(2)若对每个，皆有，则称R为反自反的。用式子来表述即是：R是反自反的xA,xxR(x)(xA,R)xx4.2关系的性质(3)对任意的，若，则，就称R为对称的。用式子来表述即是：R是对称的,xyA()()(,,,)xyxyAxyRyxR,xyR,yxR(4)对任意的，若且，则x=y，就称R为反对称的。用式子来表述即是：R是反对称的,xyA,xyR,yxR()()(,,,)xyxyAxyRyxRxy4.2关系的性质,yzR(5)对任意的，若且，则，就称R为可传递的。用式子来表述即是：R是可传递的,,xyzA,xyR,xzR()()()(,,,,,)xyzxyzAxyRyzRxzR(6)存在，并且而，就称R为不可传递的。用式子来表述即是：R是不可传递的,,xyzA,,xyRyzR,xzR()()()(,,,)xyzxyRyzRxzR4.2关系的性质例1：考虑自然数集合上的普通相等关系“=”，大于关系“”和大于等于关系“”具有的性质。解：(1)“=”关系是自反的、对称的、反对称的、可传递的；(2)“”关系是反自反的、反对称的、可传递的；(3)“”关系是自反的、反对称的、可传递的。例2：空集上的二元关系的性质。自反的、对称的、反对称的、反自反的、可传递的集合的压缩和开拓定义：设R为集合A上的二元关系且，则称S上的二元关系为R在S上的压缩，记为，并称R为在A上的开拓。SA()RSS|Rs|Rs定理：设R为A的二元关系且，那么：SA(1)若R是自反的，则也是自反的；|Rs(2)若R是反自反的，则也是反自反的；|Rs(3)若R是对称的，则也是对称的；|Rs(4)若R是反对称的，则也是反对称的；|Rs(5)若R是可传递的，则也是可传递的；|Rs第四章二元关系•4.1关系的基本概念•4.2关系的性质•4.3关系的表示•4.4关系的运算•4.5特殊关系4.3关系的表示定义：设A和B为任意的非空有限集，R为任意一个从A到B的二元关系。以中的每个元素为结点．对每个皆画一条从x到y的有向边，这样得到的一个图称为关系R的关系图。一、关系图AB,xyRxAyB例：A={1,2,4};B={3,5,6};关系R={1,3,2,6,2,5}A124B356一、关系图例：设A={2,3,4,5,6},B={6,7,8,12}，从A到B的二元关系R为，画出其关系图。{,|}RxyxAyBxy整除解：先求出R{2628212363124841266612}R，，，，，，，，，，，，，，，，，386122475一、关系图yxxyxyxxRyxRxxRyyRyxRyyRxyzxxRyyRzzRx对称关系反对称关系二、关系矩阵定义：给定两个有限集合X={x1,x2,…,xm}和Y={y1,y2,…,yn}，R是从X到Y的二元关系，如果有：10ijijijxyRrxyR如果如果则称是R的关系矩阵，记作MR||||[]ijXYXYr。例：设A={1,2,3,4},R为定义在A上的二元关系，R={2,1,3,1,3,2,4,1}，写出关系矩阵。4400001000[]11001000RijMr二、关系矩阵例：设A={1,2,3},B={a,b,c},R是A到B的二元关系，并且，试画出R的关系图，给出关系矩阵。{1,,2,,3,}Rabc6612310001002000010[]3000001000000000000000000RijabcMrabc1a2b3c二、关系矩阵•如果关系矩阵主对角线上的记入值全为1，则R是自反的；•如果主对角线上的记入值全为0，则R是反自反的；•如果矩阵关于主对角线是对称的，则R是对称的；•如果矩阵关于主对角线是反对称的，(亦即rij=1时则一定有rji=0),则R是反对称的；•如果对于任意的i,j,k,rij=1并且rjk=1时一定有rik=1，则R是可传递的；•如果存在i,j,k,rij=1并且rjk=1时，有rik不等于1，则R是不可传递的；第四章二元关系•4.1关系的基本概念•4.2关系的性质•4.3关系的表示•4.4关系的运算•4.5特殊关系4.4关系的运算注意：由于关系也是特殊的集合，因此集合的运算也适用于关系中。设R1和R2是从A到B的二元关系，那么，，也是从A到B的二元关系，它们分别被称为二元关系R1和R2的交、并、差分和对称差分。12RR12RR12RR12RR4.4关系的运算例：设集合A={a,b,c}，B={d,e}，定义A到B的二元关系R1={a,d,a,e,b,d,c,e}R2={a,d,b,e,c,d}则12{,}12{,,,,,,,,,,,}12{,,,,,}21{,,,}~1{,,,}12{,,,,,,,,,}RRadRRadaebdbecdceRRaebdceRRbecdRbecdRRaebdbecdce4.4关系的运算•4.4.1关系的合成•4.4.2合成关系的矩阵表达和图解•4.4.3关系的求逆运算•4.4.4关系的闭包运算4.4.1关系的合成定义：设R是从X到Y的关系，S是从Y到Z的关系，于是可用R◦S表示从X到Z的关系，通常称它是R和S的合成关系，用式子表示即是：{,|()(,,)}RSxzxXzZyyYxyRyzS例：给定集合X={1,2,3,4}，Y={2,3,4}和Z={1,2,3}。设R是从X到Y的关系，并且S是从Y到Z的关系，并且R和S给定成：{,|6}{2,4,3,3,4,2}{,|1}{2,1,3,2,4,3}RxyxySyzyz试求R和S的合成关系，并画出合成关系图给出合成关系的关系矩阵。关系的合成解：找出所有这样的偶对——对于某一个y来说，能有x+y=6和y-z=1，由上述的偶对就可构成从X到Z的关系R◦S。,xz{2,3,3,2,4,1}RS124312431243RSSRxyxyzz关系的合成123412341234111222333010100100444010000101000RSRSMMM000000000000000110000010000定义布尔运算：0+0=0，1+0=0+1=1+1=11·1=1，0·1=1·0=0·0=0对两个关系矩阵求其合成时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。关系的合成注意：设是R从集合X到集合Y的关系，S是从集合Y到集合Z的关系，于是有：如果R关系的值域与S关系的定义域的交集是个空集，则合成关系R◦S也是个空关系；若至少有一个序偶，其中笫二个成员是S中的某一个序偶的笫一个成员，则合成关系就是个非空关系。对于合成关系R◦S来说，它的定义域是集合X的子集，而它的值域则是Z的子集，事实上，它的定义域是关系R的定义域的子集，它的值域是关系S的值域的子集。,xyR关系的合成定理：给定集合X,Y,Z和W，设R1是从X到Y的关系，R2和R3是Y到Z的关系，R4是从Z到W的关系，于是有：()()()()()()()()()()()()()()()()aRRRRRRRbRRRRRRRcRRRRRRRdRRRRRRR1231213123121323424342342434关系的合成()()()()aRRRRRRR1231213证明：当且仅当存在某一个，能使和，才有，而yY1,xyR23,yzRR123,()xzRRR123()(,,)yxyRyzRR1231213121312131213()(,(,,))()(,,,,)()(,(,)()(,,),,,()()yxyRyzRxzRyxyRyzRxyRyzRyxyRyzRyxyRyzRxzRRxzRRxzRRRR