第七章-二元关系

11第七章二元关系1.集合的笛卡尔积与二元关系2.关系的运算3.关系的性质4.关系的闭包5.等价关系和偏序关系227.1有序对与笛卡儿积定义7.1由两个元素x和y(允许x=y)按一定的顺序排列成的二元组叫做一个有序对(也称序偶),记作x,y,其中x是它的第一元素,y是它的第二元素。平面直角坐标系中点的坐标就是有序对,例如,1,－1,2,0,1,1,－1,1,…都代表坐标系中不同的点。33有序对的特点：1。当xy时,x,yy,x。2。两个有序对相等,即x,y＝u,v的充分必要条件是x＝u且y＝v。一、有序对44一个有序n元组(n≥3)是一个有序对,其中第一个元素是一个有序n－1元组。一个有序n元组记作x1,x2,…,xn,x1,x2,…,xn＝x1,x2,…,xn-1,xn例如,空间直角坐标系中点的坐标1,－1,3,2,4。5,0等都是有序3元组。n维空间中点的坐标或n维向量都是有序n元组。有序n元组55定义7.2设A,B为集合,用A中元素为第一元素,B中元素为第二元素,构成有序对,所有这样的有序对组成的集合叫做A和B的笛卡儿积,记作A×B。符号化表示为：A×B＝{x,y|x∈A∧y∈B}例1,已知A＝{a,b},B＝{0,1,2},求:A×B和B×A？例2,设A={1,2},求P(A)×A？二、笛卡儿积66如果A中有m个元素,B中有n个元素,则A×B和B×A中都有多少个元素?mn个若x,yA×B,则有x∈A和y∈B。若x,yA×B,则有xA或者yB。771。若A,B中有一个空集,则它们的笛卡儿积是空集,即B＝B×＝2。当A≠B且A,B都不是空集时,有A×B≠B×A所以,笛卡儿积运算不适合交换律。3。当A,B,C都不是空集时,有(A×B)×C≠A×(B×C)所以,笛卡儿积运算不适合结合律。笛卡儿积运算的性质884。笛卡儿积运算对∪或∩运算满足分配律即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)。99证明A×(B∪C)＝(A×B)∪(A×C)证明对于任意的x,y,x,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)。1010设A,B,C,D为任意集合,判断以下命题的真假。(1)若AC且BD,则有A×BC×D。(2)若A×BC×D,则有AC且BD。解(1)命题为真。(2)命题为假。当A＝B＝时,或者A≠且B≠时,该命题的结论是成立的。但是当A和B之中仅有一个为时,结论不一定成立,例如,令A＝C＝D＝,B＝｛1｝,这时A×BC×D,但BD。例31111设A1,A2,…,An是集合(n≥2),它们的n阶笛卡儿积,记作A1×A2×…×An,其中Al×A2×…×An＝{x1,x2,…xn|x1∈Al∧x2∈A2∧…xn∈An}。例如:A={a,b},则A3={a,a,a,a,a,b,a,b,a,a,b,b,b,a,a,b,a,b,b,b,a,b,b,b}推广---n阶笛卡儿积12127.2二元关系Relation所谓二元关系就是在集合中两个元素之间的某种相关性。例如,甲、乙、丙三个人进行乒乓球比赛,如果任何两个人之间都要赛一场,那么共要赛三场。假设三场比赛的结果是乙胜甲、甲胜丙、乙胜丙,这个结果可以记作{乙,甲,甲,丙,乙,丙},其中x,y表示x胜y。它表示了集合{甲,乙,丙}中元素之间的一种胜负关系。1313再如,有a,b,c三个人和四项工作α,,,,已知a可以从事工作α,δ,b可以从事工作,c可以从事工作α,。那么人和工作之间的对应关系可以记作R＝{a,α,a,δ,b,,c,α,c,}。这是人的集合{a,b,c}到工作的集合{α,,,}之间的关系。1414定义7.3如果一个集合或者为空集或者它的元素都是有序对,则称这个集合是一个二元关系,一般记作R。如果x,y∈R,则记作xRy；如果x,yR,则记作一、二元关系的定义1515定义7.4设A,B为集合,A×B的任何子集所定义的二元关系称作从A到B的二元关系(RAB),特别当A＝B时,则叫做A上的二元关系(RAA)。A上有多少个不同的二元关系?|A|=n|A×A|=n2|P(A×A)|=2n2每一个子集代表一个A上的关系,共2n2个关系。1616对于任何集合A都有3种特殊的关系:定义7.5对任何集合A,空关系：空集全域关系EA：EA＝{x,y｜x∈A∧y∈A}＝A×A恒等关系IA：IA＝{x,x｜x∈A}例如：A={0,1,2},则EA＝{0,0,0,1,0,2,1,0,1,1,1,2,2,0,2,1,2,2｝IA＝{0,0,1,1,2,2)}三个特殊的关系1717三个常用的关系（1）设A为实数集R的某个子集,则A上的小于等于关系定义为:LA＝{x,y｜x,y∈A∧x≤y｝（2）设B为正整数集Z＋的某个子集,则B上的整除关系定义为:DB＝{x,y｜x,y∈B∧xy}。（3）设A是集合,R是P(A)上的包含关系,R＝{x,y|x,y∈P(A)∧xy,1818例如:A={4,0。5,-1},B={1,2,3,6},则LA＝{-1。-1,-1。0。5,-1,4。0。5,0。5,0。5,4,4,4｝DB＝{1,1,1,2,1,3,1,6,2,2,2,6,3,3,3,6,6,6}。例,设A＝{a,b},则有P(A)＝{,{a},{b},A}R＝{,,,{a},,{b},,A,{a},{a},{a},A,{b},{b},{b},A,A,A}。1919有穷集A上的关系R,可用集合表达式、关系矩阵和关系图给出。设A＝{1,2,3,4},A上的关系R＝{1,1,1,2,2,3,2,4,4,2}R的关系矩阵和关系图：关系的三种表示方法20202121关系矩阵和关系图设V是顶点的集合,E是有向边的集合,令V＝A＝{x1,x2,···,xn},如果xiRxj,则有向边xi,xj∈E。那么G＝V,E就是R的关系图。设A＝{x1,x2,···,xn},R是A上的关系,则R的关系矩阵可表示为：关系矩阵是布尔矩阵。22227.3关系的运算1.关系R的定义域,值域和域2.关系R的逆运算3.关系F与G的复合运算4.关系R在集合A上的限制5.集合A在关系R下的像6.关系R的n次幂2323定义7.6关系R的定义域domR,值域ranR和域fldR分别是domR＝{xy(x,y∈R)}ranR＝{y|x(x,y∈R)}fldR＝domR∪ranRdomR就是R的所有有序对的第一个元素构成的集合,ranR就是R的所有有序对的第二个元素构成的集合。关系R的定义域,值域和域2424例1(1)R1＝{x,y｜x,y∈Z∧x≤y}(2)R2＝{x,y｜x,y∈Z∧x2+y2=1}(3)R3＝{x,y｜x,y∈Z∧y＝2x}(4)R4＝{x,y｜x,y∈Z∧x＝y=3}解(1)domR1＝ranR1＝Z(2)R2＝{0,1,0,－1,1,0,－1,0}domR2＝ranR2＝{0,1,－1}(3)domR3＝Z,ranR3＝{2z|z∈Z},即偶数集(4)domR4＝ranR4＝{-3,3}下列关系都是整数集Z上的关系,分别求出它们的定义域和值域,2525逆、复合、限制和像定义7.7设F,G为任意的关系,A为集合,则(1)F的逆记作F-1:F-1＝{x,y|yFx}(2)F与G的右复合记作F◦G,F◦G＝{x,y|t(xFt∧tGy)}(3)F在A上的限制，记作F↾AF↾A＝{x,y|xFy∧x∈A}(4)A在F下的像记作F[A],F[A]＝ran(F↾A)2626设F,G是N上的关系,其定义为F＝{x,y｜x,y∈N∧y＝x2}G＝{x,y｜x,y∈N∧y＝x＋1}例2说明：由例子不难看出（1）复合运算是不可交换的,F◦G≠G◦F,◦F=F◦=（2）在复合关系中,F的值域一定是G的定义域,否则复合关系为空。复合的结果关系的定义域就是F的定义域,值域就是G的值域。（3）F在A上的限制F↾A是F的子关系,即F↾AF（4）A在F下的像F[A]是ranF的子集,即F[A]ranF2727定理7.1设F是任意的关系,则有定理7.2设F,G,H是任意的关系,则有(3)(F◦G)◦H＝F◦(G◦H)(4)定理7.3设R是A上的关系,则有R◦IA＝IA◦R=R关系的基本运算的主要性质2828定理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证明的一般方法:按照定义证明。例证见书本2929定义7.8设R为A上的关系,n为自然数,则R的n次幂定义如下：R0=IAR1=R0◦R=R◦R0=R关系的幂运算书例3030求Rn的方法1集合运算:依据定义2关系矩阵:用关系矩阵M表示关系R,计算M·M,在两个矩阵相乘时,第i行第j列的元素rij满足下式(i,j=1,2,3,4)rij=ri1·r1j+ri2·r2j+ri3·r3j+ri4·r4j这里的加法“+”是逻辑加,即0+0=0,0+1=1,1+0=1,1+1=13关系图:对R的关系图G中的任何一个结点x,考虑从x出发的长为n的路径,如果路径的终点是y,则在Rn的关系图中有一条从x到y的有向边。3131定理7.5设R为A上的关系,m,n是自然数,则下面的等式成立。定理7.4设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt。说明：有限集合A上的关系R的幂序列是一个周期性变化的序列。利用它的周期性可以将R的高次幂化为R的低次幂。幂运算的性质32327.4关系的性质学习内容集合A上的关系R的五种基本性质学习目标认知层面关系的五种基本性质的定义理解层面能够熟练准确判断任意给定的关系的性质四种方法应用层面能够进行关系性质的证明3333关系R的五种性质R在A上是自反的x(x∈A→x,x∈R)R在A上是反自反的x(x∈A→x,xR)举例R在A上是对称的xy(x,y∈A∧x,y∈R→y,x∈R)R在A上是反对称的xy(x,y∈A∧x,y∈R∧y,x∈R→x=y)举例R在A上是传递的xyz(x,y,z∈A∧x,y∈R∧y,z∈R→x,z∈R)举例3434判断下列关系的性质全域关系自反的、对称的和传递的恒等关系自反的、对称的、反对称的和传递的整除关系自反的、反对称的和传递的小于等于关系自反的、反对称的和传递的幂集上的包含关系自反的、反对称的和传递的3535关系的性质的判定定理定理7.9设R是A上的关系,则：（1）R是自反的当且仅当（2）R是反自反的当且仅当（3）R是对称的当且仅当（4）R是反对称的当且仅当（5）R是传递的当且仅当RIAAIR1RRAIRR1RRR3636例1:设A={1,2,3},判断以下关系的自反、反自反性R1={1,1,2,2,3,3,1,2}R2={2,3,3,2}R3={1,1,2,2}小结：A上的关系可以具有①自反性,②反自反性,③既不是自反性也不是反自反性自反性反自反性3737例2:设A