第三章 二元關(guān)系備選

第三章二元關(guān)系備選第1頁，課件共100頁，創(chuàng)作于2023年2月§9等價(jià)關(guān)系與等價(jià)類試驗(yàn)證R是等價(jià)關(guān)系，畫出R的關(guān)系圖，列出R的關(guān)系矩陣解：（1）R={<1,1><1,4><1,7><2,2><2,5><3,3><3,6><4,1><4,4><4,7><5,5><5,2><6,6><6,3><7,7><7,4><7,1>}（2）R的關(guān)系矩陣第2頁，課件共100頁，創(chuàng)作于2023年2月§10相容關(guān)系例：已知相容關(guān)系圖，求出最大相容類第3頁，課件共100頁，創(chuàng)作于2023年2月§10相容關(guān)系最大相容類集合為第4頁，課件共100頁，創(chuàng)作于2023年2月例題選講例1.設(shè)A，B，C，D代表任意集合，判斷以下命題是否恒真，如果不是，請舉一反例。(1)ABCDACBD(2)ABCDA-DB-C(3)ABB=A(B-A)(4)A-B=B-AA=B解：(1)不為真。舉反例如下：令A(yù)＝{1},B={1,4},C={2},D={2,3}則AB且CD，但AC＝BD，與結(jié)論矛盾。第5頁，課件共100頁，創(chuàng)作于2023年2月例題選講(2)由于CD～D～C，又由AB可得A～DB～C即A－DB－C成立。(3)由于A(B－A)=AB故有： B=A(B－A)B=ABAB即AB的充要條件為B=AB或A=AB或A－B=第6頁，課件共100頁，創(chuàng)作于2023年2月例題選講(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=∴BA同理可證：AB從而得到：A＝B第7頁，課件共100頁，創(chuàng)作于2023年2月例題選講例2.設(shè)：A、B是任意的集合(1)試證明(A)(B)=(AB)(2)(A)(B)=(AB)成立嗎？為什么？解 ：(1)證明S(A)(B)，則S(A)且S(B)，因此：SA且SB

∴ SAB即S(AB)

∴ (A)(B)(AB)反之，設(shè)S(AB)，則SAB，第8頁，課件共100頁，創(chuàng)作于2023年2月例題選講 因此 SA且SB ∴ S(A)且S(B) 于是 S(A)(B) ∴ (AB)(A)(B)由上知 (A)(B)＝(AB)(2)(A)(B)(AB)成立。其證明如下： 設(shè)：S(A)(B)，則S(A)或S(B)因此SA或SB ∴ SAB 即S(AB)故(A)(B)(AB)成立第9頁，課件共100頁，創(chuàng)作于2023年2月例題選講 (AB)(A)(B)不成立設(shè)：S(AB)，則SAB。但此時(shí)無法推斷SA，也無法推斷SB，因此既不能得出S(A)，也不能得出 S(B)。例如：設(shè)A={a,c}，B={c,b}則AB={a,b,c}，設(shè)S={a,b}，則SAB即 S(AB)但S(A)且S(B)因此S(A)(B)第10頁，課件共100頁，創(chuàng)作于2023年2月例題選講例3. 設(shè)S={1,2,3,…10}，≤是S上的整除關(guān)系，求<S,≤>的哈斯圖，并求其中的最大元，最小元。最小上界，最大下界。分析：畫哈斯圖的關(guān)鍵在于確定結(jié)點(diǎn)的層次和元素間的蓋住關(guān)系。畫圖的基本步驟是：(1)確定偏序集<A,≤>中的極小元，并將這些極小元放在哈斯圖的最底層；(2)若第n層的元素已確定完畢，從A中剩余的元素中選取至少能蓋住第n層中一個(gè)元素的元素，將這些元素放在哈斯圖的第n+1層。第11頁，課件共100頁，創(chuàng)作于2023年2月例題選講在排列結(jié)點(diǎn)的位置時(shí)，注意把蓋住較多元素的結(jié)點(diǎn)放在中間，將只蓋住一個(gè)元素的結(jié)點(diǎn)放在兩邊，以減少連線的交叉；(3)將相鄰兩層的結(jié)點(diǎn)根據(jù)蓋住關(guān)系進(jìn)行連線。第12頁，課件共100頁，創(chuàng)作于2023年2月例題選講在畫哈斯圖時(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)的排列順序，第13頁，課件共100頁，創(chuàng)作于2023年2月例題選講如果出現(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)。第14頁，課件共100頁，創(chuàng)作于2023年2月例題選講例4.設(shè)Z+={x|xZx>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)的。即：<x,y>Rx和y在的同一劃分塊里。本題中，1的劃分塊都是單元集，沒有含兩個(gè)以上元素的劃分塊；第15頁，課件共100頁，創(chuàng)作于2023年2月例題選講

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第16頁，課件共100頁，創(chuàng)作于2023年2月例題選講然后，順序?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ù)。第17頁，課件共100頁，創(chuàng)作于2023年2月例題選講這種通過直線方程構(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的雙射，如下排列：第18頁，課件共100頁，創(chuàng)作于2023年2月例題選講

Z：0，-1，1，-2，2，-3，3，……. N：0，1，2，3，4，5，6，…….即：顯然f是從Z到N的雙射。第19頁，課件共100頁，創(chuàng)作于2023年2月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①第20頁，課件共100頁，創(chuàng)作于2023年2月同理：A-B=B-A

A∩～B=B∩～A

A∩～B∩A=B∩～A∩A

A∩～B=Φ

A-B=Φ

B

A②由①、②可得：A=B

第21頁，課件共100頁，創(chuàng)作于2023年2月【例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）。第22頁，課件共100頁，創(chuàng)作于2023年2月例如，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）。第23頁，課件共100頁，創(chuàng)作于2023年2月【例3.4.3】

設(shè)Ai是實(shí)數(shù)集合，它被定義為：則證明

（1）先證設(shè)則必存在某個(gè)自然數(shù)k，使x∈Ak，即則有x＜1，故x∈A0。所以第24頁，課件共100頁，創(chuàng)作于2023年2月（2）再證設(shè)x∈A0，即x＜1，故必有ε＞0，使x=1-ε，令則，即x∈Ak，所以故第25頁，課件共100頁，創(chuàng)作于2023年2月【例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

第26頁，課件共100頁，創(chuàng)作于2023年2月習(xí)題三1．證明：如果B∈{{a}}，那么a∈B。2．試用描述法表示下列集合：(1)小于5的非負(fù)整數(shù)集合。(2)10與20之間的素?cái)?shù)集合。(3)小于65的12的正倍數(shù)集合。(4）能被5整除的自然數(shù)的集合。第27頁，課件共100頁，創(chuàng)作于2023年2月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第28頁，課件共100頁，創(chuàng)作于2023年2月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)}

第29頁，課件共100頁，創(chuàng)作于2023年2月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。第30頁，課件共100頁，創(chuàng)作于2023年2月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。第31頁，課件共100頁，創(chuàng)作于2023年2月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。第32頁，課件共100頁，創(chuàng)作于2023年2月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）第33頁，課件共100頁，創(chuàng)作于2023年2月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ù)集合，它被定義為：證明：第34頁，課件共100頁，創(chuàng)作于2023年2月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整除。第35頁，課件共100頁，創(chuàng)作于2023年2月定理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)第36頁，課件共100頁，創(chuàng)作于2023年2月證明(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)第37頁，課件共100頁，創(chuàng)作于2023年2月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)系。第38頁，課件共100頁，創(chuàng)作于2023年2月【例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。第39頁，課件共100頁，創(chuàng)作于2023年2月""（再證充分性）(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是對稱的。第40頁，課件共100頁，創(chuàng)作于2023年2月(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是傳遞的。第41頁，課件共100頁，創(chuàng)作于2023年2月【例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。""（再證充分性）第42頁，課件共100頁，創(chuàng)作于2023年2月(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是對稱的。第43頁，課件共100頁，創(chuàng)作于2023年2月【例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反對稱。第44頁，課件共100頁，創(chuàng)作于2023年2月(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)系。第45頁，課件共100頁，創(chuàng)作于2023年2月【例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

第46頁，課件共100頁，創(chuàng)作于2023年2月圖4.11.1第47頁，課件共100頁，創(chuàng)作于2023年2月【例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}。第48頁，課件共100頁，創(chuàng)作于2023年2月圖4.11.2第49頁，課件共100頁，創(chuàng)作于2023年2月【例4.11.10】設(shè)f：A→B是函數(shù)，并定義一個(gè)函數(shù)g：B→P（A）。對于任意的b∈B，有

g（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）}第50頁，課件共100頁，創(chuàng)作于2023年2月因此有a1∈g（b1），a2(g（b2），但a1

g（b2），

a2g（b1），所以g（b1）≠g（b2），故g為單射。第51頁，課件共100頁，創(chuàng)作于2023年2月【例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是對稱的。第52頁，課件共100頁，創(chuàng)作于2023年2月③〈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)系。第53頁，課件共100頁，創(chuàng)作于2023年2月（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

因而φ是單射。第54頁，課件共100頁，創(chuàng)作于2023年2月又A∈P（X）-{}，A

X，A≠，取定元素a∈A，定義f：X→X為則φ（［f］R）=Ranf=A，因而φ是滿射。綜上所述，存在雙射φ：XX/R→P（X）-{}。第55頁，課件共100頁，創(chuàng)作于2023年2月【例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ù)合。）第56頁，課件共100頁，創(chuàng)作于2023年2月證明（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是滿射。第57頁，課件共100頁，創(chuàng)作于2023年2月（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是單射。第58頁，課件共100頁，創(chuàng)作于2023年2月【例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)锽。第59頁，課件共100頁，創(chuàng)作于2023年2月若有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）的單射。第60頁，課件共100頁，創(chuàng)作于2023年2月習(xí)題四1．已知A={},求P(A)×A。2．設(shè)A={1,2,3},R為實(shí)數(shù)集,請?jiān)诘芽▋浩矫嫔媳硎境鯝×R和R×A。3．以下各式是否對任意集合A，B，C，D均成立？試對成立的給出證明，對不成立的給出適當(dāng)?shù)姆蠢?。?1頁，課件共100頁，創(chuàng)作于2023年2月（1）(A-B)×C=(A×C)-(B×C)（2）(A∩B)×(C∩D)=(A×B)∩(C×D)（3）(A-B)×(C-D)＝(A×C)-(B×D)（4）(A∪B)×(C∪D)=(A×C)∪(B×D)第62頁，課件共100頁，創(chuàng)作于2023年2月4．設(shè)A,B,C,D為任意集合，求證：（1）若A

C，B

D，那么A×B

C×D。（2）若C,A×C

B×C，則A

B。（3）(A×B)-(C×D)＝((A-C)×B)∪(A×(B-D))。5．證明定理4.1.3中的（2）、（3）、（4）、（6）。6．證明定理4.1.4和定理4.1.5。第63頁，課件共100頁，創(chuàng)作于2023年2月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。第64頁，課件共100頁，創(chuàng)作于2023年2月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=k·y∧k∈N∧k＜2)}（5）R5={〈x,y〉|x(A∧y∈A∧(x=0∨2x＜3)}第65頁，課件共100頁，創(chuàng)作于2023年2月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)系矩陣。第66頁，課件共100頁，創(chuàng)作于2023年2月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，R2

1,R2

2。

第67頁，課件共100頁，創(chuàng)作于2023年2月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）。第68頁，課件共100頁，創(chuàng)作于2023年2月16．設(shè)R1,R2,R3,R4,R5都是整數(shù)集上的關(guān)系，且xR1y|x-y|=1xR2y

x·y＜0xR3y

x|y(x整除y)xR4y

x+y=5xR5y

x=y

n(n是整數(shù))請用T(True)和F(False)填寫表4.1。

第69頁，課件共100頁，創(chuàng)作于2023年2月表4.1第70頁，課件共100頁，創(chuàng)作于2023年2月17．證明定理4.4.2和定理4.4.6。18．設(shè)A={0，1，2，3}，R

A×A且

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)系？第71頁，課件共100頁，創(chuàng)作于2023年2月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,從而得到矛盾。第72頁，課件共100頁，創(chuàng)作于2023年2月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有第73頁，課件共100頁，創(chuàng)作于2023年2月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=。第74頁，課件共100頁，創(chuàng)作于2023年2月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）。第75頁，課件共100頁，創(chuàng)作于2023年2月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。第76頁，課件共100頁，創(chuàng)作于2023年2月34．設(shè)S={1,2,3,4,5}且A=S×S,在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)的。第77頁，課件共100頁，創(chuàng)作于2023年2月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)系。第78頁，課件共100頁，創(chuàng)作于2023年2月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是m

2的倍數(shù)。第79頁，課件共100頁，創(chuàng)作于2023年2月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

第80頁，課件共100頁，創(chuàng)作于2023年2月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}的下界和下確界。第81頁，課件共100頁，創(chuàng)作于2023年2月圖4.1第82頁，課件共100頁，創(chuàng)作于2023年2月圖4.2第83頁，課件共100頁，創(chuàng)作于2023年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}的上界、下界，上確界、下確界（如果有的話）。第84頁，課件共100頁，創(chuàng)作于2023年2月43．設(shè)R是集合A={a，b，c，d}上的偏序關(guān)系，關(guān)系矩陣為第85頁，課件共100頁，創(chuàng)作于2023年2月（1）寫出R的表達(dá)式；（2）畫出R的哈斯圖；（3）求子集B={a，b}關(guān)于R的上界和上確界。44．對下列每一條件構(gòu)造滿足該條件的有限集和無限集各一個(gè)。（1）非空有序集，其中有子集沒有最大元素。（2）非空有序集，其中有子集有下確界，但它沒有最小元素。（3）非空有序集，其中有一子集存在上界，但它沒有上確界。第86頁，課件共100頁，創(chuàng)作于2023年2月45．圖4.3給出了集合S={a,b,c,d}上的四個(gè)關(guān)系圖。請指出哪些是偏序關(guān)系圖，哪些是全序關(guān)系圖，哪些是良序關(guān)系圖，并對偏序關(guān)系圖畫出對應(yīng)的哈斯圖。第87頁，課件共100頁，創(chuàng)作于2023年2月圖4.3第88頁，課件共100頁，創(chuàng)作于2023年2月46．下列集合中哪些是偏序集合，哪些是全序集合，哪些是良序集合？（1）〈P(N),〉（2）〈P(N),〉（3）〈P{a},〉（4）〈P(),〉第89頁，課件共100頁，創(chuàng)作于2023年2月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′〉也是良序集。第90頁，課件共100頁，創(chuàng)作于2023年2月48．設(shè)〈A,≤〉為一有限全序集，|A|≥2，R是A×A上的關(guān)系，根據(jù)R下列各定義，確定〈A×A,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