《第节关系的概念性质及运算》由会员分享，可在线阅读，更多相关《第节关系的概念性质及运算（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)
2、 R，则称，则称a与与b不符合关系不符合关系R，并记为，并记为aRb。潭爱阎猖迭仰俘吃虏贮仍愤球酥观粒限冻熔炸矮霹凄檄苇嚷寂寨甭琵蚁我第节关系的概念性质及运算第节关系的概念性质及运算2集合与图论 定义定义2 设设R A B，集合，集合 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)。 集合集合
3、 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。映射是特殊的二元关系。映射是特殊的二元关系。令令f:AB，f(1)=a，f(2)=b，则则映射映射f就对应着就对应着A B的子集的子集(1,a)，(2,b)关系与映射关系与映射问题问题1：映射与二元关系有什么联系？映射与二元关系有什么联系？ （前提：映射和二元关系都是从前提
4、：映射和二元关系都是从A到到B的的）寡注习漆耀悸操钡正锅婆僵曼项勺橡枪悄怖遥霍惋娃孙穆凄袁鸟孵祁跨埠第节关系的概念性质及运算第节关系的概念性质及运算4集合与图论 定义定义1 设设A,B是两个集合，一个从是两个集合，一个从A B到到是是,否否的映射的映射R，称为从，称为从A到到B的一个的一个二元关系二元关系，或，或A与与B间的一个二元关系。间的一个二元关系。 (a, b) A B，如果，如果(a, b)在在R下的象为下的象为“是是”，则，则a与与b符合关系符合关系R，记为，记为aRb；若若A=B，则称，则称R为为A上的二元关系。上的二元关系。 如果如果(a, b)在在R下的象为下的象为“否否”，
5、则说，则说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)，
6、b称称 a在在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、型墓吁疡伏赔灭羔喷攀岭捍沤焙隆楔第节关系的概念性质及运算第节关系的概念性质及运算7集合与图论 集合集合(a, a) a A称为称为A上的上的恒等关系恒等关系或相等或相等关关系，并记为系，并记为IA。 空集空集也是也是A B的一个子集。的一个子集。 空集空集叫做叫做A到到B的的空关系空关系。 A B是是A B的一个子集，按定义的一个子集，按定义A B也是从也是从A到到B的一个二元关系。的一个二元关系。 A B叫做叫做A到到B的的全关系全关系。四个特殊二元关系四个特殊二元关系 设设R是是A到到B的二元关系，集合的二元关系，集合 (y, x) (x, y) R称为称为R的的逆关系，简称逆关系，简称R
8、的的逆，逆，记为记为R-1。 显然：显然：R-1是是B到到A的二元关系。的二元关系。澎匆畜震后盅胺戴持歇癌推挞豆躇敢舰犁聘俭疯橙辽奠观约宿氖插许锑谓第节关系的概念性质及运算第节关系的概念性质及运算8集合与图论例例1：整除关系整除关系例例2：整数集整数集Z上的模上的模n同余关系同余关系 设设Z为整数集，为整数集，Z上的整除关系记为上的整除关系记为。 m, n Z, m n 当且仅当当且仅当 m能除尽能除尽n。 设设n为任一给定的自然数。对任意两个整数为任一给定的自然数。对任意两个整数m, k，如果如果m和和k被被n除，所得余数相等，则称除，所得余数相等，则称m与与k为为模模n同同余余，并记为：，
9、并记为：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称为称为R的一个的一个域域。例例4： 设设 1、A为某单位职工为某单位职工“姓名姓名”的集合；的
10、集合； 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大学大学
11、是是400李四李四男男50硕士硕士是是1400李晓芬李晓芬女女18高中高中否否300 这其实就是关系型数据库的一个数据表。这其实就是关系型数据库的一个数据表。 n元关系是关系数据模型的核心，而关系数据模型元关系是关系数据模型的核心，而关系数据模型是关系型数据库的基础。是关系型数据库的基础。二元关系到二元关系到n元关系的推广元关系的推广闻撼汽扮慨符营崭镊掺齐疫摹离色蜂撕桌追鸽挪紫到椅鸥借卵伏炮嗽诺椿第节关系的概念性质及运算第节关系的概念性质及运算11集合与图论2 关系的性质关系的性质 定义定义1 X上的二元关系上的二元关系R称为称为自反的自反的，如果，如果 x X, xRx。 在这个定义中，要求
12、在这个定义中，要求X的每个元素的每个元素x，都有，都有xRx，即即(x, x) R。设设IX是是X上的恒等关系，即：上的恒等关系，即：IX=(x, x) x X。显然：显然：R是自反的，当且仅当是自反的，当且仅当IX R。胀嘿醋汗袒侥辛诺爹耗问罕场衙寝箍斥寝惫均砖北额恫程蕾斟南釜努析师第节关系的概念性质及运算第节关系的概念性质及运算12集合与图论 例例1：IX是是X上的自反关系，但上的自反关系，但IX的任一真子集的任一真子集R IX不是不是X上的自反关系。上的自反关系。 例例2：实数集上的实数集上的“小于或等于小于或等于”关系关系“”是是不是自反的？小于关系不是自反的？小于关系“是反自反的。是
13、反自反的。注意：注意： 反自反的二元关系必不是自反的；反自反的二元关系必不是自反的； 但不是自反的二元关系，却不一定是反自反。但不是自反的二元关系，却不一定是反自反。例例5：令令X=a,b,c，R=(a,b),(a,a),(b,c),(c,c)。 关系的性质：反自反关系的性质：反自反R不是自反的，但它也不是反自反的。不是自反的，但它也不是反自反的。显然：显然：R是反自反的，当且仅当是反自反的，当且仅当RIX= 。雹滑误敷强肋咖肮艳滑馆苛法柳头阀俐诞膜来挥佰今疮澈邯烧衅生蔗粮盗第节关系的概念性质及运算第节关系的概念性质及运算14集合与图论 定义定义3 设设R为为X上的二元关系。如果上的二元关系。
14、如果 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是对称的，当且仅当是对称的，当且仅当R= R-1。式复锰达剖沟擂撅亿簿姓稗宛肾揍疗祁阿家昂七若仕扮眉作僚要徽罗汛绎第节关系的概念性质及运算第节关系的概念性质及运算15集合与图论 定义定义4 设设R为为X上的二元关系。
15、对上的二元关系。对X的任意元素的任意元素x,y,如果如果xRy且且yRx，则，则x=y，那么就称，那么就称R为为反对称的反对称的。例例8：集合间的包含关系集合间的包含关系 是不是反对称关系？是不是反对称关系？ 例例9：实数集上的实数集上的“小于或等于小于或等于”关系关系是不是反对是不是反对称的？称的？例例10：恒等关系恒等关系Ix。关系的性质：反对称关系的性质：反对称显然：显然：R是反对称的，当且仅当是反对称的，当且仅当RR-1 IX。道骨振晚龚雁如翱坠烟蜘硫锋闹冲危酷摸肉阜盘艺酞硝遮瘫类郡优共景萄第节关系的概念性质及运算第节关系的概念性质及运算16集合与图论 定义定义8：设设R为为X上的二元
16、关系。如果对上的二元关系。如果对X上的任意上的任意x,y,z，只要，只要xRy且且yRz，就有，就有xRz，则称，则称R为为传递关系传递关系。例例11： Z上的模上的模n同余关系是不是传递关系？同余关系是不是传递关系？例例12： R上的上的“小于或等于小于或等于”关系关系？ Z上的整除关系是不是传递关系？上的整除关系是不是传递关系？关系的性质：传递关系的性质：传递显然：显然：R是传递的，当且仅当是传递的，当且仅当 ？。柬践海突操招刽定众赏白儒妓车拢幽土辊橡肾由错万小汞圭欧逆纷伸招校第节关系的概念性质及运算第节关系的概念性质及运算17集合与图论例例13：设设R为为X上的二元关系。上的二元关系。如
17、果如果R且且R是反自是反自反和对称的，则反和对称的，则R不是传递的。不是传递的。例例14：设设R为为X上的二元关系。上的二元关系。R是对称的且反对称的是对称的且反对称的当且仅当当且仅当R IX。关系的性质关系的性质例例15：设设R,S是集合是集合X上的两个传递关系，问上的两个传递关系，问RS是否是传递关系呢？是否是传递关系呢？帮韶柿趴请童汁缀洋玲吞植瞩顽裁撩嘘翌腥钞无哭输动瓢轩媳痴犹设汝憾第节关系的概念性质及运算第节关系的概念性质及运算18集合与图论自反性自反性 反自反性反自反性 对称性对称性 反对称性反对称性 传递性传递性R1 1 R1R2 R1R2 R1 R2 R1 R2 运算与性质的关系
18、运算与性质的关系玻绅沥夫折垣妙鹏鸦吼详挎蚀鳞咀疚逗霉耪沧匠翁狠猎蒋菲碰呛肾范日寐第节关系的概念性质及运算第节关系的概念性质及运算19集合与图论 定义定义1 设设R是是A到到B的二元关系的二元关系，S是是B到到C的二元的二元关系。关系。R与与S的的合成合成是是A到到C的一个二元关系，记成的一个二元关系，记成R S，并且，并且 R S=(x,z) (x,z) A C且且 y B使得使得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 关系的合成关系的合成侥颈喊萌匣冤臣欧妥孵
19、判擒司章侠琵刊蓟君悠似断过米掌埃敲损箱蛮脯伤第节关系的概念性质及运算第节关系的概念性质及运算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的二元关系，的二元关系，R4是从是从C到到D的二元关系，则的二元关系，则 (1)R1 (R2R3)=
20、(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
21、，R1=(a,a),(a,b), R2=(a,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
22、、关系的逆的合成、关系的逆的合成关系合成的性质关系合成的性质 定理定理4 设设R是是X上的二元关系，则上的二元关系，则R是传递的当是传递的当且仅当：且仅当：R R R。 6、关系、关系R是传递关系的充要条件是传递关系的充要条件例例3：集合集合X上的上的二元关系二元关系R是对称且传递的，当且是对称且传递的，当且仅当仅当R=R R-1。痛张屉笺汀菱舰养咕取十耶蚁吗源领奋呈煮穗犹葱币衡廓远瘤秘巾诺嘉弦第节关系的概念性质及运算第节关系的概念性质及运算23集合与图论关系幂运算的定义及性质关系幂运算的定义及性质 定义定义2 设设R是是X上的一个二元关系，上的一个二元关系，R的的n次幂次幂记作记作Rn，n为
23、非负整数。为非负整数。(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
