第4章二元关系(一).

第4章二元关系第4章二元关系4.1二元关系及其表示4.2关系的运算4.3关系的性质4.4关系的闭包运算4.5等价关系4.6相容关系第4章二元关系第4章二元关系4.1二元关系及其表示4.1.1二元关系的概念定义4.1.1设A和B是任意集合，如果RA×B，则称R是A到B的二元关系。如果R是A到A的二元关系，则称R是A上的二元关系。设A=1,2,3，B=a,b，R=1,a,2,a,3,b。R是A到B的二元关系。S=3,1,2,2,2,1,1,1。S是A上的二元关系。定义4.1.2设A和B是任意集合，RA×B，若x,yR，则称x与y有R关系。记为xRy。若x,yR，则称x与y没有R关系。记为xy。R第4章二元关系定义4.1.3设A和B是任意集合，空集叫做A到B的空关系，仍然记为。A，B的笛卡尔积A×B叫做A到B的全域关系，记为E。集合a,a|aA叫做A上的恒等关系。记为IA。【例4.1】设A=a,b，B=1,2，求A上的恒等关系IA和A到B的全域关系A×B。解：A上的恒等关系IA=a,a,b,b，A到B的全域关系E=A×B=a,1,a,2,b,1,b,2定理4.1.1设A是具有n个元素的有限集，则A上的二元关系有2n2种。证明：设A为具有n个元素的有限集，即|A|=n，由排列组合原理知|A×A|=n2。根据定理3.1.2有|P(A×A)|=2|A×A|=2，即A×A的子集有2个。所以具有n个元素的有限集A上有2种二元关系。2n2n2n第4章二元关系例：若|A|=m，|B|=n，问A到B共有多少个不同的二元关系？解：2m×n4.1.2二元关系的表示1.用列举法表示二元关系例4.1中的A到B的全域关系E=A×B=a,1,a,2,b,1,b,2A上的恒等关系IA=a,a,b,b都是用列举法表示的。2.用描述法表示二元关系设R是实数集，LR=x,y|xR∧yR∧x≤y，LR是实数集R上的二元关系。第4章二元关系3.用矩阵表示二元关系如果A，B是有限集，A=a1,a2,…,am，B=b1,b2,…,bn，R是A到B的二元关系，R的关系矩阵定义为：MR=mnRRbbaarjjiiij,,01i=1,…,mj=1,…,n称为二元关系R的关系矩阵。ijr第4章二元关系【例4.3】设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关系，定义为：R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2写出R的关系矩阵。解：R的关系矩阵为：MR=011001110101第4章二元关系【例4.4】设A=1,2,3,4，R是A的二元关系，定义为：R=1,1,1,2,2,1,3,2,3,1,4,3,4,2,4,1写出A上二元关系R的关系矩阵。解：R的关系矩阵为：MR=0111001100010011例4.4中的二元关系R是A上的二元关系，只需看成A到A的二元关系，利用上述定义，就可以方便地写出它的关系矩阵。A上的二元关系和A到B的二元关系的关系矩阵的定义是相同的。第4章二元关系4.用图表示二元关系如果A和B是有限集，R是A到B二元关系，表示二元关系R的图叫做R的关系图。A到B二元关系的关系图和A上的二元关系的关系图的定义是不一样的。分别描述如下：⑴A到B二元关系R的关系图设A=a1,a2,…,am，B=b1,b2,…,bn，R是A到B二元关系，R的关系图的绘制方法如下：①画出m个小圆圈表示A的元素，再画出n个小圆圈表示B的元素。这些小圆圈叫做关系图的结点(下同)。②如果ai,bjR，则从ai到bj画一根有方向(带箭头)的线。这些有方向(带箭头)的线叫做关系图的边(下同)。第4章二元关系⑵A上的二元关系R的关系图设A=a1,a2,…,am，R是A上的二元关系，其关系图如下绘制：①画出m个小圆圈表示A的元素。②如果ai,ajR，则从ai到aj画一根有方向(带箭头)的线。例4.3、例4.4中的二元关系R的关系图如下图第4章二元关系4.2关系的运算定义4.2.1设A，B是集合，RA×B。domR=x|x,yR叫做R的定义域。ranR=y|x,yR叫做R的值域。FLDR=domR∪ranR叫做R的域。4.2.1二元关系的交、并、补、对称差运算定理4.2.1设R，S是X到Y的二元关系，则R∪S，R∩S，R-S，~R，RS也是X到Y的二元关系。证明：因为R，S是X到Y的二元关系，所以，RX×Y且SX×Y。显然，R∪SX×Y，即R∪S是X到Y的二元关系。R∩SX×Y，即R∩S是X到Y的二元关系。R-SX×Y，即R-S是X到Y的二元关系。第4章二元关系在二元关系运算中，认为全域关系是全集。所以~R=X×Y-RX×Y，即~R是X到Y的二元关系。由以上结论可以得到：(R－S)X×Y和(S－R)X×Y，从而(R－S)∪(S－R)X×Y，所以RS=(R－S)∪(S－R)X×Y，即RS是X到Y的二元关系。【例4.5】设X=1,2,3,4，X上的二元关系H和S定义如下：H=x,y|是整数S=x,y|是正整数试求H∪S，H∩S，~H，S-H2yx3yx第4章二元关系解：将H和S用列举法表示：H=1,1,1,3,2,2,2,4,3,3,3,1,4,4,4,2S=4,1H∪S=1,1,1,3,2,2,2,4,3,3,3,1,4,4,4,2,4,1H∩S=~H=X2-H=1,2,1,4,2,1,2,3,3,2,3,4,4,3,4,1S－H=4,14.2.2二元关系的复合运算定义4.2.2设X，Y，Z是集合，RX×Y，SY×Z，集合x,zxX∧zZ∧(y)(yY∧x,yR∧y,zS)叫做R和S的复合关系。记为R∘S，R∘SX×Z，即R∘S是X到Z的二元关系。第4章二元关系【例4.6】X=1,2,3,4,5，X上的二元关系R和S定义如下：R=1,2,3,4,2,2S=4,2,2,5,3,1,1,3试求R∘S，S∘R，R∘(S∘R)，(R∘S)∘R，R∘R，S∘S，R∘R∘R解：R∘S=1,5,3,2,2,5S∘R=4,2,3,2,1,4(R∘S)∘R=3,2R∘(S∘R)=3,2R∘R=1,2,2,2S∘S=4,5,3,3,1,1R∘R∘R=1,2,2,2从例4.6可以看出，R∘S≠S∘R，这说明，二元关系的复合运算不满足交换律。第4章二元关系定理4.2.2设X，Y，Z，W是集合，RX×Y，SY×Z，TZ×W，则(R∘S)∘T=R∘(S∘T)证明：x,w(R∘S)∘T(z)(x,zR∘S∧z,wT)(z)((y)(x,yR∧y,zS)∧z,wT)(z)(y)((x,yR∧y,zS)∧z,wT)(y)(z)(x,yR∧(y,zS∧z,wT))(y)(x,yR∧(z)(y,zS∧z,wT))(y)(x,yR∧y,wS∘T)x,wR∘(S∘T)所以(R∘S)∘T=R∘(S∘T)(y)(x,yR∧y,zS)(y)(y)(z)(y,zS∧z,wT)(z)y,wS∘T第4章二元关系定理4.2.3设R是A上的二元关系，R∘IA=IA∘R=R证明：先证R∘IA=Rx,yR∘IA(z)(x,zR∧z,yIA)(z)(x,zR∧z=y)x,yR所以R∘IARx,yRx,yR∧y,yIAx,yR∘IA所以RR∘IA故R∘IA=R类似的，可以证明IA∘R=R第4章二元关系定理4.2.4设R，S，T是A上的二元关系,则⑴R∘(S∪T)=R∘S∪R∘T⑵(R∪S)∘T=R∘T∪S∘T⑶R∘(S∩T)R∘S∩R∘T⑷(R∩S)∘TR∘T∩S∘T证明：仅证明⑶，类似地可证明⑴、⑵和⑷。x,yR∘(S∩T)(z)(x,zR∧z,yS∩T)(z)(x,zR∧(z,yS∧z,yT))(z)((x,zR∧z,yS)∧(x,zR∧z,yT))(z)(x,zR∧z,yS)∧(z)(x,zR∧z,yT)x,yR∘S∧x,yR∘Tx,yR∘S∩R∘T故R∘(S∩T)R∘S∩R∘T第4章二元关系一般地说，R∘S∩R∘T⊈R∘(S∩T)，举反例如下：设A=1,2,3,4,5R=4,1,4,2A×AS=1,5,3,5A×AT=2,5,3,5A×AR∘S∩R∘T=4,5∩4,5=4,5R∘(S∩T)=4,1,4,2∘3,5=R∘S∩R∘T⊈R∘(S∩T)定理4.2.4的⑴说明，关系的复合运算“∘”对并运算“∪”满足左分配律。⑵说明，关系的复合运算“∘”对并运算“∪”满足右分配律。所以，复合运算“∘”对并运算“∪”满足分配律。由⑶和⑷知，复合运算“∘”对交运算“∩”不满足分配律。第4章二元关系例：A=a,bB=1,2C=x,yR=a,1,a,2A×BS=1,x,2,yB×CT=1,yB×C求：R∘S∩R∘TR∘(S∩T)解：R∘S∩R∘T=a,x,a,y∩a,y=a,yR∘(S∩T)=a,1,a,2∘=第4章二元关系定义4.2.3设R是A上的二元关系，n为自然数，R的n次幂记为Rn，定义为：⑴R0=IA⑵Rn+1=Rn∘R由定义4.2.3可以看出，A上的任何二元关系的0次幂都相等，等于A上的恒等关系IA。由定义4.2.3还可以看出：R1=R0∘R=IA∘R=RR2=R1∘R=R∘RR3=R2∘R=(R∘R)∘R……因为复合运算满足结合律，所以R3又可以写成：R3=R∘R∘R同样的道理Rn也可以写成：Rn=R∘R∘…∘R第4章二元关系例如,在例4.6中R2=R∘R=1,2,2,2S2=S∘S=4,5,3,3,1,1R3=R∘R∘R=1,2,2,2定理4.2.5设A是具有n个元素的有限集，R是A上的二元关系，则必存在自然数s和t，使得Rs=Rt，0≤s＜t≤2。证明：R是A上的二元关系，对任何自然数k，由复合关系的定义知，Rk仍然是A上的二元关系，即RkA×A。另一方面，根据定理4.1.1，A上的二元关系仅有2种。列出R的各次幂R0，R1，R2，…，，共有2＋1个，必存在自然数s和t，使得Rs=Rt，0≤s＜t≤2。2n2n2n22nR2n第4章二元关系【例4.7】A=1,2,3,4，A上的二元关系R定义如下：R=1,2,2,1,2,3,3,4求二元关系R的各次幂，验证定理4.2.5。解：|A|=4R0=IA=1,1,2,2,3,3,4,4R1=R=1,2,2,1,2,3,3,4R2=R1∘R=R∘R=1,1,1,3,2,2,2,4R3=R2∘R=1,2,2