《離散數學二元關系》PPT課件.ppt

《《離散數學二元關系》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《離散數學二元關系》PPT課件.ppt（141頁珍藏版）》請在裝配圖網上搜索。

2020/4/26,1,第四章二元關系,主要內容：關系的概念及表示方法關系的性質關系的運算:－關系的復合，求逆關系，關系的閉包。三種關系:－等價關系，相容關系，次序關系。,2020/4/26,2,一、序偶與有序n元組1.定義:由兩個對象x、y組成的序列稱為有序二元組，也稱之為序偶，記作；稱x、y分別為序偶的第一，第二元素。注意，序偶與集合{x,y}不同：序偶：元素x和y有次序；集合{x,y}：元素x和y的次序無關緊要。,4-1序偶與集合的笛卡爾積,2020/4/26,3,2.定義：設，是兩個序偶，如果x=u和y=v則稱和相等，記作=。3.定義：有序3元組是一個序偶,其第一個元素也是個序偶。有序3元組,c>可以簡記成，但>不是有序3元組。,2020/4/26,4,4.定義：有序n元組是一個序偶,其第一個元素本身是個有序n-1元組,記作,xn>。且可以簡記成。5.定義=?(x1=y1)?(x2=y2)???(xn=yn),2020/4/26,5,例如“斗獸棋”的16顆棋子，,設：A={紅,藍}B={象,獅,虎,豹,狼,狗,貓,鼠}每個棋子可以看成一個序偶，斗獸棋可記成集合A?B：{,,,,,,,,,,,,,,,},2020/4/26,6,1.定義:設A、B是集合，由A的元素為第一元素，B的元素為第二元素組成序偶的集合，稱為A和B的笛卡爾積，記作AB，即A?B={|x?A∧y?B}例1設A={0,1}，B={a,b}，求A?B，B?A，A?A。解：A?B={,,,}B?A={,,,}A?A={,,,}可見AB≠BA所以，集合的笛卡爾積運算不滿足交換律。,2020/4/26,7,另外(A?B)?C={,c>|?A?B?c?C}A?(B?C)={>|a?A??B?C},因>不是有序三元組,所以(A?B)?C?A?(B?C)。故?也不滿足結合律。,2.性質1)如果A、B都是有限集，且|A|=m,|B|=n，則|A?B|=mn。證明：由笛卡爾積的定義及排列組合中的乘法原理，直接推得此定理。2)A?Φ=Φ?B=Φ,2020/4/26,8,3)?對∪和∩滿足分配律。設A,B,C是任意集合，則⑴A?(B∪C)=(A?B)∪(A?C)；⑵A?(B∩C)=(A?B)∩(A?C)；⑶(A∪B)?C=(A?C)∪(B?C)；⑷(A∩B)?C=(A?C)∩(B?C)；證明⑴：任取?A?(B∪C)?x?A?y?B∪C?x?A?(y?B∨y?C)?(x?A?y?B)∨(x?A?y?C)??A?B∨?A?C??(A?B)∪(A?C)所以⑴式成立。（其余可以類似證明）,2020/4/26,9,4)若C??,則A?B?(A?C?B?C)?(C?A?C?B)證明：充分性：設A?B，求證A?C?B?C任取?A?C?x?A?y?C?x?B?y?C(因A?B)??B?C所以,A?C?B?C。必要性：若C??,由A?C?B?C求證A?B取C中元素y,任取x?A?x?A?y?C??A?C??B?C(由A?C?B?C)?x?B?y?C?x?B所以,A?B。所以A?B?(A?C?B?C)類似可以證明A?B?(C?A?C?B)。,2020/4/26,10,5)設A、B、C、D為非空集合，則A?B?C?D?A?C∧B?D證明：首先,由A?B?C?D證明A?C∧B?D任取x?A，任取y?B，所以x?A?y?B??AB??CD(由A?B?C?D)?x?C?y?D所以,A?C∧B?D。其次,由A?C，B?D證明A?B?C?D任取?AB?x?A?y?B?x?C?y?D(由A?C，B?D)??CD所以,A?B?C?D證畢。,2020/4/26,11,6)約定(…(A1?A2)?…?An-1)?An)=A1?A2?…?An特別A?A?…?A=An設R是實數集合，則R2表示笛卡爾坐標平面，R3表示三維空間，Rn表示n維空間。3.應用1)令A1={x|x是學號}A2={x|x是姓名}A3={男,女}A4={x|x是出生日期}A5={x|x是班級}A6={x|x是籍貫}則A1?A2?A3?A4?A5?A6中一個元素：這就是學生檔案數據庫的一條信息，所以學生的檔案就是A1?A2?A3?A4?A5?A6的一個子集。,2020/4/26,12,2)令A={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}是英文字母表一個英文單詞可以看成有序n元組：如at=,boy=,data=,computer=于是可以說：at?A2,boy?A3,data?A4,computer?A8,…所以英文詞典中的單詞集合可以看成是A∪A2∪…∪An的一個子集。作業(yè)P105⑵,2020/4/26,13,4-2關系及其表示法,相關按照某種規(guī)則，確認了二個對象或多個對象之間有關系，稱這二個對象或多個對象是相關的。,例1：大寫英文字母與五單位代碼的對應關系R1:令α={A,B,C,D,…Z}β={30,23,16,22,…,21}是五單位代碼集合β={11000,10011,01110,10010,…,10001}R1={,,,...,}?αβ,2020/4/26,14,例2：令Ａ={1,2,3,4},A中元素間的≤關系R2：R2={,,,,,,,,,}?AA,關系的定義定義1:設A、Ｂ是集合，如果Ｒ?AB，則稱R是一個從A到B的二元關系。如果R?AA，則稱R是A上的二元關系。二元關系簡稱為關系。定義2:任何序偶的集合，都稱之為一個二元關系。如:R={,,},基本概念,2020/4/26,15,?R?xRy也稱之為x與y有Ｒ關系。,?R?xRy也稱之為x與y沒有Ｒ關系。,例3.R是實數集合，R上的幾個熟知的關系,從例3中可以看出關系是序偶(點)的集合(構成線、面)。,2020/4/26,16,關系的定義域與值域定義域(domain)：設R?AB，由所有?R的第一個元素組成的集合，稱為R的定義域。記作domR，即domR={x|?y(?R)}值域(range)：設R?AB，由所有?R的第二個元素組成的集合，稱為R的值域。記作ranR，即ranR={y|?x(?R)}令：R1={,,,,,,,,,}domR1={1,2,3,4}ranR1={1,2,3,4},2020/4/26,17,枚舉法：即將關系中所有序偶一一列舉出，寫在大括號內。如R={,,,,,,,,,}。謂詞公式法：即用謂詞公式表示序偶的第一元素與第二元素間的關系。例如R={|x?R時，從x到y(tǒng)引一條有向弧(邊)。這樣得到的圖形稱為R的關系圖。,關系的表示方法,2020/4/26,18,例設A={1,2,3,4},B={a,b,c},R1?AB,R2?AA，R1={,,,,},R2={,,,,,,},R1、R2的關系圖如下：,2020/4/26,19,矩陣表示法：設A={a1,a2,?,am}，B={b1,b2,?,bn}是個有限集，R?AB，定義R的mn階矩陣MR=(rij)mn，其中,例：R1={,,,,}R2={,,,,,,},2020/4/26,20,空關系Φ：因為Φ?AB，(或Φ?AA)，所以Φ也是一個從A到B(或A上)的關系，稱之為空關系。即無任何元素的關系，它的關系圖中只有結點,無任何邊；它的矩陣中全是0。完全關系(全域關系)：AB(或AA)本身也是一個從A到B(或A上)的關系，稱之為完全關系。即含有全部序偶的關系。它的矩陣中全是1。,三個特殊關系,2020/4/26,21,A上的恒等關系IA：IA?AA,且IA={|x∈A}為A上的恒等關系。例如A={1,2,3},則IA={,,}A上的Φ、完全關系及IA的關系圖及矩陣如下：,2020/4/26,22,由于關系就是集合，所以集合的∩、∪、-、?和~運算對關系也適用。例如A是學生集合，R是A上的同鄉(xiāng)關系，S是A上的同姓關系，則R∪S：或同鄉(xiāng)或同姓關系R∩S：既同鄉(xiāng)又同姓關系R-S：同鄉(xiāng)而不同姓關系R?S：同鄉(xiāng)而不同姓,或同姓而不同鄉(xiāng)關系~R：不是同鄉(xiāng)關系,這里~R=(AA)-R作業(yè)P109⑵、⑸c)d),關系的集合運算,2020/4/26,23,本節(jié)中所討論的關系都是集合A中的關系。關系的性質主要有：自反性、反自反性、對稱性、反對稱性和傳遞性。一.自反性定義:設R是集合A中的關系，如果對于任意x∈A都有∈R(xRx)，則稱R是A中自反關系。即R是A中自反的關系??x(x?A?xRx)例如：在實數集合中,“?”是自反關系，因為，對任意實數x，有x?x.,4-3關系的性質,2020/4/26,24,從關系有向圖看自反性:每個結點都有環(huán)。從關系矩陣看自反性：主對角線都為1。,令A={1,2,3}，確定以下八個關系中哪些是自反的？,2020/4/26,25,二.反自反性定義：設R是集合A中的關系，如果對于任意的x∈A都有?R，則稱R為A中的反自反關系。即R是A中反自反的??x(x?A??R)從關系有向圖看反自反性:每個結點都無環(huán)。從關系矩陣看反自反性：主對角線都為0。如實數的大于關系>，父子關系是反自反的。注意：一個不是自反的關系，不一定就是反自反的，如前邊R6、R7非自反,也非反自反。,2020/4/26,26,R2、R5、R8、均是反自反關系。,觀察下圖：,2020/4/26,27,三.對稱性定義:R是集合A中關系,若對任何x,y∈A,如果有xRy,必有yRx,則稱R為A中的對稱關系。R是A上對稱的??x?y((x?A?y?A?xRy)?yRx)從關系有向圖看對稱性:在兩個不同的結點之間，若有邊的話，則有方向相反的兩條邊。從關系矩陣看對稱性：以主對角線為對稱的矩陣。例鄰居關系和朋友關系是對稱關系。,2020/4/26,28,R3、R4、R6、R8均是對稱關系。,2020/4/26,29,四.反對稱性定義:設R為集合A中關系,若對任何x,y∈A,如果有xRy,和yRx,就有x=y,則稱R為A中反對稱關系。,由R的關系圖看反對稱性：兩個不同的結點之間最多有一條邊。從關系矩陣看反對稱性：以主對角線為對稱的兩個元素中最多有一個1。另外對稱與反對稱不是完全對立的，有些關系它既是對稱也是反對稱的，如空關系和恒等關系。,2020/4/26,30,上面R1、R2、R4、R5、R8均是反對稱關系。R4、R8既是對稱也是反對稱的。,2020/4/26,31,五.傳遞性定義:R是A中關系，對任何x,y,z∈A,如果有xRy,和yRz,就有xRz,則稱R為A中傳遞關系。即R在A上傳遞??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)例實數集中的≤、＜，集合?、?是傳遞的。從關系關系圖和關系矩陣中不易看清是否有傳遞性。必須直接根據傳遞的定義來檢查。檢查時要特別注意使得傳遞定義表達式的前件為F的時候此表達式為T，即是傳遞的。即若∈R與∈R有一個是F時(即定義的前件為假)，R是傳遞的。,例如A={1,2},下面A中關系R是傳遞的。通過帶量詞的公式在論域展開式說明R在A上傳遞,??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)??x?y?z((xRy?yRz)?xRz)(為了簡單做些刪改)??y?z((1Ry?yRz)?1Rz)??y?z((2Ry?yRz)?2Rz)?(?z((1R1?1Rz)?1Rz)??z((1R2?2Rz)?1Rz)?(?z((2R1?1Rz)?2Rz)?(?z((2R2?2Rz)?2Rz))?(((1R1?1R1)?1R1)?((1R1?1R2)?1R2))?(((1R2?2R1)?1R1)?((1R2?2R2)?1R2))?(((2R1?1R1)?2R1)?((2R1?1R2)?2R2))?(((2R2?2R1)?2R1))?((2R2?2R2)?2R2))?(((F?F)?F)?((F?T)?T))?(((T?F)?F)?((T?F)?T))?(((F?F)?F)?((F?T)?F))?(((F?F)?F))?((F?F)?F))?T,2020/4/26,33,以上R1、R3、R4、R5、R8均是傳遞的關系。,本節(jié)要求：1.準確掌握這五個性質的定義。2.熟練掌握五個性質的判斷和證明。R是A中自反的??x(x?A?xRx)R是A中反自反的??x(x?A??R)R是A上對稱的??x?y((x?A?y?A?xRy)?yRx)R是A上反對稱的??x?y((x?A?y?A?xRy?yRx)?x=y)??x?y((x?A?y?A?x?y?xRy)?yx)R在A上傳遞??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)注意性質表達式的前件為F時此表達式為T，即R是滿足此性質的。(自反和反自反性除外),2020/4/26,35,2020/4/26,36,下面歸納這八個關系的性質：Y-有N-無,2020/4/26,37,2020/4/26,38,練習1:令I是整數集合，I上關系R定義為：R={|x-y可被3整除}，求證R是自反、對稱和傳遞的。證明：⑴自反性：任取x∈I,因x-x=0,0可被3整除,所以有∈R,故R自反。⑵對稱性：任取x,y∈I,設∈R,由R定義得x-y可被3整除,即x-y=3n(n∈I)，y-x=-(x-y)=-3n=3(-n),-n∈N∴∈R,R是對稱的。⑶傳遞性:任取x,y,z∈I,設xRy,yRz,由R定義得x-y=3m,y-z=3n(m.n∈I)x-z=(x-y)+(y-z)=3m+3n=3(m+n),m+n∈N所以xRz,所以R傳遞。證畢,2020/4/26,39,練習2：設R是集合A上的一個自反關系,求證：R是對稱和傳遞的，當且僅當和在R中,則有也在R中。證明：必要性已知R是對稱和傳遞的。設?R又?R，(要證出?R)因R對稱的故?R,又已知?R由傳遞性得?R。所以有如果和在R中,則有也在R中。充分性已知任意a,b,c?A，如和在R中,則有也在R中。,2020/4/26,40,先證R對稱任取a,b?A設?R，(要證出?R)因R是自反的,所以?R，由?R且?R，根據已知條件得?R，所以R是對稱的。再證R傳遞任取a,b,c?A設?R，?R。(要證出?R)由R是對稱的,得?R，由?R且?R，根據已知條件得?R，所以R是傳遞的。作業(yè)第113頁⑴、⑶、⑷,2020/4/26,41,4-4關系的復合,下面介紹由兩個關系生成一種新的關系，即關系的復合運算。例如，有3個人a,b,c，A={a,b,c}，R是A上兄妹關系，S是A上母子關系，∈R∧∈S即a是b的哥哥,b是a的妹妹;b是c的母親，c是b的兒子。則a和c間就是舅舅和外甥的關系,記作R?S,稱它是R和S的復合關系。,2020/4/26,42,1.定義:設R是從X到Y的關系，S是從Y到Z的關系，則R和S的復合關系記作R?S。定義為：R?S={|x?X?z?Z??y(y?Y??R??S)}顯然，R?S是從X到Z的關系。2.復合關系的計算方法(俗稱過河拆橋法)A={1,2,3}B={1,2,3.4}C={1,2,3,4,5}R?ABS?BC枚舉法R={,,,}S={,,,,,則R?S={,,,,,},2020/4/26,43,有向圖法,⑶關系矩陣法令A={a1,a2,…,am}B={b1,b2,…,bn}C={c1,c2,…,ct}R?ABS?BC,,2020/4/26,44,2020/4/26,45,⑷謂詞公式法設I是實數集合，R和S都是I上的關系，定義如下：R={|y=x2+3x}S={|y=2x+3},所以R?S={|y=2x2+6x+3},三.性質關系復合運算不滿足交換律，但是1.滿足結合律:R?ABS?BCT?CD則,2020/4/26,46,??b(b∈B∧∈R∧∈(S○T)??b(b∈B∧∈R∧?c(c∈C∧∈S∧∈T))??b?c(b∈B∧∈R∧(c∈C∧∈S∧∈T))??c?b(c∈C∧(b∈B∧∈R∧∈S∧∈T))??c(c∈C∧?b(b∈B∧∈R∧∈S)∧∈T)??c(c∈C∧∈(R○S)∧∈T)?∈,所以,可以用下圖形象表示:,證明：任取∈,2020/4/26,47,2.R?ABS?BCT?BC,證明⑴任取∈R○(S∪T)??b(b∈B∧∈R∧∈S∪T)??b(b∈B∧∈R∧(∈S∨∈T))??b((b∈B∧∈R∧∈S)∨(b∈B∧∈R∧∈T))??b(b∈B∧∈R∧∈S)∨?b(b∈B∧∈R∧∈T)?∈R○S∨∈R○T?∈(R○S)∪(R○T)所以R○(S∪T)=(R○S)∪(R○T),2020/4/26,48,證明⑵任取∈R○(S∩T)??b(b∈B∧∈R∧∈S∩T)??b(b∈B∧∈R∧(∈S∧∈T))??b((b∈B∧∈R∧∈S)∧(b∈B∧∈R∧∈T))??b(b∈B∧∈R∧∈S)∧?b(b∈B∧∈R∧∈T)?∈R○S∧∈R○T?∈(R○S)∩(R○T)所以R○(S∩T)?(R○S)∩(R○T)?x(A(x)∧B(x))??xA(x)∧?xB(x),2020/4/26,49,3.R是從A到B的關系，則,驗證:,令A={1,2,3},B={a,b,c,d},從這兩個圖看出它們的復合都等于R。,2020/4/26,50,4.關系的乘冪令R是A上關系，由于復合運算可結合，所以關系的復合可以寫成乘冪形式。即,例如R是A上關系，如上圖所示,可見?R2,表明在R圖上有從a到c有兩條邊的路徑:a→b→c;?R3,表明在R圖上有從a到d有三條邊的路徑:a→b→c→d。...如果?Rk,表明在R圖上有從x到y(tǒng)有k條邊(長為k)的路徑(x,y?A)。,有,(m,n為非負整數),,2020/4/26,51,4-5逆關系,一.定義R是從A到B的關系，如果將R中的所有序偶的兩個元素的位置互換，得到一個從B到A的關系，稱之為R的逆關系，記作RC，或R-1。RC={|?R}∈RC??R二.計算方法1.R={,,,}RC={,,,},2020/4/26,52,2.RC的有向圖：是將R的有向圖的所有邊的方向顛倒一下即可。3.RC的矩陣M=(MR)T即為R矩陣的轉置。如,三.性質令R、S都是從X到Y的關系，則1.(RC)C=R2.(R∪S)C=RC∪SC。3.(R∩S)C=RC∩SC。4.(R－S)C=RC－SC。,2020/4/26,53,證明1：任取?(R∪S)C，則?(R∪S)C??R∪S??R∨?S??RC∨?SC??RC∪SC所以(R∪S)C=RC∪SC，其它類似可證。5.R?S?RC?SC。證明：充分性，已知RC?SC，則任取∈R??RC??SC??S∴R?S必要性，已知R?S，則任取∈RC??R??S??SC∴RC?SC,2020/4/26,54,6.(~R)C=~RC證明:任取∈(~R)C?∈~R??R??RC?∈~RC∴(~R)C=~RC,7.令R是從X到Y的關系，S是Y到Z的關系，則(R○S)C=SC○RC。(注意≠RC○SC)證明：任取∈(R○S)C??R○S??y(y∈Y∧∈R∧∈S)??y(y∈Y∧∈SC∧∈RC)??SC○RC所以(R○S)C=SC○RC,2020/4/26,55,8.R是A上關系，則⑴R是對稱的，當且僅當RC=R⑵R是反對稱的，當且僅當R∩RC?IA。證明：⑴充分性，已知RC=R(證出R對稱)任取x,y?A設?R,則?RC,而RC=R所以有?R，所以R對稱。必要性，已知R對稱，(證出RC=R)先證RC?R，任取∈RC,則?R,因R對稱所以有∈R，所以RC?R。再證R?RC，任取?R,因R對稱，所以有∈R，則∈RC,所以R?RC。最后得RC=R。,2020/4/26,56,證明⑵充分性，已知R∩RC?IA，(證出R反對稱)任取x,y?A設?R且∈R，?R∧∈R??R∧∈RC，??R∩RC??IA(因R∩RC?IA)?x=y所以R反對稱。必要性，已知R反對稱，(證出R∩RC?IA)任取?R∩RC?R∩RC??R∧?RC??R∧?R?x=y(因R反對稱)??IA所以R∩RC?IA。,作業(yè)：第118頁⑴⑵a)b)、⑶、⑸,2020/4/26,57,4-6關系的閉包運算,關系的閉包是通過關系的復合和求逆構成的一個新的關系。這里要介紹關系的自反閉包、對稱閉包和傳遞閉包。,一.例子給定A中關系R，如圖所示，求A上另一個關系R’，使得它是包含R的“最小的”(序偶盡量少)具有自反(對稱、傳遞)性的關系。這個R就是R的自反(對稱、傳遞)閉包。,2020/4/26,58,這三個關系圖分別是R的自反、對稱、傳遞閉包。,二.定義：給定A中關系R,若A上另一個關系R′，滿足：⑴R?R′；⑵R′是自反的(對稱的、傳遞的)；⑶R′是“最小的”，即對于任何A上自反(對稱、傳遞)的關系R″,如果R?R″,就有R′?R″。則稱R′是R的自反(對稱、傳遞)閉包。記作r(R)、s(R)、t(R))(reflexive、symmetric、transitive),2020/4/26,59,三.計算方法定理1.給定A中關系R,則r(R)=R∪IA。證明：令R=R∪IA,顯然R是自反的和R?R，下面證明R是“最小的”：如果有A上自反關系R"且R?R",又IA?R",所以R∪IA?R",即R?R"。所以R就是R的自反閉包。即r(R)=R∪IA。定理2.給定A中關系R,則s(R)=R∪RC。證明方法與1.類似。定理3.給定A中關系R,則t(R)=R∪R2∪R3∪...。證明：令R=R∪R2∪R3∪...,⑴顯然有R?R；,2020/4/26,60,⑵證R是傳遞的：任取x,y,z?A,設有?R?R,由R定義得必存在整數i,j使得?Ri,?Rj,根據關系的復合得?Ri+j,又因Ri+j?R,所以?R,∴R傳遞。⑶證R是“最小的”：如果有A上傳遞關系R"且R?R",（證出R?R"）任取?R,則由R定義得必存在整數i,使得?Ri,根據關系的復合得A中必存在i-1個元素e1,e2,...,ei-1，使得(見49頁)?R∧?R∧...∧?R。因R?R",∴有?R"∧?R"∧...∧?R"。由于R"傳遞，所以有?R"。∴R?R"。綜上所述，R就是R的傳遞閉包，即t(R)=R∪R2∪R3∪…=∪Ri,2020/4/26,61,用上述公式計算t(R)，要計算R的無窮大次冪,好象無法實現似的。其實則不然，請看下例:A={1,2,3}A中關系R1,R2,R3,如下：R1={,,}R2={,,}R3={,,}R12={},R13=R14=Φ所以t(R1)=R1∪R12∪R13=R1R22={,,}R23={,,},R23=IA,R24=R2...t(R2)=R2∪R22∪R23R32={,,},R33=R32t(R3)=R3∪R32,2020/4/26,62,定理4.給定A中關系R,如果A是有限集合，|A|=n則t(R)=R∪R2∪...∪Rn。證明：令R=R∪R2∪R3∪...,R"=R∪R2∪...∪Rn顯然有R"?R,下面證明R?R"：任取?R,由R定義得必存在最小的正整數i使得?Ri,(下面證明i≤n)如果i＞n,根據關系的復合得A中必存在i-1個元素e1,e2,...,ei-1，使得?R∧?R∧...∧?R。上述元素序列:x=e0,e1,e2,...,ei-1,y=ei中共有i+1個元素，i+1>n,而A中只有n個元素，所以上述元素中至少有兩個相同，設ej=ek(j,,1>,,1>,,1>,,2>,,2>,,2>,,2>},2020/4/26,121,P109⑴X={a,b,c}Y={s}X到Y的所有關系：XY={,,}XY的任何一個子集都是一個從X到Y的關系。如果|X|=m|Y|=n則有2mn個從X到Y的關系,故,有23=8個關系:R0=ΦR1={}R2={}R3={}R4={,}R5={,}R6={,}R7={,,},⑵設|A|=n，有多少個A上的關系？因為R?AA,所以AA有多少個子集就有多少個A上關系,由集合的冪集就是該集合的子集構成的,所以A上關系個數就是AA的冪集P(AA)的元素個數|P(AA)|,而2|AA|=2nn=2n2。所以有2n2個不同的A上關系。P113⑴A={1,2,3}，A上五個關系如下：(T略有改動),上述五個關系中，哪些是等價關系？如果是等價關系，求其商集。哪些是相容關系？如果是相容關系，求其完全覆蓋。哪些是偏序關系？如是偏序關系,畫Hasse圖,并求Ａ的極小(大)元、最小(大)元、上界與下界、上確界和下確界。等價關系：S和AA，對應的商集分別是：A/S={{1,2},{3}}A/AA={{1,2,3}}相容關系:S和AA，對應的完全覆蓋分別是：CS(A)={{1,2},{3}}CAA(A)={{1,2,3}}偏序關系:TＡ的極小元、最小元、下界、下確界都是：1Ａ的極大元、最大元、上界、上確界都是：3,c)R和S都對稱，R?S不一定對稱。,舉反例：,第118頁⑴R和S都是A上關系，a)R和S都自反,R?S一定自反。b)R和S都反自反,R?S不一定反自反。,舉反例：,d)R和S都傳遞，R?S不一定傳遞。,舉反例：,⑵S是Ｘ上關系。a)證明Ｓ傳遞，當且僅當S2?S(可用此定理判定傳遞)證明：充分性，已知S2?S任取x,y,z∈X,且有∈S,∈S,根據關系的復合得∈S2,由已知得∈S,所以Ｓ傳遞。必要性，已知Ｓ傳遞,任取∈S2,根據關系的復合得?z(z∈X∧∈S∧∈S),由Ｓ傳遞得∈S所以S2?S,2020/4/26,126,b)證明Ｓ自反，當且僅當IX?S。(可用此定理判定自反)證明：充分性，已知IX?S，任取x∈X,有∈IX,由已知得∈S,所以Ｓ自反。必要性，已知Ｓ自反，任取∈IX,得x=y,而S自反，所以∈S∴IX?S,⑶S是Ｘ上關系，證明Ｓ是自反和傳遞，則S2=S。其逆為真嗎？證明由⑵a)得Ｓ傳遞，則S2?S，只證明S?S2任取∈S,又已知Ｓ自反，所以∈S,于是有∈S∧∈S，由關系的復合得∈S2所以有S?S2,最后得S2＝Ｓ。其逆不一定為真。例如S如圖所示：它滿足S2＝Ｓ，但Ｓ不自反。,2020/4/26,128,⑸R是A上關系，a)R自反，Rc也自反。因為任取x∈A,因R自反，所以∈R,∴∈Rcb)R對稱，Rc也對稱。因為R對稱，所以Rc=R∴Rc也對稱。,c)R傳遞，Rc也傳遞。方法1.任取x,y,z∈A,且有∈Rc,∈Rc,于是∈R,∈R，因R傳遞，∴∈于是有∈Rc，∴Rc傳遞。方法2.t(Rc)=Rc∪(Rc)2∪(Rc)3∪…=Rc∪(R2)c∪(R3)c∪…=(R∪R2∪R3∪…)c=(t(R))c=Rc(因為R傳遞，所以t(R)=R)所以Rc傳遞。(R2)c＝(R?R)c=(Rc?Rc)=(Rc)2,P113(4)R和S都A上是自反、對稱、傳遞的，求證R∩S也是自反、對稱和傳遞的。證明：一.證明R∩S的自反性方法1用自反定義證：任取x∈A,(證出∈R∩S)因R和S都自反，所以有∈R，∈S，于是有∈R∩S，所以R∩S也自反。方法2用恒等關系IA證：(證出IA?R∩S)方法3用自反閉包證：(證出r(R∩S)=R∩S,即(R∩S)∪IA=R∩S)因R和S都自反，所以r(R)=R,r(S)=S,r(R∩S)=(R∩S)∪IA=(R∪IA)∩(S∪IA)=r(R)∩r(S)=R∩S所以R∩S也自反。,二.證明R∩S的對稱性：方法1用對稱定義證：任取x,y∈A,設∈R∩S,(證出∈R∩S.)方法2用求逆關系證：(證出(R∩S)c=R∩S.)因為R和S對稱，所以有Rc=R，Sc=S，而(R∩S)c=Rc∩Sc=R∩S，∴R∩S對稱。方法3用對稱閉包證：(證出s(R∩S)=R∩S,即(R∩S)∪(R∩S)c=R∩S.)因為R和S對稱，所以s(R)=R,s(S)=Ss(R∩S)=(R∩S)∪(R∩S)c=(R∩S)∪(Rc∩Sc)=(R∪Rc)∩(R∪Sc)∩(S∪Sc)∩(S∪Rc)=(s(R)∩(R∪Sc))∩(s(S)∩(S∪Rc))=(R∩(R∪Sc))∩(S∩(S∪Rc))=R∩S∴R∩S對稱。,三.證明R的傳遞性：方法1用傳遞定義證：任取x,y,z∈A,設∈R∩S,∈R∩S,(證出∈R∩S)∈R∩S∧∈R∩S?∈R∧∈S∧∈R∧∈S?(∈R∧∈R)∧(∈S∧∈S)?∈R∧∈S（因為R、S傳遞）?∈R∩S所以R∩S傳遞。方法2用傳遞閉包證：證出t(R∩S)=R∩S,即(R∩S)∪(R∩S)2∪(R∩S)3∪...=R∩S.方法3用定理證：證出(R∩S)?(R∩S)?(R∩S)用方法2、方法3證明此題的傳遞性有很大難度。R?(S∩T)?(R?S)∩(R?T),P127(1)R的有向圖如圖所示，求r(R)、s(R)、t(R)。(5)R1和R2是A上關系，且R2?R1，求證a)r(R2)?r(R1),b)s(R2)?s(R1),c)t(R2)?t(R1)。證明：a)r(R2)=R2∪IA?R1∪IA=r(R1),b)s(R2)=R2∪(R2)c?R1∪(R1)c=s(R1),(因為R2?R1，所以(R2)c?(R1)c)c)先用歸納法證明(R2)i?(R1)i,⑴i=1時，R2?R1顯然結論成立⑵假設i≤k時，結論成立，即(R2)i?(R1)i；⑶i=k+1時,(R2)k+1=(R2)kR2?(R1)kR1=(R1)k+1,t(R2)=R2∪(R2)2∪...∪(R2)k∪...?R1∪(R1)2∪...∪(R1)k∪…=t(R1)。c)的另一證法：,,,,c)因為R2?R1，又R1?t(R1)，所以R2?t(R1)。于是有t(R2)和t(R1)都是包含R2的傳遞關系，而t(R2)是包含R2的最小的傳遞關系，所以t(R2)?t(R1)。(7).R1和R2是A上關系，求證a)r(R1∪R2)=r(R1)∪r(R2),b)s(R1∪R2)=s(R1)∪s(R2),c)t(R1)∪t(R2)?t(R1∪R2),證明：a)r(R1∪R2)=(R1∪R2)∪IA=(R1∪IA)∪(R2∪IA)=r(R1)∪r(R2),b)s(R1∪R2)=(R1∪R2)∪(R1∪R2)c=(R1∪R2)∪(R1)c∪(R2)c=(R1∪(R1)c)∪(R2∪(R2)c)=s(R1)∪s(R2),c)因R1?(R1∪R2)且R2?(R1∪R2)，由題(5)得t(R1)?t(R1∪R2),t(R2)?t(R1∪R2)，所以有t(R1)∪t(R2)?t(R1∪R2)。,(8).R是A上關系，R*=tr(R),求證:a)(R+)+=R+b)R?R*=R+=R*?Rc)(R*)*=R*R+=t(R)=R∪R2∪R3∪…=R*=rt(R)=IA∪R∪R2∪R3∪...=證明：a)(R+)+=t(t(R)),因為t(R)是傳遞的，所以t(t(R))=t(R),即(R+)+=R+。b)R?R*=R?(IA∪R∪R2∪R3∪...)∵復合對并可分配，=R∪R2∪R3∪…=R+。類似可證R*?R=R+c)(R*)*=tr(tr(R))=trtr(R)=trrt(R)(∵tr(R)=rt(R))=trt(R)(∵rt(R)是自反的，∴rrt(R)=rt(R))=ttr(R)=tr(R)(∵tr(R)是傳遞的，∴ttr(R)=tr(R))=R*,第130頁(1).X是集合，且|X|=4，X有多少個不同的劃分？解.第134頁(2).X是集合，且|X|=4，X上有多少個不同的等價關系？解.此題的答案與上題一樣。因為每個劃分對應一個等價關系。,(4).R是A上關系，設S={|?c∈A∧∈R∧∈R}求證若R是等價關系，則S也是等價關系。證明：a)證S自反：任取a∈A，∵R是自反的，∴有∈R,由S定義得∈S,(S定義中c就是a)∴S自反.b)證S對稱:任取a,b∈A，且有∈S,由S定義得?c∈A∧∈R∧∈R,由R對稱得?c∈A∧∈R∧∈R,由S定義得∈S,S對稱.c)證S傳遞:任取a,b,c∈A,有∈S,∈S,由S定義得(?d∈A∧∈R∧∈R)∧(?e∈A∧∈R∧∈R),由于R傳遞,所以有∈R,∈R,由S定義得∈S,所以S傳遞.所以S是A上等價關系.(6).R是A上對稱和傳遞的關系，證明如果?a∈A,?b∈A,使得∈R,則R是一個等價關系.證明:任取a∈A,有已知得?b∈A,使得∈R,由R對稱得∈R,又由R傳遞得,∈R,R自反,∴R是等價關系.,(1)(7).R和S都是A上等價關系,下面哪個是A上等價關系?證明或舉反例說明.a)R∪Sb)R∩Sc)~R(即AA-R)d)R-Se)R2f)r(R-S)解.a)c)d)f)不是.請看反例:,,,,,b).R∩S是等價關系,前面已經證明過.(第113頁題(4))e).①證R2自反,任取a∈A,因為R自反,所以∈R,根據關系的復合得,∈RR,即∈R2,所以R2自反。②證R2對稱,(R2)c=(Rc)2=R2(由R對稱得Rc=R)∴R2對稱③證R2傳遞，任取a,b,c∈A,設有∈R2,∈R2,根據關系的復合得,(?d∈A∧∈R∧∈R)∧(?e∈A∧∈R∧∈R),由于R傳遞,所以有∈R,∈R,∴∈R2所以R2傳遞。最后得R2是等價關系。第139頁(2).X={x1,x2,x3,x4,x5,x6},R是X上相容關系，其簡化關系矩陣如下：求X的完全覆蓋。解.R的簡化圖為：CR(X)={{x1,x2,x3,},{x1,x3,x6},{x3,x4,x5},{x3,x5,x6}},o,第145頁(1).給定集合{3,5,15}，{1,2,3,6,12}，{3,9,27,54}，≤為整除關系，分別畫出上述集合上的≤的關系圖，Hasse圖，并指出哪些是全序關系。,(6)P={x1,x2,x3,x4,x5},P上偏序關系的Hasse圖如圖所示，求子集{x1,x2,x3}，{x2,x3,x4}，{x3,x4,x5}和P的極小(大)元、最小(大)元、上界、下界、最小上界和最大下界(上確界和下確界)。,