第三章集合与关系6.复合和逆

六、复合关系和逆关系(一)复合关系

设R1是从X到Y的二元关系，R2是从Y到Z的二元关系，则R1与R2的复合关系为从X到Z的二元关系，记为R1

R2，定义为

R1

R2={<x,z>|xXzZ(y)(yY<x,y>R1<y,z>R2)}其中表示二元关系的合成运算.关系合成运算的性质设R是从X到Y的二元关系，IX,IY分别是X,Y上的恒等关系，则IX

R=R

IY=R;如果二元关系R1的值域与R2的定义域的交集为空集，则复合关系R1

R2是空关系；二元关系的合成运算满足结合律：设R1,R2,R3分别是从A到B,B到C,C到D的二元关系，则(R1

R2)

R3=R1

(R2

R3).合成运算满足交换律吗？No.六、复合关系和逆关系例3.6.1设二元关系R={<1,2>,<2,2>,<2,3>,<3,4>},S={<1,3>,<2,5>,<3,1>,<3,5>,<4,2>}，求复合关系R

S,S

R,R

R,R

R

R.解：R

S={<1,5>,<2,5>,<2,1>,<3,2>},S

R={<1,4>,<3,2>,<4,2>,<4,3>},R

R={<1,2>,<1,3>,<2,2>,<2,3>,<2,4>},R

R

R=={<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,<2,4>}.(R

R)

R

用关系图来反映关系的复合，更为直观、可靠.比如R

S：123451234123六、复合关系和逆关系用关系矩阵求复合关系

设A

B

=C，关系矩阵为MA=(aij)n

n,MB=(bij)n

n,MC=(cij)n

n,则cij=(aikbkj).

nk=1上式中，代表逻辑加，满足00=0,01=1,10=1,11=1.代表逻辑乘，满足00=0,01=0,10=0,11=1.如何理解？公式的理解：要想“i”与“j”建立关系，则至少存在一个“k”，使“i”与“k”有关系，且“k”与“j”有关系.（公式中的和分别体现的就是“至少存在一个”和“且”.）逻辑加和逻辑乘的理解：关系矩阵中的元素1和0，表达的是关系“有”和“无”，即T和F.（把运算规则中的1和0分别换成T和F，易见等式成立.）六、复合关系和逆关系例3.6.2设A={1,2,3,4},B={2,3,4},C={1,2,3}，R1是从A到B的二元关系，R2是从B到C的二元关系：R1={<x,y>|x+y=6}分别用列举法、图示法、关系矩阵法表示关系的合成R1

R2

.={<2,4>,<3,3>,<4,2>},R2={<y,z>|y-z=1}={<2,1>,<3,2>,<4,3>},解：(1)列举法R1

R2={<2,3>,<3,2>,<4,1>}.(2)图示法1234234123六、复合关系和逆关系例3.6.2设A={1,2,3,4},B={2,3,4},C={1,2,3}，R1是从A到B的二元关系，R2是从B到C的二元关系：R1={<x,y>|x+y=6}分别用列举法、图示法、关系矩阵法表示关系的合成R1

R2

.={<2,4>,<3,3>,<4,2>},R2={<y,z>|y-z=1}={<2,1>,<3,2>,<4,3>},(3)关系矩阵法解：六、复合关系和逆关系关系的幂

设R是集合A上的二元关系，nN为任一自然数，则R的n次幂记为Rn，定义为：(1)R0为A上的恒等关系，R0={<x,x>|xA}.(2)Rn+1=Rn

R.从a到b有一条长度为2的路径.在R2的图形上，有一条a到b的弧，则在R的图形上从a到b有一条长度为n的路径.在Rn的图形上，有一条a到b的弧，则在R的图形上六、复合关系和逆关系(二)逆关系例3.6.3设二元关系R={<1,a>,<2,b>,<3,c>}，其逆关系Rc={<a,1>,<b,2>,<c,3>}.注意一个常用的表达：<a,b>R<b,a>Rc

设R是从X到Y的二元关系，R的逆关系（简称为R的逆）记为Rc，定义如下：

Rc={<y,x>|<x,y>R}.例3.6.4整数集上的“<”关系的逆是恒等关系；空关系的逆是空关系；AB的全域关系的逆是BA的全域关系.恒等关系的逆是“>”关系；集合族上的“

”关系的逆是“”关系；六、复合关系和逆关系逆关系的求法

将矩阵MR转置，得Rc的关系矩阵,即关系图：

把R中每一序偶的元素顺序互换，可得到逆关系Rc的所有序偶.六、复合关系和逆关系

在R的关系图中，颠倒弧（有向边）的箭头方向，得到Rc的关系图.关系矩阵：列举法：逆关系的性质性质一：设R,R1,R2是X到Y的二元关系，则6)R1R25)(R1-R2)c=4)(~R)c=3)(R1∩R2)c=2)(R1∪R2)c=1)(Rc)c=R;R1c∪R2c;R1c∩R2c;~(Rc);R1c-R2c;R1c

R2c.<a,b>R<a,b>~R;或<a,b>R<a,b>~R.其中~R=XY-R是XY中不属于R的序偶所组成的集合，称为R的关系补，或说~R是R关于XY的补集.有常用关系式：六、复合关系和逆关系性质一的证明1)(Rc)c=R;证明：

任取<x,y>，则<x,y>R

<y,x>Rc

<x,y>(Rc)c3)(R1∩R2)c=R1c∩R2c;证明：

任取<x,y>，则<x,y>(R1∩R2)c

<y,x>R1∩R2

<y,x>R1<y,x>R2

<x,y>R1c

<x,y>R2c

<x,y>R1c∩R2c六、复合关系和逆关系性质一的证明4)(~R)c=~(Rc);证明：

任取<x,y>，则<x,y>(~R)c

<y,x>R

<y,x>~R

<x,y>Rc

<x,y>~(Rc).5)(R1-R2)c=R1c-R2c;证明：

因为R1-R2=R1∩~R2，故有(R1-R2)c=(R1∩~R2)c

=R1c∩(~R2)c

=R1c∩~(R2)c

=R1c-R2c.6)R1R2R1c

R2c.证明：

任取<x,y>R1c，则<x,y>R1c

<y,x>R1<y,x>R2<x,y>R2c六、复合关系和逆关系逆关系的性质性质二：设R1是从X到Y的二元关系，R2是从Y到Z的二元关系，则(R1

R2)c=R2c

R1c.证明：

任取<z,x>，则<z,x>(R1

R2)c

<x,z>R1

R2

(y)(yY<x,y>R1<y,z>R2)

<z,x>R2c

R1c.

(y)(yY<y,x>R1c<z,y>R2c)

XYZR1R2(R1

R2)cR1

R2六、复合关系和逆关系逆关系的性质性质三：设R是集合X上的二元关系，则(1)R是对称的，当且仅当R

=Rc；(2)证明：

(2)R是反对称的，当且仅当R

∩RcIX.设R是反对称的，任取<x,y>R

∩Rc，则<x,y>R<x,y>Rc<x,y>R<y,x>R而R是反对称的，故x=y.所以<x,y>=<y,x>IX即R

∩RcIX.六、复合关系和逆关系逆关系的性质性质三：设R是集合X上的二元关系，则(1)R是对称的，当且仅当R

=Rc；(2)证明：

(2)R是反对称的，当且仅当R

∩RcIX.反之，设R

∩RcIX

，<x,y>R<y,x>R故R是反对称的.<x,y>R<y,x>R，则<x,y>R<x,y>Rc<x,y>R

∩Rc

<x,y>IX

x=y.六、复合关系和逆关系任取x,yX,若(1)R在X上自反，当且仅当例3.6.5设R为X上的二元关系，证明：(2)R在X上反自反，当且仅当(3)R在X上传递，当且仅当证明：IX

R.R∩IX=

.R

R

R.(1)必要性：任取<x,x>IX,如果R在X上自反，必有<x,x>IXxX

<x,x>R

,从而IX

R.充分性：当IX

R时，xX<x,x>IX<x,x>R

,因此R在X上是自反的.从关系矩阵角度看，R是自反的，则MR的主对角元全为1.所以IX

R.任取xX

,有六、复合关系和逆关系结论可直接用(1)R在X上自反，当且仅当例3.6.5设R为X上的二元关系，证明：(2)R在X上反自反，当且仅当(3)R在X上传递，当且仅当证明：IX

R.R∩IX=

.R

R

R.(2)必要性:(反证法)设R在X上反自反，但R∩IX,则必存在<x,y>R∩IX,从而<x,y>R∩IX

<x,y>R

<x,y>IX

<x,y>R

x=y

<x,x>R.

这与“R是反自反的”矛盾.设R