离散数学关系的概念、性质及运算.ppt

《离散数学关系的概念、性质及运算.ppt》由会员分享，可在线阅读，更多相关《离散数学关系的概念、性质及运算.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、集合与图论第第6节节 关系的概念、性质及合成关系的概念、性质及合成主要内容：主要内容：关系的概念关系的概念关系的性质关系的性质关系的合成关系的合成1集合与图论 定义定义1 设设A,B是两个集合。是两个集合。A B的任一子集的任一子集R称为从称为从A到到B的一个的一个二元关系二元关系。如果如果A=B，则称，则称R为为A上的一个二元关系。上的一个二元关系。1 关系的概念关系的概念 如果如果(a,b)R，则称，则称a与与b符合关系符合关系R，并记，并记为为aRb;如果如果(a,b)R，则称，则称a与与b不符合关系不符合关系R，并记为，并记为aRb。2集合与图论 定义定义2 设设R A B，集合，集合

2、 x x A且且 y B使得使得(x,y)R称为称为R的的定义域定义域，并记为，并记为dom(R)。例如：例如：设设A=1,2,3,4，B=a,b,c,d,e，(1,a),(2,b),(2,c),(3,c)是一个二元是一个二元关系。关系。1,2,3是定义域，是定义域，a,b,c是值域是值域一般情况下：一般情况下：A dom(R);B ran(R)。集合集合 y y B且且 x A使得使得(x,y)R称为称为R的的值域值域，并记为，并记为ran(R)。dom(R)A;ran(R)B。定义域与值域定义域与值域3集合与图论例如例如:A=1,2，B=a,b,c。映射是特殊的二元关系。映射是特殊的二元关

3、系。令令f:AB，f(1)=a，f(2)=b，则则映射映射f就对应着就对应着A B的子集的子集(1,a)，(2,b)关系与映射关系与映射问题问题1：映射与二元关系有什么联系？映射与二元关系有什么联系？（前提：映射和二元关系都是从前提：映射和二元关系都是从A到到B的的）4集合与图论 定义定义1 设设A,B是两个集合，一个从是两个集合，一个从A B到到是是,否否的映射的映射R，称为从，称为从A到到B的一个的一个二元关系二元关系，或，或A与与B间的一个二元关系。间的一个二元关系。(a,b)A B，如果，如果(a,b)在在R下的象为下的象为“是是”，则，则a与与b符合关系符合关系R，记为，记为aRb；

4、若若A=B，则称，则称R为为A上的二元关系。上的二元关系。如果如果(a,b)在在R下的象为下的象为“否否”，则说，则说a与与b没有没有或不符合关系或不符合关系R，并记为，并记为aRb。关系与映射关系与映射5集合与图论 定义定义1 一个从一个从A到到B的多值部分映射的多值部分映射R称为从称为从A到到B的一个的一个二元关系二元关系。关系与映射关系与映射 设设A,B是两个集合，一个从是两个集合，一个从A到到2B 的映射的映射R称为称为从从A到到B的一个的一个多值部分映射多值部分映射。如果如果a A，R(a)=，则称，则称R在在a无定义；无定义；而如果而如果R(a)，则，则 b R(a)，b称称 a在

5、在R下的一下的一个象或值个象或值。6集合与图论例如：例如：设设A=1,2，B=a,b,c，A B=(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)。A B有有6个元素，个元素，从而有从而有26个子集，个子集，因此从因此从A到到B就有就有26个关系。个关系。答案：答案：2mn问题问题2：A到到B的关系的个数的关系的个数设设|A|=m，|B|=n，则，则A到到B上有多少个二元关系？上有多少个二元关系？关系的个数关系的个数7集合与图论 集合集合(a,a)a A称为称为A上的上的恒等关系恒等关系或相等或相等关关系，并记为系，并记为IA。空集空集也是也是A B的一个子集。的一个子集

6、。空集空集叫做叫做A到到B的的空关系空关系。A B是是A B的一个子集，按定义的一个子集，按定义A B也是从也是从A到到B的一个二元关系。的一个二元关系。A B叫做叫做A到到B的的全关系全关系。四个特殊二元关系四个特殊二元关系 设设R是是A到到B的二元关系，集合的二元关系，集合 (y,x)(x,y)R称为称为R的的逆关系，简称逆关系，简称R的的逆，逆，记为记为R-1。显然：显然：R-1是是B到到A的二元关系。的二元关系。8集合与图论例例1：整除关系整除关系例例2：整数集整数集Z上的模上的模n同余关系同余关系 设设Z为整数集，为整数集，Z上的整除关系记为上的整除关系记为。m,n Z,m n 当且

7、仅当当且仅当 m能除尽能除尽n。设设n为任一给定的自然数。对任意两个整数为任一给定的自然数。对任意两个整数m,k，如果如果m和和k被被n除，所得余数相等，则称除，所得余数相等，则称m与与k为为模模n同同余余，并记为：，并记为：m k(mod n)当当n=3时，时，2 5(mod 3)，5 7(mod 3)。关系实例关系实例例例3：设设X是一个集合，集合的包含于是一个集合，集合的包含于“”是是2X上的上的二元关系。二元关系。9集合与图论 定义定义3 设设A1,A2,.,An是是n个集合，一个个集合，一个A1 A2.An的子集的子集R称为称为A1,A2,.,An间的间的n元关系元关系。每个每个Ai

8、称为称为R的一个的一个域域。例例4：设设 1、A为某单位职工为某单位职工“姓名姓名”的集合；的集合；2、B为为“性别性别”之集合，之集合，B=男，女男，女；3、C为职工年龄集合为职工年龄集合 C=1,2,.,100;4、D表示表示“文化程度文化程度”；D=小学小学,初中初中,高中高中,大学大学,硕士硕士,博士博士；5、E是是“婚否婚否”集合，集合，E=是，否是，否；6、F表示月工资，表示月工资，F=0,20000。二元关系到二元关系到n元关系的推广元关系的推广10集合与图论姓名姓名A性别性别B年龄年龄C文化程度文化程度D婚否婚否E工资工资F张三张三男男28大学大学是是400李四李四男男50硕士

9、硕士是是1400李晓芬李晓芬女女18高中高中否否300 这其实就是关系型数据库的一个数据表。这其实就是关系型数据库的一个数据表。n元关系是关系数据模型的核心，而关系数据模型元关系是关系数据模型的核心，而关系数据模型是关系型数据库的基础。是关系型数据库的基础。二元关系到二元关系到n元关系的推广元关系的推广11集合与图论2 关系的性质关系的性质 定义定义1 X上的二元关系上的二元关系R称为称为自反的自反的，如果，如果 x X,xRx。在这个定义中，要求在这个定义中，要求X的每个元素的每个元素x，都有，都有xRx，即即(x,x)R。设设IX是是X上的恒等关系，即：上的恒等关系，即：IX=(x,x)x

10、 X。显然：显然：R是自反的，当且仅当是自反的，当且仅当IX R。12集合与图论 例例1：IX是是X上的自反关系，但上的自反关系，但IX的任一真子集的任一真子集R IX不是不是X上的自反关系。上的自反关系。例例2：实数集上的实数集上的“小于或等于小于或等于”关系关系“”是是不是自反的？小于关系不是自反的？小于关系“是反自反的。是反自反的。注意：注意：反自反的二元关系必不是自反的；反自反的二元关系必不是自反的；但不是自反的二元关系，却不一定是反自反。但不是自反的二元关系，却不一定是反自反。例例5：令令X=a,b,c，R=(a,b),(a,a),(b,c),(c,c)。关系的性质：反自反关系的性质

11、：反自反R不是自反的，但它也不是反自反的。不是自反的，但它也不是反自反的。显然：显然：R是反自反的，当且仅当是反自反的，当且仅当RIX=。14集合与图论 定义定义3 设设R为为X上的二元关系。如果上的二元关系。如果 x,y X,只要只要xRy就有就有yRx，则称，则称R是是对称的对称的。例例6：定义在人的集合定义在人的集合X上的上的“同学同学”、“战友战友”、“兄弟兄弟”关系是对称关系。关系是对称关系。例例7：令令f:AB,Ker(f)=(x,y)x,y A且且f(x)=f(y),Ker(f)称为称为f的的核核。自反自反对称对称关系的性质：对称关系的性质：对称显然：显然：R是对称的，当且仅当是

12、对称的，当且仅当R=R-1。15集合与图论 定义定义4 设设R为为X上的二元关系。对上的二元关系。对X的任意元素的任意元素x,y,如果如果xRy且且yRx，则，则x=y，那么就称，那么就称R为为反对称的反对称的。例例8：集合间的包含关系集合间的包含关系 是不是反对称关系？是不是反对称关系？例例9：实数集上的实数集上的“小于或等于小于或等于”关系关系是不是反对是不是反对称的？称的？例例10：恒等关系恒等关系Ix。关系的性质：反对称关系的性质：反对称显然：显然：R是反对称的，当且仅当是反对称的，当且仅当RR-1 IX。16集合与图论 定义定义8：设设R为为X上的二元关系。如果对上的二元关系。如果对

13、X上的任意上的任意x,y,z，只要，只要xRy且且yRz，就有，就有xRz，则称，则称R为为传递关系传递关系。例例11：Z上的模上的模n同余关系是不是传递关系？同余关系是不是传递关系？例例12：R上的上的“小于或等于小于或等于”关系关系？Z上的整除关系是不是传递关系？上的整除关系是不是传递关系？关系的性质：传递关系的性质：传递显然：显然：R是传递的，当且仅当是传递的，当且仅当？。17集合与图论例例13：设设R为为X上的二元关系。上的二元关系。如果如果R且且R是反自是反自反和对称的，则反和对称的，则R不是传递的。不是传递的。例例14：设设R为为X上的二元关系。上的二元关系。R是对称的且反对称的是

14、对称的且反对称的当且仅当当且仅当R IX。关系的性质关系的性质例例15：设设R,S是集合是集合X上的两个传递关系，问上的两个传递关系，问RS是否是传递关系呢？是否是传递关系呢？18集合与图论自反性自反性 反自反性反自反性 对称性对称性 反对称性反对称性 传递性传递性R1 1 R1R2 R1R2 R1 R2 R1 R2 运算与性质的关系运算与性质的关系19集合与图论 定义定义1 设设R是是A到到B的二元关系的二元关系，S是是B到到C的二元的二元关系。关系。R与与S的的合成合成是是A到到C的一个二元关系，记成的一个二元关系，记成R S，并且，并且 R S=(x,z)(x,z)A C且且 y B使得

15、使得xRy且且ySz例例1：设设X=a,b,c,d，R=(a,b),(c,d)，S=(b,c),(d,a)。R S=(a,c),(c,a)S R=(b,d),(d,b)3 关系的合成关系的合成20集合与图论 定理定理1 设设R1,R2,R3分别是从分别是从A到到B，B到到C，C到到D的的二元关系，则二元关系，则(R1 R2)R3=R1(R2 R3)。2、合成运算满足结合律、合成运算满足结合律1、一般来说，合成运算不满足交换律，即、一般来说，合成运算不满足交换律，即R S S R。关系合成的性质关系合成的性质 定理定理2 设设R1是是A到到B的二元关系，的二元关系，R2,R3是从是从B到到C的二

16、元关系，的二元关系，R4是从是从C到到D的二元关系，则的二元关系，则 (1)R1(R2R3)=(R1 R2)(R1 R3)(2)R1(R2R3)(R1 R2)(R1 R3)(3)(R2R3)R4=(R2 R4)(R3 R4)(4)(R2R3)R4(R2 R4)(R3 R4)3、合成运算对并、交运算的分配关系、合成运算对并、交运算的分配关系21集合与图论 4、一般说来，合成运算对差运算不满足分配律：、一般说来，合成运算对差运算不满足分配律：R1(R2R3)(R1 R2)(R1 R3)(R2R3)R4(R2 R4)(R3 R4)例例2：设设X=a,b,c，R1=(a,a),(a,b),R2=(a,

17、a),(b,c)，R3=(a,c),(b,b)。R2R3=(a,a),(b,c)(R1 R2)=(a,a),(a,c)R1(R2R3)=(a,a),(a,c)(R1 R3)=(a,c),(a,b)(R1 R2)(R1 R3)=(a,a)关系合成的性质关系合成的性质22集合与图论 定理定理3 设设R,S是集合是集合X上的两个二元关系，则上的两个二元关系，则 (1)(R S)-1=S-1 R-1；(2)R R-1是对称的。是对称的。5、关系的逆的合成、关系的逆的合成关系合成的性质关系合成的性质 定理定理4 设设R是是X上的二元关系，则上的二元关系，则R是传递的当是传递的当且仅当：且仅当：R R R

18、。6、关系、关系R是传递关系的充要条件是传递关系的充要条件例例3：集合集合X上的上的二元关系二元关系R是对称且传递的，当且是对称且传递的，当且仅当仅当R=R R-1。23集合与图论关系幂运算的定义及性质关系幂运算的定义及性质 定义定义2 设设R是是X上的一个二元关系，上的一个二元关系，R的的n次幂次幂记作记作Rn，n为非负整数。为非负整数。(1)R0=IX，R1=R，R2=R R;(2)Rn+1=Rn R。定理定理5 设设R是是X上的一个二元关系，则对任意的非上的一个二元关系，则对任意的非负整数负整数m,n有有 (1)Rm Rn=Rm+n,(2)(Rm)n=Rmn。24集合与图论 定理定理7 设设R是是X上的二元关系。如果存在非负整上的二元关系。如果存在非负整数数s,t，st，使得，使得Rs=Rt，则，则 (1)Rs+k=Rt+k，k为非负整数；为非负整数；(2)Rs+kp+i=Rs+i，其中，其中p=t-s，而，而k,i为非负整数；为非负整数；(3)令令S=R0,R,R2,.,Rt-1，则对任意的非负的，则对任意的非负的整数整数q有有Rq S。定理定理6 设设X是一个有限集合且是一个有限集合且 X=n，R为为X上的任上的任一二元关系，则存在非负整数一二元关系，则存在非负整数s,t使得使得0st2n2且且Rs=Rt。关系幂运算的定义及性质关系幂运算的定义及性质25