《主要内容有序对与笛卡儿积的定义与性质二元关系、从A到B》由会员分享，可在线阅读，更多相关《主要内容有序对与笛卡儿积的定义与性质二元关系、从A到B（77页珍藏版）》请在金锄头文库上搜索。
1、主要内容有序对与笛卡儿积的定义与性质二元关系、从A到B的关系、A上的关系关系的表示法：关系表达式、关系矩阵、关系图关系的运算：定义域、值域、域、逆、合成、限制、像、幂关系运算的性质A上关系的自反、反自反、对称、反对称、传递的性质A上关系的自反、对称、传递闭包A上的等价关系、等价类、商集与A的划分A上的偏序关系与偏序集第七章 二元关系要求：熟练掌握关系的三种表示法能够判定关系的性质（等价关系或偏序关系）掌握含有关系运算的集合等式掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念基本运算AB,domR,ranR,fldR,R1,RS,Rn,r(R),s(R),t(R)求等价类和商集A/R给定A
2、的划分，求出所对应的等价关系求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界掌握基本的证明方法证明涉及关系运算的集合等式证明关系的性质、证明关系是等价关系或偏序关系7.1有序对与笛卡儿积一、有序对1定义由两个元素x和y，按照一定的顺序组成的二元组称为有序对，记作.2有序对性质（1）有序性（当xy时）（2）与相等的充分必要条件是=x=uy=v.二、笛卡儿积定义:设A,B为集合，A与B的笛卡儿积记作AB，且AB =|xAyB.例：A=1,2,3,B=a,b,cAB =,BA =,A=,B=P(A)A =,P(A)B =笛卡儿积的性质（1）不适合交换律AB BA(AB,A,B)
3、（2）不适合结合律(AB)C A(BC)(A,B,C)（3）对于并或交运算满足分配律A(BC)=(AB)(AC)(BC)A =(BA)(CA)A(BC)=(AB)(AC)(BC)A =(BA)(CA)（4）若A或B中有一个为空集，则AB就是空集.A=B =（5）若|A|=m,|B|=n,则|AB|=mn证明A(BC)=(AB)(AC)证任取A(BC)xAyBC xA(yByC)(xAyB)(xAyC)ABAC(AB)(AC)所以有A(BC)=(AB)(AC).例1（1)证明A=B,C=D AC=BD（2）AC =BD是否推出A=B,C=D?为什么？解（1）任取ACxAyCxByDBD（2)不一
4、定.反例如下：A=1，B=2,C =D =,则AC =BD但是A B.7.2 二元关系一、二元关系的定义1定义：如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.如果R,可记作xRy；如果R,则记作xy2例：R=,S=,a,b.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,a c等.二、从A到B的关系与A上的关系1定义：设A,B为集合,AB的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例A=0,1,B=1,2,3,那么R1=,R2=AB,R
5、3=,R4=R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.2.计数|A|=n,|AA|=n2,AA的子集有个.所以A上有个不同的二元关系.例如|A|=3,则A上有=512个不同的二元关系.3.A上的重要关系定义：设A为任意集合是A上的关系，称为空关系EA,IA分别称为全域关系与恒等关系EA =|xAyA=AA IA =|xA例如,A=1,2,则EA =,IA =,特定集合上的小于等于关系LA、整除关系DA、包含关系R定义如下：LA =|x,yAxy,这里AR，R为实数集合DB =|x,yBx整除y,这里AZ*,Z*为非0整数集合R=|x,yAxy,这里A是集合族
6、.例如A =1,2,3,B=a,b,则LA =,DA =,A =P(B)=,a,b,a,b,则A上的包含关系是R=,类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等.4关系的表示表示一个关系的方式有三种：关系的集合表达式、关系矩阵、关系图.关系矩阵若A=x1,x2,xm，B=y1,y2,yn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=rijmn,其中rij=1R.关系图若A=x1,x2,xm，R是从A上的关系，R的关系图是GR=,其中A为结点集，R为边集.如果属于关系R，在图中就有一条从xi到xj的有向边.注意：关系矩阵适合表示从A到B的关系或者A上的关系（A,B为有穷集）
7、关系图适合表示有穷集A上的关系（2）例A=1,2,3,4,R=, R的关系矩阵MR和关系图GR如下：定义：令R为二元关系，由的所有x组成的集合称为R的定义域，即R的定义域和值域一起称做R的域，记做FLDR，即7.3关系的运算使的所有y组成的集合ranR称做R的值域，即一、关系的基本运算由关系的定义可知，二逆与合成定义R1=|R定义RS=|y(RS)例R=,S=,R1=,RS=,SR=,因为关系可用矩阵表示，故复合关系亦可用矩阵表示。已知从集合到集合有关系R,则表示R的关系矩阵，利用矩阵求合成同理从集合到集合的关系S,可用矩阵表示，表示复合关系表示复合关系 的矩阵的矩阵 可构造如下：可构造如下：
8、如果如果Y至少有一个这样的元素至少有一个这样的元素 ,使得使得且且在集合在集合Y中能够满足这样条件的元素可能不只一个，中能够满足这样条件的元素可能不只一个，例如另有例如另有 也满足也满足 且且在所有的这样情况下在所有的这样情况下, 都是成立都是成立的。这样，当我们扫描的。这样，当我们扫描 的第的第i行和第行和第 的第的第k列时，列时，如若发现至少有一个这样的如若发现至少有一个这样的j,使得此行第使得此行第j个位置上的个位置上的记入值和第记入值和第k列的第列的第j个位置上的记入值都是个位置上的记入值都是1时，时，则在则在 的第的第i行和第行和第k列（列（i,k）上的记入）上的记入值亦是值亦是1；
9、否则为；否则为0。扫描过。扫描过 的每一行和的每一行和Ms的每的每一列，就能给出一列，就能给出 的一行，再继续类似的方法的一行，再继续类似的方法就能得到就能得到 的其他各行，因此的其他各行，因此就可以用类似于矩阵乘法的方法得到，就可以用类似于矩阵乘法的方法得到，即即 式中代表逻辑加，满足00=0，01=1，10=1，11=1。代表逻辑乘，满足00=0，01=0，10=0，11=1。其中，其中，例题给定集合A=1，2，3，4，5，在集合A上定义两种关系。R=,S=,求RoS和SoR的矩阵。解=定义：设R为X到Y的二元关系，如将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系。记作，即从逆关
10、系的定义，我们容易看出这是因为这是因为如在集合I上，关系“”。而在集合X=1,2,3,4到Y=a,b,c上的关系R=,，其逆关系为Rc=,三、关系运算的性质：设都是从A到B的二元关系，则有定理定理:设设T为从为从X到到Y的关系，的关系，S为从为从Y到到Z的关系，的关系，证明证明: 证明:定理设设R为为X上的二元关系。则上的二元关系。则R是对称的，当且仅当R是反对称的，当且仅当证明证明 a) 因为因为R是对称的，故是对称的，故 所以所以 反之，反之，若若 因为因为 所以所以R是对称的。是对称的。 b) 其证明留作练习。其证明留作练习。 例给定集合X=a,b,c,R是X上的二元关系，R的关系矩阵：
11、解：自反性自反性反自反性反自反性定义定义关系矩关系矩阵的特阵的特点点主对角线主对角线元素全为元素全为1主对角线主对角线元素全为元素全为0关系图关系图的特点的特点图中每个图中每个顶点都有顶点都有环环图中每个图中每个顶点都没顶点都没环环传递性传递性如果顶点如果顶点xi到到xj有有边，边，xj到到xk有边，有边，则从则从xi到到xk有边有边7.4 关系的性质关系的性质对称性对称性反对称性反对称性定义定义关系矩关系矩阵的特阵的特点点矩阵为对称矩阵矩阵为对称矩阵如果如果ij则则rijrji关系图关系图的特点的特点如果两个顶点之间如果两个顶点之间有边，一定是一对有边，一定是一对方向相反的边方向相反的边如果
12、两个顶点之间有边，如果两个顶点之间有边，一定是一条有向边一定是一条有向边证： 因为对于任意xA， (x-x)/2=0， 即 R,故R是自反的。 又设x,y A,如果R,即(x-y)/2是整数则(y-x)/2也必是整数。 即 R,因此R是对称的。 例 设A=2,3,5,7,R=|(x-y)/2是整数，验证R在A上是自反和对称的。例：X=1,2,3,R1=,R2=, R3=, R1,R2和R3都是传递关系吗？解: R1和R2是传递的,但R3不是传递的。注：注：A上的自反关系一定包含了上的自反关系一定包含了A上的恒等关系；而上的恒等关系；而A上上的反自反关系一定与的反自反关系一定与IA不交。不交。A
13、上的对称关系上的对称关系R一定满足一定满足R-1=R，而反对称关系一定，而反对称关系一定满足满足RR-1包含于包含于IA, 如果如果R既是对称的，又是反对称既是对称的，又是反对称的，则的，则R包含于包含于IA.传递关系传递关系R满足满足RR包含于包含于R对对A上的关系上的关系R, R不是对称的，不一定就是反对称的，不是对称的，不一定就是反对称的，同理，对同理，对A上的关系上的关系R, R不是反对称的，不一定就是不是反对称的，不一定就是对称的。对称的。例例 集合I=1,2,3,4,I上的关系R=, ,讨论R的性质。 解：写出R的关系矩阵并画出关系图4132原有性质运算自反性 反自反性对称性 反对
14、称性传递性R-1R1R2R1R2R1R2R1。R2关系的性质和运算之间的联系一一、定定义义: :设设R R是是非非空空集集合合A A上上的的关关系系，R R的的自自反反闭闭包包（对对称称闭闭包包或或传传递递闭闭包包）是是A A上上的的关关系系R R，且且R R满足以下条件：满足以下条件：1) R是自反的（对称的是自反的（对称的 或传递的）；或传递的）；2) R R；3) 对对A上任何包含上任何包含R的自反（对称或传递）关系的自反（对称或传递）关系R”,都有都有R R 。 记作记作 r(R) , S(R), t ( R)7.5 7.5 关系的闭包关系的闭包证证 明明 令令 R=RIxR=RIx，
15、 对对 任任 意意 xX,xX,因因 为为 有有x,xIx,x,xIx,故故x,xR,x,xR,于于是是RR在在X X上上是是自自反的。反的。又又R R R R Ix Ix 即即R R RR。若若有有自自反反关关系系R R且且R R R R，显然有，显然有R R Ix Ix ，于是，于是 R R Ix R= R Ix R= R故故 r(R)=R Ixr(R)=R Ix定理定理 设设R R是集合是集合X X上的二元关系，则上的二元关系，则 r(R)=RIxr(R)=RIx二、闭包的构造方法二、闭包的构造方法1、集合表示、集合表示证证明明 令令R= R= R R R Rc c ，因因为为R R R
16、 R R Rc c即即RR,RR,又又设设x,yRx,yR，则则x,yRx,yR或或x,y x,y R Rc c ，即即y,x y,x R Rc c或或y,xRy,xR，故故y,xR Ry,xR Rc c ，所以，所以RR是对称的。是对称的。设设 R R 是是 对对 称称 的的 且且 R R R R， 对对 任任 意意x,yRx,yRx,yRx,yR或或x,y Rx,y Rc c 。当。当x,yRx,yR则则x,yRx,yR，当当x,yRx,yRc c时时，y,xRy,xR，y,xRy,xR，因因为为R R对对称称，所以所以x,yRx,yR，因此，因此R RR R，故，故 s(R)=R Rs(
17、R)=R Rc c 定理定理 设设R R是集合是集合X X上的二元关系上的二元关系, ,则则 s(R)=RRs(R)=RR-1-1 故证明：a)先证，用归纳法。（1）根据传递闭包定义:（2）假定n1时，设。因为，故必有某个，使和,，故有和即,所以定理定理 设设R R是是X X上的二元关系，则上的二元关系，则b）再证。设，则必存在正整数s和t，使得这样，即所以是传递的。由于包含R的可传递关系都包含t(R)，故由a)和b)可得，通常，将记作。解：解：r(R)=R U Ir(R)=R U IA A =, =,s(R)=RURs(R)=RUR-1-1=,=,例例 设设A=a,b,c ,RA=a,b,c
18、 ,R是是A A上的二元关系，且给定上的二元关系，且给定R=,R=,求求r(R),s(R),t(R)r(R),s(R),t(R)。R R2 2=,=,R R3 3=,=,R R4 4=,=R=,=R2、用关系图3、用矩阵3=2=MRMR MR=100010001*MR= MR2= =例例：设设A=a,b,c,d，给给定定A上上的的关关系系R 为为R=,求求t(R)。MR= =MR2=MR3=MR4=所以Mt=当有限集X的元素较多时，对关系R的传递闭包t(R)进行矩阵运算，显得很为繁琐，为此Warshall在19062年提出了t(R) 的一个有效算法如下：（1） 置新矩阵A:=M；（2） 置i:
19、=1；（3） 对所有j 如果Aj,i=1,则对k=1,2,n Aj,k:=Aj,k+Ai,k；（4） i加1；（5） 如果 ,则转到步骤（3），否则停止。已知，已知，求t(R).例解：i=1时，第一列中只有A1,1=1,将第一行与第一行各对应元素进行逻辑相加，仍记于第一行得：i=2时，第二列中只有A1,2=1,A4,2=1,分别将第一行、第四行各元素和第二行各对应元素进行逻辑相加，仍记于第一行和第四行得：i=3时，第三列中没有不等于零的元素，A的赋值不动。 i=4时，第四列中1.4=A2.4=A4.4=1,将一、二、四这三行和第四行对应元素逻辑相加，仍分别记于一、二、四这三行得:i=5i=5时
20、，时，A3.5=1,A3.5=1,将第三行与第五行的对应元素将第三行与第五行的对应元素逻辑相加，仍记于第三行，由于第五行的元素都逻辑相加，仍记于第三行，由于第五行的元素都等于零，等于零，A A的赋值不变。的赋值不变。i=6,i=7i=6,i=7时，由于第六、时，由于第六、七列各元素均为零，七列各元素均为零，A A的赋值不变的赋值不变。传递闭包t( R )在语法分析中有很多应用，现以下例说明定理设X是集合，R是X上的二元关系，则a)rs(R)=sr(R)b)rt(R)=tr(R)c)ts(R)st(R)证明令Ix表示X上的恒等关系。c)自证如平面上三角形集合中，三角形的相似关系是等如平面上三角形
21、集合中，三角形的相似关系是等价关系；集合上的恒等关系与全域关系都是等价关系；集合上的恒等关系与全域关系都是等价关系；但朋友关系只是相容关系（不传递）价关系；但朋友关系只是相容关系（不传递） 7.6等价关系与划分等价关系与划分定义定义 设为定义设为定义R R在集合在集合A A上的一个关系，上的一个关系，R R是自是自反的对称的和传递的，则反的对称的和传递的，则R R称为等价关系。称为等价关系。例例例例 集合集合集合集合 T=1,2,3,4, T=1,2,3,4, R=,R=,3,2,。 验证验证R R是是T T上的等价关系。上的等价关系。一、等价关系一、等价关系解解 画出画出R R的关系矩阵与关
22、系图的关系矩阵与关系图说明说明R R是自反的、对称的。从是自反的、对称的。从R R的序偶表示式中，可以的序偶表示式中，可以看出看出R R是传递的，逐个检查序偶，知是传递的，逐个检查序偶，知R R是是T T上的等价关系。上的等价关系。同样地，从关系矩阵亦可验证同样地，从关系矩阵亦可验证R R是等价关系是等价关系。证明证明 设任意设任意a a，b b，cIcII.I.因为因为a-a=ka-a=k0 0，所以，所以RRII.II.若若ab(modk),a-b=kt(tab(modk),a-b=kt(t为整数为整数),),则则b-b-a=kt,a=kt,所以所以ba(modk)ba(modk)III.
23、III.若若ab(modk),bc(modk),ab(modk),bc(modk),则则a-b=kt,b-a-b=kt,b-c=ks(t,sc=ks(t,s为整数为整数),), a-c=a-b+b-c=k(t+s), a-c=a-b+b-c=k(t+s),所以所以ac(modk)ac(modk) 因此因此R R是等价关系。是等价关系。例例例例 设设I I为整数集，为整数集，R=R=xy(modk)xy(modk)，证明证明R R是等价关系是等价关系. .定义定义设设R为集合为集合A上的等价关系，对任何上的等价关系，对任何xA,集合集合 =y|yA, xRy称为元素称为元素x关于关于R的等价类的
24、等价类。 定理：设定理：设R R是非空集合是非空集合A A上的等价关系，对任意的上的等价关系，对任意的x,yAx,yA，以下结论成立：，以下结论成立： 1 1、 是非空的，因为是非空的，因为xx 2 2、若、若xRyxRy，则，则 3 3、若、若xRy,xRy,则则 f f 4 4、 A A二、等价类二、等价类例：设例：设I I是整数集合，是整数集合，R是模是模3 同余的关系，即同余的关系，即 R=|xI,yI,x y(mod3)确定确定I 的元素所产生的等价类的元素所产生的等价类。解解 R R是是I I上的等价关系，由上的等价关系，由I I的元素所产生的等价类是的元素所产生的等价类是00R=
25、,-6,-3,0,3,61R=,-5,-2,1,4,72R=,-4,-1,2,5,800R=3R=-3R= 1R=4R=-2R= 2R=5R=-1R= 且有：且有：定义定义 集合集合A上的等价关系上的等价关系R，以，以R的不交的等价类为的不交的等价类为元素的集合叫做元素的集合叫做A在在R下的商集。记作下的商集。记作A/R 即：即： A/R | x A 如：非空集合如：非空集合A上的全域关系上的全域关系EA是是A上的等上的等价关系，价关系， A/EA A 非空集合非空集合A上的恒等关系上的恒等关系IA是是A上的等上的等价关系，价关系，A/IA= x | xA 。三、商集与集合的划分三、商集与集合
26、的划分定理：定理： 非空集合非空集合A上的等价关系上的等价关系R，决定了，决定了A的一个划分，该划分就是商集的一个划分，该划分就是商集A/R。集合的划分集合的划分: 设设A为非空集合为非空集合, 若若A的子集族的子集族( P(A)满足下面条件：满足下面条件：（1） （2） x y(x,y xyxy=)（3） = A则称则称是是A的一个划分的一个划分, 称称中的元素为中的元素为A的划分的划分 例设Aa,b,c,d,给定1,2,3,4,5,6如下：1=a,b,c,d2=a,b,c,d3=a,a,b,c,d4=a,b,c5=,a,b,c,d6=a,a,b,c,d则1和2是A的划分,其他都不是A的划分
27、.7.7 偏序关系一、偏序关系定义：非空集合A上的自反、反对称和传递的关系，记作.设为偏序关系,如果,则记作xy,读作x“小于或等于”y.例：集合A上的恒等关系IA是A上的偏序关系.小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系.相关概念定义：设R为非空集合A上的偏序关系,x,yA,x与y可比xyyx.任取两个元素x和y,可能有下述几种情况发生：xy(或yx),xy,x与y不是可比的.定义：R为非空集合A上的偏序关系,x,yA,x与y都是可比的，则称R为全序（或线序）例：数集上的小于或等于关系是全序关系整除关系不是正整数集合上的全序关系定义7.22x,yA,如果xy且不存在zA使得
28、xzy,则称y覆盖x.例如1,2,4,6集合上的整除关系,2覆盖1,4和6覆盖2.但4不覆盖1.二、偏序集与哈斯图1偏序集：集合A和A上的偏序关系一起叫做偏序集,记作.例：整数集合Z和数的小于或等于关系构成偏序集集合A的幂集P(A)和包含关系R构成偏序集.2哈斯图利用偏序关系的自反、反对称、传递性进行简化的关系图特点：每个结点没有环两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前具有覆盖关系的两个结点之间连边例 偏序集和的哈斯图.例已知偏序集的哈斯图如下图所示,试求出集合A和关系R的表达式.解A=a,b,c,d,e,f,g,hR=,IA三、偏序集中的特殊元素.1.最小元
29、、最大元、极小元、极大元定义设为偏序集,BA,yB.（1）若x(xByx)成立,则称y为B的最小元.（2）若x(xBxy)成立,则称y为B的最大元.（3）若x(xBxyx=y)成立,则称y为B的极小元.（4）若x(xByxx=y)成立,则称y为B的极大元.性质：对于有穷集，极小元和极大元一定存在，还可能存在多个.最小元和最大元不一定存在，如果存在一定惟一.最小元一定是极小元；最大元一定是极大元.孤立结点既是极小元，也是极大元.2下界、上界、下确界（最大下界）、上确界（最小上界）定义设为偏序集,BA,yA.（1）若x(xBxy)成立,则称y为B的上界.（2）若x(xByx)成立,则称y为B的下界
30、.（3）令Cy|y为B的上界,则称C的最小元为B的最小上界或上确界.（4）令Dy|y为B的下界,则称D的最大元为B的最大下界或下确界.性质：下界、上界、下确界、上确界不一定存在下界、上界存在不一定惟一下确界、上确界如果存在，则惟一集合的最小元就是它的下确界，最大元就是它的上确界；反之不对.例设偏序集，求A的极小元、最小元、极大元、最大元.设Bb,c,d,求B的下界、上界、下确界、上确界.解极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B的下界和最大下界都不存在,上界有d和f,最小上界为d.例设X为集合,AP(X)X,且A.若|X|=n,n2.问：（1）偏序集是否存在最大元？（2）偏序集是否存在最小元？（3）偏序集中极大元和极小元的一般形式是什么？并说明理由.解不存在最小元和最大元,因为n2.的极小元就是X的所有单元集,即x,xX.的极大元恰好比X少一个元素,即Xx,xX.
