版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1/36第四章二元關(guān)系2/452/45回顧關(guān)系的冪運算關(guān)系的性質(zhì)3/453/45四、關(guān)系的閉包運算閉包的定義:給定集合X,R是X中的二元關(guān)系。如果有另一個關(guān)系滿足(1)是自反的(對稱的、可傳遞的);
(2)(3)對于任何自反的(對稱的、可傳遞的)關(guān)系,如果,則則稱關(guān)系為R的自反的(對稱的,可傳遞的)閉包。
并用r(R)表示的R自反閉包,用s(R)表示R的對稱閉包,用t(R)表示R的可傳遞閉包。4/454/45四、關(guān)系的閉包運算定理:給定集合X,R是X中的關(guān)系。于是可有(a)當(dāng)且僅當(dāng),R才是自反的。(b)當(dāng)且僅當(dāng),R才是對稱的。(c)當(dāng)且僅當(dāng),R才是傳遞的。證明:僅給出(a)的證明過程由閉包的定義可知,又由于R是包含了R的自反關(guān)系,根據(jù)自反閉包的定義有。因此有。反之,如果,則由自反閉包定義可知R是自反的。
5/455/45四、關(guān)系的閉包運算定理:設(shè)R為A上的關(guān)系,則有(1)r(R)=R∪R0(2)s(R)=R∪R1(3)t(R)=R∪R2∪R3∪…說明:對有窮集A(|A|=n)上的關(guān)系,(3)中的并最多不超過Rn證只證(1)和(3).(1)由IA=R0R∪R0知R∪R0是自反的,且滿足RR∪R0設(shè)R
是A上包含R的自反關(guān)系,則有RR
和IAR
.從而有R∪R0R.R∪R0滿足閉包定義,所以r(R)=R∪R0.6/456/45四、關(guān)系的閉包運算(3)先證R∪R2∪…t(R)成立.用歸納法證明對任意正整數(shù)n有Rnt(R).n=1時有R1=Rt(R).假設(shè)Rnt(R)成立,那么對任意的<x,y>
<x,y>∈Rn+1=RnR
t(<x,t>∈Rn∧<t,y>∈R)
t(<x,t>∈t(R)∧<t,y>∈t(R))<x,y>∈t(R)這就證明了Rn+1t(R).由歸納法命題得證.再證t(R)R∪R2∪…成立,為此只須證明R∪R2∪…傳遞.任取<x,y>,<y,z>,則
<x,y>∈R∪R2∪…∧<y,z>∈R∪R2∪…
t(<x,y>∈Rt)∧s(<y,z>∈Rs)
ts(<x,z>∈RtRs)
ts(<x,z>∈Rt+s)
<x,z>∈R∪R2∪…從而證明了R∪R2∪…是傳遞的.7/457/45四、關(guān)系的閉包運算在整數(shù)集合中,小于關(guān)系“<”的自反閉包是“≤”;恒等關(guān)系IX的自反閉包是IX。不等關(guān)系“≠”的自反閉包是全域關(guān)系;空關(guān)系的自反閉包是恒等關(guān)系。在整數(shù)集合中,小于關(guān)系“<”的對稱閉包是不等關(guān)系“≠”;小于或等于關(guān)系“≤”的對稱閉包是全域關(guān)系;恒等關(guān)系IX的對稱閉包是IX;不等關(guān)系“≠”的對稱閉包是不等關(guān)系“≠”。8/458/45四、關(guān)系的閉包運算例:給定集合X={a,b,c},R和S是X中的關(guān)系,給定試求出t(R),t(S),并畫出關(guān)系圖解:R,t(R)St(S)9/459/45四、關(guān)系的閉包運算定理:設(shè)X是集合,R是X中的二元關(guān)系,于是有(1)如果R是自反的,那么s(R),t(R)也是自反的;(2)如果R是對稱的,那么r(R),t(R)也是對稱的;(3)如果R是可傳遞的,那么r(R)也是可傳遞的。證明(1):若R是自反的,則對于所有的
都有即s(R),t(R)是自反的10/45四、關(guān)系的閉包運算11/45四、關(guān)系的閉包運算證明(3):
12/4512/45四、關(guān)系的閉包運算定理:設(shè)X是集合,R是集合中的二元關(guān)系,于是有證明:13/4513/45四、關(guān)系的閉包運算證明(b):因為,,而對于所有的有,以及。根據(jù)這些關(guān)系式,可有于是14/4514/45四、關(guān)系的閉包運算證明(c):如果,則,根據(jù)對稱閉包的定義,有。首先構(gòu)成上式兩側(cè)的可傳遞閉包,再依次構(gòu)成兩側(cè)的對稱閉包,可以求得以及。而ts(R)是對稱的,所以,從而有。15/4515/45四、關(guān)系的閉包運算注意:(1)通常用R+表示R的可傳遞閉包t(R),并讀作“R加”。(2)通常用R*表示R的自反可傳遞閉包tr(R),并讀作“R星”。16/4516/454.5特殊關(guān)系一、集合的劃分和覆蓋定義:給定非空集合S,設(shè)非空集合A={A1,A2,…,An},如果有則稱集合A是集合S的覆蓋。注意:集合的覆蓋不唯一。例如:S={a,b,c},A={{a,b},{b,c}},B={{a},{b,c}},A和B都是集合S的覆蓋。17/4517/45一、集合的劃分和覆蓋定義:給定非空集合S,設(shè)非空集合A={A1,A2,…,An},如果有則稱集合A是集合S的一個劃分。劃分中的元素Ai稱為劃分的類。劃分的類的數(shù)目叫劃分的秩。劃分是覆蓋的特定情況,即中元素互不相交的特定情況。18/4518/45一、集合的劃分和覆蓋例:設(shè)S={1,2,3},考慮下列集合S的覆蓋S的覆蓋S的覆蓋、劃分,秩為2S的覆蓋、劃分,秩為1,最小劃分S的覆蓋、劃分,秩為3,最大劃分19/4519/45一、集合的劃分和覆蓋定義:設(shè)A和A'是非空集合S的兩種劃分,并可以表示成如果A'的每一類A'j,都是A的某一類Ai的子集,那么稱劃分A'是劃分A的加細,并稱A'加細了A。如果A'是A的加細并且A'≠A,則稱A'是A的真加細。20/4520/45極小項、完全交集定義:劃分全集E的過程,可看成是在表達全集的文氏圖上劃出分界線的過程。設(shè)A,B,C是全集E的三個子集。由A,B和C生成的E的劃分的類,稱為極小項或完全交集。
n個子集生成2n個極小項,用表示。21/4521/45一、集合的劃分和覆蓋定理:由全集的n個子集A1,A2,…,An所生成的全部極小項集合,能夠構(gòu)成全集E的一個劃分。證明:證明這個定理,只需證明全集E中的每一個元素,都僅屬于一個完全交集就夠了。如果,則,或,或;…;或。由此可見,定有這里或是Ai或是~Ai
。試考察兩個不同的完全交集T。因為兩個完全交集是不同的,就是說存在這樣一個i,使得和,因此可有,即;因而任何一個都不能同時屬于兩個不同的完全交集。22/4522/45一、集合的劃分和覆蓋注意:不難看出,這里所說的完全交集,與命題演算中的極小項相似。但是和極小項的集合不同,極大項的集合不能構(gòu)成全集的劃分。23/4523/45二、等價關(guān)系定義:設(shè)X是任意集合,R是集合中的二元關(guān)系。如果R是自反的、對稱的和可傳遞的,則稱R是等價關(guān)系。即滿足以下幾點:如果R是集合X中的等價關(guān)系,則R的域是集合X自身,所以,稱R是定義于集合X中的關(guān)系。例如
數(shù)的相等關(guān)系是任何數(shù)集上的等價關(guān)系。
又例如一群人的集合中姓氏相同的關(guān)系也是等價關(guān)系。但朋友關(guān)系不是等價關(guān)系,因為它不可傳遞。
24/4524/45二、等價關(guān)系例:給定集合X={1,2,…,7},R是X中的二元關(guān)系,并且給定成試證明R是等價關(guān)系。解:R的關(guān)系矩陣如下:R的關(guān)系圖如下:25/4525/45二、等價關(guān)系注意:上例是模數(shù)系統(tǒng)中模等價關(guān)系的特定情況。
設(shè)Z+是正整數(shù)集合,m是個正整數(shù)。對于來說,可將R定義成。這里,“x-y可被m整除”等價于命題“當(dāng)用m去除x和y時,它們都有同樣的余數(shù)”。故關(guān)系R也稱為模m同余關(guān)系。26/4526/45元素的等價
設(shè)R是集合A上的等價關(guān)系,若元素aRb,則稱a與b等價,或稱b與a等價。定義:設(shè)m是個正整數(shù),。如果對于某一個整數(shù)n,有x-y=n?m,則稱x模m等價于y,并記作整數(shù)m稱為等價的模數(shù)?!啊北硎灸等價關(guān)系R。27/4527/45二、等價關(guān)系定理:任何集合中的模m相等關(guān)系,是一個等價關(guān)系。證明:設(shè)R是任何集合中的模m相等價關(guān)系。如果X=Ф,則R是個空關(guān)系,顯然有是自反的、對稱的和可傳遞的。如果X≠Ф
,則需考察下列三條:(1)對于任何來說,因為x-x=0?m,所以有。因此,模m相等關(guān)系是自反的。
(2)對于任何來說,如果,則存在某一個,能使x-y=n?m。于是可有y-x=(-n)?m,因此有,即模m相等關(guān)系是對稱的。(3)設(shè),和。于是存在,能使和。而,從而可有,即模m相等關(guān)系是可傳遞的。
28/4528/45等價類
定義
設(shè)是集合A上的等價關(guān)系,則A
中等價于元素的所有元素組成的集合稱為生成的等價類,用表示,即說明:簡單起見,有時候把[a]R簡單寫作[a]或a/R。29/4529/45等價類例:設(shè)X={a,b,c,d},R是X中的等價關(guān)系,并把R給定成
則:30/4530/45等價類的性質(zhì)設(shè)X是一集合,X是R中的等價關(guān)系2.對于所有的,或者,或者證明:當(dāng)X=Ф,上述結(jié)論肯定為真。當(dāng)X≠Ф時,分兩種情況討論(1)xRy(2)xR'y1.如果x∈X,則x∈[x]R。該性質(zhì)是明顯的,因為R是自反的,所以有xRx,于是x∈[x]R31/4531/45等價類的性質(zhì)(1)xRy故。類似地可以證明由上得若,則xRz
,
由R的對稱性有zRx,
又由R的傳遞性有zRy
,因此(2)xR'y假設(shè),因此有且,故于是由xRz,zRy,得xRy,與xR'y相矛盾32/4532/45等價類的性質(zhì)3.證明:假定,對于某個,有。由于,會有,因而。設(shè),于是因而
證畢。33/4533/45等價類的性質(zhì)例
設(shè)A={a,b,c,d},A上的關(guān)系R是A上的等價關(guān)系
同一個等價類中元素均相互等價。不同等價類中的元素互不等價。由A的各元素所生成的等價類必定覆蓋A,決定了集合A的一種劃分。34/4534/45二、等價關(guān)系定理:設(shè)R是非空集合X中的等價關(guān)系。R的等價類的集合,是X的一個劃分。定義:設(shè)R是非空集合X中的等價關(guān)系。R的各元素生成的等價類集合叫按R去劃分X的商集,記作X/R,也可以寫成X(modR)。由定義可知,按R對集合X的劃分X/R是一個集合,并且X/R的基數(shù)是X的不同的R等價類的數(shù)目,因此X/R的基數(shù)又稱為等價關(guān)系R的秩。35/4535/45特殊的等價關(guān)系全域關(guān)系:令等價關(guān)系R1=XX,這里X的每一個元素與X的所有元素都有R1的關(guān)系。按R1劃分X的商集乃是集合{X}。等價關(guān)系R1是全域關(guān)系。全域關(guān)系會造成集合X的最小劃分。恒等關(guān)系R:X的每一個元素僅關(guān)系到它自身,而不關(guān)系到其它元素。顯然,R是個恒等關(guān)系。按R劃分X的商集,僅由單元素集合組成。恒等關(guān)系R會造成集合X的最大劃分。這些劃分均稱作X的平凡劃分。36/4536/45等價關(guān)系與集合的劃分例:令R是整數(shù)集合I中的“模3同余”關(guān)系,R可給定成
求Z的元素所生成的R等價類。
解:等價類是可以看出,等價關(guān)系可以造成集合的一個劃分。
37/4537/45等價關(guān)系與集合的劃分定理:設(shè)C是非空集合X的一個劃分,則由這個劃分所確定的下述關(guān)系R必定是個等價關(guān)系,并稱R為由C劃分導(dǎo)出的X中的等價關(guān)系。證明:要證明R是個等價關(guān)系,就必須證明R是自反的、對稱的和可傳遞的。(a)由于C是X的劃分,C必定覆蓋X。對任意的
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度水路貨運運輸承包服務(wù)合同2篇
- 二零二五版水電安裝工程安全評估與施工合同2篇
- 二零二五版農(nóng)業(yè)貸款定金合同規(guī)范文本3篇
- 二零二五版幼兒園教師勞動權(quán)益保護及勞動合同解除程序協(xié)議3篇
- 二零二五版房產(chǎn)托管居間服務(wù)合同協(xié)議3篇
- 二零二五年房地產(chǎn)物業(yè)管理合作開發(fā)合同3篇
- 二零二五年度重點單位保安勤務(wù)合同5篇
- 二零二五版微電影導(dǎo)演定制化拍攝合同3篇
- 二零二五版KTV員工心理健康關(guān)愛計劃合同2篇
- 二零二五年度高端酒店場地租賃合同范本2篇
- DB34∕T 4010-2021 水利工程外觀質(zhì)量評定規(guī)程
- 納米復(fù)合材料的增韌增能機制
- 圖書館前臺接待工作總結(jié)
- 衛(wèi)生院藥品管理制度
- 神經(jīng)外科進修匯報課件
- 2024老年人靜脈血栓栓塞癥防治中國專家共識(完整版)
- 騰訊營銷師認(rèn)證考試題庫(附答案)
- 鄰近鐵路營業(yè)線施工安全監(jiān)測技術(shù)規(guī)程 (TB 10314-2021)
- 四年級上冊脫式計算100題及答案
- 資本市場與財務(wù)管理
- 河南近10年中考真題數(shù)學(xué)含答案(2023-2014)
評論
0/150
提交評論