主講教師：常亮E-mail:changl@QQ：737059669辦公室電話:2291071手機(jī)導(dǎo)教師：周小川答疑時(shí)間：星期四上午10:20-11:50答疑地點(diǎn)：5教5樓軟件工程教研室離散數(shù)學(xué)2.3關(guān)系的運(yùn)算基本運(yùn)算交、并、補(bǔ)、差、對稱差運(yùn)算復(fù)合運(yùn)算逆運(yùn)算冪運(yùn)算閉包運(yùn)算復(fù)合運(yùn)算的矩陣實(shí)現(xiàn)令A(yù)、B、C為有限集合，R是A到B的關(guān)系，S是B到C的關(guān)系，MR和MS分別為R和S的關(guān)系矩陣。則，R

S的關(guān)系矩陣為MR

S=MR

MS。關(guān)系矩陣乘法:按照傳統(tǒng)矩陣乘法進(jìn)行運(yùn)算，得到初步結(jié)果；將大于等于1的地方修改為1。復(fù)合運(yùn)算的性質(zhì)定理2.3給定任意集合A、B、C和D，設(shè)R、S和T分別是集合A到B、B到C和C到D的關(guān)系，那么(R?S)?T=R?(S?T)。

復(fù)合運(yùn)算滿足結(jié)合律！復(fù)合運(yùn)算的性質(zhì)定理2.4對于任意集合A、B、C和D，設(shè)R,S1,S2和T分別是A到B,B到C,B到C和C到D的關(guān)系。那么：①R?(S1

S2)=(R?S1)

(R?S2)②R?(S1

S2)

(R?S1)

(R?S2)③(S1

S2)?T=(S1?T)

(S2?T)④(S1

S2)?T

(S1?T)

(S2?T)復(fù)合對并運(yùn)算滿足分配律！復(fù)合對交運(yùn)算不滿足分配律！關(guān)系的運(yùn)算-逆運(yùn)算定義2.16設(shè)R是從集合A到集合B的關(guān)系，則R的逆為集合B到集合A的關(guān)系，并且R-1={<x,y>|<y,x>

R}。例2.34設(shè)R={<1,a>,<2,c>,<3,b>,<4,b>,<4,d>}，S={<a,2>,<b,4>,<c,3>,<c,5>,<d,5>}①計(jì)算R-1、S-1、(R-1)-1、(S-1)-1、(R?S)-1和S-1?R-1；解①根據(jù)逆運(yùn)算和復(fù)合運(yùn)算的定義，有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>}逆運(yùn)算的性質(zhì)定理2.5對于任意集合A和B，設(shè)R是集合A到B的關(guān)系，則有：

(R-1)-1

=R。

逆運(yùn)算的性質(zhì)定理2.6對于任意集合A、B和C，設(shè)R和S分別是集合A到B和集合B到C的關(guān)系，那么

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

逆運(yùn)算的性質(zhì)定理2.7對于任意集合A、B和C，設(shè)R和S分別是集合A到B和集合B到C的關(guān)系，那么：①(R

S)-1

=R-1

S-1②(R

S)-1

=R-1

S-1③(R

S)-1

=R-1

S-1④(

R)-1

=

(R-1)⑤(A

B)-1=B

A⑥R-1

S-1當(dāng)且僅當(dāng)R

S

自反性反自反性對稱性反對稱性傳遞性定義對于所有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關(guān)系矩陣主對角線上全為1主對角線上全為0對稱陣反對稱陣(當(dāng)i

j時(shí)rij和rji不能同時(shí)為1)如果rik=1并且rkj=1，則rij=1關(guān)系圖圖中每個(gè)結(jié)點(diǎn)都有環(huán)圖中每個(gè)結(jié)點(diǎn)都無環(huán)任意兩個(gè)不同的結(jié)點(diǎn)間要么沒有弧，要么有方向相反的一對弧。任意兩個(gè)結(jié)點(diǎn)間至多有一條弧若a到b有弧，b到c有弧，則a到c有弧集合IARR∩IA=

R=R-1R∩R-1

IAR?R

R對關(guān)系性質(zhì)的判斷冪運(yùn)算定義2.17設(shè)R是一個(gè)集合A上的關(guān)系，n為自然數(shù)，則關(guān)系R的n次冪定義為：R0={<x,x>|x

A}=IA

Rn+1=Rn?R例2.35設(shè)集合A={a,b,c,d}上的關(guān)系R={<a,b>,<b,a>,<b,c>,<c,d>}用關(guān)系矩陣法求R的各次冪。解：R0的關(guān)系矩陣為：R的關(guān)系矩陣為:R2的關(guān)系矩陣為：例冪運(yùn)算的性質(zhì)定理2.9設(shè)R是集合A上的關(guān)系，m和n為自然數(shù)，那么

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

③R-n=(R-1)n冪運(yùn)算的性質(zhì)定理2.8定理2.10(略)如果R是一個(gè)有限集合上的關(guān)系，則R0、R1、R2、R3、R4、R5、R6…是一個(gè)周期變化的序列。例2.36設(shè)集合A={a,b,d,e,f}上的關(guān)系R={<a,b>,<b,a>,<d,e>,<e,f>,<f,d>}求出最小的自然數(shù)s和t（s

t）使得Rs=Rt。

解：關(guān)系R的關(guān)系矩陣為那么，R2、R3、R4、