離散數(shù)學(xué)集合論部分

離散數(shù)學(xué)集合論部分第二部分集合與關(guān)系對(duì)于從事計(jì)算機(jī)科學(xué)工作的人們來說，集合論是必不可少的基礎(chǔ)知識(shí)。例如程序設(shè)計(jì)語言、數(shù)據(jù)結(jié)構(gòu)、形式語言等都離不開子集、冪集、集合的分類等概念。集合成員表和范式在邏輯設(shè)計(jì)、定理證明中也都有重要應(yīng)用。本部分從集合的直觀概念出發(fā)，介紹了集合論中的一些基本概念和基本理論。

集合論是研究集合的一般性質(zhì)的數(shù)學(xué)分支，它研究集合不依賴于組成它的事物的特性的性質(zhì)。集合論總結(jié)出由各種對(duì)象構(gòu)成的集合的共同性質(zhì)，并用統(tǒng)一的方法來處理。集合論的特點(diǎn)是研究對(duì)象的廣泛性，集合是各種不同對(duì)象的抽象，這些對(duì)象可以是數(shù)或圖形，也可以使任意其它事務(wù)。

1.二十六個(gè)英文字母可以看成是一個(gè)集合；2.所有的自然數(shù)看成是一個(gè)集合；3.重慶郵電大學(xué)計(jì)算機(jī)學(xué)院2010級(jí)的本科學(xué)生可以看成是一個(gè)集合；4.這間教室中的所有座位可以看成是一個(gè)集合。例:集合的基本概念

組成一個(gè)集合的那些對(duì)象或單元稱為這個(gè)集合的元素。通常，用小寫的英文字母a,b,c,…表示集合中的元素。元素可以是單個(gè)的數(shù)字也可以是字母，還可以是集合。如：A={a,c,b};B={{a},,{c}}集合的元素元素與集合的屬于關(guān)系：設(shè)A是一個(gè)集合，a是集合A中的元素，元素與集合的關(guān)系：屬于∈；不屬于

若a是集合A中的元素記為a

A，讀作a屬于A；若a不是集合A中的元素，則記為a

A，讀作a不屬于A。例如：A是正偶數(shù)集合，則2

A，4

A，6

A；而1

A，3

A，19

A。特別注意：①集合并不決定于它的元素展示方法。集合的元素被重復(fù)或重新排列，集合并不改變，即{a,a,b,c,d,c}={a,b,c,d}。②集合的元素可以是具體事物，可以是抽象概念，也可以是集體，如一本書，一支筆；集合{1,2,3}可以是集合B={一本書，一支筆，{1,2,3}}的元素。特別地，以集合為元素的集合稱為集合族或集合類如A={{1,2,3},{8,9,6}}。③集合中元素之間可以有某種關(guān)聯(lián)，也可以彼此毫無關(guān)系。

有限集A中所含元素的個(gè)數(shù)稱為集合的元數(shù)。記作：|A|如：A={1,3,2,4,5,9}則|A|=

6；

設(shè)A是所有英文字母組成的集合，則

A=26。特別，||=0集合的元素?cái)?shù)列舉法(列元素法)：將集合中的元素一一列舉，或列出足夠多的元素以反映集合中元素的特征，例如：V={a,b,c,d,e}或

B={1,2,3,4,5,6,……}。描述法(謂詞表示法):將集合元素的條件或性質(zhì)用文字或符號(hào)在花括號(hào)內(nèi)豎線后面表示出來。A={x|關(guān)于x的一個(gè)命題P};

如：B={x|0<x<10};B={x|x=a2,a是自然數(shù)}。集合的表示法EAae文氏圖

用一個(gè)大的矩形表示全集，在矩形內(nèi)畫一些圓或其它的幾何圖形，來表示集合，有時(shí)也用一些點(diǎn)來表示集合中的特定元素。

例如：集合A={a,b,c,d,e}，用文氏圖表示如下:dcb幾類特殊集合:N={0,1,2,3,···}，即自然數(shù)集合。Z={···,-2,-1,0,1,2,3,···}，即整數(shù)集合。Z+={1,2,3,···}，即正整數(shù)集合。Q=有理數(shù)集合。R=實(shí)數(shù)集合。C=復(fù)數(shù)集合。確定性；互異性；無序性；多樣性；集合的特征任何一個(gè)對(duì)象，或者是這個(gè)集合的元素，或者不是，二者必居其一；例如：A={x|x是自然數(shù)，且x<100}； B={x|x+1=3}； C={x|x是大學(xué)生}。確定性集合中任何兩個(gè)元素都是不同的，即集合中不允許出現(xiàn)重復(fù)的元素。例如：集合A={a,b,c,c,b,d}，實(shí)際上，應(yīng)該是A={a,b,c,d}。

再如{1,2,3,2,4}={1,2,3,4}?；ギ愋约吓c其中的元素的順序無關(guān)；例如：集合{a,b,c,d,e}、{d,c,e,a,b}、{e,c,d,b,a}，都是表示同一個(gè)集合。集合{4,2,1,3}={1,2,3,4}。無序性集合中的元素可以是任意的對(duì)象，相互獨(dú)立，不要求一定要具備明顯的共同特征。例如：

A={a,{a},{{a},b},{{a}},1}；

A={1,a,*,-3,{a,b},{x|x是汽車},地球}注意:對(duì)于任何集合A,都有A

A。多樣性設(shè)A，B是兩個(gè)集合，若B的元素都是A的元素，則稱B是A的子集，也稱A包含B，或B被A包含，記以B

A

，或A

B

。若B

A

，且A

B，則稱B是A的真子集，也稱A真包含B，或B真包含于A，記以A

B，或B

A。子集：例3.1設(shè)A={a,b,{c},{a},{a,b}}試判斷下列表達(dá)式正確與否。（1）aA（2）{a}A（3）{a}

A（4）?A（5）?

A（6）bA（7）A（8）

A（9）{a,b}A

(10){a,b}A(11)cA(12){c}A(13){c}

A(14){a,b,c}A。

解：(4)，(7)，(11)，(13),(14)錯(cuò)誤。例3.2對(duì)于任意集合A,B和C,下述論斷是否正確（1）若AB,BC則AC（2）若AB,BC則AC（3）若AB,BC則AC

解：（1）√（2）×（3）×對(duì)(3)舉反例A=?,B={1},C={{1}}。例3.3設(shè)A={{1,2,3},{4,5},{6,7,8}}下列選項(xiàng)正確的是（3）；（1）1A（2）{1,2,3}

A

（3）{{4,5}}

A（4）?A

例3.4下列各選項(xiàng)錯(cuò)誤的是（2）；（1）?

?

（2）?

?

（3）?

{

?}

（4）?

{

?}

例3.5在0___?之間填上正確的符號(hào)：（4）（1）=

（2）

（3）

（4）

當(dāng)兩個(gè)集合A和B的元素完全一樣，即A，B實(shí)際上是同一個(gè)集合時(shí)，則稱集合A，B相等，記為A=B。

符號(hào)化表示為：A=B

A

B∧B

A例：設(shè)A={x|x是偶數(shù)，且0<x<10}，B={2,4,6,8}，則A=B。集合相等注：說明兩個(gè)集合A、B相等，需說明兩個(gè)問題：1、A是集合B的子集（A

B）（任意元素a∈A，有a∈B）2、B是集合A的子集（A

B）（任意元素a∈B，有a∈A）集合的包含關(guān)系也可表成A

B

(

x)(x

A

x

B)這表明，要證明A

B，只需對(duì)任意元素x，有下式x

A

x

B成立即可?？占缓魏卧氐募辖凶隹占?，記作φ?？占姆?hào)化表示為：

={x|P(x)

P(x)}。其中P(x)為任何謂詞公式。如：A={x|x∈R∧x2+1=0}。該方程無實(shí)數(shù)解。注意：φ≠{φ}由定義可知，對(duì)任何集合A，有

A。這是因?yàn)槿我庠豿，公式x

x

A總是為真。注意：

與{

}是不同的。{

}是以

為元素的集合，而

沒有任何元素，能用

構(gòu)成集合的無限序列：

，{

}，{{

}}，···該序列除第一項(xiàng)外，每項(xiàng)均以前一項(xiàng)為元素的集合。定理：空集是一切集合的子集。證明：對(duì)于任何集合A，由子集定義有,φ

A

x(x∈φx∈A)右邊的蘊(yùn)涵式中前件為x∈φ為假，所以整個(gè)蘊(yùn)涵式對(duì)一切x為真，所以φ

A為真推論：空集是唯一的。證明:如不唯一,設(shè)存在空集φ1和φ2,由空集是一切集合的子集得φ1

φ2和φ2

φ1。根據(jù)集合相等的定義得，φ1=φ2全集：如果一個(gè)集合包含了所要討論的每一個(gè)集合，則稱該集合為全集，記為E或U。它可形式地表為E={x|P(x)

P(x)}。其中P(x)為任何謂詞公式。注意符號(hào)和意義的區(qū)別：表示元素與集合之間的關(guān)系，而則表示集合與集合之間的關(guān)系。但由于集合的抽象性，集合中的元素可以是集合，故可以發(fā)生如：AB且AB的情形例設(shè)A={{1,2,3},1,2,3}，則{1,2,3}

A且{1,2,3}

A。

注意：對(duì)任意集合A,有A

A。空集是任意集合的子集，且空集是唯一的。對(duì)于任意兩個(gè)集合A、B，A=B的充要條件是A

B且B

A。（這個(gè)結(jié)論非常簡(jiǎn)單，但它非常重要，很多證明都是用這個(gè)方法或思路來證明。）重要結(jié)論設(shè)A是集合，A的所有子集為元素做成的集合稱為A的冪集,記以P(A)

符號(hào)化表示為：

P(A)={x|xA}。例：A={a,b,c}，則

P(A)={,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}。冪集例3.6設(shè)A={a,{a}}下列選項(xiàng)錯(cuò)誤的是A.aP(A)B.{a}P

(A)C.{{a}}P(A)D.{{a}}P

(A)例3.7冪集P(P(P()))為（C）A.{{

},{,{

}}}B.{,{,{

},{}}

C.{,{,{

}},{{}},{

}}D.{,{,{

}}}

∵P(A)={,{a},{{a}},{a,{a}}}

例3.8判斷下面的關(guān)系是否正確,并簡(jiǎn)要說明理由。⑴{a,b}{a,b,c,{a,b,c}}⑵{a,b}∈{a,b,c,{a,b,c}}⑶{a,b}{a,b,{{a,b}}}⑷{a,b}∈{a,b,{{a,b}}}解答：

對(duì)選項(xiàng)⑴,因?yàn)閧a,b}中每個(gè)元素(只有a和b)均在集合{a,b,c,{a,b,c}}對(duì)選項(xiàng)⑶,因?yàn)閧a,b}中每個(gè)元素(只有a和b)均在集合{a,b,{{a,b}}}對(duì)選項(xiàng)⑵,集合{a,b,c,{a,b,c}}中含有4個(gè)元素，分別為a,b,c,{a,b,c}沒有{a,b}，所以不正確。對(duì)選項(xiàng)⑷,集合{a,b,{{a,b}}}中含有3個(gè)元素，分別為a,b,{{a,b}}沒有{a,b}，所以不正確。若A為有窮集，|A|=n，則

|2A|=Cn0+Cn1+

…+Cnn

=2n。xP(A)當(dāng)且僅當(dāng)x

A。設(shè)A、B是兩個(gè)集合，A

B當(dāng)且僅當(dāng)P(A)P(B)。冪集的性質(zhì)并A

B={x|x

A

x

B}；交A

B={x|x

A

x

B}；相對(duì)補(bǔ)A

B={x|x

A

x

B}；對(duì)稱差A(yù)

B=(A

B)

(B

A)=(A

B)(A

B)；絕對(duì)補(bǔ)

A=E

A?！?.2集合的基本運(yùn)算ABAAB~AABABA-BABAABBCAB(AB)-C集合運(yùn)算對(duì)應(yīng)的文氏圖表示并和交運(yùn)算可以推廣到有窮個(gè)集合上，即

A1

A2

…An={x|x

A1

x

A2

…

x

An}

A1

A2

…An={x|x

A1

x

A2

…

x

An}某些重要結(jié)果：

A

B

A

A

B

A

B=

A

B=

A

B=A集合的廣義交和廣義并

設(shè)S為集合，S的元素的元素構(gòu)成的集合稱為S的廣義并，記為

S，其中

S={x

z(z

S

x

z}；

設(shè)S非空集合，S的元素的公共元素構(gòu)成的集合稱為S的廣義交，記為

S，其中

S={x

z(z

S

x

z}。說明：（1）規(guī)定

=，

無意義。（2）若，則由定義不難證明

S=

S=（3）并運(yùn)算和廣義并運(yùn)算的運(yùn)算符相同，但前者是二元運(yùn)算，后者是一元運(yùn)算，因此在運(yùn)算過程中不會(huì)對(duì)

產(chǎn)生誤解。例：設(shè)集合A={{a,b,c},{a,c,d},{a,c,e}}，求

A，

A，

A，

A，

A，

A。解：

A={a,b,c,d,e}；

A={a,c}；

A=a

b

c

d

e；

A=a

c；

A=a

c；

A=a

b

c

d

e。優(yōu)先級(jí)一般地,一元運(yùn)算符(補(bǔ)集,冪集,廣義并,廣義交)優(yōu)先于二元運(yùn)算符(差集,并集,交集,對(duì)稱差,笛卡兒積)；二元運(yùn)算符優(yōu)先于集合關(guān)系符(∈,,＝,)。此外,許多集合表達(dá)式里還使用到聯(lián)結(jié)詞,和邏輯關(guān)系符以及括號(hào),我們規(guī)定:(1)集合運(yùn)算優(yōu)先于邏輯運(yùn)算；(2)括號(hào)內(nèi)優(yōu)先于括號(hào)外；(3)同一括號(hào)內(nèi),同一優(yōu)先級(jí)按從左至右運(yùn)算。集合運(yùn)算律冪等律：A∪A＝A；A∩A＝A同一律：A∪

＝A；A∩E=A零律：A∪E=E；A∩

＝

結(jié)合律：(A∪B)∪C＝A∪(B∪C)；(A∩B)∩C＝A∩(B∩C)交換律：A∪B＝B∪A；A∩B＝B∩A分配律：A∪（B∩C）＝（A∪B）∩(A∪C)；A∩(B∪C)=(A∩B)∪(A∩C)排中律：矛盾律：吸收律：A∩（A∪B）＝AA∪(A∩B)＝A摩根律：雙重否定律：其它常用結(jié)論：A∩BA,A∩BB；A

A∪B,B

A∪B；A-B

A，A-B=A∩~B；A∪B=BABA∩B=A

A-B=；

AB=BA；(AB)C=A(BC)

A

=A；AA=

；AB=ACB=C。集合等式的證明，可采用命題邏輯的等值式證明，其基本思想是互為子集：欲證:A=B即證:即證:對(duì)任意的x,，當(dāng)上述過程可逆時(shí)，可以合并為對(duì)任意的x,集合相等的證明方法例：證明下列集合恒等式。（1）A∪（B∩C）＝（A∪B）∩(A∪C)（2）（3）證明：(1)對(duì)任意的x(2)對(duì)任意的x(3)對(duì)任意的x例3.3.2證明：（1）（2）A

B=（A∪B）-（A∩B）證明：(1)(2)A

B=（A-B）（B-A）例證明(A∪B)-C=(A-C)∪(B-C).證明:對(duì)于

xx∈(A∪B)-C

x∈(A∪B)∧x

C

(

x∈A∨x∈B)∧x

C

(

x∈A∧x

C)∨(x∈B∧x

C)

x∈(A-C)∨x∈(B-C)

x∈(A-C)∪(B-C)∴(A∪B)-C=(A-C)∪(B-C)例證明證明：(1)必要性：對(duì)任意的X,因此，。(2)充分性：對(duì)任意的x，因此，結(jié)論得證。例求在1和1000之間不能被5或6，也不能被8整除的數(shù)的個(gè)數(shù)解：設(shè)1到1000之間的整數(shù)構(gòu)成全集E，A，B，C分別表示其中可被5，6或8整除的數(shù)的集合。解：在A∩B∩C中的數(shù)一定可被5,6和8的最小公倍數(shù)5,6,8=120整除，即

A∩B∩C=1000/5,6,8=8同樣可得

A∩B=1000/5,6=33；

A∩C=1000/5,8=25；

B∩C=1000/6,8=41；然后計(jì)算

A=1000/5=200；B=1000/6=166；C=1000/8=125從而得到A∪B∪C=200+100+33+67=400所以，不能被5或6,也不能被8整除的數(shù)有600個(gè)。150100671733258對(duì)上述子集計(jì)數(shù)：

|S|=1000；|A|=

1000/5

=200；|B|=1000/6=133；|C|=1000/8

=125；|AB|=1000/30

=33；|BC|=1000/40

=25|BC|=1000/24

=41；|ABC|=1000/120

=8。代入公式：

N=1000

(200+133+125)+(33+25+41)

8=600。這個(gè)方法叫容斥原理。稱為包含排斥原理，簡(jiǎn)稱容斥原理。容斥原理定理：有窮集S中不具有p1,p2,…,pm元素?cái)?shù)是推論設(shè)A1,A2,…,An是n個(gè)集合，則例某班有25個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球(指籃球或排球)，求不會(huì)打這三種球的人數(shù)。解：設(shè)會(huì)打排球、網(wǎng)球、籃球的學(xué)生集合分別為A，B和C，則有A=12，B=6，C=14，S=25A∩C=6，B∩C=5，A∩B∩C=2現(xiàn)在求A∩B，因?yàn)闀?huì)打網(wǎng)球的人都會(huì)打另一種球，即籃球和排球，而其中會(huì)打籃球的有5人，那么另一個(gè)人肯定會(huì)打排球但不會(huì)打籃球，再加上會(huì)打三種球的2人，共有3人會(huì)打排球和網(wǎng)球，即A∩B=3，根據(jù)容斥定理有A∩B∩C=25-（12+6+14）+（3+6+5）-2=5324排球12籃球14網(wǎng)球6155不會(huì)打三種球人數(shù)為：25-(12+5+3)=5課堂練習(xí)：證明下列等式第四章二元關(guān)系和函數(shù)說起關(guān)系這個(gè)詞，對(duì)我們并不陌生，世界上存在著各種各樣的關(guān)系，人與人之間的“同志”關(guān)系；“同學(xué)”關(guān)系；“朋友”關(guān)系；“師生”關(guān)系；“上下級(jí)”關(guān)系；“父子”關(guān)系；兩個(gè)數(shù)之間有“大于”關(guān)系；“等于”關(guān)系和“小于”關(guān)系；兩個(gè)變量之間有一定的“函數(shù)”關(guān)系；計(jì)算機(jī)內(nèi)兩電路間有導(dǎo)線“連接”關(guān)系；程序間有“調(diào)用”關(guān)系等等。所以對(duì)關(guān)系進(jìn)行深刻的研究，對(duì)數(shù)學(xué)與計(jì)算機(jī)科學(xué)都有很大的用處。集合的笛卡爾積與二元關(guān)系由兩個(gè)元素x,y（允許x=y）按一定順序排列成的二元組叫做一個(gè)有序?qū)蛐蚺迹涀?lt;x,y>,其中x是它的第一元素，y是它的第二元素。有序?qū)?lt;x,y>具有以下性質(zhì)：(1)當(dāng)x≠y時(shí)，<x,y>≠<y,x>(2)<x,y>=<w,v>x=w∧y=v例：已知<x+3,y-2>=<y+7,3y-x>，求x和y。解：由有序?qū)ο嗟鹊某湟獥l件得x+3=y+7y-2=3y-x解得x=6,y=2。一個(gè)有序n元組(n≥3)是一個(gè)有序?qū)?，其中第一個(gè)元素是一個(gè)有序n-1元組，一個(gè)有序n元組記作<x1,x2,…,xn>,即<x1,x2,…,xn>=<

<x1,x2,…,xn-1>,xn>

例：空間直角坐標(biāo)系中點(diǎn)的坐標(biāo)<1,-1,3>,<2,4.5,0>等都是有序3元組。n維空間中點(diǎn)的坐標(biāo)或n維向量都是有序n元組。形式上也可以把<x>看成有序1元組。設(shè)A，B為集合，用A中元素為第一元素，B中元素為第二元素構(gòu)成有序?qū)ΑＫ羞@樣的有序?qū)M成的集合叫做A和B的笛卡兒積，記作A×B。笛卡兒積的符號(hào)化表示為：A×B={<x,y>|x∈A∧y∈B}例：若A={1,2},B={a,b,c},則A×B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}B×A={<a,1>,<a,2>,<b,1>,<b,2>,<c,1>,<c,2>}易知：若|A|=m,(即集合A的元素的個(gè)數(shù)),|B|=n,則|A×B|=|B×A|=mn有序?qū)褪怯许樞虻臄?shù)組，如<x,y>，x,y的位置是確定的，不能隨意放置。注意：有序?qū)?lt;a，b>

<b,a>，以a,b為元素的集合{a,b}={b,a}；有序?qū)?a,a)有意義，而集合{a,a}不成立。笛卡兒積是一種集合合成的方法，把集合A，B合成集合A×B，規(guī)定A×B＝{<x,y>

x

A,y

B}。由于有序?qū)?lt;x,y>中x,y的位置是確定的，因此A×B的記法也是確定的，不能寫成B×A。

笛卡兒積也可以多個(gè)集合合成A1×A2×…×An。

笛卡兒積的運(yùn)算性質(zhì)。笛卡兒積的性質(zhì)：1、對(duì)任意集合A，根據(jù)定義有A×φ=φ×A=φ2、一般來說，笛卡兒積不滿足交換律，即A×B≠B×A（當(dāng)A≠BB≠φ、A≠φ時(shí)）3、笛卡兒積不滿足結(jié)合律，即(A×B)×C≠A×(B×C)（當(dāng)A≠φ∧B≠φ∧C≠φ時(shí)）4、笛卡兒積運(yùn)算對(duì)并和交運(yùn)算滿足分配律，即

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)例：證明(B∩C)×A=(B×A)∩(C×A)對(duì)于<x,y><x,y>∈(B∩C)×Ax∈(B∩C)∧y∈Ax∈B∧x∈

C∧y∈Ax∈B∧x∈C∧y∈A∧y∈A(x∈B∧y∈A)∧(x∈C∧y∈A)<x,y>∈B×A∧<x,y>∈C×A<x,y>∈(B×A)∩(C×A)∴(B∩C)×A=(B×A)∩(C×A)例：設(shè)A，C，B，D為任意集合，判斷以下命題是否為真，并說明理由。(1)A×B=A×C=>B=

C。(2)A-(B×C)=(A-B)×(A-C)。(3)存在集合A,使得A

A×A。解：(1)不一定為真。反例A=φ,B、C為任意不相等的非空集合。(2)不一定為真。反例A={1},B={2},C={3}.(3)為真。當(dāng)A=φ時(shí)成立。

設(shè)A1,A2,…,An,是集合(n≥2),它們的n階笛卡兒積記作A1×A2×…×An，其中A1×A2×…×An={<x1,x2,…,xn>

|x1

A1∧x2

A2∧…∧xn

An

}。當(dāng)A1=A2=…=An=A時(shí),將起n階笛卡兒積記作An例，A={a,b},則：A3=A×A×A={a,b}×{a,b}×{a,b}={<a,a,a>,<a,a,b>,<a,b,a>,<a,b,b>,<b,a,a>,<b,a,b>,<b,b,a>,<b,b,b>}。例：設(shè)集合A={a,b},B={1,2,3},C=iecekwk,求A×B×C，B×A。解：先計(jì)算A×B＝{<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>}A×B×C＝{<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>}×oyekgey＝{<a,1,d>,<a,2,d>,<a,3,d>,<b,1,d>,<b,2,d>,<b,3,d>}B×A＝{<1,a>,<2,a>,<3,a>,<1,b>,<2,b>,<3,b>}

。例：設(shè)集合A＝{1,2},求A×P(A)。解：P(A)={

,{1},{2},{1,2}} A×P(A)＝{1,2}×{

,{1},}{2},{1,2} ={<1,

>,<2,

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

如果一個(gè)集合符合以下條件之一：(1)集合非空，且它的元素都是有序?qū)?2)集合是空集則稱該集合為一個(gè)二元關(guān)系，記作R，簡(jiǎn)稱為關(guān)系。對(duì)于二元關(guān)系R，若<x,y>∈R,可記作xRy;如果<x,y>R,則記作xRy。例：R1={<1,2>,<a,b>}aR1b,1R12。二元關(guān)系是兩種客體之間的聯(lián)系，例如某學(xué)生學(xué)習(xí)語文、數(shù)學(xué)、外語，表示為：A＝{語文,數(shù)學(xué),外語}功課的成績(jī)分四個(gè)等級(jí)，記作B＝{A，B，C，D}于是該生成績(jī)的全部可能為A×BA×B＝{<語文,A>,<語文,B>,<語文,C>,<語文,D>,<數(shù)學(xué),A>,<數(shù)學(xué),B>,<數(shù)學(xué),C>,<數(shù)學(xué),D>,<外語,A>,<外語,B>,<外語,C>,<外語,D>}而該生的實(shí)際成績(jī)P＝{<語文,B>,<數(shù)學(xué),A>,<外語,D>}P是A×B的一個(gè)子集，它表示了功課與其成績(jī)的一種關(guān)系。由此可見：兩個(gè)集合之間的二元關(guān)系，實(shí)際上就是兩個(gè)元素之間的某種相關(guān)性。設(shè)A，B為集合，A×B的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系；特別當(dāng)A=B時(shí)則叫做A上的二元關(guān)系。例：若A={a,b}，B={1,2,3}，則A×B={<a,1>,<a,2>,<a,3>,<b,1>,<b,2><b,3>}令R1={<a,1>,<a,3>,<b,1>},R2={<a,2>,<b,1><b,2>},R3={<a,1>}。因?yàn)镽1

A×B，R2

A×B，R3

A×B，所以R1,

R2和R3均是由A到B的二元關(guān)系。又例：若A={a,b}，B={1,2,3}，則B×A={<1,a>,<1,b>,<2,a>,<2,b>,<3,a><3,b>}令R4={<1,a>,<1,b>},R5={<2,a>,<3,a><3,b>},因?yàn)镽4B×A，R5B×A，所以R4和R5均是由B到A的關(guān)系。又B×B={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}。令R6={<1,1>，<3,2>},R7={<3,2>,<2,1><1,3>}因?yàn)镽6B×B，R7B×B，所以R6和R7均是集合B上的關(guān)系。若集合|A|=n,則集合A上的二元關(guān)系有多少個(gè)？答：|A|=n，則|A×A|=n2,A×A的任一個(gè)子集就是A上的二元關(guān)系，即P(A)=2n個(gè)。２例A={1,2}則A×A有2n個(gè)不同的二元關(guān)系；A×A={1,2}×{1,2}={<1

1>,<1,2>,<2,1>,<2,2>}。A×A的任一個(gè)子集就是A×A的冪集，即P(A)P(A)={,{<1,1>},{<1,2>},{<2,1>},{<2,2>}{<1,1>,<1,2>},{<1,1>,<2,1>},{<1,1>,<2,2>}

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

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

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

{<1,1>,<1,2>,<2,2>},{<1,1>,<2,1>,<2,2>},{<1,2>,<2,1>,<2,2>}{<1,1>,<1,2>,<2,1>,<2,2>}}２三類特殊的關(guān)系空關(guān)系：對(duì)于任何集合A，空集φ是A×A的子集，稱作A上的空關(guān)系；全關(guān)系：定義EA={<x,y>|x∈A∧y∈A}=A×A為全域關(guān)系；恒等關(guān)系：定義IA={<x,x>|x∈A}為A上恒等關(guān)系。例：若A={1,2,3}，則EA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}

IA={<1,1>,<2,2>}。例：設(shè)A={1,2,3,4}，請(qǐng)表示下列關(guān)系。(1)R={<x,y>|x是y的倍數(shù)}(2)R={<x,y>|(x-y)2∈A}(3)R={<x,y>|x除y是素?cái)?shù)}(4)R={<x,y>|x≠y}解：(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<2,1>,<3,1>,<4,1>,<4,2>}；(2)R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}；(3)R={<1,2>,<1,3>,<2,4>}；(4)R=

<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}關(guān)系表示法有窮集合上的二元關(guān)系的三種表示方法：集合表示法（前已使用）關(guān)系矩陣法關(guān)系圖關(guān)系矩陣是表示關(guān)系的另一種有效的方法，其優(yōu)點(diǎn)是可以利用矩陣作為研究關(guān)系的手段，而且這樣做便于計(jì)算機(jī)進(jìn)行處理。

設(shè)R：AB，A和B都是有限集，且

|A|=n,|B|=m,A,B中的元素已按一定的次序排列若A={x1,x2,…,xn},B={y1,y2,…,ym}且R

A

B,若則稱矩陣M(R)=(rij)n

m為R的關(guān)系矩陣。關(guān)系矩陣法

0111MR=001100010000例A={1,2,3,4},R為A上的小于關(guān)系，則R={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}R的關(guān)系矩陣為：12341234例:設(shè)集合A＝{2,3,4},B={8,9,12,14}。R是由A到B的二元關(guān)系，定義：R={<a,b>|a整除b}寫出R的表達(dá)式和關(guān)系矩陣。解：R={<2,8>,<2,12>,<2,14>,<3,9>,<3,12>,<4,8>,<4,12>}R的關(guān)系矩陣：

關(guān)系圖關(guān)系圖是表示關(guān)系的一種直觀形象的方法，設(shè)R：AB，A和B都是有限集，A={x1,x2,…,xn},B={y1,y2,…,ym}關(guān)系R的有序?qū)?lt;xi,yj>可用圖中從結(jié)點(diǎn)xi到y(tǒng)j的有向邊表示，這樣即可將關(guān)系用圖表示之。例設(shè)R:AB，A={x1,x2,x3,x4},B={y1,y2,y3}R={<x1,y2>,<x2,y1>,>,<x2,y2>，<x2,y3><x3,y3>}R的關(guān)系如下圖所示x1x2x3x4y1y2y3設(shè)R是在A上的二元關(guān)系，A={x1,x2,…,xn}關(guān)系R的有序偶<xi,xj>可用圖中從結(jié)點(diǎn)xi到xj的有向邊表示，這樣即可將關(guān)系用圖表示之。例：設(shè)R:AA，A={a,b,c,d}R={<a,b>,<a,c>,<b,a>,<b,c>,<c,c>}R的關(guān)系如下圖所示：abcd

例：設(shè)集合A={a,b,c,d},R是A上的關(guān)系R={<a,a>,<a,b>,<a,c>,<b,c>,<d,c>,<d,d>},試以關(guān)系矩陣和關(guān)系圖來表示關(guān)系R。解：（1）關(guān)系矩陣為：（2）關(guān)系圖為：關(guān)系的運(yùn)算（1）R中所有的有序?qū)Φ牡谝辉貥?gòu)成的集合稱為R的定義域，記作domR。domR={x|

y(<x,y>

R}（2）R中所有的有序?qū)Φ牡诙貥?gòu)成的集合稱為R的值域，記作ranR。ranR={y|

x<x,y>

R}（3）R的定義域和值域的并集稱為R的域，記作fldR。

fldR=domR

ranR例：設(shè)R={<1,1>,<1,4>,<2,2>,<3,3>}則domR={1，2，3}ranR={1，2，3，4}fldR={1，2，3，4}限制關(guān)系設(shè)R為二元關(guān)系，A是集合（1）R在A上的限制，記作R

A,其中R

A={<x,y>|xRy

x

A}（2）A在R下的象，記作R[A]，其中R[A]=ran(R

A)例：設(shè)集合A={1,2,3,4},R是A上的關(guān)系R={<1,1>,<1,3>,<2,4>,<3,2>,<3,4>,<4,1>},集合B={1,2,4},試求R

B及R[B]。解：RB={<1,1>,<1,3>,<2,4>,<4,1>}；R[B]={1，3，4}。逆運(yùn)算設(shè)R為二元關(guān)系，稱為R的逆關(guān)系，其中={<x,y>|<y,x>

R}

定理4.1設(shè)F是任意關(guān)系，則（1）（2）證明：（1）對(duì)任意的<x,y>（2）對(duì)任意的y對(duì)任意的x復(fù)合運(yùn)算設(shè)F,G為二元關(guān)系G對(duì)F的右復(fù)合記作F?G,其中F?G={<x,y>|

t(<x,t>

F

<t,y>

G}。說明：（1）本書采用右復(fù)合的規(guī)則，而有的教材采用左復(fù)合規(guī)則，兩者都可行，只是需要注意它們的區(qū)別，從變換的角度來說，G對(duì)F的右復(fù)合是先F變換后G變換，而G對(duì)F的左復(fù)合是先G變換后F變換。（2）一般來說，并沒有F?G等于G?F，請(qǐng)讀者仔細(xì)注意其區(qū)別。例：設(shè)F={<3,3>,<6,2>},G={<2,3>},則求F?F，G?G，F(xiàn)?G和G?F。解：F?F={<3,3>}，G?G=

F?G={<6,3>}G?F={<2,3>}。例：設(shè)有集合A={4,5,8,15},B={3,4,5,9,11}C={1,6,8,13},F是由A到B的關(guān)系,G是由B到C的關(guān)系,分別定義為F={<a,b>||b-a|=1}G={<b,c>||b-c|=2或|b-c|=4}求合成關(guān)系G

F和F

G解：先求G

F,由題意知F={<4,3>,<4,5>,<5,4>,<8,9>}；G={<3,1>,<4,6>,<4,8>,<5,1>,<9,13>,<11,13>}；G

F={<4,1>,<5,6>,<5,8>,<8,13>}。

定理：設(shè)F、G、H是任意關(guān)系,則(1)(F-1)-1=F(2)dom(F-1)=ranF,ranF-1=domF(3)(F

G)

H=F

(G

H)(4)(F

G)-1=G-1

F-1證明:(1)任取<x,y>,由逆的定義有<x,y>∈(F-1)-1<y,x>∈F-1<x,y>∈F∴(F-1)-1=F(2)任取x,x∈ranF-1

y(<y,x>∈F-1)

y(<x,y>∈F)

x∈domF∴ranF-1=domF同理可證dom(F-1)=ranF證明:(3)任取<x,y>,<x,y>∈(F

G)

H

t(<x,t>∈F

G∧<t,y>∈H)

ts(<x,s>∈F∧

<s,t>∈G∧<t,y>∈H)

s(<x,s>∈F∧

t(<s,t>∈G∧<t,y>∈H))

s(<x,s>∈F∧

<s,y>∈G。H))<x,y>∈F

(G

H)(4)任取<x,y>,<x,y>∈(F

G)-1<y,x>∈F

G

t(<y,t>∈F∧

<t,x>∈G)

t(<x,t>∈G-1

∧

<t,y>∈F-1)<x,y>∈G-1

F-1

定理：設(shè)F、G、H是任意關(guān)系,則(1)F

(G∪H)=F

G∪F

H(2)(G∪H)

F=G

F∪H

F(3)F

(G∩H)

F

G∩F

H(4)(G∩H)

F

G

F∩H

F證明:(1)任取<x,y>,<x,y>∈F

(G∪H)

t(<x,t>∈F∧<t,y>∈G∪H)

t(<x,t>∈F∧(<t,y>∈G∨<t,y>∈H))

t((<x,t>∈F∧<t,y>∈G)∨(<x,t>∈F∧<t,y>∈H))

t(<x,t>∈F∧<t,y>∈G)∨t(<x,t>∈F∧<t,y>∈H)<x,y>∈F

G∨<x,y>∈F

H<x,y>∈F

G∪F

H證明:(3)任取<x,y>,<x,y>∈F

(G∩H)

t(<x,t>∈F∧<t,y>∈G∩H)

t(<x,t>∈F∧

<t,y>∈G∧

<t,y>∈H)

t((<x,t>∈F∧<t,y>∈G)∧(<x,t>∈F∧<t,y>∈H))=>t(<x,t>∈F∧<t,y>∈G)∧t(<x,t>∈F∧<t,y>∈H)<x,y>∈F

G∧

<x,y>∈F

H<x,y>∈F

G∩F

H本定理對(duì)有限個(gè)關(guān)系的并和交都成立。R

(R1∪R2∪…∪Rn)=R

R1∪R

R2∪…∪R

Rn(R1∪R2∪…∪Rn)

R=R1

R∪R2

R∪…∪Rn

RR

(R1∩

R2∩…∩Rn)

R

R1∩R

R2∩…∩R

Rn(R1∩R2∩…∩Rn)

R

R1

R∩R2

R∩…∩Rn

R冪運(yùn)算：設(shè)R是A上的關(guān)系,n為自然數(shù)，則R的n次冪規(guī)定如下：(1)R0={<x,x>|x∈A}(2)Rn=Rn-1

Rn≥1由定義可以知道R0就是A上的恒等關(guān)系IA，不難證明下面的等式R

R0=R=R0

R。由這個(gè)等式立即可以得到R1=R0

R=R例：設(shè)A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}求R0，R1，R2，R3，R4和R5解：R0={<a,a>,<b,b>,<c,c>,<d,d>}R1=R0

R={<a,b>,<b,a>,<b,c>,<c,d>}

{<a,a>,<b,b>,<c,c>,<d,d>}={<a,b>,<b,a>,<b,c>,<c,d>}。R2=R

R={<a,b>,<b,a>,<b,c>,<c,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R3=R2

R={<a,a>,<a,c>,<b,b>,<b,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<b,a>,<b,c>,<a,d>}R4=R3

R={<a,b>,<b,a>,<b,c>,<a,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R5=R4

R={<a,a>,<a,c>,<b,b>,<b,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<b,a>,<b,c>,<a,d>}定理：設(shè)R是A上的關(guān)系,m,n為自然數(shù)，則下面的等式成立(1)Rm

Rn=Rm+n(2)(Rm)n=Rmn證明：(1)任給m，對(duì)n作歸納法。

n=0時(shí)，Rm?R0=Rm=Rm+0。

假設(shè)Rm?Rn=Rm+n，那么Rm?Rn+1=Rm?(Rn?R1)=(Rm?Rn)?R1=Rm+n?R1=Rm+n+1=Rm+(n+1)。(2)任給m，對(duì)n作歸納法。

n=0時(shí)，(Rm)0=R0=Rm

0。

假設(shè)(Rm)n=Rmn。那么(Rm)n+1=(Rm)n

?Rm

=Rmn?Rm=Rmn+m=Rm(n+1)

例:已知集合A={a,b,c,d},A上的關(guān)系R={<a,b>,<b,a>,<b,c>,<c,d>}，求。解：法一：由復(fù)合定義知={<a,a>,<a,c>,<b,b>,<b,d>}={<a,b>,<a,d>,<b,a>,<b,c>}法二：關(guān)系R矩陣為==法三：R的關(guān)系圖為的關(guān)系圖為

的關(guān)系圖為定理A為n元集,R為A上的關(guān)系,則存在自然數(shù)s和t，使得Rs=Rt證明：因?yàn)锳為n元集，所以集合A上的關(guān)系為有限N=個(gè)，而關(guān)系序列存在無限多個(gè)關(guān)系，故存在自然數(shù)s和t，使得Rs=Rt.。設(shè)R是A上的關(guān)系，R的性質(zhì)主要有以下5種:(1)自反性：若x(x∈A<x,x>∈R),則稱R在A上是自反的。也就是說，對(duì)R

A

A，若A中每個(gè)x，都有xRx，則稱R是自反的，即A上關(guān)系R是自反的

x(x

A

xRx)。該定義表明了，在自反的關(guān)系R中，除其它有序?qū)ν?，必須包括有全部由每個(gè)x

A所組成的元素相同的有序?qū)Α＠纾涸O(shè)A={1,2,3},R

是A上的關(guān)系，R={<1,1>,<2,2>,<3,3>,<1,2>}則R

是自反的關(guān)系的性質(zhì)(2)反自反性：若x(x∈A<x,x>∈R)，則稱R在A上是反自反的。也就是說，對(duì)R

A

A，若A中每個(gè)x，有xRx，則稱R是反自反的，即A上關(guān)系R是反自反的

x(x

A

xRx)該定義表明了，一個(gè)反自反的關(guān)系R中，不應(yīng)包括有任何相同元素的有序?qū)?。例如：設(shè)A={1,2,3}，R

是A上的關(guān)系，R={<2,3>,<3,2>}

R是反自反的。應(yīng)該指出：任何一個(gè)不是自反的關(guān)系，未必是反自反的；任何一個(gè)不是反自反的關(guān)系，未必是自反的。這就是說，存在既不是自反的也不是反自反的二元關(guān)系。例：設(shè)A={1,2,3},R

是A上的關(guān)系，R={<1,1>,<2,2>}缺少{<3,3>}則R是既不是自反的，也不是反自反的。(3)對(duì)稱性：若xy(x,y∈A∧<x,y>∈R<y,x>∈R),則稱R在A上是對(duì)稱的。也就是說,對(duì)R

A

A,對(duì)A中每個(gè)x和y,若xRy,則yRx,稱R是對(duì)稱的,即A上關(guān)系R是對(duì)稱的(x)(

y)(x,y

A

xRy→yRx)該定義表明了，在表示對(duì)稱的關(guān)系R的有序?qū)现校粲杏行驅(qū)?lt;x,y>，則必定還會(huì)有<y,x>。例：設(shè)A={1,2,3},R是A上的關(guān)系，R4={<1,2>,<2,1>,<2,3>,<3,2>,<2,2>,<3,3>}則R

是對(duì)稱的。(4)反對(duì)稱性：若xy(x,y∈A∧<x,y>∈R∧x≠y<y,x>R),則稱R在A上是反對(duì)稱的。

也就是說，對(duì)R

A

A，對(duì)A中每個(gè)x和y，若xRy且yRx，則x=y，稱R是反對(duì)稱的，即A上關(guān)系R是反對(duì)稱的

(

x)(

y)(x,y

A

xRy

yRx→x=y)該定義表明了，在表示反對(duì)稱關(guān)系R的有序?qū)现?，若存在有序?qū)?lt;x,y>和<y,x>，則必定是x=y。或者說，在R中若有有序?qū)?lt;x,y>，則除非x=y，否則必定不會(huì)出現(xiàn)<y,x>。例：設(shè)A={1,2,3},R={<1,2>,<1,3>,<1,1>}是A上的關(guān)系，則R是反對(duì)稱的。

注意：有些關(guān)系既是對(duì)稱的又是反對(duì)稱的；有的關(guān)系既不是對(duì)稱的又不是反對(duì)稱的。例：設(shè)A={1,2,3},R6,R7是A上的關(guān)系，R6={<1,1>,<2,2>}R7={<1,2>,<2,1>,<1,3>,<3,3>}則R6是對(duì)稱的，也是反對(duì)稱的R7既不是對(duì)稱的又不是反對(duì)稱的

課堂問題：設(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上的對(duì)稱和反對(duì)稱關(guān)系。(5)傳遞性：xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R<x,z>∈R)則稱R在A上是傳遞的關(guān)系。也就是說,對(duì)R

A

A，對(duì)于A中每個(gè)x,y,z，若xRy且yRz，則xRz，稱R是傳遞的，即A上關(guān)系R是傳遞的

(

x)(

y)(

z)(x,y,z

A

xRy

yRz→xRz)該定義表明了，在表示可傳遞關(guān)系R的有序?qū)现?，若?lt;x,y>和<y,z>，則必有<x,z>。例：設(shè)A={1,2,3,4,5},A上的關(guān)系R為

R={<a,b>|a-b是偶數(shù)}①用列舉法表示R②R是否是可傳遞的？解:①R={<1,1>,<1,3>,<1,5>,<2,2>,<2,4>,<3,3><3,1>,<3,5>,<4,2>,<4,4>,<5,1>,<5,3><5,5>}②對(duì)于任意的a,b,c∈A若a-b=2m,b-c=2n,則a-c=(a-b)+(b-c)=2(m+n)也是偶數(shù)。因此A是可傳遞的。∵<a,b>∈R∧<b,c>∈R<a,c>∈R例：設(shè)A={1,2,3},R1,R2和R3是A上的關(guān)系，R1={<1,1>,<2，2>}，R2={<2,3>,<1,2>}，R3={<1,3>}。試說明R1,R2和R3是否為A上的傳遞關(guān)系。解：其中R1，R3是傳遞關(guān)系，R2不是傳遞關(guān)系。例：設(shè)A={1,2,3,4,5,6,7,8}，R是A上的關(guān)系，R={<x,y>|x,y∈A∧x+y=9}說明R具有哪些性質(zhì)。解：R={<1,8>,<2,7>,<3,6>,<4,5>,<5,4>，<6,3>,<7,2>,<8,1>}易知R既不是自反也不是反自反的；是對(duì)稱的

R不是反對(duì)稱的；R不是傳遞的。性質(zhì)的判定定理設(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上對(duì)稱當(dāng)且僅當(dāng)R=R-1。（4）R在A上反對(duì)稱當(dāng)且僅當(dāng)R

R-1

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

R。證明：（1）必要性：若R在A上自反，則對(duì)

x

A有<x,x>

R，所以IA

R。充分性：若IA

R，則

x

A,有<x,x>

IA

R，則R在A上自反。2）必要性：若R在A上反自反，則對(duì)

x

A有<x,x>

R，所以R

IA=

。充分性：若R

IA=

，則對(duì)

x

A有<x,x>

R，否則，不妨設(shè)y

A有<y,y>

R,則有R

IA≠

,與已知矛盾,所以R在A上反自反。3）必要性：若R在A上對(duì)稱，下證R=。對(duì)任意

x

A,

y

A,若<x,y>

R,即R=R-1成立。

充分性：若R=R-1則對(duì)任意

x

A,

y

A,若<x,y>R,則<x,y>R-1

則有<y,x>

R，則R在A上對(duì)稱成立。（4）必要性：若R在A上反對(duì)稱，任取<x,y>則有充分性，若R

R-1IA，任取<x,y>則有（5）必要性：若R在A上傳遞，任取<x,y>則有充分性：若R?R

R成立，任取<x,y>R，<y,z>R，則有關(guān)系性質(zhì)的幾種表示R=性質(zhì)表示自反性反自反性對(duì)稱性反對(duì)稱性傳遞性集合表達(dá)R?R

R關(guān)系矩陣主對(duì)角元全是1主對(duì)角元全是0對(duì)稱矩陣關(guān)于對(duì)角線對(duì)稱的元素不同時(shí)為1關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒有環(huán)無單邊無雙邊凡兩步能夠間接到達(dá)，則必能一步直接到達(dá)例：判斷下圖中關(guān)系的性質(zhì)，并說明理由。（3）（2）

（1）解：（1）該關(guān)系圖有的頂點(diǎn)有環(huán)，有的頂點(diǎn)沒有環(huán)，故關(guān)系即不是自反關(guān)系，也不是反自反關(guān)系；關(guān)系圖中，無雙邊，故應(yīng)該是反對(duì)稱關(guān)系；該關(guān)系圖從頂點(diǎn)a到頂點(diǎn)b有邊，頂點(diǎn)b到頂點(diǎn)c，但從頂點(diǎn)a到頂點(diǎn)c沒有邊，故該關(guān)系不是傳遞關(guān)系。（2）該關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)，故關(guān)系是自反關(guān)系；在關(guān)系圖中，無雙邊，故應(yīng)該是反對(duì)稱關(guān)系；該關(guān)系圖從頂點(diǎn)a到頂點(diǎn)b有邊，頂點(diǎn)b到頂點(diǎn)c，從頂點(diǎn)a到頂點(diǎn)c有邊，故該關(guān)系是傳遞關(guān)系。（3）該關(guān)系圖每個(gè)頂點(diǎn)都沒有環(huán)，故關(guān)系是反自反關(guān)系；在關(guān)系圖中，無雙邊，故應(yīng)該是反對(duì)稱關(guān)系；該關(guān)系圖中沒有兩步間接到達(dá)的路徑，故該關(guān)系是傳遞關(guān)系。思考題：

設(shè)A為集合，R1和R2是A上的關(guān)系，說明下面命題是否成立，若成立，則證明之，若不成立，則舉例說明。

R1和R2是A上的自反關(guān)系，則也是A上的自反關(guān)系。(2)R1和R2是A上的傳遞關(guān)系，則R1-R2也是A上的傳遞關(guān)系。設(shè)R是非空集合A上的關(guān)系，R的自反(對(duì)稱或傳遞)閉包是A上的關(guān)系R′,使得R′滿足以下條件:(1)R′是自反(對(duì)稱或傳遞)的(2)RR′

(3)對(duì)A上的任何包含R的自反(對(duì)稱或傳遞)關(guān)系R″均有R′R″。一般將R的自反閉包記作r(R)；對(duì)稱閉包記作s(R)；傳遞閉包記作t(R)。關(guān)系的閉包設(shè)R是非空集合A上的關(guān)系，則有(1)r(R)=R∪R0(2)s(R)=R∪R-1(3)t(R)=R∪R2∪R3∪…此定理提供了一種集合表示形式下關(guān)系閉包的求解方法。例：設(shè)A={a,b,c,d},在A的定義二元關(guān)系R={<a,b>,<b,a>,<b,b>,<b,c>,<c,d>,<d,b>},則r(R)=R∪R0={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>,<c,c>,<d,d>,<b,b>,<a,a>};s(R)=R∪R-1={<a,b>,<b,a>,<b,b>,<b,c>,<c,d>,<d,b>,