離散數(shù)學(xué)課件：關(guān)系的運(yùn)算

05:3711離散數(shù)學(xué)

(DiscreteMathematics)05:372關(guān)系的集合運(yùn)算關(guān)系的復(fù)合小結(jié)4.4關(guān)系的復(fù)合05:373一、關(guān)系的集合運(yùn)算解4.4關(guān)系的復(fù)合例1

設(shè)A={1,2,3}，求R∪S，R∩S，R-S，，定理4.4.1

若R與S都是集合A到集合B的關(guān)系，則R∪S，R∩S，R-S，，均為A到B的關(guān)系。05:374二、關(guān)系的復(fù)合4.4關(guān)系的復(fù)合1.復(fù)合關(guān)系的定義定義4.4.1

設(shè)R是由A到B的關(guān)系，S是由B到C的關(guān)系，則稱為R和S的復(fù)合關(guān)系，是一個(gè)由A到C的關(guān)系，表示為：這種由R和S求復(fù)合關(guān)系的運(yùn)算稱為關(guān)系的復(fù)合運(yùn)算。05:375于是復(fù)合關(guān)系例2

設(shè)R是由A={1,2,3,4}到B={2,3,4}的關(guān)系，S是由B到C={3,5,6}的關(guān)系，分別定義為：4.4關(guān)系的復(fù)合123653234R4SBAC05:376例3

設(shè)A是所有人的集合，于是復(fù)合關(guān)系4.4關(guān)系的復(fù)合05:377定理4.4.2

設(shè)集合A={a1,a2,am}，B={b1,b2,bp}，C={c1,c2,cn}，R是由A到B的關(guān)系，S是由B到C的關(guān)系，MR=(uij)mp，MS=(vij)pn

，則MR?S=MR?MS=(wij)mn，這里2.復(fù)合關(guān)系的關(guān)系矩陣4.4關(guān)系的復(fù)合其中的加法和乘法分別為布爾加和布爾乘。05:3784.4關(guān)系的復(fù)合例4

設(shè)A={1,2,3,4}，B={a,b,c}，C={e,f,g}.A到B的關(guān)系B到C的關(guān)系則abcfegfeg05:3794.4關(guān)系的復(fù)合例5

設(shè)A={1,2,3,4}，B={2,3,4}，C={1,2,3}.A到B的關(guān)系B到C的關(guān)系則23421321305:3710定理4.4.3

設(shè)R是由集合A到B的關(guān)系，則例如

設(shè)R是由A={1,2,3,4}到B={2,3,4}的關(guān)系，從關(guān)系圖，可知：3.復(fù)合關(guān)系的性質(zhì)4.4關(guān)系的復(fù)合123432234R4IABAB1234AIB05:3711

定理4.4.4

設(shè)R是由A到B的關(guān)系，S是由B到C的關(guān)系，則有(1)(2)(3)4.4關(guān)系的復(fù)合05:3712

復(fù)合關(guān)系的性質(zhì)：4.4關(guān)系的復(fù)合(1)結(jié)合律：若，，，則05:3713

復(fù)合關(guān)系的性質(zhì)：4.4關(guān)系的復(fù)合(1)結(jié)合律：若，，，則(2)若，，05:3714

復(fù)合關(guān)系的性質(zhì)：4.4關(guān)系的復(fù)合(1)結(jié)合律：若，，，則(2)若，，05:3715則A到C的關(guān)系因此因此所以例6

設(shè)A={1,2,3,4}，B={2,3,4}，C={1,2,3}，D={4,5,6}.A到B的關(guān)系B到C的關(guān)系C到D的關(guān)系4.4關(guān)系的復(fù)合05:3716一般地，若R1是一由A1到A2的關(guān)系，R2是由A2到A3的關(guān)系，…，Rn是一由An到An+1的關(guān)系，則不加括號(hào)的表達(dá)式，唯一地表示一由A1到An+1的關(guān)系，在計(jì)算這一關(guān)系時(shí)，可以運(yùn)用結(jié)合律將其中任意兩個(gè)相鄰的關(guān)系先結(jié)合。4.4關(guān)系的復(fù)合特別地，當(dāng)A1=A2=

=An+1，R1=R2=

=Rn=R時(shí)，復(fù)合關(guān)系R?R?

?R簡(jiǎn)記作Rn，它也是集A上的一個(gè)關(guān)系。05:3717三、小結(jié)4.4關(guān)系的復(fù)合本節(jié)主要介紹了復(fù)合關(guān)系的運(yùn)算與性質(zhì)。重點(diǎn)掌握復(fù)合關(guān)系的運(yùn)算及其性質(zhì)。05:371818離散數(shù)學(xué)

(DiscreteMathematics)05:3719逆關(guān)系的定義逆關(guān)系的性質(zhì)小結(jié)4.5逆關(guān)系05:37204.5逆關(guān)系一.逆關(guān)系的定義定義4.5.1

設(shè)A、B是任意集合，R是由A到B的關(guān)系，由B到A的關(guān)系稱為關(guān)系R的逆關(guān)系。

RC是由B到A的關(guān)系。RC的關(guān)系矩陣：RC的關(guān)系圖：R的關(guān)系圖中所有有向弧線全部反向。05:3721于是解例1

設(shè)A={2,3,5}，B={4,6,10}，定義由A到B的關(guān)系D如下：當(dāng)且僅當(dāng)a整除b時(shí)，有aDb，試求D的逆關(guān)系DC。4.5逆關(guān)系由D的定義知05:3722定理4.4.6

設(shè)A、B是任意集合，R1、R2和R都是由A到B的關(guān)系，則有二.逆關(guān)系的性質(zhì)4.5逆關(guān)系(1)(2)(3)(4)(5)(6)(7)05:3723(8)令R是由A到B的關(guān)系，S是B到C的關(guān)系，則4.5逆關(guān)系證因?yàn)樗?5:37244.5逆關(guān)系(9)設(shè)R是集合A上的二元關(guān)系，則(1)R是對(duì)稱的，當(dāng)且僅當(dāng)R=RC。(2)R是反對(duì)稱的，當(dāng)且僅當(dāng)RRCIA.證(1)已知R對(duì)稱，則對(duì)任意的a,bA，同理反之，已知所以對(duì)任意的a,bA，設(shè)設(shè)，因?yàn)镽對(duì)稱則所以，因此R=RCR=RC因?yàn)镽=RC所以，因此R對(duì)稱。05:37254.5逆關(guān)系(9)設(shè)R是集合A上的二元關(guān)系，則(1)R是對(duì)稱的，當(dāng)且僅當(dāng)R=RC。(2)R是反對(duì)稱的，當(dāng)且僅當(dāng)RRCIA.證(2)設(shè)R反對(duì)稱，則對(duì)任意的a,bA，所以反之，當(dāng)RRCIA。所以，R是反對(duì)稱的。對(duì)任意的a,bA，設(shè)05:3726三、小結(jié)4.5逆關(guān)系本節(jié)主要介紹了逆運(yùn)算的定義與性質(zhì)。重點(diǎn)掌握逆關(guān)系的應(yīng)用、性質(zhì)及其性質(zhì)的證明方法。05:372727離散數(shù)學(xué)

(DiscreteMathematics)05:3728關(guān)系的閉包的概念關(guān)系的閉包的性質(zhì)關(guān)系的閉包的求法小結(jié)4.6關(guān)系的閉包運(yùn)算05:3729例1

設(shè)R是由A上的關(guān)系，A={1,2,3}，(1)求一個(gè)A上的關(guān)系R’，使得R

R’，且R’是自反的。(2)這樣的關(guān)系共有多少個(gè)?4.6關(guān)系的閉包運(yùn)算解(1)舉例：(2)一、

關(guān)系的閉包的概念05:37304.6關(guān)系的閉包運(yùn)算定義4.6.1

設(shè)R、是集合A上的關(guān)系，如果滿足：(1)是自反的(對(duì)稱的/可傳遞的)(2)(3)對(duì)任何自反的(對(duì)稱的/可傳遞的)的關(guān)系，若，則。稱

為R的自反(對(duì)稱/傳遞)閉包。R的自反閉包、對(duì)稱閉包、傳遞閉包分別記作05:3731說明:求集合A上的關(guān)系的自反、對(duì)稱、傳遞閉包的運(yùn)算，稱為關(guān)系的閉包運(yùn)算。R的自反(對(duì)稱、傳遞)閉包是包含R的具有自反(對(duì)稱/可傳遞)性質(zhì)的最小關(guān)系。4.6關(guān)系的閉包運(yùn)算05:37324.6關(guān)系的閉包運(yùn)算二、

關(guān)系的閉包的性質(zhì)定理4.6.1

設(shè)R是集合A上的二元關(guān)系，則(1)R是自反的

r(R)=R(2)R是對(duì)稱的

s(R)=RR是可傳遞的

t(R)=R證明略05:37334.6關(guān)系的閉包運(yùn)算三、

關(guān)系的閉包的求法定理4.6.2

設(shè)R是集合A上的二元關(guān)系，則(1)1.利用定義求閉包(2)(3)(通常，將記作R+，所以t(R)=R+)05:37344.6關(guān)系的閉包運(yùn)算三、

關(guān)系的閉包的求法定理4.6.2

設(shè)R是集合A上的二元關(guān)系，則(1)1.利用定義求閉包證明(3)分兩部分證明。(2)(3)(a)先證，用數(shù)學(xué)歸納法。(通常，將記作R+，所以t(R)=R+)05:37354.6關(guān)系的閉包運(yùn)算①由傳遞閉包的定義，立即有Rt(R).②假設(shè)Rnt(R)，n1。設(shè)，由①及②，有再由t(R)的傳遞性，有所以故所以05:37364.6關(guān)系的閉包運(yùn)算首先證明(a)再證。設(shè)則必存在整數(shù)s和t，s1，t1，使得因此，所以因?yàn)榘琑的傳遞關(guān)系都包含t(R)，故由(a)和(b)，得。而05:3737例2

設(shè)A={a,b,c}，R是集合A上的關(guān)系，解求r(R)、s(R)、t(R)。4.6關(guān)系的閉包運(yùn)算05:3738定理4.6.3

設(shè)R是集合A上的二元關(guān)系，A為含有n個(gè)元素的集合，則存在某個(gè)正整數(shù)kn，使得因此，我們有4.6關(guān)系的閉包運(yùn)算05:37394.6關(guān)系的閉包運(yùn)算2.利用關(guān)系矩陣求閉包例3

設(shè)A={a,b,c}，R是集合A上的關(guān)系，求r(R)、s(R)、t(R)。解abcabc05:37404.6關(guān)系的閉包運(yùn)算abc因?yàn)樗杂谑且驗(yàn)樗杂谑?5:37414.6關(guān)系的閉包運(yùn)算因?yàn)閨A|=3，所以于是而所以故05:37424.6關(guān)系的閉包運(yùn)算3.利用Warshall求傳遞閉包的關(guān)系矩陣算法如下：(1)置新矩陣N:=MR(2)置i:=1(3)對(duì)所有j，如果N[j,i]=1，則對(duì)k=1,2,,nN[j,k]:=N[j,k]+N[i,k](4)i加1

(5)如果i

n，則轉(zhuǎn)(3)，否則停止。

05:37434.6關(guān)系的閉包運(yùn)算例4

設(shè)A={1,2,3}，R是集合A上的關(guān)系，求t(R)。解i=105:37444.6關(guān)系的閉包運(yùn)算i=2i=3求t(R)。例4

設(shè)A={1,2,3}，R是集合A上的關(guān)系，解i=4時(shí)，N的第4列全為0，所以矩陣不變。故05:3745整數(shù)集合上的以下關(guān)系的自反，對(duì)稱，傳遞閉包是什么？小于小于等于