离散数学二元关系PPT精品文档

1、1 1第四章第四章二元关系二元关系2 2主要内容n二元关系的基本概念二元关系的基本概念n关系的运算关系的运算n关系的性质关系的性质n关系的闭包关系的闭包n等价关系与偏序关系等价关系与偏序关系3 3有序对与笛卡儿积的概念n定义定义(有序对有序对)：由两个元素由两个元素x和和y，按一定顺序排列成按一定顺序排列成的二元组。称为的二元组。称为有序对有序对或或序偶序偶，记作，记作。nx为第一元素，为第一元素，y为第二元素；为第二元素；n有顺序的要求：当有顺序的要求：当xy时，时，；n=x=uy=v。n定义定义(笛卡儿积笛卡儿积)：设设A,B为集合，用为集合，用A中的元素为第中的元素为第一元素，一元素，B

2、中的元素为第二元素构成有序对的集合，中的元素为第二元素构成有序对的集合，称为称为A和和B的的笛卡儿积笛卡儿积，记作，记作AB。nAB=|xAyB4 4笛卡儿积的性质(1)n任意集合与空集的笛卡儿积为空集任意集合与空集的笛卡儿积为空集nA=nA=n笛卡儿积不满足交换律笛卡儿积不满足交换律nABBAn笛卡儿积不满足结合律笛卡儿积不满足结合律n(AB)CA(BC)5 5笛卡儿积的性质(2)n笛卡儿积对交并满足分配律笛卡儿积对交并满足分配律nA(BC)=(AB)(AC)n(BC)A=(BA)(CA)nA(BC)=(AB)(AC)n(BC)A=(BA)(CA)n子集的笛卡儿积仍为子集子集的笛卡儿积仍为子

3、集nACBDABCD6 6笛卡儿积n例：例：A=1,2，求求P(A)A。7 7二元关系的概念n定义定义(二元关系二元关系)：如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：(1)集合非空，且它的元素都是有序对；集合非空，且它的元素都是有序对；(2)集合是空集合是空集，则称该集合为一个集，则称该集合为一个二元关系二元关系(简称简称关系关系)，记作，记作R。n二元关系是集合二元关系是集合n二元关系是有序对的集合二元关系是有序对的集合n若若R，可记为可记为xRy。n定义：设定义：设A和和B为集合，为集合，AB的任何子集所定义的二的任何子集所定义的二元关系叫做从元关系叫做从A到到B的二元关

4、系；若的二元关系；若AB，则叫做则叫做A上的二元关系。上的二元关系。8 8二元关系的域n定义域定义域：R中所有有序对的第一元素构成的集合称为中所有有序对的第一元素构成的集合称为R的定义域，记作的定义域，记作domR。n值域值域：R中所有有序对的第二元素构成的集合称为中所有有序对的第二元素构成的集合称为R的值域，记作的值域，记作ranR。n域域：R的定义域和值域的并集称为的定义域和值域的并集称为R的域，记作的域，记作fldR。n例：例：R=,9 9二元关系的概念n有限集合上的关系总数也是有限的有限集合上的关系总数也是有限的n|A|=m，|B|=n，则则|AB|=mn，所以，所以，A到到B上的关上

5、的关系共有系共有2mn种。种。nA上的特殊关系上的特殊关系n空关系：空关系：AA的空集的空集n全域关系：全域关系：EA=|xAyA=AA；n恒等关系：恒等关系：IA=| xA。1010常见关系n小于等于关系：小于等于关系：nLA=|x,yAxy，其中其中ARn整除关系：整除关系：nDB=|x,yBx整除整除y，其中其中BZ*n包含关系：包含关系：nR=|x,yA Axy，其中其中A A为集合族为集合族n例：例：B=a,b，A A=P(B)，求求R。1111关系的表示方法n集合表达式集合表达式n关系矩阵关系矩阵n关系图关系图1212关系矩阵n设设A=x1,x2,.,xn，R是是A上的关系，令上的

6、关系，令nrij=1，若若Rnrij=0，若若 R则有则有是是R的关系矩阵的关系矩阵，记作，记作MR。111212122212.( ).nnijnnnnrrrrrrrrrr1313关系图n设设A=x1,x2,.,xn，R是是A上的关系。令图上的关系。令图G=V,E，其中顶点集其中顶点集V=A，有向边集合有向边集合E满足满足xi,xjV，ExiRxj。则称图则称图G为为R的关的关系图，记作系图，记作GR。1414关系的表示n例：例：A=1,2,3,4, R=, , , , ，求求MR和和GR。1515关系的运算n逆关系逆关系：设：设R为二元关系，为二元关系，R的逆关系的逆关系(简称简称R的逆的逆

7、) 记作记作R-1，其中其中R-1=|R。n右复合右复合：设：设F和和G为二元关系，为二元关系，G对对F的右复合记作的右复合记作F G，其中其中F G=|t(FG)。n左复合左复合：设：设F和和G为二元关系，为二元关系，G对对F的左复合的左复合记作记作F G，其中其中F G=|t(GF)。1616关系的运算n限制限制：设：设R为二元关系，为二元关系，A为集合，为集合，R在在A上的限制上的限制记记作作R A，其中其中R A=|RxA。 R A的值域称为的值域称为A在在R下的像下的像，记作，记作RA，其中其中RA=ran(R A)。n幂幂：设：设R为为A上的关系，上的关系，n为自然数，则为自然数，

8、则R的的n次幂次幂定定义为：义为：nR0=|xA=IAnRn+1=Rn Rn基本的集合运算基本的集合运算1717关系的运算规律n定理定理1：设：设F是任意关系，则是任意关系，则n(F-1)-1=FndomF-1=ranF, ranF-1=domFn定理定理2：设：设F、G和和H是任意的关系，则是任意的关系，则n(F G) H=F (G H)n(F G)-1=G-1 F-1n定理定理3：设：设R为为A上的关系，则上的关系，则nR IA=IA R =R1818关系的运算规律n定理定理4：设：设F、G和和H为任意关系，则为任意关系，则nF (GH)=F GF Hn(GH) F=G FH FnF (G

9、H)F GF Hn(GH) FG FH Fn定理定理5：设：设F为关系，为关系，A、B为集合，则为集合，则nF (AB)=F AF BnFAB=FAFBnF (AB)=F AF BnFABFAFB1919关系的运算规律n定理定理6：设：设A为为n元集，元集，R是是A上的关系，则存在自然上的关系，则存在自然数数s和和t，使得使得Rs=Rt。n定理定理7：设：设R为为A上的关系，上的关系，m、n为自然数，则有为自然数，则有nRm Rn=Rm+n；n(Rm)n=Rmn。n定理定理8：设：设R为为A上的关系，若存在自然数上的关系，若存在自然数s和和t(st)，满足满足Rs=Rt，则则n对任意自然数对任

10、意自然数k，有有Rs+k=Rt+k；n对任意自然数对任意自然数k和和i，有有Rs+kp+i=Rs+i，其中其中p=t-s；n令令S=R0,R1,.,Rt-1，则对于任意的自然数则对于任意的自然数q，RqS。2020关系的性质n自反性自反性n反自反性反自反性n对称性对称性n反对称性反对称性n传递性传递性2121自反性与反自反性n定义定义1：设：设R为集合为集合A上的二元关系，上的二元关系，n若若x(xAR)，则称则称R在在A上具有上具有自反性自反性；n若若x(xA R)，则称则称R在在A上具有上具有反自反性反自反性。n例：设例：设A=1,2,3,R1,R2,R3是是A上的关系，判断他上的关系，判

11、断他们是否具有自反性或反自反性们是否具有自反性或反自反性nR1=,nR2=,nR3=2222对称性与反对称性n定义定义2：设：设R为为A上的二元关系上的二元关系n若若xy(x,yARR)，则称则称R是是A上的上的对称关系对称关系；n若若xy(x,yARR x=y)，则则称称R是是A上的上的反对称关系反对称关系。n例：设例：设A=1,2,3,R1,R2,R3,R4为为A上的关系，判断上的关系，判断他们的对称性与反对称性：他们的对称性与反对称性：nR1=,nR2=,nR3=,nR4=,2323传递性n定义定义3：设：设R为为A上的二元关系，若上的二元关系，若nxyz(x,y,zARRR)，则称则称

12、R是是A上的上的传递关系传递关系。n例：设例：设A=1,2,3，,R1,R2,R3是是A上的关系，判断上的关系，判断他们是否具有传递性他们是否具有传递性nR1=,nR2=,nR3=2424五种性质成立的充要条件n定理：设定理：设R为为A上的二元关系，则上的二元关系，则nR在在A上自反当且仅当上自反当且仅当IAR；nR在在A上反自反当且仅当上反自反当且仅当RIA=；nR在在A上对称当且仅当上对称当且仅当R=R-1；nR在在A上反对称当且仅当上反对称当且仅当RR-1IA；nR在在A上传递当且仅当上传递当且仅当R RR2525关系性质的保持自反性自反性反自反性反自反性对称性对称性反对称性反对称性传递

13、性传递性R-1YYYYYR1R2YYYYYR1R2YYYNNR1R2NYYYNR1 R2YNNNN2626关系的闭包n定义：设定义：设R是是A上的关系，上的关系，R的自反（对称或传递）闭的自反（对称或传递）闭包是包是A上的关系上的关系R，并满足并满足nR是自反的（对称的或传递的）；是自反的（对称的或传递的）；nRR；n对对A上任何一个包含上任何一个包含R的自反（对称或传递）关系的自反（对称或传递）关系R，RR；nR的的自反闭包自反闭包记作记作r(R)，对称闭包对称闭包记作记作s(R)，传递闭传递闭包包记作记作t(R)。2727闭包的构造n定理：设定理：设R为为A上的关系，则有上的关系，则有nr

14、(R)=RIA；ns(R)=RR-1nt(R)=RR2R3.2828例n设设A=a,b,c,d，A上的关系上的关系R=, , , ，求，求R的自反闭包、对称闭包和传递的自反闭包、对称闭包和传递闭包。闭包。2929等价关系与等价类n定义：设定义：设R为非空集合为非空集合A上的关系，如果上的关系，如果R满足自反性、满足自反性、对称性和传递性，则称对称性和传递性，则称R为为A上的一个上的一个等价关系等价关系。若。若R，则称则称x等价于等价于y。n例：集合例：集合A=N，定义定义A上的关系上的关系R为：为：nR=|x,yAxy(mod 3)n设设R为非空集合为非空集合A上的等价关系，上的等价关系，xA

15、，令令xR=y|yAR，称称xR为为x关于关于R的的等价类等价类，简称为，简称为x的等价类的等价类，简记为，简记为x。3030等价类的性质n定理：设定理：设R为为A上的等价关系，则上的等价关系，则nxA，x非空；非空；nx,yA，若若 R，则则xy=；nx,yA，若若R，则则x=y；nx=A。3131商集与集合的划分n定义：设定义：设R为非空集合为非空集合A上的等价关系，以上的等价关系，以R的所有等的所有等价类为元素的集合称为价类为元素的集合称为A关于关于R的的商集商集，记作，记作A/R，即即A/R=x|xA。n定义：设定义：设A为非空集合，若为非空集合，若A的子集族的子集族 满足：满足：n

16、；nxy(x,y xyxy=)；n =A。则称则称 为为A的一个的一个划分划分，称，称 中的元素为中的元素为A的划分块。的划分块。n商集商集A/R是是A的一个划分。的一个划分。3232商集与集合的划分n定理：对于集合定理：对于集合A的任何一个划分，存在的任何一个划分，存在A上的一个上的一个等价关系等价关系R，使得该划分为，使得该划分为A关于关于R的商集的商集A/R。反之。反之亦然。亦然。3333练习n设集合设集合A=1,2,3,4,5，找出找出A上的等价关系上的等价关系R，使使得得R能产生划分能产生划分1,2,3,4,5，并画出关系图。，并画出关系图。n设设R是一个二元关系，是一个二元关系，S

17、=|c(RR)。证明：证明：若若R是等价关系，则是等价关系，则S也是等价关系。也是等价关系。3434偏序关系n定义：设定义：设R为非空集合为非空集合A上的一个关系，若上的一个关系，若R具有自反具有自反性、反对称性和传递性，则称性、反对称性和传递性，则称R为为A上的上的偏序关系偏序关系，记作记作 。如果。如果 ，则称，则称x小于或等于小于或等于y。n定义：设定义：设R为非空集合为非空集合A上的偏序关系，定义上的偏序关系，定义nx,yA，x yx yxy；nx,yA，x与与y可比可比x yy x。n定义：集合定义：集合A和和A上的偏序关系上的偏序关系 一起叫做一起叫做偏序集偏序集，记作记作(A,

18、)。n定义：设定义：设R为非空集合为非空集合A上的偏序关系，如果上的偏序关系，如果x,yA，x与与y都是可比的，则称都是可比的，则称R为为A上的上的全序关全序关系系（或（或线序关系线序关系）。）。3535偏序图的表示n哈斯图哈斯图n排序：若排序：若x y，将将x放在放在y的下方；的下方；n连线：连线：x,yA，如果如果x y，且不存在且不存在z，使得使得x z y，则将则将x和和y连线。连线。n例：偏序集例：偏序集(1,2,3,4,5,6,7,8,9,整除整除)3636偏序集中的特殊元素n定义：设定义：设(A, )为偏序集，为偏序集，BA，yB，n若若x(xBy x)，则称则称y为为B的的最小

19、元最小元；n若若x(xBx y)，则称则称y为为B的的最大元最大元；n若若x(xBx yx=y)，则称则称y为为B的的极小元极小元；n若若x(xBy xx=y)，则称则称y为为B的的极大元极大元。n定义：设定义：设(A, )为偏序集，为偏序集， BA，yA，n若若x(xBx y)，则称则称y为为B的的上界上界；n若若x(xBy x)，则称则称y为为B的的下界下界；n令令C=y|y为为B的上界的上界，则，则C的最小元为的最小元为B的的上确界上确界；n令令D=y|y为为B的下界的下界，则，则D的最大元为的最大元为B的的下确界下确界。3737偏序集中的特殊元素n例：设例：设A=1,2,3,4,5,6

20、,7,8,9,10,11,12,24，集合集合A上的偏序关系为整除关系，上的偏序关系为整除关系，B=2,3,4,6,93838函数的概念n定义：设任意两非空集合定义：设任意两非空集合A和和B，F为为A到到B上的关系，上的关系，若若xA，都存在都存在唯一的唯一的yB，使得使得F，则称则称F为为A到到B的的函数函数或或映射映射，记作，记作F：AB。n若若F，可记作可记作y=F(x)，称称x为自变量，为自变量，y为为F在在x上上的函数值。的函数值。n函数是关系，所以函数是集合。函数是关系，所以函数是集合。n函数函数F=GFGGFn所有从所有从A到到B的函数记作的函数记作BA=F|F: AB，读作读作B上上A。3939函数的概念n定义：设函数定义：设函数F: ABn若若x1,x2A，且且x1x2，都有都有F(x1)F(x2)，则称则称F为为A到到B的的单射单射；n若若ranF=B，则称则称F为为A到到B的的满射满射；n若若F既是单射又是满射，则称既是单射又是满射，则称F为为A到到B的的双射