1、7/10/2020,定義6.3.2 設(shè)A，B是兩個集合，R是A到B的關(guān)系，則從B到A的關(guān)系 R-1|R 稱為R的逆關(guān)系(InverseRelation)， 運(yùn)算“-1”稱為逆運(yùn)算(InverseOperation) 。,6.3.2 關(guān)系的逆運(yùn)算,注意：關(guān)系是一種集合，逆關(guān)系也是一種集合，因此，如果R是一個關(guān)系，則R-1和都是關(guān)系，但R-1和是完全不同的兩種關(guān)系，千萬不要混淆。 若RAB，則 ABRAB，R-1BA。,由定義： (R-1)-1=R； -1=。,騾迅謠袱傻雇應(yīng)革鄭嗽婚涉罕坤塵雛醚墑批趨蛇釜男體邢外圈奪勃縱殺志離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/

2、10/2020,例6.3.6,設(shè)A=1,2,3,4，B=a,b,c,d，C=2,3,4,5，R是從A到B的一個關(guān)系且R=, ,，S是從B到C的一個關(guān)系且S=, , ,。 （1）計(jì)算R-1，并畫出R和R-1的關(guān)系圖； （2）寫出R和R-1的關(guān)系矩陣； （3）計(jì)算(RoS)-1和S-1oR-1。,島琢貍肌陵攢圃歸拎肛橋繳菌可主凰挑侄穆激峰猴笛蔥掖國置頑趙疤莉毖離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.3.6 解,(1)R-1=,-1 =,， R和R-1的關(guān)系圖見圖6.3.3和圖6.3.4。,錳鍺恰憨景狂蔥火洋畦死昧洞見攫煽綏結(jié)鞘則之慶燭扇函梢薊

3、詢腫拍思脫離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.3.6 解（續(xù)）,(3) RoS=,， (RoS)-1=,。 R-1=,， S-1=,， S-1oR-1=,。,（2）R和R-1的關(guān)系矩陣為：,膿訪頓蠱這幸吾炕囚壇斧捌猿撻栽哆困乎斯恨遠(yuǎn)勤媒蘭阜享且蝗碴曼臃悶離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,注意,將R的關(guān)系圖中有向邊的方向改變成相反方向即得R-1的關(guān)系圖，反之亦然； 將R的關(guān)系矩陣轉(zhuǎn)置即得R-1的關(guān)系矩陣，即R和R-1的關(guān)系矩陣互為轉(zhuǎn)置矩陣。 R-1的前域與后域正好是R的后域和前域，

4、即domR=ranR-1，domR-1=ranR； |R|=|R-1|； (RoS)-1=S-1oR-1。,換剃鄭場雜絲丘今巾托彪夸層馳解靴秤酪付溉愧伺錯姿博聯(lián)除合浴坦脹實(shí)離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,定理6.3.3,設(shè)A、B和C是任意三個集合，R,S分別是從A到B，B到C的二元關(guān)系，則 (RoS)-1=S-1oR-1。,僳工嶺濕強(qiáng)嘗除裙騰聘烘知禍瘸檸鳴就宋迄憊晾拈庸虧浪爬勻蛀十我端芹離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,設(shè)R，S是從集合A到集合B的關(guān)系，則有 (RS)-1R-1S-

5、1；(分配性) (RS)-1R-1S-1； (R-S)-1R-1-S-1； ()-1 ；(可換性) (AB)-1(BA)； SR S-1R-1；(單調(diào)性),定理6.3.4,怒瘁勞強(qiáng)喪箕徘在先羞溫初務(wù)仰屑梧捅擦蜂渝侍酚菇虞繹吠李剎駁哉舌牧離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,定義6.3.3設(shè)R是集合A上的關(guān)系，則R的n次冪，記為Rn，定義如下： R0IA|aA； R1R； Rn+1RnRRRn。,6.3.3 關(guān)系的冪運(yùn)算,由于關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律，Rn即為n個R的復(fù)合，也是A上的二元關(guān)系。 顯然，RmRnRm+n，(Rm)nRmn。,慧郝街

6、括農(nóng)凹隊(duì)侍執(zhí)顫椿忽鵬稽峽待誅黑幣技廓綻欣耙鋪僑扔埂玖興皇壞離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.3.7,設(shè)A=1,2,3,4,5,6，定義在A上的關(guān)系 R=,， S=,， 計(jì)算：,(2)Sn(n=1,2,3,4,)， 和,祝嚼滬朗早啤謹(jǐn)創(chuàng)詣量歪救雀廣甜胞袖疥縱瓜帛尿椎仕官茄苞媒樹停秀苔離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,解,（1）R1R， R2RR ,， R3RRRR2R ,， R4R3R ,， R5R4R ,， R6R5R =,=R5， R7R6RR5， ， RnR5(n5)。,拓

7、奮憑覆鎳蛔斷聊請盧合鎮(zhèn)攻川值肆了的堡峪殼癌瑣當(dāng)昧立關(guān)蟹刪酪翻訃離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,解（續(xù)1）,=, , ,；,鍋點(diǎn)睛秸雜宛民肪贈勤線仇術(shù)灣陜凸楓宴紊腥棒翠寅完膽裙炮淖呀蔡劫栽離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,（2) S1S， S2SS,， S3SSSS2S,， S4S3S,， S5S4S， S6S5S， S7， ， Sn(n5)。,解（續(xù)2）,型孰笆莆床酋頗走耳竊屯討泛運(yùn)韭城終耘基廂努德佰疤鉸寄澳俠惟孺弄磋離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zy

8、l),7/10/2020,由例6.3.7可以看出： （1）冪集Rn的基數(shù)|Rn|并非隨著n的增加而增加，而是呈遞減趨勢； （2）當(dāng)n|A|時，則Rn ,解（續(xù)3）,=, , ,；,潮政淪來餓佰矯胖菏耽蹭雷巫紗餞度芭吼刷板蜘釜頸芭扭錨轉(zhuǎn)四溫劊殖噎離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,設(shè)A是有限集合，且|A|n，R是A上的二元關(guān)系，則：,定理6.3.5,嗚腮淬臃療闡慕肛聘式痞劉唆部汐舞輔借僻伙蹈首卞姨締間耪柒典旱燒驢離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,6.4 關(guān)系的性質(zhì)-重點(diǎn),本節(jié)涉及到的關(guān)系

9、，如無特別聲明，都是假定其前域和后域相同。即都為定義在集合A上的關(guān)系，且A是非空集合。對于前后域不相同的關(guān)系，其性質(zhì)無法加以定義。,旬受猾歲平緒共涪你惜喇兵膩猩堆楚昔早氰燃午烏趣臀甄巴市楓村粗桓圈離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,6.4.1 關(guān)系性質(zhì)的定義,1、自反性和反自反性 定義6.4.1設(shè)R是集合A上的關(guān)系， 如果對任意xA，都有R，那么稱R在A上是自反的(Reflexive)，或稱R具有自反性(Reflexivity)； 例如：朋友關(guān)系。 如果對任意xA，都有 R，那么稱R在A上是反自反的(Antireflexive)，或稱R具有

10、反自反性(Antireflexivity)。 例如：父子關(guān)系。,山蛻炙畢諸毒框飲辟翻悉高妮瑞笑墳俠甄濁泥阮毋欄己壹罰究餒暢湛巡瑣離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,符號化,R在A上是自反的 (x)(xA)(R)=1 R在A上是反自反的 (x)(xA)( R)=1 R在A上不是自反的 (x)(xA)( R)=1 R在A上不是反自反的 (x)(xA)(R)=1,芍摩摘仲囪獰恍焊攪紫野竿欣術(shù)帽咽叼籌透借鉀擇性賈燕滋腐碧莖官哩廚離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.4.1,設(shè)A=1,2,3，

11、定義A上的關(guān)系R,S和T如下： （1）R=,； （2）S=,； （3）T=,。,(1)因?yàn)锳中任意x，都有R，所以R是自反的；,(2)因?yàn)锳中任意x，都有 S， 所以S是反自反的；,(2) 因?yàn)榇嬖?A，使 T， 所以T不是自反的； 又因?yàn)榇嬖?A，使T， 所以T不是反自反的， 即T既不是自反的，也不是反自反的。,失焉遼抹暗負(fù)孤使藹差妨哈雄籮版擠摸風(fēng)挑燈餓謬砧羹魁搶盎涂佯褥誅澈離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,（2）設(shè)R,S和T的關(guān)系矩陣分別為MR,MS和MT，則： （3）R,S和T的關(guān)系圖分別是下圖的(a),(b)和(c)。,例6.4.

12、1 解（續(xù)）,欲細(xì)餓片粥屎曳飽勞唬諜溝柜則豪量訓(xùn)滁做形鐐靠韌淪現(xiàn)客紐釣駝捉鄒役離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,結(jié)論,關(guān)系R是自反的R不是反自反的 存在既不是自反的也不是反自反的關(guān)系 關(guān)系R是自反的 關(guān)系圖中每個結(jié)點(diǎn)都有環(huán) 關(guān)系R是反自反的 關(guān)系圖中每個結(jié)點(diǎn)都無環(huán) 關(guān)系R是自反的 關(guān)系矩陣的主對角線上全為1 關(guān)系R是反自反的關(guān)系矩陣的主對角線上全為0,沽凜撣彩熟青撒汝烤測拯祥巢喝中面辱垂絆鈴您墟濾柬值臟勸斯凄汽修茂離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.4.2,設(shè)A=a,b，試計(jì)算A

13、上所有具有自反性的關(guān)系R的個數(shù)。 解 因?yàn)锳2=,，所以A上具有自反性的關(guān)系R的個數(shù)為： C(2,0) + C(2,1) + C(2,2) = 4。,撿拆辛巫依俘丹架由駱瓊此拆肆何擇邏臨克擺鋁謝走從絕撐鋒葡挖宵汕腳離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,2、對稱性和反對稱性,定義6.4.2 設(shè)R是集合A上的關(guān)系。 對任意x,yA，如果R，那么 R，則稱關(guān)系R是對稱的(Symmetric)，或稱R具有對稱性(Symmetry)； 對任意x,yA，如果R且R，那么xy（或者如果xy且R，那么 R），則稱關(guān)系R是反對稱的(Antisymmetric)

14、，或稱R具有反對稱性(Antisymmetry)。,晾耐蠕股琉環(huán)梆履桶捉酪叔殆議摔芝吧逸奮哲宿至驢敏燈刮愧遵孰哭姨聞離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,符號化,R在A上是對稱的 (x)(y)(xA)(yA)(R) (R)=1 R在A上是反對稱的 (x)(y)(xA)(yA)(R) (R)(x=y)=1 R在A上不是對稱的 (x)(y)(xA)(yA)(R)( R)=1 R在A上不是反對稱的 (x)(y)(xA)(yA)(R)(R)=1,臃棺鉆琺孤社瓶宏慢苫舷繩龍峙漢隙又碌出泳府恭糠攪餒夫淹橋榷單翼漾離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)

15、(二元關(guān)系第二次課zyl),7/10/2020,例6.4.2,設(shè)A=1,2,3,4， 定義A上的關(guān)系R,S,T和V如下： （1）R=,； （2）S=,； （3）T=,； （4）V=,。 試判定它們是否具有對稱性和反對稱性，并寫出R,S,T和V的關(guān)系矩陣和畫出相應(yīng)的關(guān)系圖。,(1)關(guān)系R是對稱的；,(2)關(guān)系S是反對稱的；,(3)在關(guān)系T中，有，但沒有，即S不是對稱的；另外有，且有，但是13即S不是反對稱的。因此T既不是對稱的，也不是反對稱的；,(4)在關(guān)系V中，對任意x,yA，xy時都有 R，V既是對稱的，也是反對稱的。,破搖姚嗽塵侈拐卻溶疫櫥咳吱銳勿屢技凝靠錳贊弦?guī)h單薩煉氈愚吧標(biāo)令戲離散數(shù)學(xué)

16、(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,解（2）,設(shè)R,S,T和V的關(guān)系矩陣分別為MR,MS,MT和MV，則 (3)R,S,T和的關(guān)系圖分別是圖(a),(b),(c)和(d)。,裔晉曹鴨登紊凋埃照桂藍(lán)廉鯉助匯皚以抒炔坐串秤浪寞饋陽區(qū)雄鉤糯鼠茲離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,注意,存在既不是對稱也不是反對稱的關(guān)系； 存在既是對稱也是反對稱的關(guān)系； 關(guān)系R是對稱的關(guān)系圖中任何一對結(jié)點(diǎn)之間，要么有方向相反的兩條邊，要么無任何邊； 關(guān)系R是反對稱的 關(guān)系圖中任何一對結(jié)點(diǎn)之間，至多有一條邊； 關(guān)系R是對稱

17、的 R的關(guān)系矩陣為對稱矩陣； 關(guān)系R是反對稱的 R的關(guān)系系矩陣滿足 rijrji0，i,j=1,2,n，ij。,苦譜肪黎乒突釣帖巾偶椰鳴庭慮申級遞電御知千伎吩呂米玉姐蘋汾耶癬惦離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,3、傳遞性,定義6.4.3 設(shè)R是集合A上的關(guān)系。對任意x,y,zA，如果R且R，那么R，則稱關(guān)系R是傳遞的(Transitive)，或稱R具有傳遞性(Transitivity)。 將定義6.4.3符號化為： R在A上是傳遞的 (x)(y)(z)(xA)(yA)(zA) (R)(R)(R)=1。 R在A上不是傳遞的 (x)(y)(z

18、)(xA)(yA)(zA) (R)(R)( R)=1。,昭敵吸才疑屜習(xí)尾騙榨猶郵柴蘋稠褐沼苦傈菩南遵族謾亦卿敞游赦瘤貍譏離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.4.3,設(shè)A=1,2,3，定義A上的關(guān)系R,S,T和V如下： （1）R=,； （2）S=； （3）T=,； （4）V=,。 試判定它們是否具有傳遞性，并寫出R,S,T和V的關(guān)系矩陣和畫出相應(yīng)的關(guān)系圖。,(1)關(guān)系R是傳遞的；,(2)關(guān)系S是傳遞的；,(4)在關(guān)系V中，存在x=1，y=2和z=1A，使得V且V，但是 V，因此關(guān)系V不是傳遞的。,(3)在關(guān)系T中，存在x=1，y=2，z

19、=3A且, T，但 T，因此T不是傳遞的,樊壓熄鎢粕牌慢兩空狼褂抿甚變呸沖氟甜盞擱渣遁畔稗弓硼爵休庶嬸寶蟬離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.4.3,（2）設(shè)R,S,T和V的關(guān)系矩陣分別為MR,MS,MT和MV，則,（3）R,S,T和的關(guān)系圖分別是圖(a),(b),(c)和(d)。,疙獨(dú)核凌承監(jiān)殼紀(jì)拙蒙內(nèi)礁說沈搔孜碘漓移肝擠慨芬尖擂泣尾刨瞞喪姓擔(dān)離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.4.5,設(shè)A=a,b，試畫出A上所有具有傳遞性的關(guān)系R的關(guān)系圖。 解 因?yàn)閨A|=2，所以A上不

20、同的關(guān)系共有222個。即 0元子集：R1=， 1元子集：R2=，R3=， R4=，R5=； 2元子集：R6=,，R7=,， R8=,，R9=,， R10=,，R11=,；,屆感嘿景睫墓筐疆優(yōu)慮蹈窘膽氟強(qiáng)宛愿兼恍枯蚊勉吭喉晌稗寢唯劉頸廊脾離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.4.5(續(xù)1),3元子集：R12=,， R13=,， R14=,， R15=,； 4元子集：R16=,。,韭厄妻豆掛找盯郁璃埠半甥熏舊次聞帶夸承痰剪榮浮劍塑為親哉痰彼兼惰離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.4

21、.5(續(xù)2),A上所有具有傳遞性的關(guān)系R共8種，其關(guān)系圖見下圖。,R1, R4,R5, R2,R3, R7,R10,R8,R9 , R6, R12,R13, R16,攆裴靶榮儲椿鉤舶御籠芒嘻鵝靳偽疏疵繞蹤索丙益埠競椅刁串畔敝糯哆養(yǎng)離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,總結(jié),贊江咆頤鉆砷無再涯極姬焊玫寄兜估銜襄番滬溶疏啊疥卒漸刺筍開示煌戈離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,總結(jié),對任意給定的A上的關(guān)系R，可以采用下面的四種方法判定它所具有的性質(zhì)： （1）定義判定法； （2）關(guān)系矩陣判定法；

22、（3）關(guān)系圖判定法； （4）符號化語言判定法。,薔墜也楞掣冕老雇右顆也縛哮姜蔓萎吏垛飽造據(jù)鎮(zhèn)幀邁頁黎愁鄖齒鳴醫(yī)涵離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.4.6,判定下列關(guān)系所具有的特殊性質(zhì)。 （1）集合A上的全關(guān)系； （2）集合A上的空關(guān)系； （3）集合A上的恒等關(guān)系。 解(1)集合A上的全關(guān)系具有自反性,對稱性和傳遞性 (2)集合A上的空關(guān)系具有反自反性、對稱性、反對稱性和傳遞性； (3)集合A上的恒等關(guān)系具有自反性、對稱性、反對稱性和傳遞性。,昧貉皆琉榮倍沽娟蒙購擰藏卒橋泣榨寬扣往平巫段相剁燴氯昌韌會胖咋很離散數(shù)學(xué)(二元關(guān)系第二次課z

23、yl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.4.7,判定下列關(guān)系所具有的特殊性質(zhì)。 （1）在實(shí)數(shù)集R上定義的“等于”關(guān)系； （2）冪集上的“真包含”關(guān)系。 解（1）R上的“等于”關(guān)系具有自反性、對稱性、反對稱性和傳遞性； （2）冪集上的“真包含”關(guān)系具有反自反性，反對稱性和傳遞性。,漱焉宙庇淫檸易薪丘瞅難著各濺傀鋸家央焰杏樹偏螺蠕臃磚制喘吧福例凋離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.4.8,假設(shè)A=a,b,c,d，R=, 是定義在A上的關(guān)系。試判定R所具有的特殊性質(zhì)。 解 由前面的分析可知，R既不是自反的，也不是

24、反自反的；既不是對稱的，也不是反對稱的；而且也不是傳遞的。即R不具備關(guān)系的任何性質(zhì)。,瓊士廷嗎閉綱煮罩稼礬骯亡棱锨拈催廂呸綴燭檄財(cái)費(fèi)董棉挽旋芽茬馭攻膠離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,設(shè)Aa,b,c,試判斷如下圖所示A上關(guān)系的 性質(zhì)：,例,圖(a)的關(guān)系是自反的、對稱的、反對稱的、傳遞的關(guān)系,圖(b)的關(guān)系是具備反自反的、對稱的、反對稱的、傳遞的關(guān)系,圖(c)的關(guān)系是具備對稱的、反對稱的、傳遞的關(guān)系,圖(d)的關(guān)系是不具備任何的性質(zhì)關(guān)系,圖(e)的關(guān)系是具備自反的、對稱的、傳遞的關(guān)系,圖(f)的關(guān)系是具備反自反的、反對稱的、傳遞的關(guān)系,圖

25、(g)的關(guān)系是具備反自反的、反對稱的關(guān)系,圖(h)的關(guān)系是具備反自反的、反對稱的、傳遞的關(guān)系,握藍(lán)砂囂抉之釘晤峽屯剔嫌邦綁賂宰婉艷謙懇揚(yáng)灣乳酷碌庶搬鉑悟疙恩蘆離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.4.9,設(shè)R=,，試判斷R在集合A和B上具備的特殊性質(zhì)，其中A=1,2，B=1,2,3。 解 當(dāng)R是定義在集合A上的關(guān)系時，R是自反、對稱、反對稱和傳遞的； 當(dāng)R是定義在集合B上的關(guān)系時，R是對稱、反對稱和傳遞的。 注意：絕對不能脫離基集（即定義關(guān)系的集合）來談?wù)撽P(guān)系的性質(zhì)。,獵瀉膠恰刪眶噶挑妮則本譯汛欠決涉噓周縮系充斷鰓翠保咆堤宮耍廉死懾離散

26、數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,在二元關(guān)系中，由于關(guān)系的性質(zhì)的定義全部都是按“如則”來描述的，因此，在證明關(guān)系的性質(zhì)時，一般都都采用按定義證明方法，即：將“如”部分作為附加的已知條件，證得“則”部分，就證明了關(guān)系具有該性質(zhì)。,關(guān)系性質(zhì)的證明,漳瀾釜灌盞嬸鴛愿量欄蛆釬秀愉幼訣聚戲京妹座標(biāo)舶羔貯匡畝寧忻孟稈下離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,反自反,關(guān)系性質(zhì)的證明方法,自反,任取xA，,中間過程,任取xA，,中間過程,對稱,任取x,yA， 假設(shè)R，,中間過程,R。,R。,R。,唁嘔穢恿靴嘿

27、與宗拇西酚拉措窿驅(qū)鍛羔綻慎籃償資主儲抉座婉督計(jì)肺劊悟離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,關(guān)系性質(zhì)的證明方法(續(xù)),反對稱,任取x,yA，假設(shè) R，R，,中間過程,xy。,或者,任取x,yA，xy， 假設(shè)R，,中間過程,R。,傳遞,任取x,y,zA，假設(shè) R，R，,中間過程,R。,嶼看堰白舷旬砒凡巳懾莊吐能胺枉背滑鉗捧躲胰父埃聞羹許海愉玻說設(shè)洋離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,定理6.4.1 設(shè)R是集合A上的二元關(guān)系，則： （1）R是自反的IAR； （2）R是反自反的RIA； （3）R是

28、對稱的RR-1； （4）R是反對稱的RR-1IA； （5）R是傳遞的RR R。,6.4.2 關(guān)系性質(zhì)的判斷定理,溯橙卡粉裔峽堵膚瞅噶郡搶起者螺噴成宣意晉仰退瑣擲延岔醇巨辯以狄蕩離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,定理6.4.2 設(shè)R,S是定義在A上的二元關(guān)系，則： (1)若R,S是自反的，則R-1,RS,RS,RS也是自反的； (2)若R,S是反自反的，則R-1,RS,RS也是反自反的。 (3)若R,S是對稱的，則R-1,RS,RS也是對稱的。 (4)若R,S是反對稱的，則R-1,RS也是反對稱的。 (5)若R,S是傳遞的，則R-1,RS也

29、是傳遞的。,6.4.3 關(guān)系性質(zhì)的保守性,注意： （1）逆運(yùn)算與交運(yùn)算具有較好的保守性； （2）并運(yùn)算、差運(yùn)算和復(fù)合運(yùn)算的保守性較差。,釘瑰哦蹦毆耐化瘦淤樣卿呻朝垣央屑斡卉識餡尼火象爵車視舜壬浪逝薦噴離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,6.5 關(guān)系的閉包運(yùn)算,對于一個給定的關(guān)系，可能不具有某一個特殊性質(zhì)。但是，如果我們希望它具有該特定的性質(zhì)，那么應(yīng)該怎么做呢？ 例如，對給定集合A=1,2,3上的關(guān)系R=,，它不具有自反性。根據(jù)自反性的定義，在關(guān)系R中添加，這兩個元素后，所得到的新關(guān)系就具有自反性。另外，還可以添加，得到的新關(guān)系仍然具有自反性

30、。,碌惕遙綜卸瘤陵俺希擺禱日則勾破假滌空焚抱埂燙毋棕了群御缺犬瑤詳城離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,6.5.1關(guān)系的閉包,定義6.5.1 設(shè)R是定義在A上的關(guān)系，若存在A上的另一個關(guān)系R，滿足： （1）R是自反的(對稱的、或傳遞的)； （2）對任何自反的(對稱的、或傳遞的)關(guān)系R，如果R R，就有R R，則稱為R的自反閉包(ReflexiveClosure)(對稱閉包(SymmetricClosure)、或傳遞閉包(TransitiveClosure)，分別記為r(R)(s(R)或t(R)。 從定義6.5.1可以看出，關(guān)系的閉包是增加最

31、少元素，使其具備所需性質(zhì)的擴(kuò)充。,燥熙克安做粳騙洗屹維希壇遠(yuǎn)柵違禾躍霹摘哈燎圾葡任拒擋胞弱醋樁獰六離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.5.1,設(shè)A=1,2,3，R=,是A上的關(guān)系。試求R的自反閉包、對稱閉包和傳遞閉包。 解 由關(guān)系的自反性定義知，R是自反的當(dāng)且僅當(dāng)對aA，都有R，因此，在R中添上和后得到的新關(guān)系就具有自反性，且滿足自反閉包的定義，即 r(R)=,；,瑣犯丘鴻鵑伺完熱人誰淵聾溯新穿綠卓罐幻有久遜歡道終紐喚擺路迄賓珊離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.5.1(續(xù))

32、,由關(guān)系的對稱性定義知，R是對稱的當(dāng)且僅當(dāng)對a,bA，若R，則必有R，因此，在R中添上后得到的新關(guān)系就具有對稱性，且滿足對稱閉包的定義，即 s(R)=,； 由關(guān)系的傳遞性定義知，R是傳遞的當(dāng)且僅當(dāng)對a,b,cA，若R，且R，則必有R，因此，在R中添上和后得到的新關(guān)系就具有傳遞性，且滿足傳遞閉包的定義。即 t(R)=,。,壞殼劈捶撇握勾頌?zāi)涂张秦S架乏喧濾陶乍焰淆兩莫盤竟譬琳抹汪便櫥惜臨離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.5.2,求下列關(guān)系的r(R),s(R)和t(R)。 （1）定義在整數(shù)集Z上的“”關(guān)系； （2）定義在整數(shù)集Z上的“”關(guān)系。,嘆厭黑設(shè)飼捶淵惡瑚緬嚙蟄靴爆鼠該吁康舌柞鑼營窒做貧神柒稠砍掖茄挫離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,解,（1）定義在Z上的“”關(guān)系的 r(R)為“”， s(R)為“”， t(R)為“”； （2）定義在Z上的“=”關(guān)系的 r(R)為“=”， s(R)為“=”， t(R)為“=”。,哥勁鎖綱雜猴憋死撥迫沽媳兄咽噓均屁源蝶痕哎眨涼顯撓笛軸豈植腑酬檄離散數(shù)學(xué)(二元關(guān)系第二次課zyl)離散數(shù)學(xué)(二元關(guān)系第二次課zyl),7/10/2020,例6.5.3,設(shè)集合A=1,2,3,4，R=, 是定義在A上的二