一、關(guān)系的基本概念及其性質(zhì)

1、關(guān)系的概念

二元關(guān)系：

　　定義：設(shè)A和B是兩個(gè)集合，A×B的任一子集R稱為從A到B的一個(gè)二元關(guān)系。

　　如果(a,b)∈R，則a與b符合關(guān)系R，記為aRb；

　　?如果(a,b) R，則a與b不符合關(guān)系R，記為aRb。

　　如果A=B，則稱R為A上的二元關(guān)系。

　　性質(zhì)：?若|A|=m，|B|=n，則|A×B|=m×n，A×B共有2m×n個(gè)子集，所以從A到B的二元關(guān)系共有2m×n個(gè)。

　　A×B也是從A到B的二元關(guān)系（全域關(guān)系）。

　　A×A上的任意子集都是A上的一個(gè)關(guān)系

　　若|A|=n，則A上的關(guān)系有2n2個(gè)

　　空集Φ稱為從A到B的空關(guān)系。

?　　集合{(a,a)|a∈A}稱為A上的恒等關(guān)系或相等關(guān)系，記為IA。

　　全域關(guān)系：EA=A×A

?　　RC=A×A-R

　　序?qū)Γ╝,b）=(c,d)的充要條件是a=c,b=d

　　定義：設(shè)二元關(guān)系R?A×B，集合{x|x∈A且?y∈B使(x,y)∈R}稱為R的定義域，并記為dom(R)；集合{y|y∈B且 ?x∈A使(x,y)∈R}稱為R的值域，并記為ran(R)。

　　一般地，dom(R)?A，ran(R)?B。

n元關(guān)系：

　　定義：設(shè)A1，A2，…，An是n個(gè)集合，A1×A2×…×An的一個(gè)子集R稱為A1，A2，…，An間的一個(gè)n元關(guān)系，每個(gè)Ai稱為R的一個(gè)域。

2、關(guān)系矩陣和關(guān)系圖

關(guān)系矩陣

　　定義：設(shè)有窮集合A={a1，a2，…，an}和B={b1，b2，…，bm}，R是從A到B的一個(gè)二元關(guān)系，R的關(guān)系矩陣定義為一個(gè)矩陣M=(mij)，其中

　　從有窮集合A到有窮集合B的二元關(guān)系R用圖表示時(shí)，首先用點(diǎn)表示A和B的元素，并在旁邊標(biāo)注元素的名字，然后用從點(diǎn)x到點(diǎn)y的矢線表示R中的序?qū)?x,y)。若(x,x)∈R，則畫一條從點(diǎn)x指向自身的線，稱為環(huán)。這樣由點(diǎn)和線組成的有向圖稱為R的關(guān)系圖。

?關(guān)系的并、交、差、余：

?　　集合的并、交、差、余運(yùn)算的性質(zhì)對(duì)關(guān)系運(yùn)算也成立。

　　作為關(guān)系時(shí)，余運(yùn)算是對(duì)全域關(guān)系而言的，即將A×B作為全集E

3、偏序的性質(zhì)

自反

　　定義：集合A上的二元關(guān)系R稱為自反的，如果?x∈A，有xRx。

　　說明：?在這個(gè)定義中要求A的每個(gè)元素x，都有xRx，即(x,x)∈R， 這并不排斥某個(gè)序?qū)?x,y)，當(dāng)x≠y時(shí)，仍有(x,y)∈R。 顯然，R是自反的，當(dāng)且僅當(dāng)IA?R。（R-1也是自反的）

反自反

　　定義：集合A上的二元關(guān)系R稱為反自反的，如果?x∈A，有xRx都不成立。

　　R是反自反的，則IA∩R=?

　　說明：非空集合上的一個(gè)二元關(guān)系是自反的，必不是反自反的，反之亦然。 一個(gè)二元關(guān)系不是自反的，未必是反自反的，反之亦然。 即存在既不是自反的，也不是反自反的二元關(guān)系。

對(duì)稱

　　定義：集合A上的二元關(guān)系R，如果?x，y∈A，只要xRy就有yRx，則稱R是對(duì)稱的。（R-1=R）

反對(duì)稱

　　定義：集合A上的二元關(guān)系R，對(duì)?x，y∈A，如果xRy且yRx，則x=y，則稱R是反對(duì)稱的。（如果xRy，則yRz,除非x=y時(shí)有yRx成立）（R∩R-1?IA）

　　關(guān)于對(duì)稱與反對(duì)稱的說明： 二元關(guān)系的對(duì)稱性和反對(duì)稱性不是矛盾的 存在既是對(duì)稱的，也是反對(duì)稱的二元關(guān)系

傳遞

　　定義：集合A上的二元關(guān)系R，對(duì)? x，y，z∈A，如果xRy且yRz，則xRz，那么稱R是傳遞的。

具有某種性質(zhì)的關(guān)系的關(guān)系矩陣、關(guān)系圖的特點(diǎn)

　　關(guān)系矩陣

　　(1)R是自反的，當(dāng)且僅當(dāng)M的對(duì)角線上的全部元素均為1。

　　(2)R是反自反的，當(dāng)且僅當(dāng)M的對(duì)角線上的全部元素為0。 　

　　(3)R是對(duì)稱的，當(dāng)且僅當(dāng)M是對(duì)稱矩陣。

　　(4)R是反對(duì)稱的，當(dāng)且僅當(dāng)i≠j時(shí)M中元素mij與mji不同時(shí)為1。 　　

　　(5)R是傳遞的，當(dāng)且僅當(dāng)M中的元素mij=1且mjk=1時(shí)必有mik=1。

　　關(guān)系圖

　　(6)R是自反的，當(dāng)且僅當(dāng)G的每個(gè)頂點(diǎn)上均有一個(gè)環(huán)。

　　(7)R是反自反的，當(dāng)且僅當(dāng)G中沒有環(huán)。

　　(8)R是對(duì)稱的，當(dāng)且僅當(dāng)G中任兩不同的頂點(diǎn)之間如果有矢線，則必有兩條方向相反的矢線。

　　(9)R是反對(duì)稱的，當(dāng)且僅當(dāng)G中任兩頂點(diǎn)之間最多有一條矢線。

　　(10)R是傳遞的，當(dāng)且僅當(dāng)G從某頂點(diǎn)i沿矢線方向經(jīng)兩條矢線可到達(dá)另一頂點(diǎn)j，則必有從頂點(diǎn)i到頂點(diǎn)j的矢線。

4、復(fù)合關(guān)系和逆關(guān)系

復(fù)合關(guān)系：　　

　　定義：設(shè)R是A到B的二元關(guān)系，S是B到C的二元關(guān)系，則R與S的復(fù)合關(guān)系為一個(gè)從A到C的二元關(guān)系，記為R?S。 R?S={(x,z)|x∈A，z∈C， ?y∈B使xRy且yRz}

　　關(guān)系的復(fù)合運(yùn)算不滿足交換律，也不滿足冪等律，但是關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律。

　　設(shè)R，S，T分別是集合A到B，B到C，C到D的二元關(guān)系，則(R?S)?T=R?(S?T)。

　　冪的定義：設(shè)R是A上的一個(gè)二元關(guān)系，遞歸地定義R的非負(fù)整數(shù)次冪為：

　　R0=IA，R1=R，Rn+1=Rn?R

　　定理：設(shè)R是A上的一個(gè)二元關(guān)系，對(duì)任意的非負(fù)整數(shù)m，n，有 Rm?Rn=Rm+n，(Rm)n=Rmn

　　設(shè)A是一個(gè)有限集且|A|=n，R是A上的一個(gè)二元關(guān)系，則存在非負(fù)整數(shù)s，t，使0≤s＜t≤2n2?且Rs=Rt。

　　定理：設(shè)R是A到B的二元關(guān)系，則 IA?R=R?IB=R

　　定理：設(shè)R1是A到B的二元關(guān)系，R2和R3是B到C的二元關(guān)系，R4是C到D的二元關(guān)系，則

　　(1)R1?(R2∪R3)=(R1?R2)∪(R1?R3)

　　(2)R1?(R2∩R3)=(R1?R2)∩(R1?R3)

　　(3)(R2∪R3)?R4=(R2?R4)∪(R3?R4)

　　(4)(R2∩R3)?R4=(R2?R4)∩(R3?R4)

復(fù)合運(yùn)算的矩陣實(shí)現(xiàn)

　　設(shè)R和S都是A到B的二元關(guān)系，其關(guān)系矩陣分別為MR和MS，R∪S與R∩S的關(guān)系矩陣分別記為MR∪S和MR∩S，易證明： MR∪S=MR∨MS，MR∩S=MR∧MS。

　　設(shè)R是A到B的二元關(guān)系，S是B到C的二元關(guān)系，其關(guān)系矩陣分別為MR和MS，R?S的關(guān)系矩陣MR?S，易證明： MR? S=MR?MS。

　　集合A上的關(guān)系R具有傳遞性的充要條件是R○R?R

逆關(guān)系

　　定義：設(shè)R是從A到B的二元關(guān)系，則從B到A的二元關(guān)系R-1={(y,x)|(x,y)∈R}稱為R的逆關(guān)系。

　　定理：設(shè)R是A到B的二元關(guān)系，則(R-1)-1=R。

　　定理：設(shè)R和S分別是A到B、B到C的二元關(guān)系，則 (R?S)-1= R-1?S-1

逆運(yùn)算的矩陣實(shí)現(xiàn)

　　關(guān)系R-1的關(guān)系矩陣 是關(guān)系R的關(guān)系矩陣MR的轉(zhuǎn)置矩陣，即 =(MR)T。

關(guān)系的閉包

傳遞閉包

　　定義：設(shè)R是A上的一個(gè)二元關(guān)系，A上一切包含R的傳遞關(guān)系的交稱為R的傳遞閉包，記為R+。　　

　　說明：R+是包含R的那些傳遞關(guān)系中最小的那個(gè)關(guān)系。

　　定理：二元關(guān)系R的傳遞閉包R+是傳遞關(guān)系。

　　定理：設(shè)R是A上的一個(gè)二元關(guān)系，則

?　　定理：設(shè)A是n元集，R是A上的一個(gè)二元關(guān)系，則?

?　　傳遞閉包的矩陣運(yùn)算實(shí)現(xiàn)，即：

?自反傳遞閉包

　　定義：設(shè)R是A上的一個(gè)二元關(guān)系，A上包含R的所有自反且傳遞的二元關(guān)系的交稱為R的自反傳遞閉包，記為R*。

　　定理：設(shè)R是A上的一個(gè)二元關(guān)系，則 R*=R0∪R+

自反閉包

　　定義：A上包含R的所有自反關(guān)系的交，記為r(R)，易知 r(R)=R0∪R 而且R是自反的，當(dāng)且僅當(dāng)r(R)=R。

對(duì)稱閉包

　　定義：A上包含R的所有對(duì)稱關(guān)系的交，記為s(R)，易知 s(R)=R∪R-1 而且R是對(duì)稱的，當(dāng)且僅當(dāng)s(R)=R。文章來源地址http://www.zghlxwxcb.cn/news/detail-759803.html

到了這里，關(guān)于關(guān)系的基本概念及其性質(zhì)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！