4.离散数学_二元关系.ppt

庄伯金bjzhuang,1,第四章,二元关系,庄伯金bjzhuang,2,主要内容,二元关系的基本概念关系的运算关系的性质关系的闭包等价关系与偏序关系,庄伯金bjzhuang,3,有序对与笛卡儿积的概念,定义(有序对)：由两个元素x和y，按一定顺序排列成的二元组。称为有序对或序偶，记作。x为第一元素，y为第二元素；有顺序的要求：当xy时，；=x=uy=v。定义(笛卡儿积)：设A,B为集合，用A中的元素为第一元素，B中的元素为第二元素构成有序对的集合，称为A和B的笛卡儿积，记作AB。AB=|xAyB,庄伯金bjzhuang,4,笛卡儿积的性质(1),任意集合与空集的笛卡儿积为空集A=A=笛卡儿积不满足交换律ABBA笛卡儿积不满足结合律(AB)CA(BC),庄伯金bjzhuang,5,笛卡儿积的性质(2),笛卡儿积对交并满足分配律A(BC)=(AB)(AC)(BC)A=(BA)(CA)A(BC)=(AB)(AC)(BC)A=(BA)(CA)子集的笛卡儿积仍为子集ACBDABCD,笛卡儿积,例：A=1,2，求P(A)A。,庄伯金bjzhuang,6,庄伯金bjzhuang,7,二元关系的概念,定义(二元关系)：如果一个集合满足以下条件之一：(1)集合非空，且它的元素都是有序对；(2)集合是空集，则称该集合为一个二元关系(简称关系)，记作R。二元关系是集合二元关系是有序对的集合若R，可记为xRy。定义：设A和B为集合，AB的任何子集所定义的二元关系叫做从A到B的二元关系；若AB，则叫做A上的二元关系。,庄伯金bjzhuang,8,二元关系的域,定义域：R中所有有序对的第一元素构成的集合称为R的定义域，记作domR。值域：R中所有有序对的第二元素构成的集合称为R的值域，记作ranR。域：R的定义域和值域的并集称为R的域，记作fldR。例：R=,庄伯金bjzhuang,9,二元关系的概念,有限集合上的关系总数也是有限的|A|=m，|B|=n，则|AB|=mn，所以，A到B上的关系共有2mn种。A上的特殊关系空关系：AA的空集全域关系：EA=|xAyA=AA；恒等关系：IA=|xA。,庄伯金bjzhuang,10,常见关系,小于等于关系：LA=|x,yAxy，其中AR整除关系：DB=|x,yBx整除y，其中BZ*包含关系：R=|x,yAxy，其中A为集合族例：B=a,b，A=P(B)，求R。,庄伯金bjzhuang,11,关系的表示方法,集合表达式关系矩阵关系图,庄伯金bjzhuang,12,关系矩阵,设A=x1,x2,.,xn，R是A上的关系，令rij=1，若Rrij=0，若R则有是R的关系矩阵，记作MR。,庄伯金bjzhuang,13,关系图,设A=x1,x2,.,xn，R是A上的关系。令图G=V,E，其中顶点集V=A，有向边集合E满足xi,xjV，ExiRxj。则称图G为R的关系图，记作GR。,关系的表示,例：A=1,2,3,4,R=,，求MR和GR。,庄伯金bjzhuang,14,庄伯金bjzhuang,15,关系的运算,逆关系：设R为二元关系，R的逆关系(简称R的逆)记作R-1，其中R-1=|R。右复合：设F和G为二元关系，G对F的右复合记作FG，其中FG=|t(FG)。左复合：设F和G为二元关系，G对F的左复合记作FG，其中FG=|t(GF)。,庄伯金bjzhuang,16,关系的运算,限制：设R为二元关系，A为集合，R在A上的限制记作RA，其中RA=|RxA。RA的值域称为A在R下的像，记作RA，其中RA=ran(RA)。幂：设R为A上的关系，n为自然数，则R的n次幂定义为：R0=|xA=IARn+1=RnR基本的集合运算,庄伯金bjzhuang,17,关系的运算规律,定理1：设F是任意关系，则(F-1)-1=FdomF-1=ranF,ranF-1=domF定理2：设F、G和H是任意的关系，则(FG)H=F(GH)(FG)-1=G-1F-1定理3：设R为A上的关系，则RIA=IAR=R,庄伯金bjzhuang,18,关系的运算规律,定理4：设F、G和H为任意关系，则F(GH)=FGFH(GH)F=GFHFF(GH)FGFH(GH)FGFHF定理5：设F为关系，A、B为集合，则F(AB)=FAFBFAB=FAFBF(AB)=FAFBFABFAFB,庄伯金bjzhuang,19,关系的运算规律,定理6：设A为n元集，R是A上的关系，则存在自然数s和t，使得Rs=Rt。定理7：设R为A上的关系，m、n为自然数，则有RmRn=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，RqS。,庄伯金bjzhuang,20,关系的性质,自反性反自反性对称性反对称性传递性,庄伯金bjzhuang,21,自反性与反自反性,定义1：设R为集合A上的二元关系，若x(xAR)，则称R在A上具有自反性；若x(xAR)，则称R在A上具有反自反性。例：设A=1,2,3,R1,R2,R3是A上的关系，判断他们是否具有自反性或反自反性R1=,R2=,R3=,庄伯金bjzhuang,22,对称性与反对称性,定义2：设R为A上的二元关系若xy(x,yARR)，则称R是A上的对称关系；若xy(x,yARRx=y)，则称R是A上的反对称关系。例：设A=1,2,3,R1,R2,R3,R4为A上的关系，判断他们的对称性与反对称性：R1=,R2=,R3=,R4=,庄伯金bjzhuang,23,传递性,定义3：设R为A上的二元关系，若xyz(x,y,zARRR)，则称R是A上的传递关系。例：设A=1,2,3，,R1,R2,R3是A上的关系，判断他们是否具有传递性R1=,R2=,R3=,庄伯金bjzhuang,24,五种性质成立的充要条件,定理：设R为A上的二元关系，则R在A上自反当且仅当IAR；R在A上反自反当且仅当RIA=；R在A上对称当且仅当R=R-1；R在A上反对称当且仅当RR-1IA；R在A上传递当且仅当RRR,庄伯金bjzhuang,25,关系性质的保持,庄伯金bjzhuang,26,关系的闭包,定义：设R是A上的关系，R的自反（对称或传递）闭包是A上的关系R，并满足R是自反的（对称的或传递的）；RR；对A上任何一个包含R的自反（对称或传递）关系R，RR；R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。,庄伯金bjzhuang,27,闭包的构造,定理：设R为A上的关系，则有r(R)=RIA；s(R)=RR-1t(R)=RR2R3.,例,设A=a,b,c,d，A上的关系R=,，求R的自反闭包、对称闭包和传递闭包。,庄伯金bjzhuang,28,庄伯金bjzhuang,29,等价关系与等价类,定义：设R为非空集合A上的关系，如果R满足自反性、对称性和传递性，则称R为A上的一个等价关系。若R，则称x等价于y。例：集合A=N，定义A上的关系R为：R=|x,yAxy(mod3)设R为非空集合A上的等价关系，xA，令xR=y|yAR，称xR为x关于R的等价类，简称为x的等价类，简记为x。,庄伯金bjzhuang,30,等价类的性质,定理：设R为A上的等价关系，则xA，x非空；x,yA，若R，则xy=；x,yA，若R，则x=y；x=A。,庄伯金bjzhuang,31,商集与集合的划分,定义：设R为非空集合A上的等价关系，以R的所有等价类为元素的集合称为A关于R的商集，记作A/R，即A/R=x|xA。定义：设A为非空集合，若A的子集族满足：；xy(x,yxyxy=)；=A。则称为A的一个划分，称中的元素为A的划分块。商集A/R是A的一个划分。,商集与集合的划分,定理：对于集合A的任何一个划分，存在A上的一个等价关系R，使得该划分为A关于R的商集A/R。反之亦然。,庄伯金bjzhuang,32,庄伯金bjzhuang,33,练习,设集合A=1,2,3,4,5，找出A上的等价关系R，使得R能产生划分1,2,3,4,5，并画出关系图。设R是一个二元关系，S=|c(RR)。证明：若R是等价关系，则S也是等价关系。,庄伯金bjzhuang,34,偏序关系,定义：设R为非空集合A上的一个关系，若R具有自反性、反对称性和传递性，则称R为A上的偏序关系，记作。如果，则称x小于或等于y。定义：设R为非空集合A上的偏序关系，定义x,yA，xyxyxy；x,yA，x与y可比xyyx。定义：集合A和A上的偏序关系一起叫做偏序集，记作(A,)。定义：设R为非空集合A上的偏序关系，如果x,yA，x与y都是可比的，则称R为A上的全序关系（或线序关系）。,庄伯金bjzhuang,35,偏序图的表示,哈斯图排序：若xy，将x放在y的下方；连线：x,yA，如果xy，且不存在z，使得xzy，则将x和y连线。例：偏序集(1,2,3,4,5,6,7,8,9,整除),庄伯金bjzhuang,36,偏序集中的特殊元素,定义：设(A,)为偏序集，BA，yB，若x(xByx)，则称y为B的最小元；若x(xBxy)，则称y为B的最大元；若x(xBxyx=y)，则称y为B的极小元；若x(xByxx=y)，则称y为B的极大元。定义：设(A,)为偏序集，BA，yA，若x(xBxy)，则称y为B的上界；若x(xByx)，则称y为B的下界；令C=y|y为B的上界，则C的最小元为B的上确界；令D=y|y为B的下界，则D的最大元为B的下确界。,偏序集中的特殊元素,例：设A=1,2,3,4,5,6,7,8,9,10,11,12,24，集合A上的偏序关系为整除关系，B=2,3,4,6,9,庄伯金bjzhuang,37,庄伯金bjzhuang,38,函数的概念,定义：设任意两非空集合A和B，F为A到B上的关系，若xA，都存在唯一的yB，使得F，则称F为A到B的函数或映射，记作F：AB。若F，可记作y=F(x)，称x为自变量，y为F在x上的函数值。函数是关系，所以函数是集合。函数F=GFGGF所有从A到B的函数记作BA=F|F:AB，读作B上A。,庄伯金bjzhuang,39,函数的概念,定义：设函数F:AB若x1,x2A，且x1x2，都有F(x1)F(x2)，则称F为A到B的单射；若ranF=B，则称F为A到B的满射；若F既是单射又是满射，则称F为A到B的双射，或一一对应函数。,庄伯金bjzhuang,40,常用函数,常值函数：函数F:AB，对xA，存在一固定元素cB，满足F(x)=c；恒等函数：IA=|xA；单调函数：函数F:AB，x1,x2A，若x1x2时F(x1)F(x2)，则称F为单调递增函数；F(x1)F(x2)，则称F为单调递减函数；特征函数：任意集合AA，函数XA:A0,1，若xA，则F(x)=1，否则，F(x)=0；自然映射：设R为A上的等价关系，函数G:AA/R，G(x)=x。,庄伯金bjzhuang,41,函数的运算,复合函数：设函数F与G，满足：dom(GF)=x|xdomFF(x