《二元關(guān)系備選》PPT課件.ppt

《《二元關(guān)系備選》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《二元關(guān)系備選》PPT課件.ppt（100頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

9等價(jià)關(guān)系與等價(jià)類,《定義》：設(shè)X是一個(gè)集合，R是X中的二元關(guān)系，若R是自反的，對稱的和可傳遞的，則稱R是等價(jià)關(guān)系。,例：下列關(guān)系均為等價(jià)關(guān)系（1）實(shí)數(shù)（或I、N集上）集合上的“=”關(guān)系（相等）,（2）{人類}中的同姓關(guān)系,（3）命題集合上的等價(jià)關(guān)系,例：設(shè)X={1,2,3,4,5,6,7}，,,為整數(shù)},9等價(jià)關(guān)系與等價(jià)類,試驗(yàn)證R是等價(jià)關(guān)系，畫出R的關(guān)系圖，列出R的關(guān)系矩陣,解：（1）R={},（2）R的關(guān)系矩陣,,10相容關(guān)系,例：已知相容關(guān)系圖，求出最大相容類,10相容關(guān)系,,,最大相容類集合為,,例題選講,例1.設(shè)A，B，C，D代表任意集合，判斷以下命題是否恒真，如果不是，請舉一反例。(1)A?B?C?D?A?C?B?D(2)A?B?C?D?A-D?B-C(3)A?B?B=A?(B-A)(4)A-B=B-A?A=B解：(1)不為真。舉反例如下：令A(yù)＝{1},B={1,4},C={2},D={2,3}則A?B且C?D，但A?C＝B?D，與結(jié)論矛盾。,例題選講,(2)由于C?D?～D?～C，又由A?B可得A?～D?B?～C即A－D?B－C成立。(3)由于A?(B－A)=A?B故有：B=A?(B－A)?B=A?B?A?B即A?B的充要條件為B=A?B或A=A?B或A－B=?,例題選講,(4)易見，當(dāng)A=B時(shí)，必有A-B=B-A由A-B=B-A得(A-B)?B=(B-A)?B即：(A?~B)?B=(B?~A)?B即：B-A=?∴B?A同理可證：A?B從而得到：A＝B,例題選講,例2.設(shè)：A、B是任意的集合(1)試證明?(A)??(B)=?(A?B)(2)?(A)??(B)=?(A?B)成立嗎？為什么？解：(1)證明S??(A)??(B)，則S??(A)且S??(B)，因此：S?A且S?B∴S?A?B即S??(A?B)∴?(A)??(B)??(A?B)反之，設(shè)S??(A?B)，則S?A?B，,例題選講,因此S?A且S?B∴S??(A)且S??(B)于是S??(A)??(B)∴?(A?B)??(A)??(B)由上知?(A)??(B)＝?(A?B)(2)?(A)??(B)??(A?B)成立。其證明如下：設(shè)：S??(A)??(B)，則S??(A)或S??(B)因此S?A或S?B∴S?A?B即S??(A?B)故?(A)??(B)??(A?B)成立,例題選講,?(A?B)??(A)??(B)不成立設(shè)：S??(A?B)，則S?A?B。但此時(shí)無法推斷S?A，也無法推斷S?B，因此既不能得出S??(A)，也不能得出S??(B)。例如：設(shè)A={a,c}，B={c,b}則A?B={a,b,c}，設(shè)S={a,b}，則S?A?B即S??(A?B)但S??(A)且S??(B)因此S??(A)??(B),例題選講,例3.設(shè)S={1,2,3,…10}，≤是S上的整除關(guān)系，求的哈斯圖，并求其中的最大元，最小元。最小上界，最大下界。分析：畫哈斯圖的關(guān)鍵在于確定結(jié)點(diǎn)的層次和元素間的蓋住關(guān)系。畫圖的基本步驟是：(1)確定偏序集中的極小元，并將這些極小元放在哈斯圖的最底層；(2)若第n層的元素已確定完畢，從A中剩余的元素中選取至少能蓋住第n層中一個(gè)元素的元素，將這些元素放在哈斯圖的第n+1層。,例題選講,在排列結(jié)點(diǎn)的位置時(shí)，注意把蓋住較多元素的結(jié)點(diǎn)放在中間，將只蓋住一個(gè)元素的結(jié)點(diǎn)放在兩邊，以減少連線的交叉；(3)將相鄰兩層的結(jié)點(diǎn)根據(jù)蓋住關(guān)系進(jìn)行連線。,例題選講,在畫哈斯圖時(shí)應(yīng)該注意下面幾個(gè)問題：(1)哈斯圖中不應(yīng)該出現(xiàn)三角形，如果出現(xiàn)三角形，一定是蓋住關(guān)系沒找對。糾正的方法是重新考察這3個(gè)元素在偏序集中的順序，然后將不滿足蓋住關(guān)系的那條邊去掉。(2)哈斯圖中不應(yīng)該出現(xiàn)水平線段。出現(xiàn)這種錯(cuò)誤的原因在于沒有將“較大”元素放在“較小”元素的上方。糾正時(shí)只要根據(jù)“大小”順序?qū)ⅰ拜^大”的元素放到更高的一層，將水平線改為斜線就可以了。(3)哈斯圖中要盡量減少線的交叉。圖形中線的交叉多少主要取決于同一層結(jié)點(diǎn)的排列順序，,例題選講,如果出現(xiàn)交叉過多，可以適當(dāng)調(diào)整結(jié)點(diǎn)的排列順序。最后，如何確定哈斯圖中極大元、極小元、最大元、最小元、最小上界和最大下界。方法如下：(1)如果圖中有孤立結(jié)點(diǎn)，那么這個(gè)結(jié)點(diǎn)既是極小元，也是極大元，并且圖中既無最小元，也無最大元。（除只有唯一孤立結(jié)點(diǎn)的情況）(2)除了孤立結(jié)點(diǎn)以外，其它的極小元是圖中所有向下通路的終點(diǎn)，其它的極大元是圖中所有向上通路的終點(diǎn)。,例題選講,例4.設(shè)Z+={x|x?Z?x>0}，?1，?2是Z+的2個(gè)劃分，?1={{x}|x?Z+}，?2={Z+}，求劃分?1，?2所確定的Z+上的等價(jià)關(guān)系。分析：等價(jià)關(guān)系和劃分是兩個(gè)不同的概念。等價(jià)關(guān)系是有序?qū)Φ募希鴦澐质亲蛹募?。但對于給定的集合A，A上的等價(jià)關(guān)系R和A的劃分?是一一對應(yīng)的。即：?R?x和y在?的同一劃分塊里。本題中，?1的劃分塊都是單元集，沒有含兩個(gè)以上元素的劃分塊；,例題選講,?2中只有一個(gè)劃分塊Z+，Z+包含了集合中的全體元素?！郣1就是Z+上的恒等關(guān)系；R2就是Z+上的全域關(guān)系。例5.對下面給定的集合A和B，構(gòu)造從A到B的雙射函數(shù),,分析：構(gòu)造從集合A到B的雙射函數(shù)，一般可采用下面的方法：(1)若A，B都是有窮集合，可以先用列元素的方法表示A，B,例題選講,然后，順序?qū)中的元素與B中的元素建立對應(yīng)。(2)若A，B是實(shí)數(shù)區(qū)間，可以采用直線方程作為從A到B的雙射函數(shù)。例如：A＝[1,2]，B＝[2,6]是實(shí)數(shù)區(qū)間。先將A，B區(qū)間分別標(biāo)記在直角坐標(biāo)系的x軸和y軸上，過(1,2)和(2,6)兩點(diǎn)的直線方程將A中的每個(gè)數(shù)映到B中的每一個(gè)數(shù)。因此，該直線方程：,就是從A到B的雙射函數(shù)。,例題選講,這種通過直線方程構(gòu)造雙射函數(shù)的方法對任意兩個(gè)同類型的實(shí)數(shù)區(qū)間(同為閉區(qū)間、開區(qū)間或半開半閉區(qū)間)都是適用的。此外，對于某些特殊的實(shí)數(shù)區(qū)間，可能選擇其它嚴(yán)格單調(diào)的初等函數(shù)更方便。對于本題:,(3)A是一個(gè)無窮集合，B是自然數(shù)集N只須將A中的元素排成一個(gè)有序序列，且指定這個(gè)序列的初始元素，這就叫做把A“良序化”。例如：構(gòu)造從整數(shù)集Z到自然數(shù)集N的雙射，如下排列：,例題選講,Z：0，-1，1，-2，2，-3，3，…….N：0，1，2，3，4，5，6，…….即：,顯然f是從Z到N的雙射。,3.4例題選解,【例3.4.1】設(shè)A、B為集合，已知A-B=B-A，證明：A=B。證明A-B=B-AA∩～B=B∩～AA∩～B∩B=B∩～A∩BΦ=B∩～AΦ=B-AAB①,同理：A-B=B-AA∩～B=B∩～AA∩～B∩A=B∩～A∩AA∩～B=ΦA-B=ΦBA②由①、②可得：A=B,【例3.4.2】設(shè)A、B為集合，證明：P（A）∪P（B）P（A∪B）。并舉例說明不能將“”換成“=”。證明x，x∈（P（A）∪P（B））x∈P（A）∨x∈P（B）不妨設(shè)x∈P（A），則有{x}A{x}（A∪B），所以x∈P（A∪B），故P（A）∪P（B）P（A∪B）。,例如，A={a,b}B={b,c}A∪B={a,b,c}，則P（A）={Φ,{a},,{a,b}},P(B)={Φ,,{c},{b,c}}P（A）∪P（B）={Φ,{a},,{c},{a,b},{b,c}}而P（A∪B）={Φ,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}}所以P（A）∪P（B）≠P（A∪B）。,【例3.4.3】設(shè)Ai是實(shí)數(shù)集合，它被定義為：,則,證明（1）先證,設(shè),則必存在某個(gè)自然數(shù)k，使x∈Ak，即,則有x＜1，故x∈A0。所以,（2）再證,設(shè)x∈A0，即x＜1，故必有ε＞0，使x=1-ε，令,則,，即x∈Ak，所以,故,【例3.4.4】證明（A-B）B=A∪B。證明(A-B）B=（A∩～B）B=（（A∩～B）-B）∪（B-（A∩～B））=（A∩～B∩～B）∪（B∩～（A∩～B））=（A∩～B）∪（B∩（～A∪B））=（A∩～B）∪B=A∪B,習(xí)題三,1．證明：如果B∈{{a}}，那么a∈B。2．試用描述法表示下列集合：(1)小于5的非負(fù)整數(shù)集合。(2)10與20之間的素?cái)?shù)集合。(3)小于65的12的正倍數(shù)集合。(4）能被5整除的自然數(shù)的集合。,3.選擇適宜的客體域和謂詞公式表示下列集合：(1)奇整數(shù)集合。(2)10的倍數(shù)集合。(3)永真式的集合。4．對任意元素a,b,c,d，證明：{{a},{a,b}}＝{{c}，{c，d}}當(dāng)且僅當(dāng)a=c且b=d,5．"如果A∈B,B∈C，那么A∈C"對任意A,B,C都成立嗎？都不成立嗎？舉例說明你的結(jié)論。6．列舉出下列集合的元素：(1)S={x|x∈I(3＜x＜12)}，I為整數(shù)集合(2)S={x|x是十進(jìn)制的數(shù)字}(3)S={x|(x=2)∨(x=5)},7．下面命題的真值是否為真，說明理由。(1){a}{{a}}(2){a}∈{{a}}(3){a}∈{{a},a}(4){a}{{a},a}(5）(6）(7）(8）∈｛｝(9）對任意集合A，B，C，若A∈B，BC則A∈C。(10）對任意集合A，B，C，若A∈B，BC則AC。(11）對任意集合A，B，C，若AB，B∈C則A∈C。(12）對任意集合A，B，C，若AB，B∈C則AC。,8．列舉下列集合的所有子集:（1）｛｝（2）{1,{2,3}}(3){{1,{2,3}}}（4）｛｛｝｝(5){{1,2}{2,1,1},{2,1,1,2}}9．A、B、C均是集合，若A∩C=B∩C且A∪C=B∪C，則必有A=B。10.設(shè)A={a},求A的冪集P(A)以及A的冪集的冪集P(P(A))。11．設(shè)A、B、C、D為4個(gè)集合，已知AB且CD，證明：A∩CB∩D。,12．設(shè)A、B為集合，證明：P（A）∩P（B）=P（A∩B）。13．證明定理3.2.3。14．設(shè)A、B、C為集合，證明：（A-B）-C=（A-C）-（B-C）。15．設(shè)A、B為集合，證明：（A-B）-C=A-（B∪C）。16．設(shè)A、B、C為集合，證明：（A∪B）-C=（A-C）∪（B-C）。17．證明：對任意集合A、B和C有，（A∩B）∪C=A∩（B∪C）的充分必要條件是CA。,18．設(shè)A、B、C是集合，若CA，證明：（A∩B）∪C=A∩（B∪C）。19．設(shè)全集E={a，b，c，d，e，f，g}，子集A={a，b，d，e}，B={c，d，f，g}，C={c，e}，求下面集合：（1）～A∪～B（2）～（AB）（3）（A∩B）∪（A∩C）,20．設(shè)A，B是全集E的子集，已知～A～B，證明：BA。21．設(shè)A、B為集合，且AB，證明：～A∪B=E，其中E為全集。22．證明：（A-B）B=A∪B。23．設(shè)Bi是實(shí)數(shù)集合，它被定義為：,證明：,24．設(shè)某校有58個(gè)學(xué)生，其中15人會(huì)打籃球，20人會(huì)打排球，38人會(huì)踢足球，且其中只有3人同時(shí)會(huì)三種球，試求同時(shí)會(huì)兩種球的學(xué)生共有幾人。25．求1到500的整數(shù)中（1和500包含在內(nèi)）分別滿足以下條件的數(shù)的個(gè)數(shù)：（1）同時(shí)能被4，5和7整除。（2）不能被4和5，也不能被7整除。（3）可以被4整除，但不能被5和7整除。（4）可以被4或5整除，但不能被7整除。,定理4.5.4對非空集合A上的關(guān)系R1、R2，則（1）r(R1)∪r(R2)=r(R1∪R2)（2）s(R1)∪s(R2)=s(R1∪R2)（3）t(R1)∪t(R2)t(R1∪R2),證明(1）和（2）的證明留作練習(xí)，下面僅證明（3）。因?yàn)镽1∪R2R1,由定理4.5.3知t(R1∪R2)t(R1)同理t(R1∪R2)t(R2)所以t(R1∪R2)t(R1)∪t(R2),4.11例題選解,【例4.11.1】證明：非空的對稱、傳遞關(guān)系不可能是反自反關(guān)系。證明設(shè)R是集合A上的對稱、傳遞關(guān)系，若R非空，則x，y∈A，有〈x,y〉∈R。由于R對稱，因此〈y,x〉∈R，又由于R是傳遞的，因此〈x,x〉∈R。因此非空的對稱、傳遞關(guān)系不可能是反自反關(guān)系。,【例4.11.2】設(shè)R、S均是A上的等價(jià)關(guān)系，證明：R。S于A上等價(jià)iffS。R=R。S。證明""（先證必要性）〈x,z〉〈x,z〉∈S。Ry（〈x,y〉∈S∧〈y,z〉∈R）y（〈z,y〉∈R∧〈y,x〉∈S）(由于R、S均是對稱的)〈z,x〉∈R。S〈x,z〉∈R。S(由于R。S于A上是對稱的)故S。R=R。S。,""（再證充分性）(1)x∈A，由于R、S均是自反的，因此〈x,x〉∈R且〈x,x〉∈S，所以〈x,x〉∈R。S，即R。S是自反的。(2)〈x,y〉〈x,y〉∈R。St（〈x,t〉∈R∧〈t,y〉∈S）t（〈t,x〉∈R∧〈y,t〉∈S）(由于R、S均是對稱的)〈y,x〉∈S。R〈y,x〉∈R。S(由于S。R=R。S)即R。S是對稱的。,(3)〈x,y〉，〈y,z〉〈x,y〉∈R。S∧〈y,z〉∈R。S〈x,y〉∈R。S∧〈y,z〉∈S。R(由于S。R=R。S)〈x,z〉∈R。S。S。R〈x,z〉∈R。(S。S)。R(關(guān)系的復(fù)合滿足結(jié)合律)〈x,z〉∈R。S。R（由于S傳遞，因此S。SS）〈x,z〉∈R。R。S（由于S。R=R。S)〈x,z〉∈R。S（由于R傳遞，因此R。RR）即R。S是傳遞的。,【例4.11.3】設(shè)R、S均是A上的等價(jià)關(guān)系，證明：R∪S于A上等價(jià)iffR。SR∪S且S。RR∪S。證明""（先證必要性）〈x,y〉∈R。St（〈x,t〉∈R∧〈t,y〉∈S）t（〈x,t〉∈R∪S∧〈t,y〉∈R∪S）〈x,y〉∈R∪S(由于R∪S傳遞)即R。SR∪S。同理可證：S。RR∪S。""（再證充分性）,(1)x∈A，由于R、S均是自反的，因此〈x,x〉∈R且〈x,x〉∈S，所以〈x,x〉∈R∪S，即R∪S是自反的。(2)〈x,y〉〈x,y〉∈R∪S〈x,y〉∈R∨〈x,y〉∈S〈y,x〉∈R∨〈y,x〉∈S）(由于R、S均是對稱的)〈y,x〉∈R∪S即R∪S是對稱的。,【例4.11.4】設(shè)R、S均是非空集合A上的偏序關(guān)系，證明：R∩S也是A上的偏序關(guān)系。證明(1)x∈A，由于R、S均是自反的，因此有〈x,x〉∈R且〈x,x〉∈S，即〈x,x〉∈R∩S，故R∩S自反。(2)〈x,y〉∧x≠y〈x,y〉∈R∩S〈x,y〉∈R∧〈x,y〉∈S〈y,x〉R∧〈y,x〉S（由于R、S均是反對稱的）〈y,x〉R∩S故R∩S反對稱。,(3)〈x,y〉，〈y,z〉〈x,y〉∈(R∩S)∧〈y,z〉∈(R∩S)(〈x,y〉∈R∧〈x,y〉∈S)∧(〈y,z〉∈R∧〈y,z〉∈S)(〈x,y〉∈R∧〈y,z〉∈R)∧(〈x,y〉∈S∧〈y,z〉∈S)〈x,z〉∈R∧〈x,z〉∈S（由于R、S均是傳遞的）〈x,z〉∈R∩S故R∩S傳遞。因此，R∩S也是偏序關(guān)系。,【例4.11.5】A={a,b}上有多少不同的偏序關(guān)系？解因?yàn)槠蜿P(guān)系與哈斯圖一一對應(yīng)，所以只要畫出所有不同的哈斯圖，就可求出其不同的偏序關(guān)系，詳見圖4.11.1。所以該集合上共有3個(gè)不同的偏序關(guān)系?！纠?.11.6】給出A={a,b,c}上既是等價(jià)關(guān)系又是偏序關(guān)系的R。解R=IA,圖4.11.1,【例4.11.7】設(shè)A={1,2,3,4,5,6,9,24,54},R是A上的整除關(guān)系。(1)畫出偏序關(guān)系R的Hasse圖。(2)求A關(guān)于R的極大元、極小元。(3)設(shè)B={2，3}，求B的上界和上確界。(4)找出〈A，R〉中的長度為4的反鏈。解（1）關(guān)系R的Hasse圖見圖4.11.2。（2）A關(guān)于R的極大元：54，24，5；極小元：1，5。（3）B的上界：6，54，24；下界：1。（4）長度為4的反鏈：{4，5，6，9}。,圖4.11.2,【例4.11.10】設(shè)f：A→B是函數(shù)，并定義一個(gè)函數(shù)g：B→P（A）。對于任意的b∈B，有g(shù)（b）={x|（x∈A）∧（f（x）=b）}請證明：若f是A到B的滿射，則g是B到P（A）的單射。證明對任意b1，b2∈B（b1≠b2），由于f是滿射，因此a1，a2∈A，使得f（a1）=b1，f（a2）=b2。又由于b1∈b2且f是函數(shù)，因此a1≠a2。又g（b1）={x|（x∈A）∧(f（x）=b1）}g（b2）={x|（x∈A）∧（f（x）=b2）},,因此有a1∈g（b1），a2(g（b2），但a1g（b2），a2g（b1），所以g（b1）≠g（b2），故g為單射。,【例4.11.11】設(shè)X≠，R為XX上的關(guān)系，定義為〈f,g〉∈RRanf=Rang證明:R是XX上的等價(jià)關(guān)系，且存在雙射φ：XX/R→P（X）-{}.證明（1）①f∈XX，由于Ranf=Ranf，因此〈f,f〉∈R，即R是自反的。②〈f,g〉〈f,g〉∈RRanf=RangRang=Ranf〈g,f〉∈R即R是對稱的。,③〈f,g〉，〈g,h〉〈f,g〉∈R∧〈g,h〉∈R(Ranf=Rang)∧(Rang=Ranh)Ranf=Ranh〈f,h〉∈R即R是傳遞的。綜上，R是XX上的等價(jià)關(guān)系。,（2）定義φ：XX/R→P（X）-{}：［f］R∈XX/R，φ（［f］R）=Ranf，于是φ（［f］R）=φ（［g］R）Ranf=Rang〈f,g〉∈R［f］R=［g］R因而φ是單射。,又A∈P（X）-{}，AX，A≠，取定元素a∈A，定義f：X→X為,則φ（［f］R）=Ranf=A，因而φ是滿射。綜上所述，存在雙射φ：XX/R→P（X）-{}。,【例4.11.12】設(shè)f：A→B，g：B→C是兩個(gè)函數(shù)，證明：（1）若f。g是滿射且g是單射，則f是滿射。（2）若f。g是單射且g是滿射，則f是單射。（注：這里函數(shù)的復(fù)合為右復(fù)合。）,證明（1）b∈B，因?yàn)間是函數(shù)，所以存在c∈C，使得g（b）=c。由f。g是滿射，對該元素c，存在a∈A，使得f。g（a）=c，即g（f（a））=c。由g（b）=c，所以g（f（a））=g（b）=c。由g是單射，所以有f（a）=b。即b∈B，a∈A，使得f（a）=b。因此f是滿射。,（2）對任意b1，b2∈B（b1≠b2），由于f是單射，所以a1，a2∈A，使得f（a1）=b1，f（a2）=b2。由于b1≠b2且f是函數(shù)，所以a1≠a2。再由f。g是單射，可得f。g（a1）≠f。g（a2），即g（f（a1））≠g（f（a2）），所以g（b1）≠g（b2）。因此g是單射。,【例4.11.13】設(shè)f：A→B是函數(shù)，并定義一個(gè)函數(shù)g：B→P（A）。對于任意的b∈B，有g(shù)（b）={x|（x∈A）∧（f（x）=b）}證明若f是A到B的滿射，則g是B到P（A）的單射。證明如果f是A到B的滿射，則對每個(gè)b∈B,至少存在一個(gè)a∈A,使f(a)=b,故g的定義域?yàn)锽。,若有b1,b2∈B,且b1≠b2,g(b1)={x|（x∈A）∧（f（x）=b1）}g（b2）={y|（y∈A）∧（f（y）=b2）}因?yàn)閎1≠b2,f(x)≠f(y),而f是函數(shù)，故x≠y,所以g(b1)≠g(b2)。因此g是B到P（A）的單射。,習(xí)題四,1．已知A={},求P(A)A。2．設(shè)A={1,2,3},R為實(shí)數(shù)集,請?jiān)诘芽▋浩矫嫔媳硎境鯝R和RA。3．以下各式是否對任意集合A，B，C，D均成立？試對成立的給出證明，對不成立的給出適當(dāng)?shù)姆蠢?。?（1）(A-B)C=(AC)-(BC)（2）(A∩B)(C∩D)=(AB)∩(CD)（3）(A-B)(C-D)＝(AC)-(BD)（4）(A∪B)(C∪D)=(AC)∪(BD),4．設(shè)A,B,C,D為任意集合，求證：（1）若AC，BD，那么ABCD。（2）若C,ACBC，則AB。（3）(AB)-(CD)＝((A-C)B)∪(A(B-D))。5．證明定理4.1.3中的（2）、（3）、（4）、（6）。6．證明定理4.1.4和定理4.1.5。,7．給定集合A={1，2，3}，R，S均是A上的關(guān)系，R={〈1,2〉,〈2,1〉}∪IA，S={〈1,1〉,〈2,3〉}（1）畫出R，S的關(guān)系圖；（2）說明R，S所具有的性質(zhì)；（3）求RS。,8．設(shè)A＝{0,1,2,3,4,5}，B={1,2,3}，用列舉法描述下列關(guān)系，并作出它們的關(guān)系圖及關(guān)系矩陣：（1）R1={〈x,y〉|x(A∩B∧y∈A∩B}（2）R2={〈x,y〉|x(A∧y∈B∧x=y2}（3）R3={〈x,y〉|x(A∧y∈A∧x+y=5}（4）R4={〈x,y〉|x(A∧y∈A∧k(x=ky∧k∈N∧k＜2)}（5）R5={〈x,y〉|x(A∧y∈A∧(x=0∨2x＜3)},9．設(shè)R,S為集合A上任意關(guān)系，證明：（1）Dom(R∪S)=Dom(R)∪Dom(S)（2）Ran(R∩S)Ran(R)∩Ran(S)10．設(shè)A=｛1，2，3，4,5｝，A上關(guān)系R=｛〈1，2〉，〈3，4〉，〈2，2〉｝,S=｛〈4，2〉，〈2,5〉,〈3,1〉，〈1,3〉｝。試求RS的關(guān)系矩陣。11．設(shè)A=｛1，2，3，4｝，A上關(guān)系R＝｛〈1，4〉，〈3，1〉，〈3，2〉,〈4,3〉｝。求R的各次冪的關(guān)系矩陣。,12．證明定理4.3.1中的（1）、（4）、（5）及（6）13．設(shè)A＝{a,b,c,d}，A上二元關(guān)系R1，R2分別為R1={〈b,b〉,〈b,c〉,〈c,a〉}R2={〈b,a〉,〈c,a〉,〈c,d〉,〈d,c〉}計(jì)算R1R2，R2R1，R21,R22。,14．設(shè)A={0，1，2，3}，R和S均是A上的二元關(guān)系:R={〈x，y〉|（y=x+1）∨（y=x/2）}S={〈x，y〉|（x=y+2）}（1）用列元素法表示R，S；（2）說明R，S所具有的性質(zhì)；（3）求RS。15．證明定理4.3.3中的（2）、（3）、（6）。,16．設(shè)R1,R2,R3,R4,R5都是整數(shù)集上的關(guān)系，且xR1y|x-y|=1xR2yxy＜0xR3yx|y(x整除y)xR4yx+y=5xR5yx=yn(n是整數(shù))請用T(True)和F(False)填寫表4.1。,表4.1,17．證明定理4.4.2和定理4.4.6。18．設(shè)A={0，1，2，3}，RAA且R={〈x，y〉|x=y∨x(y∈A}。(1)畫出R的關(guān)系圖；(2)寫出關(guān)系矩陣MR；(3)R具有什么性質(zhì)？19．設(shè)A為一集合，|A|=n,試計(jì)算（1）A上有多少種不同的自反的（反自反的）二元關(guān)系（2）A上有多少種不同的對稱的二元關(guān)系？（3）A上有多少種不同的反對稱的二元關(guān)系？,20．設(shè)R為A上的自反關(guān)系，證明：R是傳遞的iffRR=R。并舉例說明其逆不真。21．請判斷下述的結(jié)論和理由正確嗎？并說明理由。（1）如果R對稱且傳遞，那么R必自反，因?yàn)橛蒖對稱可知xRy蘊(yùn)涵yRx，而由R傳遞及xRy,yRx，可知xRx。（2）如果R反自反且傳遞，那么R必定是反對稱的,因?yàn)槿鬜對稱可知xRy蘊(yùn)涵yRx，而由R傳遞及xRy,yRx，可導(dǎo)出xRx,從而得到矛盾。,22．證明：當(dāng)關(guān)系R傳遞且自反時(shí)，R2＝R。23．設(shè)R、S、T均是集合A上的二元關(guān)系，證明：若RS，則TRTS。24．設(shè)R為集合A上任一關(guān)系，求證對一切正整數(shù)n有,25．設(shè)R是集合A上的二元關(guān)系，R在A上是反傳遞的定義為：若〈x,y〉∈R,〈y,z〉∈R,則〈x,z〉R即xyz(xRy∧yRz→﹁xRz)。證明：R是反傳遞的，當(dāng)且僅當(dāng)（RR）∩R=。,26．證明定理4.5.1中的（2）。27．證明定理4.5.2中的（1）、（3）。28．證明定理4.5.3中的（1）、（2）。29．證明定理4.5.4中的（1）、（2）及對（3）t(R1∪R2)=t(R1)∪t(R2)舉出反例。30．證明定理4.5.5中的（3）。,31．設(shè)R是X={1,2,3,4，5}上的二元關(guān)系，R={〈1,2〉,〈2,1〉,〈1,5〉,〈5,1〉,〈2,5〉,〈5,2〉,〈3,4〉,〈4,3〉}∪IA。請給出關(guān)系矩陣并畫出關(guān)系圖；若R是等價(jià)關(guān)系，則求出等價(jià)類。32．若{{a,c,e},{b,d,f}}是集合A={a,b,c,d,e,f}的一個(gè)劃分，求其等價(jià)關(guān)系R。33．若{{1，3，5}，{2，4}}是集合A={1,2,3,4,5}的一個(gè)劃分，求其等價(jià)關(guān)系R。,34．設(shè)S={1,2,3,4,5}且A=SS,在A上定義關(guān)系R:〈a,b〉R〈a′,b′〉當(dāng)且僅當(dāng)ab′=a′b。（1）證明R是一個(gè)等價(jià)關(guān)系。（2）計(jì)算A/R。35．設(shè)R是集合A上的二元關(guān)系，R在A上是循環(huán)的充分必要條件是：若aRb并且bRc，則cRa。證明：R為等價(jià)關(guān)系當(dāng)且僅當(dāng)R是自反的和循環(huán)的。,36．設(shè)R，S為A上的兩個(gè)等價(jià)關(guān)系，且RS。定義A/R上的關(guān)系R/S：〈［x］,［y］〉∈R/S當(dāng)且僅當(dāng)〈x,y〉∈S證明：R/S為A/R上的等價(jià)關(guān)系。,37．設(shè){A1，Ａ2,…，Am}為集合A的劃分，證明：對任意集合B，{A1∩B，A2∩B，…，Am∩B}-{}必為集合A∩B的劃分。38．設(shè)R1表示整數(shù)集上模m1相等關(guān)系，R2表示模m2相等關(guān)系，π1，π2分別是R1，R2對應(yīng)的劃分。證明：π1細(xì)分于π2當(dāng)且僅當(dāng)m1是m2的倍數(shù)。,39．確定下面集合A上的關(guān)系R是不是偏序關(guān)系。（1）A=Z,aRba=2b（2）A=Z,aRbb2|a（3）A=Z,aRb存在k使a=bk（4）A=Z,aRba≤b,40．設(shè)A={a，b，c，d，e}，A上的偏序關(guān)系R={〈c,a〉,〈c,d〉}∪IA。(1)畫出R的哈斯圖；(2)(1)畫出R的哈斯圖；求A關(guān)于R的極大元和極小元。41．偏序集〈A，≤〉的哈斯圖如圖4.1所示。（1）用列舉元素法求R；（2）求A關(guān)于R的最大元和最小元；（3）求子集{c，d，e}的上界和上確界；（4）求子集{a，b，c}的下界和下確界。,圖4.1,圖4.2,42．圖4.2為一偏序集〈A,R〉的哈斯圖。（1）下列命題哪些為真？aRb，dRa，cRd，cRb，bRe，aRa，eRa；（2）畫出R的關(guān)系圖；（3）指出A的最大、最小元（如果有的話），極大、極小元；（4）求出子集B1={c,d,e},B2={b,c,d},B3={b,c,d,e}的上界、下界，上確界、下確界（如果有的話）。,43．設(shè)R是集合A={a，b，c，d}上的偏序關(guān)系，關(guān)系矩陣為,（1）寫出R的表達(dá)式；（2）畫出R的哈斯圖；（3）求子集B={a，b}關(guān)于R的上界和上確界。44．對下列每一條件構(gòu)造滿足該條件的有限集和無限集各一個(gè)。（1）非空有序集，其中有子集沒有最大元素。（2）非空有序集，其中有子集有下確界，但它沒有最小元素。（3）非空有序集，其中有一子集存在上界，但它沒有上確界。,45．圖4.3給出了集合S={a,b,c,d}上的四個(gè)關(guān)系圖。請指出哪些是偏序關(guān)系圖，哪些是全序關(guān)系圖，哪些是良序關(guān)系圖，并對偏序關(guān)系圖畫出對應(yīng)的哈斯圖。,圖4.3,46．下列集合中哪些是偏序集合，哪些是全序集合，哪些是良序集合？（1）〈P(N),〉（2）〈P(N),〉（3）〈P{a},〉（4）〈P(),〉,47．設(shè)R是集合S上的關(guān)系，S′S，定義S′上的關(guān)系R′為：R′＝R∩(S′S′）。確定下述各斷言的真假：（1）如果R傳遞，則R′傳遞。（2）如果R為偏序關(guān)系，則R′也是偏序關(guān)系。（3）如果〈S,R〉為全序集，則〈S′,R′〉也是全序集。（4）如果〈S,R〉為良序集，則〈S′,R′〉也是良序集。,48．設(shè)〈A,≤〉為一有限全序集，|A|≥2，R是AA上的關(guān)系，根據(jù)R下列各定義，確定〈AA,R〉是否為偏序集、全序集或良序集。設(shè)x，y，u，v為A中任意元素。（1）〈x,y〉R〈u,v〉x≤u∧y≤v（2）〈x,y〉R〈u,v〉x≤u∧x≠u∨(x=u∧y≤v)（3）〈x,y〉R〈u,v〉x≤u（4）〈x,y〉R〈u,v〉x≤u∧x≠u,49．指出下列各關(guān)系是否為A到B的函數(shù)：（1）A＝B＝N，R={〈x,y〉|x∈A∧y∈B∧x+y＜100}（2）A=B=R（實(shí)數(shù)集），S={〈x,y〉|x∈A∧y∈B∧y=x2}（3）A＝{1,2,3,4}，B＝AA，R={〈1,〈2,3〉〉,〈2,〈3,4〉〉,〈3,〈1,4〉〉,〈4,〈2,3〉〉}（4）A={1,2,3,4}，B=AA，S={〈1,〈2,3〉〉,〈2,〈3,4〉〉,〈3,〈2,3〉〉},50．設(shè)f：X→Y，g：X→Y，求證：（1）f∩g為X到Y(jié)的函數(shù)當(dāng)且僅當(dāng)f=g。（2）f∪g為X到Y(jié)的函數(shù)當(dāng)且僅當(dāng)f=g。51．設(shè)f和g為函數(shù)，且有fg和Dom(g)Dom(f)。證明f=g。52．證明定理4.8.2中的（2）、（3）。53．設(shè)f:X→Y，ABX，求證f(A)f(B)。54．令f={〈,{,{}}〉，〈{},〉}為一函數(shù)。計(jì)算f()，f({})，f({,{}})。,55．設(shè)X,Y均是有窮集合。|X|=n,|Y|=m,分別找出從X到Y(jié)存在單射、滿射、雙射的必要條件。試計(jì)算集合X到集合Y有多少個(gè)不同的單射函數(shù)和多少個(gè)不同的滿射函數(shù)及多少個(gè)不同的雙射函數(shù)。,55．設(shè)X,Y均是有窮集合。|X|=n,|Y|=m,分別找出從X到Y(jié)存在單射、滿射、雙射的必要條件。試計(jì)算集合X到集合Y有多少個(gè)不同的單射函數(shù)和多少個(gè)不同的滿射函數(shù)及多少個(gè)不同的雙射函數(shù)。56．考慮下列實(shí)數(shù)集上的函數(shù)：f(x)=2x2+1，g(x)=-x+7，N(x)=2x，k(x)=sinx求gｏf，fｏg，fｏf，gｏg，fｏN，fｏk，kｏN。,57．設(shè)X={1,2，3}，請找出XX中滿足下列各式的所有函數(shù)。（1）f2(x)=f(x)（f等冪）（2）f2(x)=x（f2為恒等函數(shù)）（3）f3(x)=x（f3為恒等函數(shù)）,58．設(shè)A≠，A，B，C為集合。（1）求A，，（2）若AB，則ACBC。59．設(shè)N為X上的函數(shù)，證明下列條件中（1）與（2）等價(jià),（3）與（4）等價(jià)。（1）N為一單射。（2）對任意X上的函數(shù)f，g，fｏN＝gｏN蘊(yùn)涵f=g。（3）N為一滿射。（4）對任意X上的函數(shù)f，g，Nｏf＝Nｏg蘊(yùn)涵f＝g。,60．設(shè)A={l，2，3}，作出全部A上的置換，并以三個(gè)函數(shù)值組成的字的字典序排列這些置換。試計(jì)算p2ｏp3，p3ｏp3，p3ｏp2，并求x，使得p3ｏpx=pxｏp3=i。,61．下列函數(shù)為實(shí)數(shù)集上的函數(shù)，如果它們可逆，請求出它們的反函數(shù)。（1）y=3x+1（2）y=x2-1（3）y=x2-2x（4）y=tgx+162．根據(jù)自然數(shù)集合的定義計(jì)算：（1）4∪7，3∩5（2）6-5，42（3）25,66．證明：{1，3，5，…，2n+1,…}是可數(shù)集。67．設(shè)A，B為可數(shù)集，證明：AB為可數(shù)集。68．設(shè)f：A→B為一滿射。（1）A為無限集時(shí)，B是否一定為無限集？（2）A為可數(shù)集時(shí)，B是否一定為可數(shù)集？69．設(shè)f：A→B為一單射。（1）A為無限集時(shí)，B是否一定為無限集？（2）A為可數(shù)集時(shí)，B是否一定為可數(shù)集？70．證明定理4.10.12。71.若|A|=|B|,|C|=|D|,則|AC|=|BD|。,