离散数学第四章二元关系

第四章二元关系离散数学陈志奎主编人民邮电出版社前言在日常生活中，我们都十分熟悉关系这个词的含义，例如夫妻关系，同事关系，上下级关系，位置关系等。在数学中，关系可表达集合中元素间的联系。在计算机科学中，关系的概念也具有重要意义。例如，数字计算机的逻辑设计和时序设计中，都应用了等价关系和相容关系的概念。在编译程序设计、讯息检索、数据结构等领域中，关系的概念都是不可缺少的，常常使用复合数据结构，诸如阵列、表格或者树去表达数据集合。而这些数据集合的元素间往往存在着某种关系。在算法分析和程序结构中，关系的概念起着重要作用。与关系相联系着的，是对客体进行比较，这些被比较的客体当然是有关系的。根据比较结果的不同，计算机将去执行不同的任务。2023/5/222PART01多重序元与笛卡尔乘积主要内容PART01PART01关系的基本概念PART02PART01关系的运算PART03PART01关系的性质PART04PART01关系的表示PART05PART01关系的闭包运算PART06PART01特殊关系PART07PART01关系型数据库PART082023/5/2234.1多重序元与笛卡尔乘积定义4.1由两个元素x和y按一定顺序排列成的二元组叫作序偶或有序对，记作<x,y>，其中x是序偶的第一元素，y是序偶的第二元素。与集合不同，序偶是元素顺序相关的概念，即，而两个序偶相等的充要条件是两个序偶的第一元素相等且第二元素相等，即例如集合{1,2}和{2,1}表示同一个集合，而<1,2>和<2,1>则表示平面上不同的点，即不同的序偶。4序偶2023/5/224.1多重序元与笛卡尔乘积例4.1已知，求x和y。解：由序偶相等的充要条件可得解得x=3

,y=-2。应该指出的是，序偶<a,b>两个元素不一定来自同一个集合，他们可以代表不同类型的事务。例如，a代表操作码，b代表地址码，则序偶<a,b>就代表一条单址指令。5序偶2023/5/224.1多重序元与笛卡尔乘积把序偶的概念加以推广，可以定义n重序元。例如，三重序元是一个序偶，它的第一元素是一个序偶，一般记作<<x,y>,z>，为方便起见把它简记为<x,y,z>。依此类推，重序元是一个序偶，它的第一元素是(n-1)重序元，并可记作

。给定两个n重序元和，于是可有因此可把n重序元改写成，其中第i个元素通常称作n重序元的第i个坐标。6序偶2023/5/224.1多重序元与笛卡尔乘积定义4.2设A和B是任意两个集合。若序偶的第一元素是A的一个元素，第二元素是B的一个元素，则所有这样的序偶集合，称为A和B的笛卡儿乘积，记作AxB，即

7笛卡尔乘积2023/5/224.1多重序元与笛卡尔乘积由排列组合的知识不难证明，如果，，则。笛卡儿乘积运算具有以下性质。1．对任意集合A，根据定义有

２．一般来说，笛卡儿乘积运算不满足交换律，即

（当时）

8笛卡尔乘积2023/5/224.1多重序元与笛卡尔乘积笛卡儿乘积运算具有以下性质。3．笛卡儿乘积运算不满足结合律，即

9笛卡尔乘积2023/5/224.1多重序元与笛卡尔乘积笛卡儿乘积运算具有以下性质。4．笛卡儿乘积运算对并和交运算满足分配率，即（1）（2）（3）（4）5.

10笛卡尔乘积2023/5/224.1多重序元与笛卡尔乘积设是加标集合，与A对应的指标集合是集合的笛卡儿乘积可以表示成例如：对于n个集合的笛卡尔乘积来说，同理可有

11笛卡尔乘积2023/5/22PART01多重序元与笛卡尔乘积主要内容PART01PART01关系的基本概念PART02PART01关系的运算PART03PART01关系的性质PART04PART01关系的表示PART05PART01关系的闭包运算PART06PART01特殊关系PART07PART01关系型数据库PART082023/5/22124.2关系的基本概念定义4.3设且为n个任意集合，若集合，则称R为间的n元关系；当n=2，则称R为到的二元关系，简称关系；若，则称R为空关系；若，则称R为全关系；若，则称R为A上的n元关系。例4.4设集合，试给出集合A上的小于或等于关系，大于或等于关系。解：令集合A上的小于或等于关系为，大于或等于关系为，根据定义4.1应有：

132023/5/224.2关系的基本概念例4.5令

根据上面的定义可知，是上的一元关系，是上的二元关系，是上的三元关系。若序偶属于，则记作或，否则记作或

。

142023/5/224.2关系的基本概念定义4.4设为间的n元关系，为间的n元关系，如果（1）n=m；（2）若，则；（3）把和作为集合看，则称n元关系和m元关系相等，记作。

152023/5/224.母2关系柄的基哭本概她念定义4.轰5对任在意集尼合A，定慰义A上的盖全域卷关系闲和A上的鞭等价跃关系但为售：1620丘23材/5轿/1煎94.比2关系裂的基惨本概标念例4.性7设馆，求拥以下刺关系（1）（2）（3）（4）解：（1）（2）（3）（4）1720归23业/5机/1友9PART01多重腐序元歇与笛倾卡尔桐乘积主要内容PA如RT01PART01关系贸的基柿本概觉念PA膊RT02PART01关系砍的运搁算PA劫RT03PART01关系逝的性哑质PA洋RT04PART01关系沉的表辅示PA景RT05PART01关系船的闭戒包运散算PA拾RT06PART01特殊密关系PA尚RT07PART01关系钻型数舅据库PA抬RT0820驼23叹/5融/1尾9184.冈3关系葵的运惊算关系充作为榨序偶除的集谜合，寸集合负的运土算并胆、交旷、相晒对补纤、绝腹对补肾和对各称差艰都可陵以作戏为关的系的考运算掠。除念此之范外，侧关系裹特有牙的基灿本运睡算还裂有以作下七课种。1920姓23便/5梦/1普94.杏3关系焦的运轧算定义4.散6设R是二其元关崭系（1）R中所柏有序哗偶的些第一屠元素倘构成签的集购合称起为R的定贪义域影，记装作禽，样其形喊式化岭表示盘为（2）R中所劫有序体偶的期第二迟元素冻构成萌的集伏合称撤为故的值腹域，乳记作玩，雨其形惨式化旧表示团为（3）R的定严义域晌和值吊域的标并集壳称为R的域睬，记务作炎，臭其形绣式化屡表示锈为2020竭23泰/5拼/1过94.蝇3关系乎的运脱算例4.岛8，则2120愉23熄/5宫/1吹94.偷3关系施的运遮算定义4.披7设R是二亚元关蝴系，到将R中每柳个序朱偶的箭第一愧元素戚同第极二元慰素交禾换后哥所得犹到的蚂关系壳称为R的逆关解系，简缸称R的逆，记断作贝，其那形式吩化表赵示为定义4.作8设F，G为二脾元关靠系，G对F的右合别成记作吴，其舍形式漂化定严义为2220仆23鲁/5快/1纸94.凝3关系鱼的运斥算例4.肯9设扁，沿，则类似扬的也电可以苍定义栽关系崇的左贡合成阵，即2320扯23芝/5确/1岔94.旱3关系唯的运演算定义4.吃9设R是二孤元关龙系，A是集尺合（1）R在A上的限制记作忽，其报形式芬化定炒义为（2）R在A下的像记作尿，其阁形式笔化定所义为不难援看出住是R的子侧关系介，而吓是爹的子匠集。2420蜘23泉/5雹/1屿94.攀3关系诸的运陆算例4.节10设所，割则为了叉使关友系运照算表详达式做更为咽简洁牺，我摄们对遮关系拥运算风的优割先级删作了芽进一强步规灿定：链首先记，关咬系运滥算中虎的逆搜运算顽优先躁于其证他运固算，镜而所尼有关速系特字有的仪运算桶都优手先于这其从颂集合片继承器而得利的运溉算，事最后叫，对秃于没挤有规疮定优趋先权说的运短算以套括号仿决定田运算档顺序佩。2520棵23抓/5芦/1抄94.都3关系垫的运淡算定理4.雾1设F是任通意关芝系，唇则（1）（2）,定理4.朋2设F，G，H是任用意关残系，栽则（1）（2）2620歇23炊/5务/1刻94.伙3关系幼的运锄算定理4.衰3设F，G为任睁意关插系，莲则（1）（2）定理4.倚4设R为A上的壳关系申，则2720序23设/5惭/1件94.延3关系分的运着算定理4.事5设F，G，H为任呆意关料系，衣则（1）（2）（3）（4）2820礼23犁/5乎/1葛94.捆3关系建的运珠算定理4.赔6设F为关谨系，A，B为集善合，悟则2920桂23迷/5役/1犯94.合3关系削的运亲算上述苦的对至关系称的合姜成运北算可跨以推匙广到兆一般悬情况掀。如关果牲是固从业到愧的关枕系，井是无从恳到扰的彻关系拿，…，械是从雀到驰的炎关系塔，则耍无括灿号表氏达式芹表毅达了抄从董到静的关野系。何特别程，当和统时，贿也就晶是说臭当集稿合A上的呈所有宁都是尽同样蒸的关武系时董，A上的反合成香关系交可表走达成杏，急并称梦作关系R的幂。3020魔23印/5罢/1页94.蛇3关系席的运垒算3120糊23苹/5耕/1昆94.梅3关系成的运是算3220线23断/5姓/1温9PART01多重岗序元倚与笛扬卡尔泳乘积主要内容PA往RT01PART01关系毫的基乐本概小念PA妹RT02PART01关系悠的运粱算PA仍RT03PART01关系跌的性陪质PA共RT04PART01关系表的表鱼示PA墨RT05PART01关系部的闭半包运深算PA挪RT06PART01特殊夫关系PA笑RT07PART01关系狱型数窝据库PA弹RT0820狠23启/5淡/1颂9334.壮4关系肯的性展质定义4.连11设R为集诸合A上的惩二元宗关系（1）若彼对每背个门，茅皆有村，谈则称R为自反剪的。其认形式票化表羽示为R是自伙反的（2）若认对每翻个亭，债皆有夏，怨则称R为反自迈反的。其让形式娇化表使示为R是反吓自反戚的（3）对助任意汽的羞，世若艇，恐则邪，就昌称R为对称臭的。其固形式蚂化表嘉示为R是对渔称的（4）对黄任意枣的须，泊若犯，见且辜，则x=克y，就或称R为反对链称的。其悬形式足化表番示为R是反宅对称挡的3420惩23县/5蔑/1舅94.吧4关系江的性凑质定义4.色11设R为集数合A上的庙二元煮关系（5）对装任意娱的苏，公若免且旬，百则网就控称R为可传农递的。其怒形式朝化表来示为R是可乎传递侄的（6）存壶在粗，塑并且凡而势，逝则称R为不可掩传递符的。其录形式泉化表壁示为R是不啦可传振递的3520惕23愁/5初/1弊94.糟4关系例的性糠质例4.澡11考虑托自然限数集缴合普上的小普通酷相等难关系墨“＝碧”，屋大于绑关系哪“＞勤”和难大于桨等于妥关系马“≥馋”，项则显日然有（1）“烤＝”翅关系桐是自驼反的乞、对申称的吴、反翠对称披的、词可传色递的菜。（2）“荡≥”旨关系挠是反才自反涉的、嫌反对胞称的登、可托传递相的。（3）“多≥”胶关系庭是自璃反的数、反舍对称繁的、喘可传饶递的偿。例4.霜12空集R上的护二元玩空关务系显谜然是可自反柏的、沉对称虾的、俘反对则称的融、反戒自反逢的、药可传盐递的割。3620阶23税/5呀/1介94.菜4关系椅的性踪蝶质定理4.姥10设R为A的二秘元关凤系，元则（1）R在A上自妖反当震且仅雕当（2）R在A上反搂自反其当且旗仅当（3）R在A上对春称当顽且仅湾当（4）R在A上反崖对称嚼当且卸仅当（5）R在A上可范传递凝当且她仅当3720学23歌/5渐/1酸9PART01多重葬序元景与笛盲卡尔手乘积主要内容PA竖RT01PART01关系烛的基胞本概高念PA熄RT02PART01关系义的运灾算PA所RT03PART01关系贼的性虚质PA苹RT04PART01关系拳的表箭示PA屡RT05PART01关系播的闭棍包运框算PA志RT06PART01特殊量关系PA哈RT07PART01关系军型数士据库PA振RT0820钩23婆/5棒/1屯9384.荐5关系兴的表炉示定义4.迟12设A和B为任兰意的衡非空腰有限毫集，R为任下意一屋个从A到B的二齿元关根系。兴以周中鱼的每忌个元态素为敌结点敢。对帖每个皆画彼一条纹从x到y的有如向边参，这菠样得钱到的窜一个伪图称贫为关绸系货的关系睛图。例4.沾14设妄，恩，从A到B的二案元关卡系R为，于是虹有39关系哪图R的关葱系图20讨23男/5辣/1菜94.泥5关系啊的表胳示可以寇看出兼关系妥图明丹确地忽反映开了关旧系的芳某些唯性质众。如贴果关适系爸是自详反的队，则卸每个撤结点槐上都半有一治条从倒自身付出发齐又指天向自阴身的伞环边过；如图果关荣系是带反自兵反的躬，则炭任何融结点监上部绳没有凭带环华的边仁；如澡果一随个关代系腿既不研是自毁反的型，也建不是和反自跑反的敌，则诞在某臂些结坏点上刚有带啄环的诸边，览而在足某些肆结点抖上没腾有带崭环的握边。如果旋关系批是对幻玉称的奔，则郑从一饥个结拆点到滋另一失个结面点间宣必定也有往抢返两顷条弧影线。源如果命关系炎是反慎对称逝的，谋则在碑两个悟结点信间只狱会存朱在单伤向弧允线。40关系挖图20淘23垃/5鸦/1并94.今5关系悄的表予示图4.攀2给出速了具失有各柄种性撑质的宋关系四的关华系图建。当往集合姜中元蛛素的父数目躁较大点时，报关系合的图原解表寺示就漫不是心很方跪便了法，由剃于计证算机和上表顿达矩夕阵并础不困刚难，勉所以颂我们关试图踢寻求颤关系辆的矩肝阵表壁示。41关系惜图20筛23券/5得/1肠94.例5关系鹊的表奸示定义4.竭13给定霉两个展有限稻集合犯和席，R是从X到Y的二春元关朽系。套如果内有则称管是R的关系鸡矩阵，记动作42关系招图20前23矮/5芝/1祸94.死5关系监的表船示43关系块图20足23优/5拍/1替94.怀5关系播的表怒示44关系鞭图20傍23傅/5抢/1旺94.头5关系悬的表壮示45关系宴图20海23益/5被/1抄94.丹5关系蔑的表刻示46关系门图20丢23译/5大/1爹9PART01多重缠序元伟与笛洗卡尔柜乘积主要内容PA雾RT01PART01关系纪的基见本概干念PA拢RT02PART01关系令的运渐算PA篇RT03PART01关系班的性阅质PA狸RT04PART01关系早的表败示PA鲜RT05PART01关系勾的闭膝包运茫算PA序RT06PART01特殊丝式关系PA繁RT07PART01关系叫型数矩据库PA习RT0820尝23弯/5妖/1拉9474.森6关系手的闭或包运快算前面娇我们胸已经谊介绍呢了如省何使写用关垄系的役合成舱运算绍去构找成新拌的关机系，光下面甜我们销讨论稿如何晨由给先定的屿关系R构成蔽一个困新的简关系评并且赠和裂应具兄有某秩些性辣质。把确皱保这轧些性震质的寻那些拦序偶匹补充浙到R中去锡就可喉构成逐。给贼定一巨个二晚元关老系溉，室它规黄定了茧局部恼的性燃质，凭希望深求得笋的是仗具有饺全面寒性质飘的另开一个待二元要关系迷。码例如渠，由R构成姓一个政可传部递关折系驱。在日偶常家罩族关磨系中携也有脉类似预的情雨形。叫如果R是个掩父子才关系起，则悟可能疼是个凉祖先劲关系袭；如介果R是个煌子父结关系恰，则脸可浴能是衬个后颤代关丧系。4820蛛23罚/5帐/1您94.俱6关系泛的闭犁包运糠算定义4.逼14给定宵集合A，R是A上的抢二元孟关系茅。如孔果有偿另一采个关叮系笼满枣足（1）踢是自康反的咐（对护称的权、可红传递纠的）充。（2）伞。（3）对洪于任呢何自向反的(对称茅的、序可传敬递的)关系悉，如湾果有疼，菜则乓，鬼则称荡关系期为轻的自反菊的（乔对称骆的，削可传段递的态）闭堪包。并驳用拥表示帮的自解反闭俘包，严用酷表狭示文的对冻称闭冬包，炸用局表示的可慢传递估闭包你。4920置23绍/5樱/1仙94.藏6关系先的闭权包运升算定理4.然11给定徒集合X，R是X上的箭关系己。于添是可壮有（1）R是自反恐的当且柔仅当（2）R是对称境的当且迈仅当（3）R是可传疲递的当且骡仅当定理4.龙12设R是遗Ａ傲上的跳二元含关系恳，则历有（1）（2）（3）5020道23头/5夕/1妈94.着6关系高的闭糖包运专算不难抓看出新，整吨数集粥合Ｚ致中，约小于淘关系宾“楚＜”筐的自携反闭今包是真“狡”，悬对称兽闭包膝是不腿等关集系“泰”叠；恒担等关割系拴的自饼反闭肾包是善；对仔称闭膛包是名；诸不等刷关系侦“蚊”的佳自反徒闭包远是全马域关秘系，繁对称躲闭包押是不伤等关剥系“攻”；笔空关斤系的站自反富闭包朴是恒换等关块系屈，对框称闭克包是煌空关订系。5120兼23挣/5瞎/1足94.始6关系枯的闭曾包运吨算例4.嚷20给定硬集合租，观和劲是A上的盛关系斯，试渔求出鼻和誓，并竹画出兵相应贿的关势系图末来。解：关系R，S及其灶传递里闭包拦，馆的摇关系苦图如哪图4.惧6所示既。5220乓23眠/5券/1皮94.舍6关系件的闭农包运最算定理4.闪13设X是含播有n个元指素的年集合阀，R是X上的舅二元鸡关系俗。于碍是可狗有例4.宝21设集逃合澡，R是X中的汁二元再关系费，R的关堆系图锄如图4.桨7所示养，试绑画出R的可典传递缩慧闭包被的奸关系德图。解：R的可热传递厚闭包讽的关签系图泼如图4.蒜8所示筛。53图4.克7恐R的关烤系图图4.网8都t限(R站)的关注系图20弯23墙/5于/1虑94.遭6关系谎的闭滴包运前算定理4.纹15设A是集匪合，R是集卸合A上的缴二元仓关系梢。于取是可传有（1）（2）（3）5420正23认/5钳/1炊9PART01多重搞序元卫与笛潜卡尔钳乘积主要内容PA考RT01PART01关系肿的基篮本概庄念PA葬RT02PART01关系雀的运贿算PA烂RT03PART01关系觉的性极质PA哄RT04PART01关系音的表中示PA且RT05PART01关系琴的闭仰包运部算PA战RT06PART01特殊臭关系PA捎RT07PART01关系赤型数递据库PA宇RT0820派23烈/5懂/1夜9554.奔7特殊魄关系定义4.公15给定齐非空斥集合S，及朱非空绕集合河，标如果退有（1）（2）则称梅集合A是集夏合S的覆盖。例如束，设裁集合敢，姿并且刷给定S的各句子集轻的集捏合乔和喜；显骗然集和合A和集最合B都是羽集合S的覆盛盖。挎即覆倦盖不哨唯一。56集合晓的覆限盖20县23怀/5泉/1琴94.盆7特殊异关系定义4.共16给定票非空演集合S，及特非空鸟集狸，割如果斤有（1）（2）采或（3）则称鲁集合A是集童合雹的一倍个划分。划沉分中紧的元诵素谨称枪为划潜分的类。如豆果划口分是创个有糕限集枝合，胖则划丙分的秩是划避分的弹类的电数目蛮。若腾划分婶是个胜无限烦集合错，则构划分岭的秩宪是无庸限的昌。划浆分是英覆盖勇的特痕定情泡况，祝即A中元毒素互惰不相泡交的帜特定耗情况痕。57集合洋的划必分20貌23摸/5允/1询94.焰7特殊长关系例如设竭，叉试考帜察S的各贤子集酒的下所列集羊合。显然的集合A和B是S的覆露盖，画当然C，D，E也都罪是S的覆悟盖；阶同时C，D，E也还企是S的划扇分，缎并且C的秩锤是2，D的秩才是1，E的秩朴是3；而F既不耻是覆隐盖也皱不是熔划分霉；集博合S的最糖大划毙分是狸以S的单悉个元冠素为悔类的砖划分辫，如捧上面粘的E；S的最隔小划草分是已以S为类姐的划机分，胖如上澡面的D。58集合腔的划嗓分和光覆盖20沿23所/5西/1指94.监7特殊刃关系定义4.晴17设A和梳是非限空集锡合S的两惭种划遵分，拦并可寸表示猾成如果屋的每抹一个观类眠，都仔是A的某气一个响类合的委子集沫，则新称划腥分舍是划陕分A的加细，并导说成阵是理加细弓了A。如丝式果吉是A的加牧细和遭，步则称壁是A的真加过细。划分稻全集E的过粮程，桃可看糕成是秧在表枕达全秆集E的文沟氏图踪蝶上划抹出分材界线肤的过盏程。微设A，B，C是全樱集E的三盖个子泽集。宽由A，B和C生成挖的E的划游分的筛类，脑称为极小津项或完全呜交集。对卡于三客个子大集A，B和C来说活，共说有胀个笑极小捷项，摔分别颂用帝来表围示。59集合口的划产分和另覆盖20绪23挪/5即/1利94.比7特殊鞋关系由图4.９可酿知并且傅是觉互不妖相交柳的，一般嚷情况喉，如逆果赔是全去集E的n个子糊集，疯则由秤这n个子腐集能锻够生倾成主个极耽小项娇，分断别用答来表泄示它烛们。作这些犹极小乒项互捎不相齐交，男并且膛并起希来等含于全搁集E。60集合个的划开分和号覆盖20傻23岭/5汪/1文94.滨7特殊估关系定义4.奶18设X是任记意集掌合,宋R是集路合X中的深二元阳关系暮。如恳果R是自弟反的每、对韵称的袭和可绢传递抹的，慢也就谊是说,如果颤有（1）（2）（3）则称R是等价追关系。如果R是集株合A上的戚等价炕关系帖，则R的定蛛义域独是调集合A自身朱，所改以称R是定萌义于捞集合A上的圆关系肆。实枝数集播合中哭数的制等于书关系芳，全平集的景各子级集间胀的相失等关阳系，早命题乘集合父中等缴价命科题间多的恒橡等关法系等泉，都涛是等筋价关柴系。61等价收关系20罚23吨/5阁/1甩94.财7特殊债关系例4.吧22给定科集合鹊，R是A上的竖二元苏关系够，并蛇且R给定真成，故试证告明R是一捐个等约价关滩系，纪并画幻玉出R的关省系图总和写温出R的关网系矩答阵。解：R的关我系矩壮阵如库下：在图4.拐10中给竟出了R的关水系图孤。由R的关胖系矩增阵和削关系灰图可下以看谁出，R是等清价关锐系。62等价卵关系R的关东系图20舰23寻/5欢/1浓94.拍7特殊骗关系设焰是莫正整赵数集始合，m是正戒整数凳。对榆于校来说碎，掏可将R定义甜成这里搂，“鲁”洁等价侨于命困题“崇当用m去除x和y时，失它们勾都有紧同样蹦的余鼠数”效。故支关系R也称晴为模m同余弦关系。63等价任关系20赴23德/5胃/1飘94.敏7特殊目关系定义4.皆19设m是个拣正整愚数和舅。如土果对岗于某摔一个赢整数n，有,则称x模等邮价于y，并侧记作整数m称为等价融的模冶数。显然异，这胁里是爸用“夺”表匹示模m等价攻关系R。定理4.索17任何国集合项中伙的模m相等难关系是一项个等胜价关层系。64等价历关系20宋23润/5惭/1希94.干7特殊疗关系定义4.丈20设R是集腔合A上的置等价毫关系极：对申于任貌何屡来说去，可损把集挎合叮规定仰成并称本它是鲜由x关于R的等价困类。为了锈简单城起见硬，有帅时也哗把距就写拿成难或降。选不难捧看出市，集粒合应是恨由集级合A中与x有等判价关啦系R的那哥些元拥素所岸组成鲜的。65等价顷类20垮23局/5蚀/1掠94.赔7特殊伍关系例4.蒜23设夺，R是A上的望等价民关系薯，并袭把R给定案成试画回出等屡价关肾系图脸，求枝出A中各面元素剂关于R的等捎价类枕。解：选等价漂关系梳如图4.嚼11所示牢。由塔等价搜关系秒图不仁难看腾出图4.秒11等价耀关系稀图66等价掏类20搞23炊/5绸/1税94.统7特殊嫁关系定理4.俗18设A是一座个集慎合，R是A上的券等价脸关系输。如纤果苍，录则定理4.筐19设R是集牵合A上的找等价古关系晓。于洞是可寇有（1）对理于所荷有的讯，或蹲者恭或谷者哑。（2）67等价犬类20拍23压/5桌/1惭94.象7特殊捡关系定理4.摸20设R是非害空集争合A上的挖等价陶关系惰。R的等甚价类右的集必合是A的一络个划假分。包根据停定理4.示18和定飞理4.舰19就能趣够证栽明此匀定理疮。此称定理回说明雀非空竭集合般的划兵分和而集合娱中的滋等价干关系站之间社，存季在一困种自译然对恒应关盐系。定义4.乞21设R是非依空集店合A上的沾等价踩关系蜓。以R的所挨有等朵价类仔作为格元素衫的集宪合络称蹈为S关于R的商集，记愉作验，也拉可写醋成68商集20饿23址/5口/1忌94.青7特殊糖关系下面鹅来考井察集稼合A中的准两个或特殊塑等价宣关系况：全问域关升系拆和恒饼等关软系陆。惜显然捡这两州种关预系都旁是A上的素等价亩关系决。由爷全域世关系拦所生翼成的运商集孩仅肤包含宫一个移元素A，而祥由恒苏等关吸系所遮生成旅的商阴集纳中的酷每个挂元素原都是倒由A中的膀单个支元素庸所组哭成的屈。盾所对愿应的砖划分练是A的最印小划菊分，慢所对孙应的膜划分勺是A的最患大划夏分。泄这两菜种划拳分被鱼称为A上的平凡兔划分。6920裙23略/5哭/1展94.激7特殊草关系例4.授24令R是整品数集抖合Z中的挑“模3同余舅”关直系，R可给稻定成试求Z的元难素所粪生成自的R等价虑类。解：助等价遮类是70等价妻类20在23桐/5姐/1届94.街7特殊璃关系定理4.抓21设C是非竭空集狠合A的一县个划腥分，湖则由嫌这个揉划分单所确誉定的随下述摔关系R：必定团是个脸等价运关系辞，并亦称R为由炎划分C导出遵的A上的引等价脆关系支。71等价禾类20壤23组/5置/1廊94.蛮7特殊趣关系72等价际类20饿23适/5竟/1奖94.夜7特殊份关系定义4.铲22给定稠集合A中的捐二元猛关系R，如赌果R是自刚反的仓、对啄称的犯，则脸称危是相容掀关系。也挂就是嘴说，偿可以言把百规定面成：（1）（2）显然剃，所哥有的齐等价衣关系纸都是随相容傍关系谅，但故相容抱关系悠并不劳一定你是等井价关微系。仇下面荡举例妙说明仁相容装关系院。设集恋合吐，A中的屿关系不难见看出R是自康反的蚁和对棉称的赵，因牛此R是个视相容播关系滥。如位果，花，则宣称x和y是相盟容的苦。73相容使关系20去23凉/5饱/1茅94.挺7特殊沾关系令舟，杜，葱，孕，绵。这潜里泥并脸且绑但茅，即宪该相碧容关眉系不押是可叶传递叉的。前把R写出榆来是敌：图4.贼12给出退了该轿相容妇关系R的图畏。由于转相容卫关系陪的自寺反性酸和对魔称性券，关渔系图悦中的柄所有推结点奋上都产有环它边；叉有相霜容关殖系的申两个海结点愈间都界有往竟返弧东线。星如果探找们匹删除框全部啊结点筑上的云环边宰，并骑且用蒸一条薯直线叹取代斗两结列点间嫩的两暂条弧沿线，虽这样捐就可扶以把柿图4.源12化简杜成图4.绞13。74相容蕉关系20卫23店/5惑/1详94.鸭7特殊常关系还可帆写出正该关重系R的矩啦阵如你下：由于乎相容洋关系幸是自萍反的暴，因煤而矩波阵对牲角线拖上的趣各元蚊素都额应是l；相掉容关林系是校对称田的，找所以珍矩阵甩关于萝主对股角线现也是咽对称将的。赠这样榨，仅殿给出嗽关系闹矩阵格下部谜的三黄角形垒部分铜也就帐够了普。简滩化后巴的关刃系矩屠阵如铜图4.亿14所示令胳，灰和认。在集暗合捕，隙和缴中，私同一摘个集简合内筐的元崭素都么是相迈容的嚷。这榆些集寸合的牧并集老就是吹给定景的集漆合X，亦铅即腥。挪因此穷，集饺合厌定义迹了集饼合X的一黑个覆梳盖，卫但它择不能郑构成英集合腾的一状个划喂分。75相容保关系20单23案/5矿/1齐94.孩7特殊巴关系定义4.狐23设携是集灭合X中的壁相容轨关系翠。假蠢定梢。如只果任割何一拆个特，脂都与正其他澡所有禽的元政素有浸相容倚关系宏，而嫌中慨没有认能与A中所肾有元勤素都这有相妈容关绑系的缠元素由，则继子集碎称为最大悬相容亚类。寻找行最大楚相容洁类的品方法蕉有两帝种：关系轧图法和关系犬矩阵盈法。76最大吗相容弟类20乐23亮/5轮/1煤94.窝7特殊穿关系关系付图法踏。关系狠图法蝴的实掀质在棋于寻薄找出铃“最丽大完秧全多愤边形葵”。暗所谓祝最大剂完全狸多边昌形，锤系指怨每一唱个顶符点都棉与其刘他所戏有顶邻点相弦连结描的多夫边形绸。（1）集久合中膏仅关罚系到助它自旅身的糊结点迟，是若一个持最大致完全刻多边暗形。（2）不伶都与济其它奴的结氧点相沃连接钢的一金条直浊线所路连接抬的两植个结苗点构因成一熄个最彩大完犹全多阔边形船。（3）三能角形寨的三发个顶席点构们成一何个最舒大完眼全多牙边形冒，对免角线族相连勒的四观边形俊的四怕个顶徐点构堪成一捎个最咽大完朵全多草边形矛，正滚五角帅星的秘五个乘顶点团构成巨一个脏最大沙完全滚多边培形，配正六以边形忘的六渠个顶捕点也碰是一岭个最泽大完窄全多头边形大。一腊个最伏大完腥全多宜边形静对应贪一个套最大喂相容气类。77关系绸图法20馒23愿/5祝/1疑94.雨7特殊莲关系例4.览27在图4.江15中，川给出妄了两检个相路容关毛系图您。试坡求出像它们祝的所焦有最痕大完剂全多墓边形,并求援出与亡它们皆相应狼的最械大相屡容类朽。解：旗图（a）的泳最大牺完全澡多边抚形有籍：四菌边形12励34线段25，36和56；与差它们良相应申的最成大相造容类防分别棕是：{1，2，3，4}，{2，5}，{3，6)，{5，6}。图淋（b）的底最大构完全腰多边桌形有哨：三章角形12旗3，13筒6，35声6和孤驱立结堂点4；与俘它们前相对贴应的搏最大假相容叶类分霉别是平：{1，2，3}，{1，3，6}，{3，5，6}和{4示}。图4.准15相容纵关系刃图78关系伐图法20顿23芦/5春/1毛94.并7特殊页关系关系碍矩阵穷法。首先丘制定咐简化旋了的妇关系肤矩阵亭，继瓜之按赖下列流步骤院求出捐各最敏大相败容类捡。（1）仅符与它具们自侧身有由相容棚关系严的那驱些元随素，刚能够捡分别班单独哥地构宋成最煌大相肌容类屋，因状此从洗矩阵药中删织除这匠些元幅素所过在的矩行和久列。（2）从哭简化钳矩阵辩的最尿右一耕列开荣始向窄左扫闯描，魄直到文发现嫌至少困有一村个非迷零记忧入值伯的列腰。该酒列中料的非扭零记蹈入值厕，表队达了却相应塞的相量容偶牲对。施列举疑出所梅有这巴样的始偶对狱。（3）继苹续往券左扫冈描，腥直到织发现凯下一牵个至钞少有买一个缘瑞非零蚕记入骂值的书列。滋列举推出对妻应于济该列亚中所闷有非狐零记哨入值凶的相那容偶黎对。谎在这拒些后者发现梦的相起容偶渴对中驻，如冷果有情某一肉个元案素与旦先前雪确定型了的炎相容尸类中哲的所姜有元虽素都燃有相聪容关揉系，霜则将狐此元迫素合虾并到废该相炎容类耻中去出；如骂果某灿一个戒元素平仅与死先前坑确定仅了的博相容慕类中物的部该分元泛素有馅相容璃关系名，则峰可用羞这些冬互为得相容邻的元筋素组归成一蚕个新批的相丸容类辨。删芽除已膊被包押括在乎任何封相容匹类中辅的那病些相谊容偶径对，督并列爱举出迟尚未并被包薪含在赌任何铅相容奴类中骆的所容有相反容偶卡对。（4）重豆复步炸骤（3），巾直到赞扫描技过简要化矩嗓阵的到所有胁列。最后忆，仅写包含坚孤立诉元素节的那独些相声容类姨，也摆是最绸大相孕容类棋。79关系星矩阵担法20糠23术/5嗓/1罪94.麻7特殊葱关系例4.绝29与图4.末15（b）中舌的相圈容关灾系图显相对乓应的灶简化驼矩阵玩如下镜图所占示，鹿试求挽各最面大相泼容类拒。解：氧这里华结点4是个脾孤立拌结点志，故岁在矩抖阵中残删除全了相扫应的单行和领列。糕根据廊步骤尊（2）和蚁（3）可搂有：（a）{甩4厚}（b）{耽4杯}，{叹5，6筐}（c）{即4掀}，{击5，6纠}，{偶3，5狱}，{者3，6丢}，合木并后液有{轻4仇}，{遥3大,主5秀,枕6喇}（d）{号4助}，{捧3，5，6介}，{黄2，3韵}（e）{羞4郑}，{蚀3，5，6后}，{沙2，3块}，{名1，2牙}，{氏1抗,融3敌}，{稍1，6膊}，合炸并后咱有{不4勿}，{陪3县,键5近,缺6爷}，{裁1，2，3矩}，{竖1毫,捧3，6存}这些膛相容抢类都陷是最载大相壁容类令。80关系郊矩阵胃法20皱23援/5航/1摩94.汉7特殊鸦关系定义4.遵24设R是集边合A上的纽奉二元悟关系霜。如量果R是自决反的技、反碌对称福的和炮可传将递的纽奉，亦落即有（1）（2）（3）则称R是集稻合A中的偏序该关系，简兆称偏序。序脖偶<A登,≤齿>称为偏序序集合。这里者用符借号“呆≤”忠表示岔偏序浊。这挪样，令符号泰“≤利”就挣不单貌纯意予味着摘实数炒中的只“小合于或农等于爹”关帜系。设事实谷上，局这是抹从特封定情随况中境，借挎用符聋号“珠≤”汽去表消示更壁为普谅遍的透偏序英关系卷。对穿于偏千序关小系来阻说，肥如果率有构且x≤y，则谎按不焰同情类况称肾它是吴“x小于更或等维于y”，怕“y包含x”，夫“x在y之前尾”等经等。81次序径关系20竹23持/5拘/1芳94.糟7特殊注关系设R是实缝数集闹合。和“小架于或绍等于味”关滔系≤垄是R中的逆偏序坐关系角；这痰个关袭系的颗逆关丹系“掠大于俘或等扔于”郊关系脊≥也潜是昆中的损偏序篮关系市。设勾是A的幂鹿集，宰亦即X是A的子皮集的首集和晶。X中的终包含热关系升，是奋个偏扛序关衡系；呀这个哥关系厕的逆锈关系消也是沫个偏测序关耕系。设远是正训整数达集合闲，且,当且妨仅当恢存在z，能梳使阔，才滚有“x整除y”(可写踩成x|笼y)，换恰言之网，“y是x的整杯倍数拾”。础“整元除”苗和“估整倍拢数”址互为岩逆关穿系，柿它们潜都是惨中铃的偏慎序关拢系。82次序雷关系20阶23弹/5惯/1扣94.失7特殊偿关系例4.蒜30设充，以≤是舅中军的“嫂整除奋”关财系。蓝试表有达出表“整广除”郑和“剥整倍蒜数”钩关系放。解：牺“整呢除”招关系专≤可骨规定辣成≤“整棚倍数秩”关但系是梢≥≥实数尊集合R中的千“小均于“钻关系<和“搅大于疑”关墨系>，都劝不是刘偏序肉关系偶，因蠢为它讽们都递不是道自反伟的。融但它某们是毛实数站集合蝇中的两另一仗种关规系——拟序洗关系。83次序城关系20井23斩/5易/1推94.德7特殊臣关系定义4.你25设R是集牲合A中的灾二元窄关系泰。如退果R是反深自反雷的和棚可传允递的至，亦贫即有（1）（2）则称R是拟序冷关系，并遍借用桂符号企“<”表浸示纪。在上谈述定凯义中渐，没继有明首确列沉举反倦对称核性的探条件胞，事附实上喘关系<若是纱反自犬反的果和可污传递枯的，颈则一咬定是棵反对潮称的梯，否百则会身出现草矛盾懒。这衡是因更为，壶假定x<司y和y<唯x，因再为<是可揉传递鸡的，肥可得菊出y<恐x，而<是反航自反耕的，索故<总是挪反对添称的蜂。根据蒙偏序爱关系贩和逆可序关版系的泽定义摄，不耍难得泛出实数报集合尘中的载小于赵关系<和大挑于关沿系>都是杯拟序贷关系脆。子势集的符集合辩中的资真包赞含关恋系树和兽都是驼拟序奇关系摸。84次序台关系20梨23抓/5钱/1始94.旨7特殊亮关系定理4.赤22设R是集租合A上的霸二元夜关系阁。于职是可稿有（1）如条果R是个酸拟序芦关系亮，则爸是荒一个拆偏序赌关系宇。（2）如跑果R是个删偏序下关系备，则脉是个孔拟序寄关系逗。定理4.电23设<柏A,≤>是个紫偏序边集合叼。如默果对汤于每疫一个菜，或纯者恋或者寇，妹亦即则称末偏序讨关系莫≤是全序托关系简称全序，序秧偶<饶A,≤>称为全序轨集合。A中具令有全腾序关堡系的蜜各元冻素，宅总能所按线策性次送序但排列仅起来买，这最里当逃且仅位当i≤j，才医有蕉≤,故全粉序也军称为简单渴序或线性宾序，因号此，碍序偶<喊A,≤>在这耀种情擦况下锡也被丙称为线性露序集或链。85次序反关系20阀23荐/5辜/1积94.外7特殊拉关系设≤惑是集著合P中的场偏序给关系奥。对码于拨，群如果活有x≤y或y≤x,则A中的宝元素x和y称为可比剧的。在达偏序鼻集合赞中，疫并非屿任何屠两个画元素x和y都存柄在有x≤y或y≤x的关扔系。接事实礼上，拿对于扩某些x和y来说卫，x和y可能贸没有井关系筑。在草这种拣情况壳下，胁称x和y是不可持比的。正竞是由情于这剂种原理因，太才把胃≤称痰作“躬偏”之序关猪系。臭在全共序集帜合中息，任庭何两字个元怎素都妙是可伟比的蜡。设R是实歇数集锋合，a和b是R的元遇素。绝对于抵每一床个实愚数a，设纳和S是集敏合并劝且渣≥0妇}。如循果a<币b，则探，板因此皂是一球个全傻序集戒合。克如果A是个绞含有庄多于顶一个特元素豪的集母和，诉则瞒不是舍一个僻全序狠集合浮。例堂如，淋设伍，次于是86次序凶关系20兆23踢/5服/1戏94.钩7特殊阶关系设R是实疾数集企合且目。咬假定R上的军关系沉是耕一般昌的“树大于阴或等予于”销关系薄。对佣于P中的做任何误两个列序偶续和籍，脏可以伏定义间一个略关系S如果功，冻则有,因此S是P中的岂全序企关系共。并扩称它蚂是字母泛次序危关系或字母吊序。例协如，跳试考泡察下淹列序剑偶可以桶看出筝，这困些序皆偶之删间有赖字母获次序拍关系闸。87次序锦关系20详23演/5屿/1肺94.谈7特殊辞关系定义4.滥26设<A渐,≤>是一玩个偏纽奉序集缘瑞，如闲果对兔任何汽，x≤y和滨，而扒且不衰存在侄任何锯其他立元素昆能优使x≤z和z≤y，即(永x≤满≤z≤浇成立俯，则画称元这素y盖覆x。在哈秆斯图坟中，页用小护圈表浆示每社个元翅素。需如果另有观，且x≤y和杜，则喊把表穿示x的小市圈画急在表蹄示y的小若圈之召下。振如果y盖覆x，则蚁在x和y之间羞画上借一条勉直线迹。如提果x≤y和剂，岔但是y不盖圾覆x，则巴不能昂把x和y直接热用直页线联父结起接来，砍而是蚊要经劈燕过A的一示个或祸多个疯元素墙把它丸们联济结起交来。叶这样择，所尺有的膊边的哑方向扒都是存自下敏朝上农，故熟可略悉去边撑上的项全部铅箭头去表示像。88偏序朽集20牧23鲜/5督/1店94.思7特殊昆关系例4.最32设集害合罪，≤众是X上的奴偏序驴关系刊。并堆定义侮成：述如果x整除y，则x≤y。试步画<摇X韵,≤>的哈幕斯图窜。解：毒在图4.跳19给出中了整颗除关生系的敏哈斯档图。例4.对33设集帮合扑，笑是它垂的幂痛集。著的元牧素间狭的偏简序关掌系≤盾是包宗含关捞系支。书试画宏出薯≤>的哈姐斯图昆。解：烂在图4.械19中给期出了郊≤房诚的奔哈斯讲图89哈斯抬图图4.课19整除胖关系哪的哈她斯图图4.批2020宪23有/5塌/1乳94.兼7特殊涂关系定义4.岩27设<P袭,≤>是一事个偏太序集猫合，森并有考，（1）若终成立地，则孝称元组素y为Q的最小专元，通斧常记冒作0。（2）若桃成立辽，则欣称元闻素y称为Q的最大保元，通绵常记佣作1。（3）若笔成立灶，则跃称元变素y称为Q的极小释元。（4）若席成立吹，则捞称元朋素y称为Q的极大渐元。定理4.恼24设X是一吼个偏衬序集衬合，教且有腊。崇如果x和y都是Q的最轻小(最大)元,则9020树23档/5秒/1东94.养7特殊应关系定义4.卸28设<P捞,≤>是个慨偏序医集合成，且影有分，瓜。（1）若座≤y