《離散數(shù)學(xué)》課件-第3章

3.1集合的概念與表示

3.2集合的基本運(yùn)算

*3.3容斥原理

3.4歸納證明

3.5集合的笛卡兒積

3.6二元關(guān)系

3.7集合上的二元關(guān)系及其特性

3.8關(guān)系的閉包運(yùn)算

3.9等價關(guān)系

3.10序關(guān)系第3章集合與關(guān)系集合是一個原概念，很難嚴(yán)格定義，只能對它給予直觀描述。所謂集合，就是若干(有窮或者無窮多)個具有某種共同性質(zhì)的事物的全體。組成集合的單個事物稱為該集合的元素(element)，或稱為成員(member)。3.1集合的概念與表示

1.列舉法

列舉法是將集合中的元素在一對大括號“{}”中一一列舉出來。例如，A={a，b，c}表示集合A由a、b、c三個元素組成。又如，D={0，1，2,…，99}表示集合D由前100個自然數(shù)組成。當(dāng)集合中的元素較多且有一定規(guī)律時，為了避免書寫麻煩,可以先列出集合中的一些元素，用省略號表示其他元素，如果是有限集合還要在最后列舉出末尾元素。

需要注意的是，如果沒有特別說明，集合中的元素不能重復(fù)列舉且元素間無次序之分。

2.描述法

描述法使用自然語言或謂詞描述集合中元素的共同特征。例如，A={x|x是中國的省份}，B={y|y=a或y=b}。當(dāng)用謂詞描述集合中元素的共同特征時，集合的表示形式為S={x|P(x)}，其中P(x)是一元謂詞，對于變元x的論域D中的任一個體a，如果P(a)為真，那么a∈S，否則a∈S。

3.歸納定義法

外延性公理兩個集合A、B相等，記為A=B，當(dāng)且僅當(dāng)它們有相同的元素。用與其等價的謂詞公式可表示為

A=B

x(x∈A

x∈B)

若兩個集合A和B不相等，通常記為A≠B。除相等關(guān)系外，包含也是集合間常見的一種關(guān)系。

定義3.1.1

設(shè)A、B是任意的兩個集合，若集合A的每個元素都是集合B的元素，則稱A為B的子集(subset)或稱B包含A，記為A

B或B

A，用邏輯公式表示為

A

B

x(x∈A→x∈B)

如果集合A不是集合B的子集，通常記為A

B。

????

定義3.1.2

如果集合A的每一個元素都屬于B，但集合B中至少有一個元素不屬于A，則稱A為B的真子集(propersubset)，記為A

B，用邏輯公式表示為

A

B

x(x∈A→x∈B)∧y(y∈B∧y∈A)(A

B)∧(A≠B)

通常在研究和討論問題時，所涉及的事物或者對象總限定在一定范圍內(nèi)，為了方便起見，有必要引入兩種特殊的集合：全集和空集。?

?

?

定義3.1.3

在一定范圍內(nèi)所有事物組成的集合稱為該范圍內(nèi)的全集(universalset)，記為U，用邏輯公式表示為

U={x|P(x)∨

P(x)}

其中，P(x)是任意的謂詞。

全集由所討論的事物范圍確定。如在討論實(shí)數(shù)時，全體實(shí)數(shù)組成全集U=R，此時所提到的任一集合A必須是U的子集，而不能是{a，b，c}、{老虎，燈泡}等。又如，在初等數(shù)論中，全體整數(shù)組成全集U=Z。

定義3.1.4

不含任何元素的集合稱為空集(emptyset)，記為，用邏輯公式表示為

={x|P(x)∧

P(x)}

其中，P(x)是任意的謂詞。根據(jù)空集的定義，顯然有||=0。

定理3.1.1

空集是任一集合的子集且是任何非空集合的真子集。

證明任取集合A，由于對任意的元素x，x∈恒為假，則有x(x∈→x∈A)為真，故有A成立。

若A不為空集，則存在元素

a∈A且a∈，故有A。證畢??????????

定理3.1.2

設(shè)A、B、C是集合，若A

B且B

C，則A

C。

證明任取x∈A

，因?yàn)锳

B，所以x∈B。又因?yàn)锽

C，所以有x∈C。故有A

C。

證畢

定理3.1.3

集合A和集合B相等的充分必要條件是A和B互為子集。

證明??????

推論對于任意集合A，均有A

A。

定理3.1.4

空集是唯一的。

證明設(shè)有兩個空集和′，根據(jù)定理3.1.1，有′且′，再根據(jù)定理3.1.3，故′=。

證畢

?????????文氏圖(Venndiagram)是一種可以直觀地表示集合之間關(guān)系的圖形化工具，它是英國數(shù)學(xué)家約翰·韋恩(JohnVenn)于1881年首先發(fā)明的。在文氏圖中，用矩形表示全集U，在表示全集的矩形內(nèi)部用圓、橢圓或其他幾何圖形表示集合，在表示集合的圖形內(nèi)部用點(diǎn)來表示集合中的元素。例如，圖3.1.1表示了全集U的一個子集A和兩個元素x和y，其中x畫在集合A的橢圓內(nèi)部，這表示元素x屬于集合A，而y畫在集合A的橢圓外部，這表示元素y屬于U而不屬于集合A。圖3.1.1文氏圖示意又如，圖3.1.2所示的文氏圖顯示了集合A與集合B的四種不同關(guān)系。其中，圖(a)表示集合A和B相等，圖(b)表示集合B是A的真子集，圖(c)表示集合A和B不等且交集不為空集，圖(d)表示A和B的交集為空集。圖3.1.2

定義3.1.5

給定集合A，以A的所有子集為元素組成的集合稱為集合A的冪集(powerset)，記為ρ(A)。

1.集合的交

定義3.2.1

對于任意兩個集合A和B，由所有屬于集合A且屬于集合B的元素組成的集合稱為A和B的交集(intersection)，記為A∩B。

A∩B={x|x∈A∧x∈B}

集合交運(yùn)算的文氏圖表示如圖3.2.1所示。3.2集合的基本運(yùn)算圖3.2.1

2.集合的并

定義3.2.2

對于任意兩個集合A和B，由所有屬于集合A或?qū)儆诩螧的元素組成的集合稱為A和B的并集(union)，記為A∪B。

A∪B={x|x∈A∨x∈B}

集合并運(yùn)算的文氏圖表示如圖3.2.2所示。圖3.2.2

3.集合的補(bǔ)

定義3.2.3

對于任意兩個集合A和B，由所有屬于集合A而不屬于集合B的元素組成的集合稱為集合B在A中的相對補(bǔ)集(complementofBwithrespecttoA)，記為A－B。

A－B={x|x∈A∧x∈B}

A－B也稱為集合A與B的差。集合差運(yùn)算的文氏圖表示如圖3.2.3所示。圖3.2.3

定義3.2.4

如果U是包含集合A的全集，則屬于U而不屬于A的元素組成的集合稱為集合A的補(bǔ)(complementofA)，記為。

=U－A={x|x∈U∧x∈A}

集合A的補(bǔ)集是集合A相對于全集U的補(bǔ)，也稱A的絕對補(bǔ)。集合絕對補(bǔ)運(yùn)算的文氏圖表示如圖3.2.4所示。圖3.2.4

4.集合的對稱差

定義3.2.5

對于任意兩個集合A和B，由屬于集合A而不屬于集合B以及屬于集合B而不屬于集合A的所有元素組成的集合稱為集合A與B的對稱差(symmetricdifference)，記為A

B。

A

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

集合對稱差運(yùn)算的文氏圖表示如圖3.2.5所示。圖3.2.5

5.集合的環(huán)積

定義3.2.6

對于任意兩個集合A和B，由屬于集合A且屬于集合B，以及既不屬于集合A又不屬于集合B的所有元素組成的集合，稱為集合A與B的環(huán)積，記為AB。

A

B=

=

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

集合的環(huán)積運(yùn)算的文氏圖表示如圖3.2.6所示。圖3.2.6以上定義的集合運(yùn)算滿足若干性質(zhì)，表3.2.1給出了其中11條基本性質(zhì)。表3.2.1

定理3.2.1

設(shè)A和B是全集U的任意子集，若AB，則

(a)

;

(b)B－A=B∩

;

(c)(B－A)∪A=B。

證明

因?yàn)锳

B，就有(B∪A)=B，所以(B－A)∪A=B。?

?

?

集合的運(yùn)算可用于解決有限集合的計(jì)數(shù)問題。根據(jù)集合運(yùn)算的定義，顯然有以下各式成立。

(a)|A1∪A2|≤|A1|+|A2|。

(b)|A1∩A2|≤min(|A1|，|A2|)。

(c)|A1－A2|≥|A1|－|A2|。

(d)|A1

A2|=|A1|+|A2|－2|A1∩A2|。*3.3容斥原理

加法原理：如果A1，A2，…，An是n個兩兩互不相交的集合，那么這n個集合的并集的元素個數(shù)為這n個集合中的元素個數(shù)之和。

|A1∪A2∪…∪An|=|A1|+|A2|+…+|An|

定理3.3.1

設(shè)A1和A2是有限集合，其元素個數(shù)分別為|A1|和|A2|，則|A1∪A2|=|A1|+|A2|－|A1∩A2|。

證明(1)若A1∩A2=，即|A1∩A2|=0，則根據(jù)加法原理有

|A1∪A2|=|A1|+|A2|

這時顯然公式成立。?

(2)若A1∩A2≠，根據(jù)

(A1－A2)∪(A1∩A2)=A1

且

(A1－A2)∩(A1∩A2)=

可得

|A1|=|A1－A2|+|A1∩A2|

同理有

|A2|=|A2－A1|+|A1∩A2|??而A1∪A2可以表示A1－A2、A2－A1和A1∩A2這三個兩兩互不相交的集合的并集，所以有

|A1∪A2|=|A1－A2|+|A2－A1|+|A1∩A2|

=|A1|+|A2|－|A1∩A2|

證畢

定理3.3.1

也可以通過圖3.3.1驗(yàn)證。圖3.3.1例2以1開始或者以00結(jié)束的8位不同的二進(jìn)制符號串有多少個？

以上計(jì)算公式可以用圖3.3.2驗(yàn)證。圖3.3.2

定理3.3.2(容斥原理)設(shè)A1，A2，…，An是有限集合，那么有

|A1∪A2∪…∪An|=

|Ai|－|Ai∩Aj|

+

|Ai∩Aj∩Ak|－…+(－1)n+1|A1∩A2∩…∩An|

證明用數(shù)學(xué)歸納法。

(1)當(dāng)n=2時，結(jié)論成立，即

|A1∪A2|=|A1|+|A2|－|A1∩A2|

(2)假設(shè)當(dāng)n=k－1(k≥3)時結(jié)論成立。

(3)現(xiàn)證明當(dāng)n=k時結(jié)論也成立。

證畢3.4.1集合的歸納定義

有些集合很難用3.1節(jié)中所介紹的列舉法和描述法進(jìn)行定義，如命題合式公式集合、C語言程序集合等。為此，這里再介紹另一種

定義集合的方法——?dú)w納定義(inductivedefinition)。

一個集合S的歸納定義由三部分組成：

(1)基礎(chǔ)條款：指出某些事物屬于S，其功能是給集合S指定初始元素，使得定義的集合S非空。3.4歸納證明

(2)歸納條款：指出由集合S中的已有元素構(gòu)造新元素的方法。歸納條款的形式總是斷言：如果事物x，y，…是集合S中的元素，那么用某些方法組合它們所得的新元素也在集合S中。它的功能是給出從已知元素構(gòu)造其他元素的規(guī)則。

(3)極小性條款：斷言一個事物除非能有限次應(yīng)用基礎(chǔ)條款和歸納條款構(gòu)成，否則它不在集合S中。

集合歸納定義的極小性條款還有其他一些常見的形式，例如，“集合S是滿足基礎(chǔ)條款和歸納條款的最小集合”，“若T是S的子集，T又滿足基礎(chǔ)條款和歸納條款，那么T=S”。這些極小性條款雖然形式不同，但都指明了所定義的集合是滿足基礎(chǔ)條款和歸納條款的最小集合，即所謂的極小性。3.4.2自然數(shù)集合

自然數(shù)集合N被廣泛運(yùn)用，但是要給出一個嚴(yán)格的定義是比較困難的。這里介紹美國數(shù)學(xué)家約翰·馮·諾依曼(JohnVonNeumann)的定義方法，他巧妙地采用空集和后繼集合的概念找到了自然數(shù)集合的一個構(gòu)造。

設(shè)A是任意集合，A的后繼集合記為A′，定義A′=

A∪{A}。自然數(shù)集合N可進(jìn)行以下歸納定義：

(1)(基礎(chǔ))∈N；?

(2)(歸納)如果A∈N，那么A′∈N；

(3)(極小性)如果S

N且滿足條款(1)和(2)，那么S=N。自然數(shù)集合可以直觀地表示為以為起點(diǎn)，另一端無限延伸的一條鏈，其結(jié)構(gòu)如圖3.4.1所示。習(xí)慣上，將自然數(shù)集合的最小元素用0標(biāo)記，0的后繼集合{}用1標(biāo)記，1的后繼集合{，{}}用2標(biāo)記，以此類推，從而產(chǎn)生了人們所熟悉的自然數(shù)集合N={0,1,2,3，…}。進(jìn)一步，可以在N上定義各種運(yùn)算。例如，對于加法運(yùn)算，任取n∈N，n+1=n′。

??????圖3.4.13.4.3歸納法

對于形如(x)P(x)的命題，如果其論域是歸納定義的集合，則用歸納法往往是較為有效的證明方法。

歸納法證明的一般步驟如下：

(1)基礎(chǔ)步驟。對于基礎(chǔ)條款中指定的每個初始元素t，證明命題P(t)為真。

(2)歸納步驟。證明如果事物x，y，…有P性質(zhì)，那么用歸納條款指定的方法組合它們所得的新元素也具有P性質(zhì)。3.4.4數(shù)學(xué)歸納法

數(shù)學(xué)歸納法(mathematicalinduction)被廣泛地用來證明形如xP(x)的命題，其中x的論域常常是自然數(shù)集、正整數(shù)集等，例如，用來證明算法的復(fù)雜度，計(jì)算機(jī)程序的正確性，關(guān)于圖和樹等離散結(jié)構(gòu)滿足的等式或不等式。數(shù)學(xué)歸納法的有效性源于自然數(shù)集的歸納定義。

下面分別介紹數(shù)學(xué)歸納法第一原理和數(shù)學(xué)歸納法第二原理。

數(shù)學(xué)歸納法第一原理其實(shí)是自然數(shù)集合N上的一個推理規(guī)則，其形式如下：

為了證明n(P(n)→P(n+1))，根據(jù)謂詞邏輯中的全稱推廣規(guī)則，只需任取n證明P(n)→P(n+1)成立即可，當(dāng)然n必須是任意選取的。

用數(shù)學(xué)歸納法第一原理進(jìn)行證明的一般步驟如下：

(1)(歸納基礎(chǔ))證明P(0)為真(可以用任何方法)。

(2)(歸納假設(shè))任取n(n≥0)，假設(shè)P(n)為真。

(3)(歸納推理)由P(n)為真，推出P(n+1)也為真。當(dāng)用數(shù)學(xué)歸納法第一原理進(jìn)行證明時，首先證明P(0)為真，這時可以用任何有效的證明方法和規(guī)則；其次證明“若P(n)為真，則P(n+1)必為真”。這樣因?yàn)橛蠵(0)為真且有P(n)→P(n+1)為真，所以P(1)為真，由P(1)為真可得P(2)也為真，以此類推，即對任意的自然數(shù)k都有P(k)為真。

作為一個形象的例子，我們來考慮由一張牌開始，無窮向后延長的一列多米諾骨牌，每兩張牌都等距直立放置。假設(shè)我們能夠證明若任意的第k張牌被撞倒，則它將會撞倒第k+1張牌。現(xiàn)在我們撞倒第一張牌，第一張牌倒后第二張牌跟著被撞倒，第二張牌被撞倒后第三張牌也跟著被撞倒……如此下去，所有的牌都會被撞倒，如圖3.4.2所示。圖3.4.2數(shù)學(xué)歸納法第一原理的推理規(guī)則可以有各種變形。例如，如果我們希望證明對某整數(shù)k，謂詞P對所有x≥k成立，這時，基礎(chǔ)步驟必須換為證明P(k)，推理規(guī)則變?yōu)?/p>

例L形馬賽克瓷磚由三塊方磚構(gòu)成，其形狀如圖3.4.3(a)所示。證明：可以用L形馬賽克鋪滿去掉一個格子的任何具有2n×2n(n∈Z+)個格子的方形地板。圖3.4.3

證明設(shè)P(n)是命題：可以用L形的馬賽克瓷磚鋪滿去掉一個格子的任何具有2n×2n個格子的方形地板。

(1)(歸納基礎(chǔ))當(dāng)n=1時，P(1)為真。因?yàn)槿鐖D3.4.3(b)所示，從2×2的地板中去掉這4個格子中的任意一個，都可以用一塊L形的馬賽克瓷磚將它鋪滿。

(2)(歸納假設(shè))任取k∈Z+，假設(shè)P(k)為真，即可以用L形馬賽克鋪滿去掉一個格子的任何具有2k×2k個格子的方形地板。

(3)(歸納推理)當(dāng)n=k+1時，要考慮去掉一個格子的2k+1×2k+1規(guī)格的地板。

因?yàn)?k+1×2k+1=2×2k×2×2k=4×(2k×2k)，也就是說可以將2k+1×2k+1規(guī)格的地板分割成4塊2k×2k規(guī)格的地板。如圖3.4.4(a)所示，將該地板分成4塊大小相同的2k×2k規(guī)格的地板，按順時針方向依次編號為1＃、2＃、3＃、4＃。

由于這塊2k+1×2k+1規(guī)格的地板中去掉了一個格子，不妨設(shè)去掉的這個格子在1＃中。根據(jù)歸納假設(shè)，1＃去掉1個格子后可以用L形馬賽克鋪滿。還剩下2＃、3＃、4＃這三塊2k×2k規(guī)格的地板。為了將其鋪滿，在這三塊地板毗鄰處暫時在每一塊中去掉1個格子(如圖3.4.4(b)所示)，根據(jù)歸納假設(shè)，可以用L形馬賽克鋪滿2＃、3＃、4＃各去掉1個格子的地板，而去掉的這3個格子正好與一塊L形馬賽克瓷磚吻合，最后用一塊L形馬賽克將暫時去掉的3個格子鋪滿，故P(k+1)也為真。圖3.4.4

例7

設(shè)m是正整數(shù)，現(xiàn)有m顆白珍珠和m顆黑珍珠，將這2m顆珍珠隨意穿在一個圓環(huán)上，證明可以在圓環(huán)上找到一個位置，從這個位置出發(fā)順時針方向依次收集圓環(huán)上的所有珍珠，使得在每一時刻收集到的白珍珠的數(shù)目總是大于等于黑珍珠的數(shù)目。

證明(1)當(dāng)m=1時，圓環(huán)上有1顆白珍珠和1顆黑珍珠，如果我們從那顆白珍珠所在的位置開始收集，顯然有收集到的白珍珠的數(shù)目總是大于等于黑珍珠的數(shù)目。

(2)假設(shè)當(dāng)m=k(k>0)時，命題成立。

(3)當(dāng)m=k+1時，圓環(huán)上有k+1顆白珍珠和k+1顆黑珍珠。我們可以證明在這2(k+1)顆珍珠中，必有1顆白珍珠和1顆黑珍珠按順時針方向鄰接。

令t為圓環(huán)上的任一顆白珍珠，如果t順時針方向鄰接的1顆珍珠t′是黑珍珠，那么就找到了這樣一對珍珠(t，t′)；否則，t順時針方向鄰接的是1顆白珍珠。現(xiàn)令t=t′，重復(fù)上述過程，因?yàn)閳A環(huán)上存在黑珍珠，所以必然能夠找到這樣一對珍珠(t，t′)，如圖3.4.5所示。圖3.4.5數(shù)學(xué)歸納法第二原理的形式如下：

定義3.5.1

兩個元素a和b組成的具有固定次序的序列稱為序偶(orderedpair)或二元組(ordered2-tuples)，記為〈a，b〉。對于序偶〈a，b〉，a稱為第1元素，b稱為第2元素。

有了序偶的概念，就可以將一趟列車的運(yùn)行區(qū)間用一個序偶的形式表示，例如，K126=〈西安，長春〉。同樣，平面上橫坐標(biāo)為x、縱坐標(biāo)為y的點(diǎn)可以表示為〈x,y〉。3.5集合的笛卡兒積

定義3.5.2

兩個序偶〈a，b〉和〈c，d〉相等，記為〈a，b〉=〈c，d〉，當(dāng)且僅當(dāng)a=c且b=d。

定義3.5.3

設(shè)A和B是兩個集合，稱集合

A×B={〈a,b〉|a∈A，b∈B}

為A和B的笛卡兒積(Cartesianproduct)或叉集(productset)。例如，R×R示實(shí)平面。任取〈x，y〉∈R×R，〈x，y〉表示實(shí)平面中的一個點(diǎn)。

定義3.5.4

設(shè)A1，A2,…，An是n個集合，稱集合

A1×A2×…×An={〈a1，a2，…，an〉|ai∈Ai，1≤i≤n}為集合A1，A2,…，An的笛卡兒積。其中，〈a1，a2，…，an〉是由n個元素a1，a2,…，an組成的n元組(orderedn-tuples)，ai(1≤i≤n)是該n元組的第i個元素且ai∈Ai。若對一切i，Ai=A，則可簡記為An。

n元組可以看成是一個二元組，規(guī)定〈a1，a2，…，an〉=〈〈a1，a2，…，an－1〉，an〉，其第一元素是n－1元組。例如，〈x，y，z〉代表〈〈x，y〉,z〉，而不代表〈x，〈y，z〉〉。

定理3.5.1

設(shè)A、B、C是任意集合，則有

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

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

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

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

證明

(1)①任取〈x,y〉∈A×(B∪C)，則x∈A且y∈B∪C，即x∈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)。?②任取〈x,y〉∈(A×B)∪(A×C)，則有〈x,y〉∈A×B或〈x,y〉∈A×C，即x∈A且y∈B或x∈A且y∈C，得到x∈A且(y∈B或y∈C)，從而由x∈A且y∈B∪C可得〈x,y〉∈A×

(B∪C)。

所以(A×B)∪(A×C)A×(B∪C)。

由以上①和②得知，A×(B∪C)=(A×B)∪(A×C)。

(3)〈x,y〉∈(A∪B)×C

x∈(A∪B)∧y∈C

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

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

(〈x,y〉∈A×C)∨(〈x,y〉∈B×C)

〈x,y〉∈(A×C)∪(B×C)

所以(A∪B)×C=(A×C)∪(B×C)。

定理3.5.2

如果Ai(i=1，2，…，n)都是有限集合，那么

|A1×A2×…×An|=|A1|·|A2|·…·|An|

證明(略)

以上定理就是3.3節(jié)曾經(jīng)提到的關(guān)于集合計(jì)數(shù)的乘法原理。乘法原理還可以描述為：如果一項(xiàng)工作需要t步完成，第一步有n1種不同的選擇，第二步有n2種不同的選擇，以此類推，第t步有nt種不同的選擇，則完成這項(xiàng)工作不同的選擇共有n1×n2×…×nt種。3.6.1關(guān)系的定義

定義3.6.1

兩個集合A和B的笛卡兒積A×B的任一子集R，稱為集合A到B上的二元關(guān)系(arelationfromAtoB)。二元關(guān)系R是由序偶構(gòu)成的集合，若〈x，y〉∈R，則稱x與y有R關(guān)系，也記為xRy；否則，〈x，y〉∈R，稱x與y沒有R關(guān)系，也記為xRy。

3.6二元關(guān)系設(shè)R是集合A到B的二元關(guān)系。集合A稱為R的前域(predomain)，集合B稱為R的陪域(codomain)。集合{x|(

y)(〈x，y〉∈R)}稱為R的定義域(domain)，記為domR。集合{y|(x)(〈x，y〉∈R)}稱為R的值域(range)，記為ranR。顯然，domR

A和ranR

B。

集合A到B的二元關(guān)系R的示意圖如圖3.6.1所示。??圖3.6.1

定義3.6.2

n個集合A1，A2，…，An的笛卡兒積A1×A2

×…×An的任一子集R稱為A1，A2，…，An上的一個n元關(guān)系(relation)。

定義3.6.3

設(shè)R是A1×A2×…×An的子集，若R=，則稱R為A1，A2，…，An上的空關(guān)系，若R=A1×A2×…×An，則稱R為A1，A2，…，An上的全域關(guān)系。?3.6.2關(guān)系的表示

二元關(guān)系是一種集合，除了可以采用集合的表示方法外，下面再介紹另外兩種常用表示方法：關(guān)系矩陣(relationmetrix)和關(guān)系圖(relationgraph)。

1.關(guān)系矩陣

給定兩個有限集A={a1，a2，…，am}，B={b1，b2，…,

bn}。R為A到B上的一個二元關(guān)系，則可以用以下0－1矩陣MR=［rij］m×n來表示R：

其中:

2.關(guān)系圖

設(shè)有限集合A={a1，a2，…，am}和B={b1，b2，…,

bn}，R為A到B上的一個二元關(guān)系。R的關(guān)系圖的作法是：首先在平面上作m個結(jié)點(diǎn)分別代表a1，a2，…，am，然后另作n個結(jié)點(diǎn)分別代表b1，b2，…,bn。如果aiRbj，則畫一條從結(jié)點(diǎn)ai到結(jié)點(diǎn)bj的有向弧，如圖3.6.2所示。圖3.6.2

例3

設(shè)X={x1，x2，x3，x4}，Y={y1，y2，y3}，R={〈x1，y1〉，〈x1，y3〉，〈x2，y2〉，〈x3，y1〉，〈x4，y2〉，〈x4，y3〉}。寫出R的關(guān)系矩陣并畫出其關(guān)系圖。

解

R的關(guān)系矩陣和關(guān)系圖如圖3.6.3所示。圖3.6.3

例4

設(shè)A={1，2，4，7，8}，B={2，3，5，7}，定義A到B的二元關(guān)系R={〈a，b〉|5能整除a+b}。分別用列舉法、關(guān)系圖和關(guān)系矩陣描述R。

解

R={〈2，3〉，〈7，3〉，〈8，2〉，〈8，7〉}。R的關(guān)系矩陣和關(guān)系圖分別如圖3.6.4所示。圖3.6.43.6.3關(guān)系的運(yùn)算

由于二元關(guān)系是以序偶為元素組成的集合，因此，所有的集合運(yùn)算對于二元關(guān)系同樣適用。設(shè)R和S都是集合A到B的二元關(guān)系，則有:

(1)R∪S={〈x，y〉|(xRy)∨(xSy)}。

(2)R∩S={〈x，y〉|(xRy)∧(xSy)}。

(3)R－S={〈x，y〉|(xRy)∧(xSy)}。

(4)={〈x，y〉|xRy}=A×B－R。

(5)R

S=(R－S)∪(S－R)。

定義3.6.4

設(shè)R為集合A到B的二元關(guān)系，S為集合B到C的二元關(guān)系，令

R

S={〈a，c〉|a∈A∧c∈C∧(b)

(b∈B∧〈a，b〉∈R∧〈b，c〉∈S)}

則稱R

S為R與S的復(fù)合關(guān)系。

顯然，R

S是一個從A到C的二元關(guān)系。圖3.6.5描述了兩個關(guān)系R和S進(jìn)行復(fù)合運(yùn)算的過程。R

S由這樣的序偶〈a，c〉構(gòu)成，即存在集合B中的元素b，有aRb和bRc，形象地說，就是“存在從元素a出發(fā)，經(jīng)過B中某元素b到達(dá)c的有向路徑”。°

°

°

°

圖3.6.5

定理3.6.1

設(shè)R是從集合A到B的二元關(guān)系，S為B到C的二元關(guān)系，T為C到D的二元關(guān)系，則有

(R

S)T=R(S

T)

證明任取〈a,d〉∈(R

S)T，由復(fù)合運(yùn)算的定義可知，存在c∈C使得

〈a，c〉∈R

S

且〈c，d〉∈T

又對于〈a，c〉∈R

S，存在b∈B使得

〈a，b〉∈R

且〈b，c〉∈S

由〈b，c〉∈S和〈c，d〉∈T可得〈b，d〉∈S

T，又由〈a，b〉∈R可得

〈a，d〉∈R(S

T)°

°

°

°

°

°

°

°

°

°

故有

(RS)TR(ST)

同理可證：

R(ST)(RS)T

綜上所述，可得

(RS)T=R(ST)

證畢?°

°

°

°

°

°

°

°

?°

°

°

°

定義3.6.5

設(shè)R為集合A到B的二元關(guān)系，令R－1={〈b，a〉|〈a，b〉∈R}，則稱R－1為R的逆關(guān)系。顯然，R－1是集合B到A上的二元關(guān)系。

例10

設(shè)A={a，b，c，d}，B={1，2，3}，R={〈a，2〉，〈b，1〉，〈c，3〉，〈d，1〉}是從A到B的一個二元關(guān)系，求R、R－1的關(guān)系矩陣、關(guān)系圖，并觀察關(guān)系矩陣、關(guān)系圖，分析R－1與R之間的聯(lián)系。

解

R－1={〈2，a〉，〈1，b〉，〈3，c〉，〈1，d〉}，給出R與R－1的關(guān)系矩陣，再給出R與R－1的關(guān)系圖，如圖3.6.6所示。圖3.6.6

定理3.6.2

設(shè)R、R1、R2均為從A到B的二元關(guān)系，則有

證明(2)任取a∈A，b∈B，則有

(4)任取a∈A，b∈B，則有

證畢

定理3.6.3

設(shè)R為A到B的二元關(guān)系，S是從B到C的二元關(guān)系，那么

(R

S)－1=S－1

R－1

證明(1)任取〈c,a〉∈(R

S)－1，則有〈a,c〉∈(R

S)，由關(guān)系復(fù)合運(yùn)算的定義可知，存在b∈B，使得〈a，b〉∈R且〈b，c〉∈S，則有〈b，a〉∈R－1，〈c，b〉∈S－1。由〈c，b〉∈S－1和〈b，a〉∈R－1可得〈c，a〉∈S－1

R－1，故有(R

S)－1

S－1

R－1。?°

°

°

°

°

°

°

(2)任取〈c，a〉∈S－1

R－1，由關(guān)系復(fù)合運(yùn)算的定義可知，存在b∈B，使得〈c，b〉∈S－1且〈b，a〉∈R－1，即〈b，c〉∈S且〈a，b〉∈R，由此可得〈a，c〉∈R

S，即〈c,a〉∈(R

S)－1。

故有S－1

R－1(R

S)－1。

由(1)、(2)得到，(R

S)－1=S－1

R－1。?°

°

°

°

°

°

°

3.7.1集合上的二元關(guān)系

定義3.7.1

集合A與A的笛卡兒積A×A的子集稱為A上的二元關(guān)系。

例如，國家男子乒乓球隊(duì)由7名選手組成，主教練要從現(xiàn)役國手中挑選三對男子雙打選手參加世界乒乓球錦標(biāo)賽。設(shè)集合A為國家乒乓球男隊(duì)，共由7名運(yùn)動員組成，令A(yù)={甲，乙，丙，丁，戊，己，庚}，A×A則包含了所有可能的男子雙打配對組合，如圖3.7.1所示。3.7集合上的二元關(guān)系及其特性圖3.7.1主教練根據(jù)挑選男雙隊(duì)員的一些規(guī)則和經(jīng)驗(yàn)，最終選擇了甲與丙、己與戊、乙與丁這3對組合去參加世界乒乓球錦標(biāo)賽。這樣，R={〈甲，丙〉，〈己，戊〉，〈乙，丁〉}就構(gòu)成A上的一個“雙打配對”關(guān)系。

由于集合A上的二元關(guān)系的前域和陪域是同一個集合，因此其關(guān)系矩陣是方陣，其關(guān)系圖可以將兩組結(jié)點(diǎn)合并為一組。

定義3.7.2

設(shè)A是任一集合，稱A上的二元關(guān)系{〈a，a〉|a∈A}為集合A上的相等關(guān)系，記為IA。

例1

設(shè)A={1，2，3，4，5}，A上的二元關(guān)系R={〈1，5〉，〈1，4〉,〈2，3〉，〈3，1〉，〈3，4〉，

〈4，4〉}。

(a)求A上的相等關(guān)系IA。

(b)寫出R的關(guān)系矩陣。

(c)畫出R的關(guān)系圖。

解(a)IA={〈1，1〉，〈2，2〉，〈3，3〉，〈4，4〉，〈5，5〉}。

(b)

(c)R的關(guān)系圖如圖3.7.2所示。圖3.7.2

定義3.7.3

設(shè)R是集合A上的二元關(guān)系，n∈Z+，稱

為R的n次冪，記為Rn。

設(shè)R是集合A上的二元關(guān)系，約定R0={〈x，x〉|x∈A}

=IA。

定理3.7.1

設(shè)R是集合A上的二元關(guān)系，m，n∈N，那么有

(1)Rm

Rn=Rm+n。

(2)(Rm)n=Rmn?！?/p>

°

定理3.7.2

設(shè)R是集合A上的一個二元關(guān)系。若存在i，j∈N，i＜j且使Ri=Rj，則有

(1)對所有的k≥0，Ri+k=Rj+k。

(2)對所有的k，m≥0，Ri+md+k=Ri+k，其中d=j－i。

(3)記S={R0，R1，R2，…，Rj－1}，對于任意n∈N，均有Rn∈S。

證明(1)、(2)留作練習(xí)。

(3)任取n∈N，如果n＜j，那么根據(jù)S的定義，Rn∈S。假設(shè)n≥j，那么我們能將n表示為i+md+k，這里0≤k＜d。由(2)可知，Rn=Ri+md+k=Ri+k，因?yàn)閕+k＜j，故Rn∈S。

證畢3.7.2二元關(guān)系的特性

1.自反性

定義3.7.4

設(shè)R是集合A上的二元關(guān)系，如果對于A中的每一元素a都有aRa，則稱R在A上是自反的(reflexive)。

R是自反的(a)(a∈A→aRa)

例如，實(shí)數(shù)集上的“≤”關(guān)系是自反的，因?yàn)閷τ谌我鈱?shí)數(shù)x，均有x≤x。

2.反自反性

定義3.7.5

設(shè)R是集合A上的二元關(guān)系，如果對于A中的每一元素a都有aRa，則稱R在A上是反自反的(irreflexive)。R是反自反的(a)(a∈A→aRa)

例如，實(shí)數(shù)集上的“＞”關(guān)系是反自反的。

例3

設(shè)A={a,b,c,d}，A上的二元關(guān)系R1、R2和R3的關(guān)系圖分別如圖3.7.3(a)、(b)、(c)所示。這些關(guān)系中哪些是自反的？哪些是反自反的？圖3.7.3

解

R1是自反的，R2是反自反的，R3既不是自反的也不是反自反的。

關(guān)于自反性與反自反性的特征總結(jié)如表3.7.1所示。表3.7.1

3.對稱性

定義3.7.6

設(shè)R是集合A上的二元關(guān)系，如果對于任意a，b∈A，每當(dāng)aRb必有bRa，則稱R在A上是對稱的(symmetric)。

R是對稱的(a)(b)(a∈A∧b∈A∧aRb→bRa)

例如，三角形集合上的三角形相似關(guān)系是對稱的。

4.反對稱性

定義3.7.7

設(shè)R是集合A上的二元關(guān)系，如果對于任意a，b∈A，每當(dāng)aRb且bRa，必有a=b，則稱R在A上是反對稱的(antisymmetric)。

R是反對稱的(a)(b)(a∈A∧b∈A∧aRb∧bRa→a=b)(a)(b)(a∈A∧b∈A∧a≠b∧aRb→bRa)

例如，集合的關(guān)系是反對稱的。?

例4

設(shè)A={a，b，c，d}，A上的二元關(guān)系R1、R2、R3和R4的關(guān)系圖分別如圖3.7.4(a)、(b)、(c)、(d)所示。這些關(guān)系中哪些是對稱的?哪些是反對稱的？

解

R1是對稱的，R2是反對稱的，R3既是對稱的又是反對稱的，R4既不是對稱的又不是反對稱的。

關(guān)于對稱性與反對稱性的特征總結(jié)如表3.7.2所示。圖3.7.4表3.7.2

5.傳遞性

定義3.7.8

設(shè)R是集合A上的二元關(guān)系，若對于任意a,b,c∈A，當(dāng)aRb且bRc時必有aRc，則稱關(guān)系R在A上是傳遞的(transitive)。

R是傳遞的(a)(b)(c)(a∈A∧b∈A∧c

∈A∧aRb∧bRc→aRc)

例如，整數(shù)集上的關(guān)系≤、＜、＞、=都是傳遞的。

例5

設(shè)A={a,b,c,d}，A上的二元關(guān)系R1和R2的關(guān)系圖分別如圖3.7.5(a)、(b)所示，請問R是傳遞的嗎？

解

R1是傳遞的，R2不是傳遞的。

表3.7.3給出了滿足傳遞性的二元關(guān)系的定義和特征。圖3.7.5表3.7.3

例7

設(shè)A={a，b，c}，構(gòu)造A上的一個二元關(guān)系R，使其不滿足自反性、反自反性、對稱性、反對稱性和傳遞性。

解令R={〈a，a〉，〈b，b〉，〈b，c〉，〈c，b〉，〈c，a〉}，R的關(guān)系圖如圖3.7.6所示。圖3.7.6

定義3.8.1

設(shè)R是集合A上的二元關(guān)系，如果A上另外一個二元關(guān)系R′滿足：

(1)R′是自反的(對稱的、傳遞的)；

(2)R′R；

(3)對于A上的任何自反的(對稱的、傳遞的)關(guān)系R″，若R″R，有R″R′，則稱R′是R的自反(對稱、傳遞)閉包。

3.8關(guān)系的閉包運(yùn)算???

定理3.8.1

設(shè)R是集合A上的二元關(guān)系，則有

(1)R是自反的當(dāng)且僅當(dāng)r(R)=R。

(2)R是對稱的當(dāng)且僅當(dāng)s(R)=R。

(3)R是傳遞的當(dāng)且僅當(dāng)t(R)=R。

證明(2)必要性。若R是對稱的，令R′=R，顯然，R′滿足定義3.8.1中關(guān)于對稱閉包的約束條件(1)、(2)、(3)，所以，s(R)=R′=R。

充分性。若s(R)=R，因?yàn)閟(R)是對稱的，所以R也是對稱的。

同理可證(1)和(3)。

證畢

定理3.8.2

設(shè)R是集合A上的二元關(guān)系，那么有

(1)r(R)=R∪IA。

(2)s(R)=R∪R－1。

(3)t(R)=。

證明(1)令R′=R∪IA。

①任取x∈A，〈x，x〉∈IA，則〈x，x〉∈R∪IA，故R′是自反的。

②顯然R′R。?③任取A上的自反關(guān)系R″，且R″R，現(xiàn)證明R″R′。

任取〈x，y〉∈R′，則有〈x，y〉∈R或〈x，y〉∈IA。

若〈x，y〉∈R，則有〈x，y〉∈R″。

若〈x，y〉∈IA，則x=y，又因?yàn)镽″是自反的，所以〈x，y〉∈R″。

故有R″R′。

由此可知，r(R)=R′=R∪IA。??

(2)令R′=R∪R－1。

①R′－1=(R∪R－1)－1=R－1∪R=R′，所以R′是對稱的。

②顯然R′R。

③任取A上的對稱關(guān)系R″，且R″R，現(xiàn)證明R″R′。

任取〈x，y〉∈R′，由R′=R∪R－1知，得到〈x，y〉∈R或〈x，y〉∈R－1。

若〈x，y〉∈R，則〈x，y〉∈R″。

若〈x，y〉∈R－1，則〈y,

x〉∈R，〈y,

x〉∈R″，因?yàn)镽″是對稱的，所以〈x，y〉∈R″。故有R″R′。

由此可知，s(R)=R′=R∪R－1。????

(3)令R′=。

①任取〈x，y〉∈R′，〈y，z〉∈R′，那么必存在正整數(shù)s、t，使得〈x，y〉∈Rs，〈y，z〉∈Rt，則有〈x，z〉∈Rs

Rt=Rs+t，所以〈x，z〉∈R′，即R′是傳遞的。

②R

=R′。°

?③任取A上的傳遞關(guān)系R″，且R″R，現(xiàn)證明R″R′。

任取〈x，y〉∈R′，則存在某正整數(shù)k使得〈x，y〉∈Rk，而

，由復(fù)合運(yùn)算的定義可知：A中存在元素x1，x2，…，xk－1，使得〈x，x1〉∈R，〈x1，x2〉∈R，…，〈xk－1，y〉∈R。因?yàn)镽″R，所以有〈x，x1〉∈R″，〈x1，x2〉∈R″，…，〈xk－1，y〉∈R″。

又因?yàn)镽″是傳遞的，所以〈x，y〉∈R″，從而有R″R′。

綜上所述有t(R)=R′=。

證畢????

例2

設(shè)A={a，b，c}，A上的二元關(guān)系R={〈a，b〉，〈b，c〉，〈c，a〉}，求r(R)、s(R)和t(R)，并給出各閉包的關(guān)系矩陣和關(guān)系圖。

解

R的關(guān)系圖如圖3.8.1所示。圖3.8.1

(a)求自反閉包r(R)。

r(R)=R∪IA={〈a，b〉，〈b，c〉，〈c，a〉，〈a，a〉，〈b，b〉，〈c，c〉}

r(R)的關(guān)系圖如圖3.8.2所示。圖3.8.2

(b)求對稱閉包s(R)。

s(R)=R∪R－1={〈a，b〉，〈b，c〉，〈c，a〉，〈b，a〉，〈c，b〉，〈a，c〉}

s(R)的關(guān)系圖如圖3.8.3所示。圖3.8.3

(c)求傳遞閉包t(R)。

R={〈a，b〉，〈b，c〉，〈c，a〉}

R2={〈a，c〉，〈b，a〉，〈c，b〉}

R3={〈a，a〉，〈b，b〉，〈c，c〉}=IA=R0

因此有

R4=R，R5=R2，…，R3n+1=R，R3n+2=R2，R3n+3=R3

t(R)=R∪R2∪R3∪…=R∪R2∪R3

={〈a，b〉，〈b，c〉，〈c，a〉，〈a，c〉，〈b，a〉，〈c，b〉，〈a，a〉，〈b，b〉，〈c，c〉}

t(R)的關(guān)系圖如圖3.8.4所示。圖3.8.4

定理3.8.3

設(shè)R是有限集合A上的二元關(guān)系且|A|=n，那么有

t(R)=R∪R2∪…∪Rn

證明已知t(R)=R∪R2∪…∪Rn∪…，現(xiàn)證明R∪R2∪…∪Rn=R∪R2∪…∪Rn∪…。

(1)顯然有R∪R2∪…∪Rn

R∪R2∪…∪Rn∪…。

(2)證明R∪R2∪…∪Rn∪…R∪R2∪…∪Rn，為此，需要證明對于任何x，y∈A，如果〈x，y〉∈R∪R2∪…∪Rn

∪…，必存在正整數(shù)k≤n，使得〈x，y〉∈Rk。采用反證法：??假設(shè)k是滿足〈x，y〉∈Rk的最小正整數(shù)(因?yàn)椤磝，y〉∈R∪R2∪…∪Rn∪…，必存在正整數(shù)s，使得〈x，y〉∈Rs)，且k＞n，則A中存在元素序列x=a0，a1，…，ak－1,ak=y，使得

〈x，a1〉,〈a1，a2〉，…，〈ak－1，y〉∈R

由于|A|=n，則a0，a1，…，ak－1,ak中必有相同者，不妨設(shè)ai=aj(0≤i＜j≤k)，于是〈x，a1〉,〈a1，a2〉，…，〈ai－1，ai〉，〈aj，aj+1〉，…，〈ak－1，y〉∈R，得到〈x，ai〉∈Ri，〈aj，y〉∈Rk－j，〈x，y〉∈Ri+(k－j)

，即〈x，y〉∈Rt，其中t=i+(k－j)=k－(j－i)＜k。這與k的最小性矛盾，于是k≤n。故有R∪R2∪…∪Rn∪…R∪R2∪…∪Rn成立。

定理3.8.4

設(shè)R是集合A上的二元關(guān)系，則有

(1)如果R是自反的，那么s(R)和t(R)也是自反的。

(2)如果R是對稱的，那么r(R)和t(R)也是對稱的。

(3)如果R是傳遞的，那么r(R)也是傳遞的。

證明過程留作練習(xí)。

集合A上的二元關(guān)系R的閉包運(yùn)算可以進(jìn)行復(fù)合運(yùn)算，例如ts(R)=t(s(R))表示R的對稱閉包的傳遞閉包，通常簡稱為R的對稱傳遞閉包，而tsr(R)則表示R的自反對稱傳遞閉包。R的傳遞閉包有時用R+表示，而R的自反傳遞閉包tr(R)用R*表示。

定理3.8.5

設(shè)R是集合A上的二元關(guān)系，則有

(1)sr(R)=rs(R)。

(2)tr(R)=rt(R)。

(3)ts(R)st(R)。

證明(1)已知(R∪IA)－1=R－1∪IA－1，IA－1=IA，因此

sr(R)=s(R∪IA)=(R∪IA)∪(R∪IA)－1=R∪IA∪R－1∪IA

=(R∪R－1)∪IA=s(R)∪IA=rs(R)?

(2)對于任意n∈N，有InA=IA且，因此

tr(R)=t(R∪IA)=

(R∪IA)i=

=t(R)∪IA

=rt(R)

(3)不難證明，如果R1

R2，那么s(R1)s(R2)且t(R1)t(R2)，因?yàn)閟(R)R，所以有ts(R)t(R)，于是有sts(R)st(R)。

根據(jù)定理3.8.3(2)可知ts(R)是對稱的，所以有sts(R)=ts(R)。

故有ts(R)st(R)成立。

證畢??????3.9.1集合的劃分

在集合的研究中，除了集合的運(yùn)算、集合之間的比較之外，有時要把一個集合分成若干子集加以討論。3.9等價關(guān)系

定義3.9.1

給定非空集合A和集合簇π={A1，A2，…，Am}，如果

(1)Ai

A且Ai≠

(1≤i≤m);

(2)A=

;

(3)Ai∩Aj=

(1≤i，j≤m且i≠j)，

那么稱π是A的一個劃分(partition)。若π滿足條件(1)、(2)，則稱π是集合A的一個覆蓋(cover)。

通俗地說，如果一組兩兩不相交的非空集合的并集等于A，那么以這組集合為元素的集合稱為A的劃分。

如果一組非空集合的并集等于A，那么以這組集合為元素的集合稱為A的覆蓋。???

定義3.9.2

一個集合A的劃分π中的元素Ai稱為該劃分的塊(block)。

定義3.9.3

設(shè)π為非空集合A的一個劃分，若π為有限集合，則稱劃分的塊數(shù)|π|為劃分的秩。若π為無限集合，稱π的秩是無限的。

對于有限集合A，秩為1的劃分稱為A的最小劃分，秩為|A|的劃分稱為A的最大劃分。3.9.2等價關(guān)系和等價類

定義3.9.4

設(shè)R是集合A上的一個二元關(guān)系，若R是自反、對稱和傳遞的，則稱R為等價關(guān)系(equivalencerelation)。

例3

A={a，b，c，d}，A上的二元關(guān)系R={〈a，a〉，〈a，b〉，〈b，a〉，〈b，b〉，〈c，c〉，〈c，d〉，〈d，c〉，〈d，d〉}，驗(yàn)證關(guān)系R是等價關(guān)系。

解(a)因?yàn)镮A

R，所以R是自反的。

(b)因?yàn)镽－1={〈a，a〉，〈b，a〉，〈a，b〉，〈b，b〉，〈c，c〉，〈d，c〉，〈c，d〉，〈d，d〉}=R，所以R是對稱的。

(c)因?yàn)镽

R={〈a，a〉，〈a，b〉，〈b，a〉，〈b，b〉，〈c，c〉，〈c，d〉，〈d，c〉，〈d，d〉}R，所以R是傳遞的。

綜上所述，R是等價關(guān)系，其關(guān)系圖如圖3.9.1所示。?°

圖3.9.1

定義3.9.5

設(shè)R是非空集合A上的等價關(guān)系，對于任意a∈A，稱集合［a］R={x|x∈A，xRa}為a關(guān)于R的等價類(equivalenceclass)，a稱為等價類［a］R的代表元素。如果等價類個數(shù)有限，則R的不同等價類的個數(shù)叫做R的秩，否則秩是無限的。

等價類［a］R是所有與a具有R關(guān)系的元素構(gòu)成的集合。由等價類的定義可知，［a］R是非空的，因?yàn)閍∈［a］R。

定理3.9.1

設(shè)R是非空集合A上的等價關(guān)系,對于a，b∈A有aRb，當(dāng)且僅當(dāng)［a］R=［b］R。

證明充分性。若［a］R=［b］R，因?yàn)閍∈［a］R，所以a∈［b］R，故aRb。

必要性。若aRb，對任意x∈［a］R，有xRa，由傳遞性可知xRb，即x∈［b］R，所以［a］R

［b］R，同理可證［b］R

［a］R。

故［a］R=［b］R。

證畢??

定義3.9.6

設(shè)R是集合A上的等價關(guān)系，由R確定的所有等價類組成的集合，稱為集合A上關(guān)于R的商集(quotientset)，記為A/R。

A/R={［x］R|x∈A}

例5

設(shè)A={1，2，3，4，5，8}，R是A上的“模3同余”關(guān)系。

(a)求關(guān)于R的所有等價類。

(b)求A/R。

解

R={〈1，1〉，〈1，4〉，〈2，2〉，〈2，5〉，〈2，8〉,〈3，3〉,〈4，1〉，〈4，4〉，〈5,2〉，〈5，5〉,〈5，8〉，〈8，2〉,〈8，5〉,〈8，8〉}，R是一個等價關(guān)系，其關(guān)系圖如圖3.9.2所示。圖3.9.2

定理3.9.2

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

(1)任取x∈A，［x］R≠。

(2)任取x,y∈A，或者［x］R=［y］R，或者［x］R∩

［y］R=。

(3)

=A

。

證明(1)任取x∈A，因?yàn)椤磝，x〉∈R，所以x∈