4.离散数学_二元关系

庄伯金[e-mail]1第四章二元关系庄伯金[e-mail]2主要内容二元关系的基本概念关系的运算关系的性质关系的闭包等价关系与偏序关系庄伯金[e-mail]3有序对与笛卡儿积的概念定义(有序对)：由两个元素x和y，按一定顺序排列成的二元组。称为有序对或序偶，记作x,y。x为第一元素，y为第二元素；有顺序的要求：当x≠y时，x,y≠y,x；x,y=u,vx=u∧y=v。定义(笛卡儿积)：设A,B为集合，用A中的元素为第一元素，B中的元素为第二元素构成有序对的集合，称为A和B的笛卡儿积，记作A×B。A×B={x,y|x∈A∧y∈B}庄伯金[e-mail]4笛卡儿积的性质(1)任意集合与空集的笛卡儿积为空集A×=×A=笛卡儿积不满足交换律A×B≠B×A笛卡儿积不满足结合律(A×B)×C≠A×(B×C)庄伯金[e-mail]5笛卡儿积的性质(2)笛卡儿积对交并满足分配律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)子集的笛卡儿积仍为子集A⊆C∧B⊆D⇒A×B⊆C×D笛卡儿积例：A={1,2}，求P(A)×A。庄伯金[e-mail]6庄伯金[e-mail]7二元关系的概念定义(二元关系)：如果一个集合满足以下条件之一：(1)集合非空，且它的元素都是有序对；(2)集合是空集，则称该集合为一个二元关系(简称关系)，记作R。二元关系是集合二元关系是有序对的集合若x,y∈R，可记为xRy。定义：设A和B为集合，A×B的任何子集所定义的二元关系叫做从A到B的二元关系；若A＝B，则叫做A上的二元关系。庄伯金[e-mail]8二元关系的域定义域：R中所有有序对的第一元素构成的集合称为R的定义域，记作domR。值域：R中所有有序对的第二元素构成的集合称为R的值域，记作ranR。域：R的定义域和值域的并集称为R的域，记作fldR。例：R={1,1,1,2,2,4,3,1}庄伯金[e-mail]9二元关系的概念有限集合上的关系总数也是有限的|A|=m，|B|=n，则|A×B|=mn，所以，A到B上的关系共有2mn种。A上的特殊关系空关系：A×A的空集全域关系：EA={x,y|x∈A∧y∈A}=A×A；恒等关系：IA={x,x|x∈A}。庄伯金[e-mail]10常见关系小于等于关系：LA={x,y|x,y∈A∧x≤y}，其中A⊆R整除关系：DB={x,y|x,y∈B∧x整除y}，其中B⊆Z*包含关系：R⊆={x,y|x,y∈A∧x⊆y}，其中A为集合族例：B={a,b}，A=P(B)，求R⊆。庄伯金[e-mail]11关系的表示方法集合表达式关系矩阵关系图庄伯金[e-mail]12关系矩阵设A={x1,x2,...,xn}，R是A上的关系，令rij=1，若xi,xj∈Rrij=0，若xi,xj∉R则有是R的关系矩阵，记作MR。111212122212......()..................nnijnnnnrrrrrrrrrr庄伯金[e-mail]13关系图设A={x1,x2,...,xn}，R是A上的关系。令图G={V,E}，其中顶点集V=A，有向边集合E满足∀xi,xj∈V，xi,xj∈ExiRxj。则称图G为R的关系图，记作GR。abcd关系的表示例：A={1,2,3,4},R={1,1,1,2,2,3,2,4,4,2}，求MR和GR。庄伯金[e-mail]14庄伯金[e-mail]15关系的运算逆关系：设R为二元关系，R的逆关系(简称R的逆)记作R-1，其中R-1={x,y|y,x∈R}。右复合：设F和G为二元关系，G对F的右复合记作F∘G，其中F∘G={x,y|∃t(x,t∈F∧t,y∈G)}。左复合：设F和G为二元关系，G对F的左复合记作F∘G，其中F∘G={x,y|∃t(x,t∈G∧t,y∈F)}。庄伯金[e-mail]16关系的运算限制：设R为二元关系，A为集合，R在A上的限制记作R↾A，其中R↾A={x,y|x,y∈R∧x∈A}。R↾A的值域称为A在R下的像，记作R[A]，其中R[A]=ran(R↾A)。幂：设R为A上的关系，n为自然数，则R的n次幂定义为：R0={x,x|x∈A}=IARn+1=Rn∘R基本的集合运算庄伯金[e-mail]17关系的运算规律定理1：设F是任意关系，则(F-1)-1=FdomF-1=ranF,ranF-1=domF定理2：设F、G和H是任意的关系，则(F∘G)∘H=F∘(G∘H)(F∘G)-1=G-1∘F-1定理3：设R为A上的关系，则R∘IA=IA∘R=R庄伯金[e-mail]18关系的运算规律定理4：设F、G和H为任意关系，则F∘(G∪H)=F∘G∪F∘H(G∪H)∘F=G∘F∪H∘FF∘(G∩H)⊆F∘G∩F∘H(G∩H)∘F⊆G∘F∩H∘F定理5：设F为关系，A、B为集合，则F↾(A∪B)=F↾A∪F↾BF[A∪B]=F[A]∪F[B]F↾(A∩B)=F↾A∩F↾BF[A∩B]⊆F[A]∩F[B]庄伯金[e-mail]19关系的运算规律定理6：设A为n元集，R是A上的关系，则存在自然数s和t，使得Rs=Rt。定理7：设R为A上的关系，m、n为自然数，则有Rm∘Rn=Rm+n；(Rm)n=Rmn。定理8：设R为A上的关系，若存在自然数s和t(st)，满足Rs=Rt，则对任意自然数k，有Rs+k=Rt+k；对任意自然数k和i，有Rs+kp+i=Rs+i，其中p=t-s；令S={R0,R1,...,Rt-1}，则对于任意的自然数q，Rq∈S。庄伯金[e-mail]20关系的性质自反性反自反性对称性反对称性传递性庄伯金[e-mail]21自反性与反自反性定义1：设R为集合A上的二元关系，若∀x(x∈A→x,x∈R)，则称R在A上具有自反性；若∀x(x∈A→x,x∉R)，则称R在A上具有反自反性。例：设A={1,2,3},R1,R2,R3是A上的关系，判断他们是否具有自反性或反自反性R1={1,1,3,3}R2={1,1,1,2,2,2,2,3,3,1,3,3}R3={1,3}庄伯金[e-mail]22对称性与反对称性定义2：设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上的反对称关系。例：设A={1,2,3},R1,R2,R3,R4为A上的关系，判断他们的对称性与反对称性：R1={1,1,2,2}R2={1,1,2,1,1,2}R3={1,2,1,3}R4={1,2,2,1,1,3}庄伯金[e-mail]23传递性定义3：设R为A上的二元关系，若∀x∀y∀z(x,y,z∈A∧x,y∈R∧y,z∈R→x,z∈R)，则称R是A上的传递关系。例：设A={1,2,3}，,R1,R2,R3是A上的关系，判断他们是否具有传递性R1={1,1,2,2}R2={1,2,2,3}R3={1,3}庄伯金[e-mail]24五种性质成立的充要条件定理：设R为A上的二元关系，则R在A上自反当且仅当IA⊆R；R在A上反自反当且仅当R∩IA=；R在A上对称当且仅当R=R-1；R在A上反对称当且仅当R∩R-1⊆IA；R在A上传递当且仅当R∘R⊆R庄伯金[e-mail]25关系性质的保持自反性反自反性对称性反对称性传递性R-1YYYYYR1∩R2YYYYYR1∪R2YYYNNR1－R2NYYYNR1∘R2YNNNN庄伯金[e-mail]26关系的闭包定义：设R是A上的关系，R的自反（对称或传递）闭包是A上的关系R’，并满足R’是自反的（对称的或传递的）；R⊆R’；对A上任何一个包含R的自反（对称或传递）关系R’’，R’⊆R’’；R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。庄伯金[e-mail]27闭包的构造定理：设R为A上的关系，则有r(R)=R∪IA；s(R)=R∪R-1t(R)=R∪R2∪R3∪...例设A={a,b,c,d}，A上的关系R={a,b,b,a,b,c,c,d}，求R的自反闭包、对称闭包和传递闭包。庄伯金[e-mail]28庄伯金[e-mail]29等价关系与等价类定义：设R为非空集合A上的关系，如果R满足自反性、对称性和传递性，则称R为A上的一个等价关系。若x,y∈R，则称x等价于y。例：集合A=N，定义A上的关系R为：R={x,y|x,y∈A∧x≡y(mod3)}设R为非空集合A上的等价关系，∀x∈A，令[x]R={y|y∈A∧x,y∈R}，称[x]R为x关于R的等价类，简称为x的等价类，简记为[x]。庄伯金[e-mail]30等价类的性质定理：设R为A上的等价关系，则∀x∈A，[x]非空；∀x,y∈A，若x,y∉R，则[x]∩[y]=；∀x,y∈A，若x,y∈R，则[x]=[y]；∪[x]=A。庄伯金[e-mail]31商集与集合的划分定义：设R为非空集合A上的等价关系，以R的所有等价类为元素的集合称为A关于R的商集，记作A/R，即A/R={[x]|x∈A}。定义：设A为非空集合，若A的子集族满足：∉；∀x∀y(x,y∈∧x≠y→x∩y=)；∪=A。则称为A的一个划分，称中的元素为A的划分块。商集A/R是A的一个划分。商集与集合的划分定理：对于集合A的任何一个划分，存在A上的一个等价关系R，使得该划分为A关于R的商集A/R。反之亦然。庄伯金[e-mail]32庄伯金[e-mail]33练习设集合A={1,2,3,4,5}，找出A上的等价关系R，使得R能产生划分{{1,2},{3},{4,5}}，并画出关系图。设R是一个二元关系，S={a,b|∃c(a,c∈R∧c,b∈R)}。证明：若R是等价关系，则S也是等价关系。庄伯金[e-mail]34偏序关系定义：设R为非空集合A上的一个关系，若R具有自反性、反对称性和传递性，则称R为A上的偏序关系，记作≼。如果x,y∈≼，则称x小于或等于y。定义：设R为非空集合A上的偏序关系，定义∀x,y∈A，x≺y⇔x≼y∧x≠y；∀x,y∈A，x与y可比⇔x≼y∨y≼x。定义：集合A和A上的偏序关系≼一起叫做偏序集，记作(A,≼