第七章-二元关系

1第七章二元关系§7.1有序对与笛卡尔积§7.2二元关系§7.3关系的运算§7.4关系的性质§7.5关系的闭包§7.6等价关系与划分§7.7偏序关系2§7.1有序对与笛卡尔积一、有序对二、笛卡尔积31.定义（定义7.1）2.性质一、有序对由两个元素x和y(允许x=y)，按一定顺序组成的二元组称为有序对，记作x,y。(1)有序性x,yy,x（当xy时）(2)x,y=u,v的充分必要条件是x=uy=v如：平面直角坐标系中点的坐标3,4。二、笛卡儿积4设A,B为集合，用A中元素为第一个元素，B中元素为第二个元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作AB。AB={x,y|xAyB}1.定义（定义7.2）5例：A={1,2},B={a,b,c}AB={1,a,1,b,1,c,2,a,2,b,2,c}BA={a,1,b,1,c,1,a,2,b,2,c,2}注意：若|A|=m,|B|=n,则|AB|=mn。62.性质：①对任意集合A，A=A=②不适合交换律ABBA(当ABAB时)③不适合结合律(AB)CA(BC)(当ABC时)④对于并或交运算满足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)7证明：A(BC)=(AB)(AC)证：任取x,yx,y∈A×(B∪C)x∈A∧y∈B∪Cx∈A∧(y∈B∨y∈C)(x∈A∧y∈B)∨(x∈A∧y∈C)x,y∈A×B∨x,y∈A×Cx,y∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).8⑤ACBDABCD证明：任取x,yx,yABxAyBxCyDx,yCD注意：ACBD是否推出ABCD？不一定！反例如下：A={1}，B={2},C=D=9§7.2二元关系一、二元关系的定义二、二元关系的表示法10一、二元关系的定义1.二元关系（定义7.3）2.从A到B的二元关系（定义7.4）3.A上的某些特殊关系（定义7.5）4.A上的某些常用关系（P105）11如果一个集合满足以下条件之一：(1)集合非空,且它的元素都是有序对；(2)集合是空集，则称该集合为一个二元关系,简称为关系，记作R。如果x,y∈R,可记作xRy；如果x,yR,则记作xy。如：R={1,2,a,b},S={1,2,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,ac等.1.二元关系2.从A到B的二元关系12设A，B为集合，A×B的任何子集所定义的二元关系叫做从A到B的二元关系，当A=B时则叫做A上的二元关系。如：A={0,1},B={1,2,3},R1={0,2},R2=A×B,R3=,R4={0,1}.那么R1，R2，R3，R4是从A到B的二元关系，R3和R4同时也是A上的二元关系。|A|=n,|B|=m，|A×B|=nm，从A到B的二元关系有2nm个，A上的二元关系有个。22n3.A上的某些特殊二元关系13①空关系：对于任何集合A，是A×A的子集，叫做A上的空关系。②全域关系EA：EA={x,y|x∈A∧y∈A}=A×A③恒等关系IA：IA={x,x|x∈A}如，A={1,2}，则EA={1,1,1,2,2,1,2,2}IA={1,1,2,2}4.A上的某些常用二元关系14①小于等于关系LA：LA={x,y|x,y∈A∧x≤y}，AR，②整除关系DB：DB={x,y|x,y∈B∧x整除y}，BZ*,Z*为非0整数集。③包含关系R：R={x,y|x,y∈A∧xy},A是集合族。类似的还可以定义大于等于关系，小于关系，大于关系,真包含关系等等。如：A={1,2,3},B={a,b},则LA={1,1,1,2,1,3,2,2,2,3,3,3}DA={1,1,1,2,1,3,2,2,3,3}15A=P(B)={,{a},{b},{a,b}},则A上的包含关系R={,,,{a},,{b},,{a,b},{a},{a},{a},{a,b},{b},{b},{b},{a,b},{a,b},{a,b}}二、二元关系的表示法161.集合表示法2.关系矩阵3.关系图1.集合表示法17关系是一种特殊的集合(元素为有序对)。列举法谓词表示法例：设A={1,2,3,4}，R={x,y|x/y是素数}是A上的关系，用列举法表示R。解：R={2,13,14,2}2.关系矩阵18设A={a1,a2,…,an}，B={b1,b2,…,bm}，R是从A到B的一个二元关系，称矩阵MR=[rij]nm为关系R的关系矩阵，其中：1，ai,bjRrij=(i=1,2,…,n,j=1,2,…,m)0，ai,bjR注意：A的元素个数确定行数；B的元素个数确定列数。若R为A上的关系，则关系矩阵为n阶方阵。193.关系图设A={a1,a2,…,an}，B={b1,b2,…,bm}，R是从A到B的一个二元关系，则对应关系R的关系图是GR=V,R，其中V为结点集，R为边集。如果xi,xj属于关系R，在图中就有一条从xi到xj的有向边。注意：A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系。20例：A={1,2,3,4},R={1,1,1,2,2,3,2,4,4,2},R的关系矩阵MR和关系图GR如下：0010000011000011RM21§7.3关系的运算一、关系的集合运算二、关系的基本运算三、基本运算的性质四、关系的方幂运算一、关系的集合运算22根据关系的定义知，关系就是集合，所以在第6章中所给出的集合的运算对于关系也适用。设R和S是集合A到B的关系，则关系的并、交、相对补、绝对补、对称差运算为RS、RS、RS、R(S)、RS。注意：1.A到B的全域关系为A×B，它就是讨论集合时的全集。2.若R和S是集合A上的关系，则其运算后仍是A上的关系；返回二、关系的基本运算231.定义域、值域和域（定义7.6）2.关系的逆运算3.右复合4.限制与像返回1.定义域、值域和域24定义域domR={x|y(x,yR)}值域ranR={y|x(x,yR)}域fldR=domRranR例：R={1,2,1,3,2,4,4,3},则domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}2.关系的逆运算25设R为二元关系，R1称为R的逆关系。RA×B，R1B×A。R1={y,x|x,yR}例：设A={1,2,3,4}R={1,2,2,3,1,4,2,2}R1={2,1,3,2,4,1,2,2}26注意：1.对任意关系R，都存在R1。(-1=)2.R和R1是建立在不同集合上的(A上的关系除外)。3.将R的关系图上所有弧线改变方向，就得到R1的关系图；R1的关系矩阵MR-1就是MR的转置矩阵(行列颠倒)。3.右复合27理解：x是t的母亲，t是y的妻子；x是t的父亲，t是y的父亲。F∘G={x,y|t(x,tFt,yG)}例：设F={3,3,6,2},G={2,3}，则F∘G={6,3}G∘F={2,3}28注意：1.不是任意两个关系都求复合的，FA×B,GB×C,F∘G才有意义；2.若FA×B,GB×A,F∘G、G∘F都有意义；若F、G是A上的关系，则F∘G、G∘F都有意义；3.即使F∘G、G∘F都有意义，也不能保证F∘G=G∘F；29例：A={0,1,2,3},A上的关系F，G定义如下，计算F∘G、G∘F。F={x,y|x,y∈A,y=x+1或y=x/2}G={x,y|x,y∈A,x=y+2}解：F={0,1,1,2,2,3,0,0,2,1}G={2,0,3,1}∴F∘G={1,0,2,1}G∘F={2,1,2,0,3,2}注意：求两个关系复合的时候，要注意它们的顺序。复合运算的图示方法30利用图示（不是关系图）方法求复合。R={1,2,2,3,1,4,2,2}S={1,1,1,3,2,3,3,2,3,3}R∘S={1,2,1,4,3,2,3,3}S∘R={1,3,2,2,2,3}4.限制与像设R为二元关系，A是集合(1)R在A上的限制，记作R↾AR↾A={x,y|xRyxA}(2)A在R下的像记作R[A]=ran(R↾A)31例：R={1,2,2,3,1,4,2,2}R↾{1}={1,2,1,4}R[{1}]={2,4}R↾=R[{1,2}]={2,3,4}注意：R↾AR,R[A]ranR红色是限制条件，在R中寻找满足条件的元素。“限制”是有序对的集合。运算顺序32本节所定义的关系运算中逆运算优先于其他运算，而所有的关系运算都优先于集合运算，对于没有规定优先权的运算以括号决定运算顺序。返回三、基本运算的性质（定理7.1-7.5）33定理7.1设F是任意的关系,则(1)(F1)1=F(2)domF1=ranF,ranF1=domF证：(1)任取x,y,由逆的定义有x,y∈(F1)1y,x∈F1x,y∈F所以有(F1)1=F(2)任取x,x∈domF1y(x,y∈F1)y(y,x∈F)x∈ranF所以有domF1=ranF.同理可证ranF1=domF.34定理7.2设F,G,H是任意的关系,则(1)(F∘G)∘H=F∘(G∘H)(2)(F∘G)1=G1∘F1证：(1)任取x,y,x,y(F∘G)∘Ht(x,t∈F∘G∧t,y∈H)t(s(x,s∈F∧s,t∈G)∧t,y∈H)ts(x,s∈F∧s,t∈G∧t,y∈H)s(x,s∈F∧t(s,t∈G∧t,y∈H))s(x,s∈F∧s,y∈G∘H)x,y∈F∘(G∘H)所以(F∘G)∘H=F∘(G∘H)35(2)任取x,y,x,y∈(F∘G)1y,x∈F∘Gt(y,t∈F∧(t,x)∈G)t(x,t∈G1∧(t,y)∈F1)x,y∈G1∘F1所以(F∘G)1=G1∘F136定理7.3设R为A上的关系,则R∘IA=IA∘R=R定理7.4设F、G、H为任意的关系，则：(1)F∘(GH)=F∘GF∘H(2)(GH)∘F=G∘FH∘F(复合运算对运算满足分配律）(3)F∘(GH)F∘GF∘H(4)(GH)∘FG∘FH∘F(复合运算对运算分配后是包含关系）37定理7.5设F为关系，A、B为集合，则：(1)F↾(AB)=F↾AF↾B(2)F[AB]=F[A]F[B](3)F↾(AB)=F↾AF↾B(4)F[AB]F[A]F[B]返回四、关系的方幂运算38在右复合运算的基础上定义关系的幂运算。1.定义（定义7.10）2.求法3.性质（定理7.6-7.7）按定义直接求解；关系矩阵；关系图。1.定义39设R为A上的关系，n为自然数，则R的n次幂定义为：(1)R0={x,x|x∈A}=IA(2)Rn+1=Rn∘R注意：1