1、二元关系和运算第四章第1页1.二元有序组二元有序组二元有序组二元有序组：由两个元素由两个元素x和和y按一定次序按一定次序排成二元组，记作：排成二元组，记作：。4.1 4.1 二元关系概念二元关系概念如：平面直角坐标系中点坐标一、二元关系概念第2页(1)当x y时，(2)=，当且仅当x=u，y=v(1)、(2)说明有序组区分于集合n元有序组：由由n个元素个元素x1，x2，xn，按按一定次序排成一定次序排成n元组，记作：元组，记作：(x1，x2，xn)。第3页2.一个新集合运算一个新集合运算 积运算积运算：设A、B为两集合，用A中元素为第一元素，B中元素作为第二元素组成二元有序组全体叫做A和B笛卡
2、儿积。记作：A B符号化：A B=|xA y B第4页例例4.1 设A=a,b，B=0,1,2，求A B，B A解：解：依据笛卡儿积定义知A B=,B A=,普通地：假如|A|=m，|B|=n，则|A B|=|B A|=m n,第5页(1)若A，B中有一个空集，则笛卡儿积是空集，即：B=A =(2)当AB，且A，B都不是空集时，有ABBA(3)当A，B，C都不是空集时，有(A B)C A(B C)因为(A B)C中元素,z，而A(B C)中元素为 x,。第6页(4)A(BC)=(A B)(A C)(对分配律)(BC)A=(B A)(C A)A(BC)=(A B)(A C)(BC)A=(B A)
3、(C A)我们证实：A(BC)=(A B)(A C)(?)(?)(?)第7页 要证实两个集合相等，通常有两种方法：一是证两个集合相互包含；二是利用已经有集合运算性质(算律和已证实过公式)，仿照代数恒等式证实方法，一步步从左(右)边推出右(左)边，或从左、右边分别推出同一个集合式子。普通说来，最基本集合相等关系要用第一个证法，比较复杂集合相等关系用第二种方法更加好，但第二种方法使用取决于我们对算律和惯用公式熟练程度。第8页证实：证实：用第一个方法对于任意 A (BC)xA y(BC)xA(yB yC)(xA yB)(xA yC)A B A C(A B)(A C)A(BC)=(A B)(A C)第
4、9页例例4.2 设A=1,2，求P(A)A解：解：P(A)A=，1，2，1,2=，n阶笛卡儿积：=(x1,x2,xn)|x1A1 x2A2 xnAnA1 A2 An1,2，第10页二二元元关关系系：假假如如一一个个集集合合元元素素都都是是二二元元有有序序组组，则则这这个个集集合合称称为为一一个个二二元元关关系，记作：系，记作：R。假如 R ，记作 x R y假如 R ，记作 x R y3、二元关系数学定义、二元关系数学定义第11页从从A到到B二元关系：二元关系：设设A，B为集合，为集合，A B任何子任何子集所定义二元关系叫做从集所定义二元关系叫做从A到到B二二元关系。元关系。若A=B，叫做 A
5、上二元关系；若|A|n，则|A A|n2。就是说，A上有 个不一样二元关系，其中包含空关系、全域关系UA和恒等关系IA。A A全部子集有 个。第12页例例4.3 设A=a,b，写出P(A)上包含关系R：解：解：P(A)=,a,ba,bR=,第13页1.关系矩阵：设A=x1,x2,xn)，R是A上关系，rij=1 若xi R xj0 若xi R xj(i,j=1,2,n)则 (rij)nxn=是R关系矩阵令：二、二元关系表示方法第14页2.关系图：以E=|xiA xjA xiRxj为有向边集组成有向图G=以V=A=x1,x2,xn 为顶点集，第15页例例4.4 设A=1,2,3,4，R=,是A上
6、关系，试写出R关系矩阵并画出关系图：解：解：关系矩阵：0 0 1 10 0 0 00 1 0 01 1 0 0关系图：134 2第16页4.2 4.2 关系运算关系运算关系关系R定义域：定义域：domR=x|(y)R(即即R中有序组第中有序组第一个元素组成集合一个元素组成集合)关关系系R值值域域：ranR=y|(x)R(即即R中中有有序序组组第第二二个个元元素素组成集合组成集合)一、关系定义域与值域第17页例例4.5 以下关系都是整数集Z上关系，分别求出它们定义域和值域：(1)R1=|x,y Z xy(2)R2=|x,y Z x2+y2=1(3)R3=|x,y Z y=2x(4)R4=|x,y
7、 Z|x|=|y|=3 第18页解：解：domR1=ranR1=Z解：解：R2=,domR2=(?)ranR2=(?)(1)R1=|x,y Z xy(2)R2=|x,y Z x2+y2=1,第19页解：解：domR3=Z，ranR3=偶数 解：解：domR4=ranR4=(?)(3)R3=|x,y Z y=2x(4)R4=|x,y Z|x|=|y|=3 第20页二、关系惯用运算F是任意关系，F逆F1=|yFx F、G是任意两个关系，F与G合成记作：F G=|(z)(xGz zFy)关系F在集A上限制，记作：F|A=|xFy xA集A在关系F下象FA=ran(F|A)(1)逆：(2)合成：(3)
8、限制：(4)象：第21页例例4.6 设F，G是N上关系，其定义为：F=|x,yN y=x2G=|x,yN y=x+1求 G1，F G，G F，F|1,2，F1,2解：解：由定义知：G1=|y,xN y=x+1列出G1 中元素就是G1=,第22页为了求F G，能够先直观表示以下：对任何xNx x+1=G即 y=(x+1)2所以 F G=|x,yN y=(x+1)2 同理可求 G F=|(?)(自己做！)发觉 F G G FF|1,2=,F 1,2=ran(F|1,2)=1,4F Z Z2=y第23页关系运算性质：关系运算性质：设F、G、H、为任意关系，则有：(1)(F1)1=F(2)domF1=
9、ranF，ranF1=domF(3)(F G)H=F (G H)(4)(F G)1=G1 F1(5)F (GH)=F GF H (对分配律)(6)F (GH)F GF H (对半分配律)(7)(GH)F=G FH F(8)(GH)F G FH F(?)(?)第24页任取 (F G)1 F G(z)(G F)(z)(G1 F1)G1 F1(4)(F G)1=G1 F1证实：第25页任取F (GH)(z)(GH)F)(z)(GH)F)(注意对括号次序)(z)(G F(H F)F GF H F (GH)=F GF H(5)F (GH)=F GF H证实：第26页4.3 4.3 关系性质关系性质R关系
10、矩阵：主对角线元素全是1R关系图：每个顶点都有环自反性：x A 有R (R是A上关系)关系矩阵：主对角线元素全是0关系图：每个顶点都没有环反自反性：x A R第27页对称性：若 R，则 R 关系矩阵：对称阵关 系 图：假如两个顶点之间有边，一定是一对方向相反边。第28页反对称性：反对称性：若 R且xy，则 R 关系矩阵：假如rij=1，且 i j，则rji=0 关系图：假如两个顶点之间有边，一定是只有一条有向边。第29页传递性：传递性：若 R且 R，则 R 关系图：假如顶点xi到xj有边，xj到xk有边，则从xi到xk有边第30页例例4.7 设A=1,2,10，对于A上关系R=|(xy)/3I
11、I为整数集，问R有哪些性质？第31页解：解：逐条性质加以验证R=|(xy)/3I 任取A中元素x，因为(xx)/3=0，所以R是自反自反；又设A中任意两个元素x,y，假如 xRy，即xy可被3整除，则yx也一定可被3整除，即yRx，从而R是对称对称；假如A中三 个元素x，y，z满足xRy，yRz，则x y，yz被3整除，因为xz=(xy)+(yz)，所以xz被3整除，从而xRz即R含有传递性传递性。第32页4.4 4.4 关系闭包运算关系闭包运算闭包：设RAA，自反闭包 记作 r(R)对称闭包 记作 s(R)传递闭包 记作 t(R)由A求r(R)，s(R)，t(R)过程叫闭包运算。那么，包含R
12、而使之含有自反性质最小关系，称之为R自反闭包自反闭包；包含R而使之含有对称性质(传递性质)最小关系，称之为R对称(传递传递)闭包闭包。一、定义第33页幂运算：设RAA，kN，约定(1)R0=IA=|xA(2)R1=R(3)Rk+1=Rk R显然 Rm Rn=Rm+n (Rm)n=Rmn二、计算方法为了有效地计算关系R各种闭包，先引进关系幂运算概念。第34页闭包运算方法：闭包运算方法：设R是A上任一关系，则(1)r(R)=RIA(2)s(R)=RR(3)t(R)=RR2R3 Rn第35页矩阵形式矩阵形式：(M为R关系矩阵)(1)Mr=M+E(2)Ms=M+M (M 是M转置)(3)Mt=M+M2
13、+M3其中“+”均表示“逻辑加”第36页例例4.8 设A=a,b,c,d，A上关系求 r(R)，s(R)和 t(R)解：解：r(R)=RIA=,R=,=R,三、实例第37页s(R)=RR=,t(R)=RR2R3=R,第38页而R2=R RR3=R2 RR4=R3 R=,=,=,实际上，看到当k 4时，已经有R4 RR2R3故 t(R)=RR2R3=,第39页四、闭包运算性质设A是有限集且|A|=n，R A A，则：第40页4.6 4.6 等价关系和偏序关系等价关系和偏序关系等价关系：集A上关系R是自反,对称和传递。等价类：R是集A上等价关系，对于任一aA，aR=x|aRx,xA被称为a等价类。
14、即A中全部和a有R关系元素集合。一、等价关系及用途第41页等价类性质：等价类性质：R是非空集合，对任意x，yA，下面结论成立：(1)x且x A (等价类为A子集)(2)若xRy，则x=y(3)若xRy，则xy=第42页集A在等价关系R下商集：设R为非空集A上等价关系，以R不交等价类为元素集合叫做A在R下商集，记作A/R.即：A/R=xR|x A第43页集A划分：设A是非空集合，(1)(2)中任意两个元素不交(3)中全部元素并集为A则 为A划分。假如存在一个A子集族，P(A)满足以下条件：第44页 由等价类性质和商集定义可知，商集A/R是A划分，称之为由R诱导划分。反过来，给定A任一划分，则A被
15、分割成若干个划分块。若定义A上二元关系R：x，yA且x,y属 同一块，则xRy，那么R是A上等价关系，称之为由 诱导等价关系。集A上等价关系与划分是一一对应。第45页例例4.9 设A=1,2,3，求出A上全部等价关系：解：解：先求A各种划分：只有1个划分块划分1，含有两个划分块划分2，3，和4，含有3个划分块5。1=A2=1,2,3，4=3,1,2，3=2,1,3，5=1,2,3第46页设对应于划分i 等价关系 Ri，i=1,2,5，则有R5=，R1=，R2=，R3=，R4=，第47页偏序关系：偏序关系：集集A上关系上关系R是自反，反对称和是自反，反对称和传递，记作传递，记作“”，且称，且称A
16、,)为偏序集。为偏序集。二、偏序关系及用途第48页例例4.10 设A=2,4,6,8，A上关系R是通常意义下小于或等于关系，试写出R并验证它是偏序关系。解：解：R=,(1)自反性：(2)反对称性：(3)传递性：,均属于R对任意R，必有xy，当xy时，yx，从而R对任意R，R,因为 xy yz，所以xz，从而R。第49页例例4.11 设C=a,b,a,b,，C上关系T是集合“包含于”，试写出T，并验证它是偏序关系。解：解：同例4.10类似，自己做！第50页(1)用小圆圈表示偏序集元素(称为结点)；(2)按每个元素在偏序中次序从底向上列结点位置；(3)对于偏序集中任意两个元素x和y，假如xy且不存
17、在另一个元素a，使xa ay，则在x与y两结点之间划上一杠，即“|”(x在下，y在上)第51页全序关系：设是偏序集，(x)(y)(xA yA(xy yx)成立，则称A,)为全序集，这时偏序关系叫全序关系。全序集A,)中全部元素能够排序，它哈斯图为一条直线。假如第52页设是偏序集，B A(1)假如yB，使得(x)(xByx)为真，则y是B最小元(“小于”B中全部元)(2)假如yB，使得(x)(xB xy)为真，则y是B最大元(“大于”B中全部元)第53页(4)若yB，使得 (x)(xB xy)，则称y是B极大元(B中没有比y大其它元)(5)若yA，使得(x)(xB xy)为真，则称y是B上界(3
18、)若yB，使得 (x)(xB xy)，则称y是B极小元(B中找不到x小于y)第54页(6)若yA，使得(x)(xB yx)为真，则称y是B下界(7)令C=y|y为B上界，则称C最小元为B上确界或最小上界(8)令D=y|y为B下界，则D最大元为B下确界或最大下界第55页12 84610例例4.12 画出和哈斯图，并指出其中特殊元。解：解：(1)哈斯图以下：92513711由图可知1为最小元，没有最大元；7,8,9,10,11,12均为极大元，极小元为1；1为1,2,12下界，也是下确界；1,2,12中没有上确界或上界。第56页(2)哈斯图以下：P(a,b,c)=,a,b,c,a,b,a,c,b,
19、c,a,b,ca,b,ca,ca,bb,ccab由图可知：为P(a,b,c)最小元，a,b,c为它最大元；同时，a,b,c也分别为它们极小元和极大元、下确界和上确界。第57页abcde例例4.13 已知偏序集哈斯图以下：hgf 试写出对应A和A上偏序关系R，并指出A中特殊元。第58页,解：解：A=a,b,c,d,e,f,g,h 直接由哈斯图可知：A中没有最小元和最大元；e,g和h均为A极大元，a,b,f 和h均为A极小元；没有上确界和下确界。R=,abcdehgf,第59页了了了了解解解解二二二二元元元元关关关关系系系系定定定定义义义义和和和和表表表表示示示示方方方方法法法法；熟熟熟熟练练练练
20、掌掌掌掌握握握握关关关关系系系系性性性性质质质质和和和和运运运运算算算算；尤尤尤尤其其其其是是是是复复复复合合合合和和和和三三三三种种种种闭闭闭闭包包包包运运运运算算算算;了了了了解解解解等等等等价价价价关关关关系系系系和和和和偏偏偏偏序序序序关关关关系系系系，明明明明确确确确它它它它们们们们在在在在描描描描述述述述研研研研究究究究对对对对象象象象结结结结构构构构和和和和特特特特点点点点时时时时主主主主要要要要作作作作用用用用 (即即即即分分分分类类类类和和和和覆覆覆覆盖盖盖盖)。它它它它们们们们在在在在计计计计算算算算机机机机科科科科学学学学中中中中有有有有主主主主要要要要应用。应用。应用。应用。第60页
