1集合論簡介集合是數(shù)學(xué)中最基本的概念，又是數(shù)學(xué)各分支、自然科學(xué)及社會科學(xué)各領(lǐng)域的最普遍采用的描述工具。集合論在開關(guān)理論、形式語言、有限狀態(tài)機、編譯原理、數(shù)據(jù)庫原理等領(lǐng)域中有著廣泛的應(yīng)用。本篇介紹集合論的基礎(chǔ)知識，主要內(nèi)容包括集合的基本運算、序偶、關(guān)系、函數(shù)、基數(shù)等。2主要知識點關(guān)聯(lián)圖

有序化集合性質(zhì)互異性無序性確定性集合關(guān)系集合閉包關(guān)系等價關(guān)系范式元素計數(shù)表示方法哈斯圖集合運算笛卡爾積二元關(guān)系關(guān)系圖序偶相容關(guān)系范式偏序關(guān)系合取范式集合分劃商集關(guān)系性質(zhì)等價式函數(shù)等價類集合基數(shù)等勢優(yōu)勢函數(shù)性質(zhì)不可數(shù)集合一滿射可數(shù)集雙射單射關(guān)系矩陣閉包運算復(fù)合函數(shù)函數(shù)運算逆函數(shù)運算規(guī)律容斥原理特殊二元關(guān)系覆蓋冪集3第二篇集合論目錄第4章集合及其運算4.1集合的概念及其表示4.2集合的基本運算4.3集合中元素的計數(shù)4.4集合的應(yīng)用習(xí)題四實驗四集合的基本運算第5章二元關(guān)系5.1集合的笛卡爾積5.2二元關(guān)系5.3等價關(guān)系與集合的劃分5.4相容關(guān)系與集合的覆蓋*5.5偏序關(guān)系5.6關(guān)系的應(yīng)用習(xí)題五實驗五求關(guān)系的閉包第6章函數(shù)6.1函數(shù)的概念6.2逆函數(shù)與復(fù)合函數(shù)習(xí)題六實驗六函數(shù)的圖形可視化第7章集合的基數(shù)**7.1集合的等勢與優(yōu)勢7.2基數(shù)、可數(shù)集與不可數(shù)集習(xí)題七實驗七：自然數(shù)性質(zhì)的可視化表示4第4章集合及其運算

主要內(nèi)容：集合的基本概念（屬于、包含、冪集、空集、文氏圖等）；集合的基本運算（并、交、補、差等）；集合恒等式（集合運算的算律、恒等式的證明方法）。

教學(xué)要求：理解集合的概念，掌握集合的各種運算，掌握集合的恒等式證明方法。重點：集合恒等式難點：集合恒等式的證明實踐活動：集合運算的實現(xiàn)

54.1集合的概念及其表示4.1.1集合的概念集合的定義集合(Set)是指具有共同性質(zhì)的或適合一定條件的事物的全體。組成集合的對象稱為集合的成員（member）或元素（elements）。6常見的數(shù)的集合N—自然數(shù)集合Z—整數(shù)集合Q—有理數(shù)集合R—實數(shù)集合C—復(fù)數(shù)集合7集合的表示法枚舉法----通過列出全體元素來表示集合謂詞法----通過謂詞概括集合元素的性質(zhì)圖示法----用一個圓來表示集合,圓中的點表示集合中的元素.實例：枚舉法自然數(shù)集合N={0,1,2,3,…}謂詞法S={x|x是實數(shù)，x2

1=0}8集合的元素三個重要的性質(zhì)：互異性-集合的元素是彼此不同的，如果同一個元素在集合中多次出現(xiàn)應(yīng)該認為是一個元素。 例如：{1，1，2，2，3}＝{1，2，3}無序性-集合的元素是無序的。 例如：{1，2，3}＝{3，1，2}確定性-集合的元素是確定的9例4.1.1

（1）一個班級里的全體學(xué)生構(gòu)成一個集合；（2）平面上的所有點構(gòu)成一個集合；（3）方程x2-1=0的實數(shù)解構(gòu)成一個集合；（4）自然數(shù)的全體（包含0）構(gòu)成一個集合，用N表示；（5）整數(shù)的全體構(gòu)成一個集合，用Z表示；（6）有理數(shù)的全體構(gòu)成一個集合，用Q表示；（7）實數(shù)的全體構(gòu)成一個集合，用R表示；（8）復(fù)數(shù)的全體構(gòu)成一個集合，用C表示；（9）還有正整數(shù)集合Z+，正有理數(shù)集合Q+，正實數(shù)集合R+；（10）還有非零整數(shù)集合Z*，非零有理數(shù)集合Q*，非零實數(shù)集合R*。（11）所有n階實矩陣構(gòu)成一個集合，用

表示，即而所有n階可逆實矩陣也構(gòu)成一個集合，用表示。 10元素和集合之間的關(guān)系元素和集合之間的關(guān)系是隸屬關(guān)系，即屬于或不屬于，屬于記作∈，不屬于記作

。例如：A＝{a，{b，c}，d，{z3jilz61osys}} a∈A，{b，c}∈A，d∈A，{z3jilz61osys}∈A，

b

A，z3jilz61osys

A。

b和z3jilz61osys是A的元素的元素?？梢杂靡环N樹形圖表示集合與元素的隸屬關(guān)系。隸屬關(guān)系可以看作是處在不同層次上的集合之間的關(guān)系。規(guī)定：對任何集合A都有A

A。Aa{b,c}d{z3jilz61osys}bcz3jilz61osysd說明11集合與集合之間的關(guān)系定義4.1.1設(shè)A，B為集合，如果B中的每個元素都是A中的元素，則稱B是A的子集合，簡稱子集(subset)。這時也稱B被A包含，或A包含B，記作B

A。包含的符號化表示:B

A

x(x∈B→x∈A)如果B不被A包含，則記作BA。

例如：N

Z

Q

R

C，但ZN。

顯然對任何集合A都有A

A。12隸屬和包含的說明隸屬關(guān)系和包含關(guān)系都是兩個集合之間的關(guān)系，對于某些集合可以同時成立這兩種關(guān)系。例如A＝{a，{a}}和{a}

既有{a}∈A，又有{a}

A。 前者把它們看成是不同層次上的兩個集合， 后者把它們看成是同一層次上的兩個集合。13集合相等(equal)定義4.1.2設(shè)A，B為集合，如果A

B且B

A，則稱A與B相等，記作A＝B。相等的符號化表示為：A＝B

A

B∧B

A如果A與B不相等，則記作A≠B。14真子集定義4.1.3設(shè)A，B為集合，如果B

A且B≠A，則稱B是A的真子集，記作B

A。真子集的符號化表示為

B

A

B

A∧B≠A如果B不是A的真子集，則記作B

A。 例如：N

N

15空集(emptyset)定義4.1.4不含任何元素的集合叫做空集，記作

?？占姆柣硎緸椋?/p>

＝{x|x≠x}。例如:{x|x∈R∧x2+1=0}

是方程x2+1=0的實數(shù)解集，因為該方程無實數(shù)解，所以是空集。16空集的性質(zhì)推論空集是唯一的。證明：假設(shè)存在空集

1和

2，由定理6.1有

1

2，

2

1。 根據(jù)集合相等的定義，有

1＝

2。定理4.1.1

空集是一切集合的子集。證明：任給集合A，由子集定義有

A

x(x∈

→x∈A)

右邊的蘊涵式因前件假而為真命題， 所以

A也為真。17n元集含有n個元素的集合簡稱n元集，它的含有m(m≤n)個元素的子集叫做它的m元子集。例4.1.2A＝{1,2,3}，將A的子集分類：0元子集（空集）

1元子集（單元集）{1}，{2}，{3}2元子集{1,2}，{1,3}，{2,3}3元子集{1,2,3}18冪集(powerset)一般地說，對于n元集A，它的0元子集有個，1元子集有個，…，m元子集有個，…，n元子集有個。子集總數(shù)為定義4.1.5

設(shè)A為集合，把A的全部子集構(gòu)成的集合叫做A的冪集，記作P(A)(或2A)。冪集的符號化表示為P(A)＝{x|x

A}若A是n元集，則P(A)有2n

個元素。19全集在一個具體問題中，如果所涉及的集合都是某個集合的子集，則稱這個集合為全集，記作E。說明全集是有相對性的，不同的問題有不同的全集，即使是同一個問題也可以取不同的全集。例如，在研究平面上直線的相互關(guān)系時，可以把整個平面(平面上所有點的集合)取作全集，也可以把整個空間(空間上所有點的集合)取作全集。一般地說，全集取得小一些，問題的描述和處理會簡單些。204.2

集合的運算定義4.2.1設(shè)A，B為集合，A與B的并集A∪B，A與B的交集A∩B，B對A的相對補集A－B分別定義如下：

A∪B＝{x|x∈A∨x∈B}(unionset) A∩B＝{x|x∈A∧x∈B} (intersectionset)A－B＝{x|x∈A∧x

B}

(differenceset)舉例設(shè)A＝{a，b，c}，B＝{a}，C＝{b，d}則有

A∪B＝{a，b，c}，A∩B＝{a}，

A－B＝{b，c}，

B－A＝

，B∩C＝

說明如果兩個集合的交集為

，則稱這兩個集合是不相交的。例如B和C是不相交的。21定理4.2.1設(shè)A，B，C為任意三個集合，則⑴冪等律

A∪A=A；⑵交換律A∪B=B∪A；⑶結(jié)合律

(A∪B)∪C=A∪(B∪C)；⑷同一律

A∪Φ=A；⑸零律A∪E=E；⑹A

A∪B，B

A∪B；⑺A∪B=BA

B。證明：性質(zhì)⑴，⑵，⑷，⑸，⑹由定義4.2.1立即可以得到。22⑶的證明：(A∪B)∪C＝{x|x∈(A∪B)∪C}={x|(x∈A∪B)∨(x∈B)

}

＝{x|

((x∈A)∨(x∈B))∨(x∈B)}={x|(x∈A)∨((x∈B)∨(x∈C))}={x|(x∈A)∨(x∈B∪C)}={x|x∈A∪(B∪C)}=A∪(B∪C)

。

⑺的證明：必要性證明:所以A

B。充分性證明:由⑹知B

A∪B，現(xiàn)證明

A∪B

B

所以有

A∪B=B。

23定理4.2.2設(shè)A,B,C是任意三個集合，則(1)冪等律

A∩A=A；(2)交換律

A∩B=B∩A

；(3)結(jié)合律(A∩B)∩C=A∩(B∩C)；(4)零律Φ∩A=Φ；(5)同一律E∩A=A；(6)A∩B

A,A∩B

B

；(7)A∩B=AA

B。證明略。

24n個集合的并和交兩個集合的并和交運算可以推廣成n個集合的并和交：

A1∪A2∪…∪An＝{x|x∈A1∨x∈A2∨…∨x∈An} A1∩A2∩…∩An＝{x|x∈A1∧x∈A2∧…∧x∈An}

上述的并和交可以簡記為：＝A1∩A2∩…∩An＝A1∪A2∪…∪An兩個集合的并和交運算可以推廣到無窮多個集合的情況：＝A1∩A2∩…＝A1∪A2∪…25交運算與并運算之間的關(guān)系

定理4.2.3（分配律）設(shè)A,B,C為任意三個集合，滿足（1）交運算對并運算的分配律（2）并運算對交運算的分配律26證明：（1）A∩(B∪C)

=

{x|x∈A∩(B∪C)}

={x|(x∈A)∧(x∈B∪C)}

={x|(x∈A)∧(（x∈B）∨(x∈C))}=

{x|((x∈A)∧(x∈B))∨((x∈A)∧(x∈C))}={x|(x∈A∩B)∨(x∈A∩C)}={x|x∈(A∩B)∪(A∩C)}=(A∩B)∪(A∩C)（2）略27定理4.2.4

（吸收律）設(shè)A,B為任意兩集合，則（1）A∪(A∩B)=A；（2）A∩(A∪B)

=A

；證明：由分配律可得（1）A∪(A∩B)

=(A∩E)∪(A∩B)

=A∩(E∪B)=A∩E=A（2）A∩(A∪B)

=

(A∪Φ)∩(A∪B)=A∪(Φ∩B)=A∪Φ=A

28絕對補集定義4.2.3

＝E－A＝{x|x∈E∧x

A}因為E是全集，x∈E是真命題，所以可以定義為：＝{x|x

A}例如:E＝{a，b，c，d}，A＝{a，b，c}＝z3jilz61osys例4.2.4

設(shè)E={1，2，3，4，5，6}，A={1，2，6}，B={1，4，5}則A-B={2，6}，

={3，4，5}。

29定理4.2.5

設(shè)A,B,C

為任意三集合，則（1）對合律；（2）（3）（4）排中律；（5）矛盾律；（6）(De.MorgAn定理)①②（7）①②（8）（9）若，當(dāng)且僅當(dāng)①②

303132對稱差集定義4.2.2設(shè)A，B為集合，A與B的對稱差集

A

B定義為：

A

B＝(A－B)∪(B－A)對稱差運算的另一種定義是

A

B＝(A∪B)－(A∩B)例如:A＝{a，b，c}，B＝{b，d}， 則 A

B＝{a，c，d}33定理4.2.6

設(shè)A,B,C為任意三集合，則（1）（2）（3）（4）（5）（6）交關(guān)于對稱差的分配律（7）若，則B=C

。

證明：由對稱差的定義立即可得（1），（2），（3），（4）的結(jié)論。343536集合恒等式

下面的恒等式給出了集合運算的主要算律，其中A，B，C代表任意集合。 冪等律A∪A＝A

(4.1)

A∩A＝A

(4.2)

結(jié)合律(A∪B)∪C＝A∪(B∪C)

(4.3)

(A∩B)∩C＝A∩(B∩C)(4.4)

交換律A∪B＝B∪A

(4.5)

A∩B＝B∩A

(4.6)

分配律A∪(B∩C)＝(A∪B)∩(A∪C)

(4.7)

A∩(B∪C)＝(A∩B)∪(A∩C)

(4.8)

同一律A∪

＝A

(4.9)

A∩E＝A

(4.10)37零律A∪E＝EA∩

＝

排中律A∪～A＝E矛盾律A∩～A＝

吸收律A∪(A∩B)＝AA∩(A∪B)＝A德摩根律A－(B∪C)＝(A－B)∩(A－C)A－(B∩C)＝(A－B)∪(A－C)

～(B∪C)＝～B∩～C～(B∩C)＝～B∪～C～

＝E～E＝

雙重否定律

～(～A)＝A(4.11)(4.12)(4.13)(4.14)(4.15)(4.16)(4.17)(4.18)(4.19)(4.20)(4.21)(4.22)(4.23)38集合運算性質(zhì)的一些重要結(jié)果A∩B

A，A∩B

B(4.24)A

A∪B，B

A∪B

(4.25)A－B

A

(4.26)A－B＝A∩～B

(4.27)A∪B＝B

A

B

A∩B＝A

A－B＝

(4.28)A

B＝B

A

(4.29)(A

B)

C＝A

(B

C)

(4.30)A

＝A(4.31)A

A＝

(4.32)A

B＝A

C

B＝C(4.33)39集合恒等式的證明方法邏輯演算法 利用邏輯等值式和推理規(guī)則集合演算法 利用集合恒等式和已知結(jié)論40邏輯演算法的格式題目：A＝B證明：

x，

x∈A

…

… x∈B

所以A＝B或證P

Q∧Q

P題目：A

B證明：

x，

x∈A

…

…

x∈B

所以A

B41集合演算法的格式題目：A＝B證明：A

＝…

…

＝B

所以A＝B題目：A

B證明：A

…

…

B

所以A

B42例

證明A－(B∪C)＝(A－B)∩(A－C)證明

對任意的x，有

x∈A－(B∪C)

x∈A∧x

B∪C

x∈A∧┐(x∈B∨x∈C)

x∈A∧(┐x∈B∧┐x∈C)

x∈A∧(x

B∧x

C)

(x∈A∧x

B)∧(x∈A∧x

C)

x∈A－B∧x∈A－C

x∈(A－B)∩(A－C)

所以A－(B∪C)＝(A－B)∩(A－C)43例

證明式4.10，即A∩E＝A證明

對任意的x，有

x∈A∩E

x∈A∧x∈E

x∈A(因為x∈E是恒真命題)

所以A∩E＝A44例

假設(shè)已知等式4.1～4.14，試證等式4.15，

即A∪(A∩B)＝A。證明A∪(A∩B)

＝(A∩E)∪(A∩B)(由等式4.10)

＝A∩(E∪B)(由等式4.8)

＝A∩(B∪E)(由等式4.5)

＝A∩E(由等式4.11)

＝A(由等式4.10)45例

證明等式A－B＝A∩～B證明對于任意的x，有

x∈A－B

x∈A∧x

B

x∈A∧x∈～B

x∈A∩～B

所以A－B＝A∩～B。說明等式4.27把相對補運算轉(zhuǎn)換成交運算，這在證明有關(guān)相對補的恒等式中是很有用的。46例

證明(A－B)∪B＝A∪B證明(A－B)∪B

＝(A∩～B)∪B

＝(A∪B)∩(～B∪B)

＝(A∪B)∩E

＝A∪B47證明 A∪B＝B

A

B

對于任意的x，有

x∈A

x∈A∨x∈B

x∈A∪B

x∈B(因為A∪B＝B)

所以A

B。

48文氏圖(VennDiagram)集合之間的關(guān)系和運算可以用文氏圖給予形象的描述。文氏圖的構(gòu)造方法如下：畫一個大矩形表示全集E(有時為簡單起見可將全集省略)。在矩形內(nèi)畫一些圓(或任何其它的適當(dāng)?shù)拈]曲線)，用圓的內(nèi)部表示集合。不同的圓代表不同的集合。如果沒有關(guān)于集合不交的說明，任何兩個圓彼此相交。圖中陰影的區(qū)域表示新組成的集合?？梢杂脤嵭狞c代表集合中的元素。49文氏圖的實例集合的各種運算的文氏圖

50集合的計算機表示

假設(shè)全集E是有限的。首先為E的元素規(guī)定一個順序，例如。于是可以用長度為n的位串表示E的子集A：如果ai屬于A，則位串中第i位是1；如果ai不屬于A，則位串中第i位是0。514.3集合中元素的計數(shù)使用文氏圖可以很方便地解決有窮集的計數(shù)問題。首先根據(jù)已知條件把對應(yīng)的文氏圖畫出來。一般地說，每一條性質(zhì)決定一個集合。有多少條性質(zhì)，就有多少個集合。如果沒有特殊說明，任何兩個集合都畫成相交的然后將已知集合的元素數(shù)填入表示該集合的區(qū)域內(nèi)。通常從n個集合的交集填起，根據(jù)計算的結(jié)果將數(shù)字逐步填入所有的空白區(qū)域。如果交集的數(shù)字是未知的，可以設(shè)為x。根據(jù)題目中的條件，列出一次方程或方程組，就可以求得所需要的結(jié)果。52例4.3.1

對24名會外語的科技人員進行掌握外語情況的調(diào)查。其統(tǒng)計結(jié)果如下：會英、日、德和法語的人分別為13，5，10和9人，其中同時會英語和日語的有2人，會英、德和法語中任兩種語言的都是4人。已知會日語的人既不懂法語也不懂德語，分別求只會一種語言(英、德、法、日)的人數(shù)和會三種語言的人數(shù)。解：令A(yù)，B，C，D分別表示會英、法、德、日語的人的集合。根據(jù)題意畫出文氏圖。設(shè)同時會三種語言的有x人，只會英、法或德語一種語言的分別為y1，y2和y3人。將x和y1，y2，y3填入圖中相應(yīng)的區(qū)域，然后依次填入其它區(qū)域的人數(shù)。534-x4-x4-xxy2y1y325-2英13法9德10日5y1+2(4-x)+x+2＝13y2+2(4-x)+x＝9y3+2(4-x)+x＝10y1+y2+y3+3(4-x)+x＝24-554包含排斥原理定理4.3.5

設(shè)S為有窮集，P1,P2,…,Pm是m個性質(zhì)。S中的任何元素x或者具有性質(zhì)Pi，或者不具有性質(zhì)Pi(i=1,2,…m),兩種情況必居其一。令A(yù)i表示S中具有性質(zhì)Pk的元素構(gòu)成的子集，則S中不具有性質(zhì)P1,P2,…,Pm的元素為55推論S中至少具有一條性質(zhì)的元素數(shù)為56例4.3.2

求1到1000之間(包含1和1000在內(nèi))既不能被5和6，也不能被8整除的數(shù)有多少個。解: 設(shè)

S＝{x|x∈Z∧1≤x≤1000}A＝{x|x∈S∧x可被5整除}B＝{x|x∈S∧x可被6整除}C＝{x|x∈S∧x可被8整除} |T|表示有窮集T中的元素數(shù)

x表示小于等于x的最大整數(shù)

lcm(x1,x2,…,xn)表示x1,x2,…,xn的最小公倍數(shù) 57|A|＝

1000/5＝200|B|＝

1000/6＝166|C|＝

1000/8＝125|A∩B|＝

1000/lcm(5,6)

＝33|A∩C|＝

1000/lcm(5,8)

＝25|B∩C|＝

1000/lcm(6,8)

＝41|A∩B∩C|＝

1000/lcm(5,6,8)

＝8將這些數(shù)字依次填入文氏圖，得到58根據(jù)包含排斥原理，所求不能被5，6和8整除的數(shù)應(yīng)為由文氏圖也可得知，不能被5，6和8整除的數(shù)有

1000－(200+100＋33＋67)＝600個。594.4集合的應(yīng)用

關(guān)系數(shù)據(jù)庫的基本對象是表,表又是若干記錄(或稱為元組)的集合。關(guān)系數(shù)據(jù)庫中的關(guān)系操作是基于表的操作,其中一類關(guān)系操作就是傳統(tǒng)的數(shù)學(xué)集合運算,包括并、交和差。數(shù)學(xué)集合在關(guān)系數(shù)據(jù)庫中的作用十分明顯,能夠利用已知的數(shù)據(jù)表通過該運算產(chǎn)生新的結(jié)構(gòu)相同的數(shù)據(jù)表,使用結(jié)果數(shù)據(jù)表可以進行某些記錄的刪除操作,來避免數(shù)據(jù)表中數(shù)據(jù)的冗余,又可以進行提取操作,來快速提取滿足特殊要求的數(shù)據(jù)等。60作業(yè)：習(xí)題四

2，3，4，5，6，7，8，9，10，11，1261實驗四：集合的基本運算

1.實驗?zāi)康?熟悉實現(xiàn)集合的并、交和差等基本運算。2.實驗內(nèi)容編程實現(xiàn)集合的并、交和差等基本運算。3.實驗要求列出實驗?zāi)康?、實驗?nèi)容、實驗步驟、源程序和實驗結(jié)果。4.實驗參考62第五章二元關(guān)系主要內(nèi)容：序偶與笛卡兒積；二元關(guān)系的定義和表示；關(guān)系的運算；關(guān)系的性質(zhì)；關(guān)系的閉包；等價關(guān)系與劃分；相容關(guān)系與集合的覆蓋；偏序關(guān)系；關(guān)系的應(yīng)用。教學(xué)要求：掌握序偶與笛卡爾積概念；掌握關(guān)系，關(guān)系矩陣和關(guān)系圖；掌握關(guān)系的運算；掌握關(guān)系的性質(zhì)；掌握關(guān)系的閉包運算；理解等價關(guān)系與等價類；理解偏序概念，會作哈斯圖；了解相容關(guān)系與集合的覆蓋、關(guān)系的應(yīng)用。重點：序偶與笛卡爾積；關(guān)系；關(guān)系的運算；關(guān)系的性質(zhì)；關(guān)系的閉包運算；等價關(guān)系，偏序及哈斯圖。難點：關(guān)系的運算、性質(zhì)、閉包運算；偏序及哈斯圖。實踐活動：關(guān)系閉包運算的實現(xiàn)

635.1序偶與笛卡兒積

定義5.1.1由兩個元素x和y（允許x=y）按一定順序排列成的二元組叫做一個有序?qū)?orderedpair)或序偶，記作<x,y>，其中x是它的第一元素，y是它的第二元素。有序?qū)?lt;x,y>具有以下性質(zhì)：（1）當(dāng)x≠y時，<x,y>≠<y,x>。（2）<x,y>＝<u,v>的充分必要條件是x＝u且y＝v。說明有序?qū)χ械脑厥怯行虻募现械脑厥菬o序的64例5.1.1例5.1.1已知<x+2,4>＝<5,2x+y>，求x和y。由有序?qū)ο嗟鹊某湟獥l件有

x+2＝5

2x+y＝4解得x＝3,y＝-2。解答65定義5.1.2設(shè)A，B為集合,用A中元素為第一元素，B中元素為第二元素構(gòu)成有序?qū)ΑＫ羞@樣的有序?qū)M成的集合叫做A和B的笛卡兒積(Cartesianproduct)，記作A×B。笛卡兒積的符號化表示為A×B＝{<x,y>|x∈A∧y∈B}

笛卡兒積的定義A表示某大學(xué)所有學(xué)生的集合，B表示大學(xué)開設(shè)的所有課程的集合， 則A×B可以用來表示該校學(xué)生選課的所有可能情況。令A(yù)是直角坐標(biāo)系中x軸上的點集，B是直角坐標(biāo)系中y軸上的點集， 于是A×B就和平面點集一一對應(yīng)。舉例66笛卡爾積舉例設(shè)A={a,b},B={0,1,2}，則A×B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}B×A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}舉例說明如果|A|=m,|B|=n,則|A×B|=mn。6768笛卡兒積的運算性質(zhì)(1)對任意集合A，根據(jù)定義有

A×＝,

×A＝

(2)一般的說，笛卡兒積運算不滿足交換律，即 A×B≠B×A (當(dāng)A≠

∧B≠

∧A≠B時)(3)笛卡兒積運算不滿足結(jié)合律，即 (A×B)×C≠A×(B×C) (當(dāng)A≠

∧B≠

∧C≠

時)69(4)笛卡兒積運算對并和交運算滿足分配律，即

A×(B∪C)=(A×B)∪(A×C)

(B∪C)×A=(B×A)∪(C×A)

A×(B∩C)=(A×B)∩(A×C)

(B∩C)×A=(B×A)∩(C×A)(5)A

C∧B

D

A×B

C×D70A×(B∪C)=(A×B)∪(A×C)的證明 任取<x,y> <x,y>∈A×(B∪C)

x∈A∧y∈B∪Cx∈A∧(y∈B∨y∈C)(x∈A∧y∈B)∨(x∈A∧y∈C)<x,y>∈A×B∨<x,y>∈A×C<x,y>∈(A×B)∪(A×C)所以A×(B∪C)=(A×B)∪(A×C)71關(guān)于A

C∧B

D

A×B

C×D的討論該性質(zhì)的逆命題不成立，可分以下情況討論。（1）當(dāng)A=B=

時，顯然有A

C和B

D成立。（2）當(dāng)A≠

且B≠

時，也有A

C和B

D成立，證明如下： 任取x∈A，由于B≠

,必存在y∈B,因此有 x∈A∧y∈B

<x,y>∈A×B

<x,y>∈C×D

x∈C∧y∈D

x∈C 從而證明了A

C。 同理可證B

D。72關(guān)于A

C∧B

D

A×B

C×D的討論該性質(zhì)的逆命題不成立，可分以下情況討論。（3）當(dāng)A＝

而B≠

時，有A

C成立，但不一定有B

D成立。 反例：令A(yù)＝

,B＝{1},C＝{3},D＝{4}。（4）當(dāng)A≠

而B＝

時，有B

D成立，但不一定有A

C成立。 反例略。73例5.1.2例5.1.2

設(shè)A={1,2},求P(A)×A。P(A)×A＝ {

,{1},{2},{1,2}}×{1,2}＝ {<

,1>,<

,2>, <{1},1>,<{1},2>, <{2},1>,<{2},2>, <{1,2},1>,<{1,2},2>}

解答74例5.1.3例5.1.3

設(shè)A，B，C，D為任意集合，判斷以下命題是否為真，并說明理由。

(1)A×B＝A×C

B＝C

(2)A-(B×C)＝(A-B)×(A-C)

(3)A＝B∧C＝D

A×C＝B×D

(4)存在集合A，使得A

A×A(1)不一定為真。當(dāng)A＝

，B＝{1},C＝{2}時，有

A×B＝＝A×C，但B≠C。(2)不一定為真。當(dāng)A=B={1},C＝{2}時，有A-(B×C)＝{1}–{<1,2>}＝{1}

(A-B)×(A-C)＝

×{1}＝

(3)為真。由等量代入的原理可證。(4)為真。當(dāng)A＝

時，有A

A×A成立。解答755.2二元關(guān)系(binaryrelation)定義5.2.1如果一個集合滿足以下條件之一： （1）集合非空，且它的元素都是有序?qū)?/p>

（2）集合是空集則稱該集合為一個二元關(guān)系，記作R。二元關(guān)系也可簡稱為關(guān)系。對于二元關(guān)系R，如果<x,y>∈R，可記作xRy；如果<x,y>

R，則記作xRy。設(shè)R1＝{<1,2>,<a,b>}，R2＝{<1,2>,a,b}。則R1是二元關(guān)系，R2不是二元關(guān)系，只是一個集合，除非將a和b定義為有序?qū)Α８鶕?jù)上面的記法可以寫1R12，aR1b，aR1c等。舉例76集合A上的二元關(guān)系的數(shù)目依賴于A中的元素數(shù)。如果|A|=n，那么|A×A|=n2，A×A的子集就有個。每一個子集代表一個A上的二元關(guān)系，所以A上有個不同的二元關(guān)系。例如|A|=3，則A上有個不同的二元關(guān)系。定義5.2.2

設(shè)A，B為集合，A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系；特別當(dāng)A=B時，則叫做A上的二元關(guān)系.

A={0,1}，B={1,2,3}，那么 R1={<0,2>}，R2=A×B，R3=

，R4={<0,1>}等都是從A到B的二元關(guān)系，而R3和R4同時也是A上的二元關(guān)系。舉例說明77定義5.6設(shè)R是二元關(guān)系。(1)R中所有有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義域(domain)，記為domR。形式化表示為：

domR＝

{x|

y(<x,y>∈R

)}(2)R中所有有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域(range)

，記作ranR。形式化表示為

ranR＝{y|

x(<x,y>∈R)}(3)R的定義域和值域的并集稱為R的域(field)，記作fldR。形式化表示為

fldR＝domR∪ranR

78例5.2.1求R={<1,2>,<1,3>,<2,4>,<4,3>}的定義域、值域和域。

解

domR＝{1,2,4}ranR＝{2,3,4}fldR＝{1,2,3,4}

79常用的關(guān)系定義5.2.3對任意集合A，定義

全域關(guān)系

EA={<x,y>|x∈A∧y∈A}=A×A

恒等關(guān)系

IA={<x,x>|x∈A}

空關(guān)系

設(shè)A={1,2}，那么EA={<1,1>,<1,2>,<2,1>,<2,2>}IA={<1,1>,<2,2>}

舉例80其它常用的關(guān)系小于或等于關(guān)系：LA={<x,y>|x,y∈A∧x≤y}，其中A

R。整除關(guān)系：DB={<x,y>|x,y∈B∧x整除y},其中A

Z*

Z*是非零整數(shù)集包含關(guān)系：R

＝{<x,y>|x,y∈A∧x

y},其中A是集合族。(1)設(shè)A={1,2,3}，B＝{a,b}則LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}(2)令A(yù)=P(B)={

,{a},,{a,b}}，則A上的包含關(guān)系是R

＝{<

,

>,<

,{a}>,<

,>,<

,{a,b}>,

<{a},{a}>,<{a},{a,b}>,<,>,

<,{a,b}>,<{a,b},{a,b}>}舉例81例5.2.2例5.2.2設(shè)A={1,2,3,4}，下面各式定義的R都是A上的關(guān)系，試用列元素法表示R。 (1)R={<x,y>|x是y的倍數(shù)}

(2)R={<x,y>|(x-y)2∈A}

(3)R={<x,y>|x/y是素數(shù)}

(4)R={<x,y>|x≠y}解答(1)R={<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>}(2)R={<2,1>,<3,2>,<4,3>,<3,1>,<4,2>,<2,4>,<1,3>,<3,4>,

<2,3>,<1,2>}(3)R={<2,1>,<3,1>,<4,2>}(4)R=EA-IA={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,

<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}82關(guān)系的表示方法關(guān)系的三種表示方法：集合表達式關(guān)系矩陣關(guān)系圖關(guān)系矩陣和關(guān)系圖可以表示有窮集上的關(guān)系。83關(guān)系矩陣和關(guān)系圖的定義設(shè)A={x1,x2,…,xn},R是A上的關(guān)系。令則是R的關(guān)系矩陣，記作MR。設(shè)A={x1,x2,…,xn},R是A上的關(guān)系。令圖G=<V,E>，其中頂點集合V=A，邊集為E。對于

xi,xj∈V，滿足 <xi,xj>∈E

xiRxj稱圖G為R的關(guān)系圖，記作GR。84關(guān)系矩陣和關(guān)系圖的實例設(shè)A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，

則R的關(guān)系矩陣和關(guān)系圖分別是85關(guān)系的并、交、補、差、對稱差等運算關(guān)系也是集合,故關(guān)系可以做并、交、補、差、對稱差和包含等運算。8687關(guān)系的復(fù)合運算說明可以把二元關(guān)系看作一種作用，<x,y>∈R可以解釋為x通過R的作用變到y(tǒng)。R

S表示兩個作用的連續(xù)發(fā)生。888990919293949596關(guān)系與集合的說明關(guān)系是集合，集合運算對于關(guān)系也是適用的。規(guī)定：關(guān)系運算中逆運算優(yōu)先于其它運算所有的關(guān)系運算都優(yōu)先于集合運算，優(yōu)先權(quán)的運算以括號決定運算順序。例如：ranF-1F

G∪F

H97例題設(shè)A表示是學(xué)校的所有學(xué)生的集合，B表示學(xué)校的所有課程的集合，并設(shè)R1由所有有序?qū)?lt;a,b>組成，其中a是選修課程b的學(xué)生。R2由所有的有序?qū)?lt;a,b>構(gòu)成，其中課程b是a的必修課。則關(guān)系R1∪R2、R1∩R2、R1⊕R2、R1－R2、R2－R1的含義分別為：R1∪R2：a是一個學(xué)生，他或者選修了課程b，或者課程b是他的必修課。R1∩R2：a是一個學(xué)生，他選修了課程b并且課程b也是a的必修課。98R1⊕R2：學(xué)生a已經(jīng)選修了課程b，但課程b不是a的選修課，或者課程b是a的必修課，但是a沒有選修它。R1－R2：學(xué)生a已經(jīng)選修了課程b，但課程b不是a的選修課。R2－R1：課程b是學(xué)生a的必修課，但是a沒有選修它。99關(guān)系的性質(zhì)自反性反自反性對稱性反對稱性傳遞性100自反性和反自反性定義5.2.5設(shè)R為A上的關(guān)系，(1)若

x(x∈A→<x,x>∈R)，則稱R在A上是自反(reflexivity)的。(2)若

x(x∈A→<x,x>

R)，則稱R在A上是反自反(irreflexivity)的。例如全域關(guān)系EA，恒等關(guān)系IA，小于等于關(guān)系LA，整除關(guān)系DA都是為A上的自反關(guān)系。 包含關(guān)系R是給定集合族A上的自反關(guān)系。 小于關(guān)系和真包含關(guān)系都是給定集合或集合族上的反自反關(guān)系。101例5.2.4例5.2.4設(shè)A={1,2,3}，R1，R2，R3是A上的關(guān)系，其中

R1＝{<1,1>,<2,2>}R2＝{<1,1>,<2,2>,<3,3>,<1,2>}R3＝{<1,3>} 說明R1，R2和R3是否為A上的自反關(guān)系和反自反關(guān)系。解答 R1既不是自反的也不是反自反的， R2是自反的， R3是反自反的。 102對稱性和反對稱性定義5.2.6設(shè)R為A上的關(guān)系，（1）若

x

y(x,y∈A∧<x,y>∈R→<y,x>∈R)，則稱R為A上對稱(symmetry)的關(guān)系。（2）若

x

y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y)，則稱R為A上的反對稱(antisymmetry)關(guān)系。例如

A上的全域關(guān)系EA，恒等關(guān)系IA和空關(guān)系都是A上的對稱關(guān)系。

恒等關(guān)系IA和空關(guān)系也是A上的反對稱關(guān)系。 但全域關(guān)系EA一般不是A上的反對稱關(guān)系，除非A為單元集或空集。103例5.2.5例5.2.5設(shè)A＝{1,2,3}，R1，R2，R3和R4都是A上的關(guān)系，其中R1＝{<1,1>,<2,2>};R2＝{<1,1>,<1,2>,<2,1>};R3＝{<1,2>,<1,3>};R4＝{<1,2>,<2,1>,<1,3>} 說明R1，R2，R3和R4是否為A上對稱和反對稱的關(guān)系。解答 R1既是對稱也是反對稱的。 R2是對稱的但不是反對稱的。 R3是反對稱的但不是對稱的。 R4既不是對稱的也不是反對稱的。104傳遞性定義5.2.7設(shè)R為A上的關(guān)系，若

x

y

z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)則稱R是A上的傳遞(transitivity)關(guān)系。例如

A上的全域關(guān)系EA,恒等關(guān)系IA和空關(guān)系都是A上的傳遞關(guān)系。 小于等于關(guān)系，整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的傳遞關(guān)系。 小于關(guān)系和真包含關(guān)系仍舊是相應(yīng)集合上的傳遞關(guān)系。105例5.2.6例5.2.6設(shè)A＝{1,2,3}，R1，R2，R3是A上的關(guān)系，其中

R1＝{<1,1>,<2,2>}R2＝{<1,2>,<2,3>}R3＝{<1,3>} 說明R1，R2和R3是否為A上的傳遞關(guān)系。解答

R1和R3是A上的傳遞關(guān)系， R2不是A上的傳遞關(guān)系。106關(guān)系性質(zhì)的等價描述定理5.2.6設(shè)R為A上的關(guān)系，則（1）R在A上自反當(dāng)且僅當(dāng)IA

R（2）R在A上反自反當(dāng)且僅當(dāng)R∩IA＝

（3）R在A上對稱當(dāng)且僅當(dāng)R＝R-1（4）R在A上反對稱當(dāng)且僅當(dāng)R∩R-1

IA（5）R在A上傳遞當(dāng)且僅當(dāng)R

R

R說明利用該定理可以從關(guān)系的集合表達式來判斷或證明關(guān)系的性質(zhì)。分析關(guān)系性質(zhì)的證明方法107定理5.2.6(1)的證明（1）R在A上自反當(dāng)且僅當(dāng)IA

R必要性。任取<x,y>，有<x,y>∈IA

x,y∈A∧x＝y(tǒng)

<x,y>∈R所以IA

R充分性。任取x，有x∈A

<x,x>∈IA

<x,x>∈R所以R在A上是自反的。108定理5.2.6(2)的證明（2）R在A上反自反當(dāng)且僅當(dāng)R∩IA＝

充分性。任取x，有x∈A

<x,x>∈IA

<x,x>

R(R∩IA=

)所以R在A上是反自反的。必要性。用反證法。假設(shè)R∩IA≠

，必存在<x,y>∈R∩IA。由于IA是A上恒等關(guān)系，可知x∈A且<x,x>∈R。這與R在A上是反自反的相矛盾。109定理5.2.6(3)的證明（3）R在A上對稱當(dāng)且僅當(dāng)R＝R-1必要性。 任取<x,y>，有 <x,y>∈R

<y,x>∈R

(因為R在A上對稱)

<x,y>∈R-1 所以R＝R-1充分性。任取<x,y>，由R＝R-1得<x,y>∈R

<y,x>∈R-1

<y,x>∈R所以R在A上是對稱的。110定理5.2.6(4)的證明（4）R在A上反對稱當(dāng)且僅當(dāng)R∩R-1

IA必要性。任取<x,y>，有 <x,y>∈R∩R-1

<x,y>∈R∧<x,y>∈R-1

<x,y>∈R∧<y,x>∈R

x＝y(tǒng) (R是反對稱的)

<x,y>∈IA 所以R∩R-1

IA充分性。 任取<x,y>,則有<x,y>∈R∧<y,x>∈R

<x,y>∈R∧<x,y>∈R-1

<x,y>∈R∩R-1

<x,y>∈IA(R∩R-1

IA)

x＝y(tǒng) 所以R在A上是反對稱的。111定理5.2.6(5)的證明（5）R在A上傳遞當(dāng)且僅當(dāng)R

R

R必要性。任取<x,y>，有 <x,y>∈R

R

t(<x,t>∈R∧<t,y>∈R)

<x,y>∈R(因為R在A上是傳遞的) 所以R

R

R。充分性。任取<x,y>,<y,z>∈R，則<x,y>∈R∧<y,z>∈R

<x,z>∈R

R

<x,z>∈R(因為R

R

R) 所以R在A上是傳遞的。112關(guān)系性質(zhì)的特點自反性反自反性對稱性反對稱性傳遞性集合表達式IA

RR∩IA＝

R＝R-1R∩R-1

IAR

R

R關(guān)系矩陣主對角線元素全是1主對角線元素全是0矩陣是對稱矩陣若rij＝1，且i≠j，則rji＝0對M2中1所在位置，M中相應(yīng)的位置都是1關(guān)系圖每個頂點都有環(huán)每個頂點都沒有環(huán)如果兩個頂點之間有邊，一定是一對方向相反的邊(無單邊)如果兩點之間有邊，一定是一條有向邊(無雙向邊)如果頂點xi到xj有邊，xj到xk有邊，則從xi到xk也有邊113例5.2.7例5.2.7判斷下圖中關(guān)系的性質(zhì)，并說明理由。（1）對稱的，不是自反的，不是反自反的，不是反對稱的，不是傳遞的。（2）是反自反的，不是自反的，是反對稱的，不是對稱的，是傳遞的。（3）是自反的，不是反自反的，是反對稱的，不是對稱的，不是傳遞的。114關(guān)系的性質(zhì)和運算之間的關(guān)系自反性反自反性對稱性反對稱性傳遞性R1-1√√√√√R1∩R2√√√√√R1∪R2√√√××R1－R2×√√√×R1

R2√××××115關(guān)系的閉包(closure)閉包的定義閉包的構(gòu)造方法閉包的性質(zhì)閉包的相互關(guān)系116閉包的定義定義5.2.8設(shè)R是非空集合A上的關(guān)系，R的自反（對稱或傳遞）閉包是A上的關(guān)系R′,使得R′滿足以下條件： （1）R′是自反的（對稱的或傳遞的） （2）R

R′ （3）對A上任何包含R的自反（對稱或傳遞）關(guān)系R″有R′

R″。 一般將R的自反閉包記作r(R)，對稱閉包記作s(R)，傳遞閉包記作t(R)。117閉包的主要性質(zhì)118閉包的構(gòu)造方法定理5.2.8設(shè)R為A上的關(guān)系，則有 （1）r(R)＝R∪R0 （2）s(R)＝R∪R-1 （3）t(R)＝R∪R2∪R3∪…

證明思路(1)和(2)：證明右邊的集合滿足閉包定義的三個條件。(3)采用集合相等的證明方法。證明左邊包含右邊，即t(R)包含每個Rn。

證明右邊包含左邊，即R∪R2∪…具有傳遞的性質(zhì)。119定理5.2.8(1)的證明（1）r(R)＝R∪R0證明①由IA＝R0

R∪R0，可知R∪R0是自反的，②R

R∪R0。③設(shè)R″是A上包含R的自反關(guān)系，則有R

R″和IA

R″。任取<x,y>，必有<x,y>∈R∪R0

<x,y>∈R∪IA

<x,y>∈R″∪R″＝R″所以R∪R0

R″。綜上所述，r(R)＝R∪R0。120定理5.2.8(2)的證明（2）s(R)＝R∪R-1證明①R

R∪R-1。②證明R∪R-1是對稱的，任取<x,y>，有<x,y>∈R∪R-1

<x,y>∈R∨<x,y>∈R-1

<y,x>∈R-1∨<y,x>∈R

<y,x>∈R∪R-1所以R∪R-1是對稱的。綜上所述，s(R)＝R∪R-1。③設(shè)R″是包含R的對稱關(guān)系，任取<x,y>，有<x,y>∈R∪R-1

<x,y>∈R∨<x,y>∈R-1

<x,y>∈R∨<y,x>∈R

<x,y>∈R″∨<y,x>∈R″

<x,y>∈R″∨<x,y>∈R″

<x,y>∈R″所以R∪R-1

R″。121定理5.2.8(3)的證明（3）t(R)＝R∪R2∪R3∪…

證明先證R∪R2∪…

t(R)成立，為此只需證明對任意的正整數(shù)n有Rn

t(R)即可。用歸納法。n＝1時，有R1＝R

t(R)。假設(shè)Rn

t(R)成立，那么對任意的<x,y>有 <x,y>∈Rn+1＝Rn

R

t(<x,t>∈Rn∧<t,y>∈R)

t(<x,t>∈t(R)∧<t,y>∈t(R))

<x,y>∈t(R)（因為t(R)是傳遞的）這就證明了Rn+1

t(R)。由歸納法命題得證。122定理5.2.8(3)的證明（3）t(R)＝R∪R2∪R3∪…

證明再證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)

t

s(<x,y>∈Rt∧<y,z>∈Rs)

t

s(<x,z>∈Rt

Rs)

t

s(<x,z>∈Rt+s)

<x,z>∈R∪R2∪…從而證明了R∪R2∪…是傳遞的。123推論推論設(shè)R為有窮集A上的關(guān)系，則存在正整數(shù)r使得 t(R)=R∪R2∪…∪Rr例題求整數(shù)集合Z上的關(guān)系R＝{<a,b>|a<b}的自反閉包和對稱閉包。解答

r(R)＝R∪R0＝{<a,b>|a<b}∪{<a,b>|a＝b} ＝{<a,b>|a≤b}

s(R)＝R∪R-1＝{<a,b>|a<b}∪{<b,a>|b<a} ＝{<a,b>|a≠b}124通過關(guān)系矩陣求閉包的方法 設(shè)關(guān)系R，r(R)，s(R)，t(R)的關(guān)系矩陣分別為M，Mr，Ms和Mt，則 Mr＝M＋E (對角線上的值都改為1) Ms＝M＋M′ (若aij＝1，則令aji＝1) Mt＝M＋M2＋M3＋… (沃舍爾算法)

其中E是和M同階的單位矩陣，M′是M的轉(zhuǎn)置矩陣。 注意在上述等式中矩陣的元素相加時使用邏輯加。

125通過關(guān)系圖求閉包的方法設(shè)關(guān)系R，r(R)，s(R)，t(R)的關(guān)系圖分別記為G，Gr，Gs，Gt，則Gr，Gs，Gt的頂點集與G的頂點集相等。 除了G的邊以外，以下述方法添加新的邊。1)考察G的每個頂點，如果沒有環(huán)就加上一個環(huán)。最終得到的是Gr。2) 考察G的每一條邊，如果有一條xi到xj的單向邊，i≠j，則在G中加一條邊xj到xi的反方向邊。最終得到Gs。3) 考察G的每個頂點xi，找出從xi出發(fā)的所有2步，3步，…，n步長的路徑（n為G中的頂點數(shù)）。 設(shè)路徑的終點為。

如果沒有從xi到(l=1,2,…,k)的邊，就加上這條邊。當(dāng)檢查完所有的頂點后就得到圖Gt。126例5.2.8例5.2.8設(shè)A={a,b,c,d}，R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}，則R和r(R)，s(R)，t(R)的關(guān)系圖如下圖所示。其中r(R)，s(R)，t(R)的關(guān)系圖就是使用上述方法直接從R的關(guān)系圖得到的。127Warshall算法輸入：M（R的關(guān)系矩陣）輸出：MT（t(R)的關(guān)系矩陣）1.MT←M2.fork←1tondo3. fori←1tondo4. forj←1tondo5. MT[i,j]←MT[i,j]+MT[i,k]*MT[k,j]注意：算法中矩陣加法和乘法中的元素相加都使用邏輯加(即1+1＝1,1+0＝0+1＝1,0+0＝0)。128Warshall算法舉例例

設(shè)A={a,b,c,d}，R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}，求t(R)。分析

k＝1時，MT[i,j]←MT[i,j]+MT[i,1]*MT[1,j]MT[1,j]←MT[1,j]+MT[1,1]*MT[1,j]MT[2,j]←MT[2,j]+MT[2,1]*MT[1,j]將第1行加到第2行上MT[3,j]←MT[3,j]+MT[3,1]*MT[1,j]MT[4,j]←MT[4,j]+MT[4,1]*MT[1,j]得到M1。129Warshall算法舉例k＝1時，第1列中只有M[2,1]＝1，將第1行加到第2行上。k＝2時，第2列中M[1,2]＝M[2,2]＝M[4,2]＝1，將第2行分別加到第1,2,4行上。130Warshall算法舉例k＝3時，第3列中M[1,3]＝M[2,3]＝M[4,3]＝1，將第3行分別加到第1,2,4行上。k＝4時，第4列中M[1,4]＝M[2,4]＝M[3,4]＝M[4,4]＝1，將第4行分別加到第1,2,3,4行上。131閉包的復(fù)合

1321331341351365.3等價關(guān)系與集合的劃分A2A5A3A4A1137138139定義5.3.4設(shè)R為非空集合上的關(guān)系。如果R是自反的、對稱的和傳遞的，則稱R為A上的等價關(guān)系(equivalentrelation)。設(shè)R是一個等價關(guān)系，若<x，y>∈R，稱x等價于y，記做xy。舉例 (1)平面上三角形集合中，三角形的相似關(guān)系。 (2)人群中的同性關(guān)系?！?40例5.3.2例5.3.2設(shè)A＝{1,2,…,8}，如下定義A上的關(guān)系R：

R＝{<x，y>|x，y∈A∧x≡y(mod3)}

其中x≡y(mod3)叫做x與y模3相等，即x除以3的余數(shù)與y除以3的余數(shù)相等。不難驗證R為A上的等價關(guān)系，因為

x∈A，有x≡x(mod3)

x,y∈A，若x≡y(mod3)，則有y≡x(mod3)

x,y,z∈A，若x≡y(mod3)，y≡z(mod3)，則有x≡z(mod3)141等價類定義5.3.5設(shè)R為非空集合A上的等價關(guān)系，

x∈A，令[x]R={y|y∈A∧xRy}

稱[x]R為x關(guān)于R的等價類，簡稱為x的等價類，簡記為[x]或x。x的等價類是A中所有與x等價的元素構(gòu)成的集合。例5.3.2中的等價類是： [1]＝[4]＝[7]＝{1,4,7} [2]＝[5]＝[8]＝{2,5,8} [3]＝[6]＝{3,6}142等價類的性質(zhì)定理5.3.3

設(shè)R是非空集合A上的等價關(guān)系，則（1）

x∈A，[x]是A的非空子集。（2）

x,y∈A，如果xRy，則[x]＝[y]。（3）

x,y∈A，如果<x,y>

R，則[x]與[y]不交。（4）∪{[x]|x∈A}＝A。證明（1）由等價類的定義可知，

x∈A有[x]

A。 又由于等價關(guān)系的自反性有x∈[x]，即[x]非空。143（2）

x,y∈A，如果xRy，則[x]=[y]。任取z，則有

z∈[x]

<x,z>∈R

<z,x>∈R (因為R是對稱的)

<z,x>∈R∧<x,y>∈R

<z,y>∈R (因為R是傳遞的)

<y,z>∈R (因為R是對稱的)

z∈[y]。所以[x]

[y]；同理可證[y]

[x]。因此，[x]=[y]。144（3）

x,y∈A，如果<x,y>

R，則[x]與[y]不交。 假設(shè)[x]∩[y]≠

， 則存在z∈[x]∩[y]， 從而有z∈[x]∧z∈[y]， 即<x,z>∈R∧<y,z>∈R成立。 根據(jù)R的對稱性和傳遞性，必有<x,y>∈R，與<x,y>

R矛盾， 即假設(shè)錯誤，原命題成立。145（4）∪{[x]|x∈A}＝A。

先證∪{[x]|x∈A}

A 任取y，y∈∪{[x]|x∈A}

x(x∈A∧y∈[x])

y∈A(因為[x]

A) 從而有∪{[x]|x∈A}

A。再證A

∪{[x]|x∈A}

任取y，y∈A

y∈[y]∧y∈A

y∈∪{[x]|x∈A} 從而有A

{[x]|x∈A}成立。綜上所述得∪{[x]|x∈A}＝A。146商集定義5.3.6設(shè)R為非空集合A上的等價關(guān)系，以R的所有等價類作為元素的集合稱為A關(guān)于R的商集(quotientset)，記做A/R，即 A/R={[x]R|x∈A}例5.3.2中的商集為 {{1,4,7},{2,5,8},{3,6}}整數(shù)集合Z上模n等價關(guān)系的商集是{{nz+i|z∈Z}|i=0,1,…,n-1}147商集與劃分商集就是A的一個劃分，并且不同的商集將對應(yīng)于不同的劃分。反之，任給A的一個劃分π，如下定義A上的