離散數學關系的運算第一頁，共二十六頁，編輯于2023年，星期日2.3關系的運算基本運算交、并、補、差、對稱差運算復合運算逆運算冪運算閉包運算第二頁，共二十六頁，編輯于2023年，星期日復合運算的矩陣實現令A、B、C為有限集合，R是A到B的關系，S是B到C的關系，MR和MS分別為R和S的關系矩陣。則，RS的關系矩陣為MRS=MRMS。關系矩陣乘法:按照傳統矩陣乘法進行運算，得到初步結果；將大于等于1的地方修改為1。第三頁，共二十六頁，編輯于2023年，星期日復合運算的性質定理2.3給定任意集合A、B、C和D，設R、S和T分別是集合A到B、B到C和C到D的關系，那么(R?S)?T=R?(S?T)。

復合運算滿足結合律！第四頁，共二十六頁，編輯于2023年，星期日復合運算的性質定理2.4對于任意集合A、B、C和D，設R,S1,S2和T分別是A到B,B到C,B到C和C到D的關系。那么：①R?(S1S2)=(R?S1)(R?S2)②R?(S1S2)(R?S1)(R?S2)③(S1S2)?T=(S1?T)(S2?T)④(S1S2)?T(S1?T)(S2?T)復合對并運算滿足分配律！復合對交運算不滿足分配律！第五頁，共二十六頁，編輯于2023年，星期日關系的運算-逆運算定義2.16設R是從集合A到集合B的關系，則R的逆為集合B到集合A的關系，并且R-1={<x,y>|<y,x>R}。第六頁，共二十六頁，編輯于2023年，星期日例2.34設R={<1,a>,<2,c>,<3,b>,<4,b>,<4,d>}，S={<a,2>,<b,4>,<c,3>,<c,5>,<d,5>}①計算R-1、S-1、(R-1)-1、(S-1)-1、(R?S)-1和S-1?R-1；解①根據逆運算和復合運算的定義，有R-1={<a,1>,<c,2>,<b,3>,<b,4>,<d,4>}S-1={<2,a>,<4,b>,<3,c>,<5,c>,<5,d>}(R-1)-1={<1,a>,<2,c>,<3,b>,<4,b>,<4,d>}(S-1)-1={<a,2>,<b,4>,<c,3>,<c,5>,<d,5>}R?S={<1,2>,<2,3>,<2,5>,<3,4>,<4,4>,<4,5>}(R?S)-1={<2,1>,<3,2>,<5,2>,<4,3>,<4,4>,<5,4>}S-1?R-1={<2,1>,<3,2>,<5,2>,<4,3>,<4,4>,<5,4>}第七頁，共二十六頁，編輯于2023年，星期日逆運算的性質定理2.5對于任意集合A和B，設R是集合A到B的關系，則有：

(R-1)-1

=R。

第八頁，共二十六頁，編輯于2023年，星期日逆運算的性質定理2.6對于任意集合A、B和C，設R和S分別是集合A到B和集合B到C的關系，那么

(R?S)-1=S-1?R-1。

第九頁，共二十六頁，編輯于2023年，星期日逆運算的性質定理2.7對于任意集合A、B和C，設R和S分別是集合A到B和集合B到C的關系，那么：①(RS)-1

=R-1

S-1②(RS)-1

=R-1

S-1③(RS)-1

=R-1S-1④(R)-1

=(R-1)⑤(AB)-1=BA⑥R-1

S-1當且僅當R

S

第十頁，共二十六頁，編輯于2023年，星期日自反性反自反性對稱性反對稱性傳遞性定義對于所有aA都有<a,a>R對于所有aA都有<a,a>R若<a,b>R,則有<b,a>R若<a,b>R并且<b,a>R,則有a=b若<a,b>R并且<b,c>R,則有<a,c>R關系矩陣主對角線上全為1主對角線上全為0對稱陣反對稱陣(當ij時rij和rji不能同時為1)如果rik=1并且rkj=1，則rij=1關系圖圖中每個結點都有環圖中每個結點都無環任意兩個不同的結點間要么沒有弧，要么有方向相反的一對弧。任意兩個結點間至多有一條弧若a到b有弧，b到c有弧，則a到c有弧集合IARR∩IA=R=R-1R∩R-1IAR?R

R對關系性質的判斷第十一頁，共二十六頁，編輯于2023年，星期日冪運算定義2.17設R是一個集合A上的關系，n為自然數，則關系R的n次冪定義為：R0={<x,x>|xA}=IA

Rn+1=Rn?R第十二頁，共二十六頁，編輯于2023年，星期日例2.35設集合A={a,b,c,d}上的關系R={<a,b>,<b,a>,<b,c>,<c,d>}用關系矩陣法求R的各次冪。解：R0的關系矩陣為：R的關系矩陣為:R2的關系矩陣為：第十三頁，共二十六頁，編輯于2023年，星期日例第十四頁，共二十六頁，編輯于2023年，星期日冪運算的性質定理2.9設R是集合A上的關系，m和n為自然數，那么

①Rm?Rn=Rm+n②(Rm)n=Rmn

③R-n=(R-1)n第十五頁，共二十六頁，編輯于2023年，星期日冪運算的性質定理2.8定理2.10(略)如果R是一個有限集合上的關系，則R0、R1、R2、R3、R4、R5、R6…是一個周期變化的序列。第十六頁，共二十六頁，編輯于2023年，星期日例2.36設集合A={a,b,d,e,f}上的關系R={<a,b>,<b,a>,<d,e>,<e,f>,<f,d>}求出最小的自然數s和t（st）使得Rs=Rt。

解：關系R的關系矩陣為那么，R2、R3、R4、R5、R6、R7…的關系矩陣分別為：第十七頁，共二十六頁，編輯于2023年，星期日例由此，s=0，t=6。第十八頁，共二十六頁，編輯于2023年，星期日關系的閉包運算問題：如果關系R不具有自反性（對稱性、傳遞性），那么給R增加盡可能少的有序對，使R具有這些性質。要求：①添加序偶后使得二元關系具有所希望的性質；②添加的序偶最少。第十九頁，共二十六頁，編輯于2023年，星期日關系的自反閉包定義2.18設R和R是集合A上的關系，如果滿足：（1）R是自反的；（2）RR；（3）對A上任何包含R的自反關系R都有RR。

則將R稱為R的自反閉包，記作r(R)。即，r(R)是包含R的最小的自反關系。例2.37求集合A={1,2,3}上的關系R={<1,1>,<1,2>,<2,1>,<1,3>}的自反閉包。第二十頁，共二十六頁，編輯于2023年，星期日關系的對稱閉包定義2.18設R和R是集合A上的關系，如果滿足：（1）R是對稱的；（2）RR；（3）對A上任何包含R的自反關系R都有RR。

則將R稱為R的對稱閉包，記作s(R)。即，s(R)是包含R的最小的對稱關系。例2.38求集合A={1,2,3}上的關系R={<1,1>,<1,2>,<2,1>,<1,3>}的對稱閉包。第二十一頁，共二十六頁，編輯于2023年，星期日關系的傳遞閉包定義2.18設R和R是集合A上的關系，如果滿足：（1）R是傳遞的；（2）RR；（3）對A上任何包含R的自反關系R都有RR。

則將R稱為R的傳遞閉包，記作t(R)。即，t(R)是包含R的最小的傳遞關系。例2.39求集合A={1,2,3}上的關系R={<1,1>,<1,2>,<2,1>,<1,3>}的傳遞閉包。第二十二頁，共二十六頁，編輯于2023年，星期日閉包運算的性質設R是非空集合A上的關系（即A并且RAA），則：(1)R是自反的當且僅當r(R)=R(2)R是對稱的當且僅當s(R)=R；(3)R是傳遞的當且僅當t(R)=R。

第二十三頁，共二十六頁，編輯于2023年，星期日基于關系圖求解閉包例2.40設集合A={1,2,3}上的關系R={<1,1>,<1,2>,<2,1>,<1,3>}，畫出關系R及其自反閉包、對稱閉包和傳遞閉包的關系圖。解:關系R及其自反閉包r(R)、對稱閉包s(R)和傳遞閉包t(R)的關系圖

求r(R)：對不含自環的頂點添加自環。求s(R)：如果兩個不同的結點之間只有一條邊，則在它們之間添加一條相反方向的邊。求t(R)：如果存在結點x指向y的一條邊，且存在y指向z的一條邊，但沒有x指向z的一條邊，則添加一條x指向z的邊；重復該過程，直到不再需要添加有向邊為止。123r(R)1

23R123s(R)123t(R)第二十四頁，共二十六頁，編輯于2023年，星期日閉包運算的性質定理2.11

設R是非空集合A上的關系（即A并且RAA），則：(1)r(R)=R∪IA(2)

s(R)=R∪R1(3)

t(R)=R∪R2∪R3∪…（注意：從R開始）(4)

如果|A|=n，則

t(R)=R∪R2∪…∪Rn

(5)

當A為有窮集合時，存在自然數k1使得

t(R)=R∪R2∪…∪Rk

用來