離散數(shù)學左孝凌3

第三章集合與關系〔SetsandRelations)本章首先采用樸素集合論的方法，介紹有關集合的一些根本知識，內(nèi)容顯得較為直觀，學起來易于接受。但集合及其相關的概念是本門課程后面各章內(nèi)容的根底，同學們務必熟練的掌握。本章重點討論關系〔主要是二元關系〕，它仍然是一種集合，但它是一種更為復雜的集合。它的元素是有序二元組的形式，這些有序二元組中的兩個元素來自于兩個不同或者相同的集合。因此，關系是建立在其它集合根底之上的集合。關系中的有序二元組反映了不同集合中元素與元素之間的關系，或者同一集合中元素之間的關系。本章討論這些關系的表示方法、關系的運算以及關系的性質(zhì)，最后討論集合A上幾類特殊的關系。

3-1集合的概念和表示法3-2集合的運算3-4序偶與笛卡爾積3-5關系及其表示

3-6關系的性質(zhì)第三章集合與關系〔SetsandRelations)

3-7復合關系和逆關系3-8關系的閉包運算3-9集合的劃分與覆蓋3-10等價關系與等價類

3-11相容關系3-12序關系第三章集合與關系〔SetsandRelations)3-1集合的概念和表示方法定義(集合set)：把具有共同性質(zhì)的一些對象聚集成一個整體，就構成一個集合，這些對象稱為元素(element)或成員(member)用大寫英文字母A,B,C,…表示集合用小寫英文字母a,b,c,…表示元素aA：表示a是A的元素，讀作“a屬于A〞aA：表示a不是A的元素，讀作“a不屬于A〞3-1.1有關集合的概念n元集(n-set):有n個元素的集合稱為n元集。|A|:表示集合A中的元素個數(shù),A是n元集|A|=n0元集:記作1元集(或單元集),如{a},,{}…有限集(finiteset):|A|是有限數(shù),|A|<,也叫有窮集，否那么為無限集。3-1.2集合的表示方法通常使用“列舉法〞和“表達法〞兩種方法來給出一個集合〔1〕列舉法(roster)列出集合中的全體元素，元素之間用逗號分開，然后用花括號括起來，例如A={a,b,c,d,…,x,y,z}B={0,1,2,3,4,5,6,7,8,9}集合中的元素不規(guī)定順序C={2,1}={1,2}集合中的元素各不相同C={2,1,1,2}={2,1}3-1.2集合的表示方法〔2〕表達法(definingpredicate)用謂詞P(x)表示“x具有性質(zhì)P〞，用A={x|P(x)}表示元素具有性質(zhì)P的集合A，如果P(b)為真，那么bA，否那么bA。例如P1(x):x是英文字母A={x|P1(x)}={x|x是英文字母}={a,b,c,d,…,x,y,z}P2(x):x是十進制數(shù)字B={x|P2(x)}={x|x是十進制數(shù)字}={0,1,2,3,4,5,6,7,8,9}兩種表示法可以互相轉(zhuǎn)化例如：E={2,4,6,8,…}={x|x>0且x是偶數(shù)}={x|x=2(k+1)，k為非負整數(shù)}={2(k+1)|k為非負整數(shù)}兩個集合相等的外延性原理：兩個集合A、B是相等的，當且僅當它們有相同的成員，記作A=B；否那么記作AB。集合的元素還可以是一個集合。例如：S={a,{1,2},p,{q}}3-1.3數(shù)的集合N：自然數(shù)(naturalnumbers)集合N={0,1,2,3,…}Z：整數(shù)(integers,Zahlen)集合Z={0,

1,

2,…}={…,-2,-1,0,1,2,…}Q：有理數(shù)(rationalnumbers,Quotient)集合R：實數(shù)(Realnumbers)集合C：復數(shù)(Complexnumbers)集合3-1.4集合之間的關系子集、相等、真子集；空集、全集；冪集、n元集、有限集；〔1〕子集[定義3-1.1]子集(subset)：設A、B是任意兩個集合，如果A的每一個元素是B的成員，那么稱A為B的子集,或說A包含于B,或說B包含A,記作AB，或BA。AB(x)(xAxB)假設A不是B的子集,那么記作ABAB(x)(xAxB)證明ABx(xAxB)成立

[證明]：根據(jù)定義AB(x)(xAxB)那么AB(x)(xAxB)(x)((xA)(xB))(x)((xA)(xB))(x)(xAxB)子集(舉例)設A={a,b,c},B={a,b,c,d},C={a,b},那么AB,CA,CB〔1〕子集定理3-1.1

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

A

B

B

AA=B

(

x)(x

Ax

B)[證明]A=B

A

B

B

A(=定義)(x)(x

A

x

B)(x)(x

B

x

A)(

定義)(x)((x

A

x

B)

(x

B

x

A))(量詞分配)(x)(x

Ax

B)(等價式)〔1〕子集包含(

)的性質(zhì)：1．AA〔自反性〕證明:AA(x)(xAxA)T2．假設AB,且AB,那么BA〔反對稱性〕3．假設AB,且BC,那么AC〔傳遞性〕證明:AB(x)(xAxB)x,xAxB(AB)xC(BC)(x)(xAxC),即AC.〔2〕真子集[定義3-1.2]真子集(propersubset)如果集合A的每一個元素都屬于B，但集合B至少有一個元素不屬于A，那么稱A為B的真子集，記作AB。ABABABAB(x)(xAxB)(x)(xBxA)A

B的含義：A

B

(A

B

A

B)(

定義)

(A

B)

(A=B)(德摩根律)

x(x

A

x

B)

(A=B)(

定義)

A

B

(A=B)含義：A不是B的子集或者A和B相等。

真包含(

)的性質(zhì)1．AA〔反自反性〕證明:AAAAAATFF.2．假設AB,那么BA〔反對稱性〕證明:(反證)設BA,那么ABABABAB(化簡)BABABABA所以ABBAA=B(=定義)但是ABABABAB(化簡)矛盾!3．假設AB,且BC,那么AC〔傳遞性〕證明:ABABABAB(化簡),同理BCBC,所以AC.假設A=C,那么BCBA,又AB,故A=B,此與AB矛盾,所以AC.所以,AC.#

真包含(

)的性質(zhì)〔3〕空集[定義3-1.3]空集(emptyset)：不包含任何元素的集合是空集,記作

例如：{x

R|x2+1=0}[定理3-1.2]對任意一個集合A，

A也就是對任意集合A,

A證明:

A

x(x

x

A)

x(F

x

A)

T.對于每一個非空集合A，至少有兩個不同的子集，A和，稱為A的平凡子集。[推論]空集是唯一的.〔可作為討論〕證明:設1與2都是空集,那么12211=2.#〔3〕空集〔4〕全集[定義3-1.4]全集:在一定范圍內(nèi)，如果所有集合均為某一集合的子集,那么稱這個集合是全集,記作E。E={x|P(x)P(x)}，P(x)為任何謂詞全集是相對的,視情況而定,因此不唯一。例如,討論(a,b)區(qū)間里的實數(shù)性質(zhì)時,可以選E=(a,b),E=[a,b),E=(a,b],E=[a,b],E=(a,+),E=(-,+)等〔5〕冪集[定義3-1.5]冪集(powerset)給定集合A，由集合A的所有子集為元素組成的集合,稱為A的冪集,記作P(A)P(A)={x|x

A}注意:x

P

(A)

x

A例如:A={a,b},

P(A)={

,{a},,{a,b}}.[定理]如果有限集合A有n個元素，那么冪集P(A)有2n個元素。證明:利用二項式展開定理?！?〕冪集作業(yè)(3-1)：P85(6)(9)(10)3-2集合的運算

[定義3-2.1]集合的交(intersection):

設任意兩個集合A和B，由集合A和B的所有共同元素組成的集合S，稱為A和B的交集，記作A

B。S=A

B={x|(x

A)

(x

B)}x

A

B

(x

A)

(x

B)3-2.1交集例2:設An={xR|0x1/n},n=1,2,…,那么A1A2An=3-2.1交集例1:設An={xR|n-1xn},n=1,2,…,10,那么A1A2An=

{0}不相交(disjoint)不相交：AB=互不相交：設A1,A2,…是可數(shù)多個集合,假設對于任意的ij,都有AiAj=,那么說它們互不相交。例:設An={xR|n-1<x<n},n=1,2,…,10,那么A1,A2,…是互不相交的3-2.1交集集合交運算的性質(zhì)a)AA=A〔冪等律〕b)A=〔零律〕c)AE=A〔同一律〕d)AB=BA〔交換律〕e)(AB)C=A(BC)〔結(jié)合律〕因為集合交運算滿足結(jié)合律，故n個集合的交記為：nP=A1A2An=Aii=13-2.1交集3-2.2集合的并

[定義3-2.2]并集(union)：設任意兩個集合A和B，由所有集合A和B的元素組成的集合S，稱為A和B的并集，記作A

B。

S=A

B={x|(x

A)

(x

B)}x

A

B

(x

A)

(x

B)例2:設An={xR|0x1/n},n=1,2,…,那么A1A2An=3-2.2并集例1:設An={xR|n-1xn},n=1,2,…,10,那么A1A2An=[0，10][0，1]集合并運算的性質(zhì)a)AA=A〔冪等律〕b)A=A〔同一律〕c)AE=E〔零律〕d)AB=BA〔交換律〕e)(AB)C=A(BC)〔結(jié)合律〕因為集合并運算滿足結(jié)合律，故n個集合的并記為：nP=A1A2An=Aii=13-2.2并集3-2.3集合的補／相對補

[定義3-2.3]補集／相對補集(relativecomplement,differenceset)：屬于A而不屬于B的全體元素組成的集合S，稱為B對于A的補集／相對補集,記作A-BS=A-B={x|(x

A)

(x

B)}

[定義3-2.4]絕對補(complement)：設E為全集，對任一集合A關于E的補E-A，稱為集合A的絕對補，記作~A。~A={x|(x

E

x

A)}集合補運算的性質(zhì)〔1〕

對合律：~~A=A〔2〕

全補律：~E=〔3〕

~=E〔4〕矛盾律：A~A=〔5〕排中律：A~A=E3-2.3集合的補／相對補3-2.4集合的對稱差［定義3-2.5］對稱差(symmetricdifference)：屬于A而不屬于B,或?qū)儆贐而不屬于A的全體元素組成的集合S,稱為A與B的對稱差,記作A

B。A

B={x|(x

A

x

B)

(x

A

x

B)}A

B=(A-B)

(B-A)=(A

B)-(A

B)對稱差(

)的性質(zhì)〔1〕

交換律：AB=BA〔2〕

結(jié)合律：A(BC)=(AB)C〔3〕

分配律：A(BC)=(AB)(AC)〔4〕同一律：A=A〔5〕排中律：A~A=E〔6〕AA=〔7〕AE=~A3-2.4集合的對稱差相對補、對稱差(舉例)例:設A={xR|0x<2},B={xR|1x<3},那么A-B={xR|0x<1}=[0,1)B-A={xR|2x<3}=[2,3)AB={xR|(0x<1)(2x<3)}=[0,1)[2,3)3-2.5集合運算的性質(zhì)〔集合恒等式〕(1)冪等律(idempotentlaws)A

A=AA

A=A(2)結(jié)合律(associativelaws)(A

B)

C=A

(B

C)(A

B)

C=A

(B

C)(3)交換律(commutativelaws)A

B=B

AA

B=B

A(4)分配律(distributivelaws)A

(B

C)=(A

B)

(A

C)A

(B

C)=(A

B)

(A

C)(5)對合律(doublecomplementlaw)~~A=A(6)零律(dominancelaws)A

E=EA

=

3-2.5集合運算的性質(zhì)〔集合恒等式〕(7)同一律(identitylaws)A

=AA

E=A(8)排中律(excludedmiddle)A

~A=E(9)矛盾律(contradiction)A

~A=

(10)全補律~

=E~E=

3-2.5集合運算的性質(zhì)〔集合恒等式〕(11)吸收律(absorptionlaws)A

(A

B)=AA

(A

B)=A(12)德.摩根律(DeMorgan’slaws)~(A

B)=~A

~B~(A

B)=~A

~B(13)補交轉(zhuǎn)換律(differenceasintersection)A-B=A

~B3-2.5集合運算的性質(zhì)〔集合恒等式〕3-2.6集合恒等式證明(方法)〔1〕邏輯演算法:利用邏輯等價式和邏輯推理規(guī)那么〔2〕集合演算法:利用集合恒等式和的集合結(jié)論〔1〕邏輯演算法(格式)

題型:A=B.

證明：

x,x

A

…(????)

x

B

A=B證畢.或證明：

x,x

A

…(????)

x

B.

另，

x,x

B

…(????)

x

A.

A=B證畢.題型:A

B.

證明:

x,x

A

…(????)

x

B

A

B證畢.例1：分配律(定理3-2.1)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

A

x

C)(命題邏輯分配律)

(x

A

B)

(x

A

C)(

定義)

x

(A

B)

(A

C)(

定義)

A

(B

C)=(A

B)

(A

C)成立3-2.6集合恒等式證明(方法)例2：零律(證明)

A

=

證明:

x,x

A

x

A

x

(

定義)

x

A

F(

定義)

F(命題邏輯零律)

A

=

成立3-2.6集合恒等式證明(方法)例3.

排中律(證明)A

~A=E證明:

x,x

A

~A

x

A

x

~A(

定義)

x

A

x

A(~定義)

x

A

(x

A)(

定義)

T(命題邏輯排中律)

A

~A=E成立3-2.6集合恒等式證明(方法)(2)集合演算法〔格式〕題型:A=B.題型:A

B.

證明:A證明:A=…(????)

…(????)=B

B

A=B.#

A

B.#例1：吸收律(定理3-2.2)A

(A

B)=A證明:A

(A

B)=(A

E)

(A

B)(同一律)=A

(E

B)(逆用分配律)=A

E(零律)=A(同一律)

A

(A

B)=A3-2.6集合恒等式證明(方法)例2：吸收律(定理3-2.2)A

(A

B)=A證明:A

(A

B)=(A

A)

(A

B)(分配律)=A

(A

B)(冪等律)=A(吸收律第一式)

A

(A

B)=A3-2.6集合恒等式證明(方法)(2)集合演算法〔格式〕續(xù)

題型:A

B

證明:A

B(或A

B)=…(????)=A(或B)

A

B.#

說明:化

成=題型:A=B證明:(

)…

A

B(

)…

A

B

A=B.#說明:把=分成

與

A

B=A

A

BA

B=B

A

B3-2.7集合恒等式證明(舉例)1.根本集合恒等式例如：①補交轉(zhuǎn)換律A-B=A~B證明:x,xA-BxAxBxAx~BxA~BA-B=A~B.②德

摩根律的相對形式A-(B

C)=(A-B)

(A-C)A-(B

C)=(A-B)

(A-C)證明:A-(B

C)=A

~(B

C)(補交轉(zhuǎn)換律)=A

(~B

~C)(德

摩根律)=(A

A)

(~B

~C)(冪等律)=(A

~B)

(A

~C)(交換律,結(jié)合律)=(A-B)

(A-C)(補交轉(zhuǎn)換律).#3-2.7集合恒等式證明(舉例)

小結(jié)：本節(jié)介紹了集合的運算和運算定律。重點掌握集合的各種運算及其運算規(guī)律。作業(yè)：P94(1)(3)c)d)(4)(5)a)(6)第三章集合與關系〔SetsandRelations)3-4

序偶與笛卡爾積3-4.1

序偶(二元組)定義［序偶orderedpair］：由兩個固定次序的客體a,b組成的序列稱為序偶，記作<a,b>，其中a,b稱為序偶的分量。<a,b>其中,a是第一元素,b是第二元素,

記作<a,b>也記作(a,b)。定義3-4.1兩個序偶相等

,<x，y>=<u,v>,iffx＝u,y=v

。推論:a

b

<a,b>

<b,a>

3-4.2三元組(orderedtriple)定義［三元組］：<a,b,c>=<<a,b>,c>.定義［n(

2)元組］：

<a1,a2,…,an>=<<a1,a2,…,an-1>,an>.定理:<a1,a2,…,an>=<b1,b2,…,bn>

ai

=bi,i=1,2,…,n.

3-4.3

笛卡爾積及其性質(zhì)

定義3-4.2令A和B是任意兩個集合，假設序偶的第一個成員是A的元素，第二個成員是B的元素，所有這樣的序偶集合，稱為集合A和B的笛卡爾乘積或直積，記為AB，AB={<x,y>|xAyB}例1:A={

,a},B={1,2,3}.A

B=<

,1>,<

,2>,<

,3>,<a,1>,<a,2>,<a,3>}.B

A=<1,

>,<1,a>,<2,

>,<2,a>,<3,

>,<3,a>}.A

A={<

,

>,<

,a>,<a,

>,<a,a>}.B

B={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}.3-4.3

笛卡爾積及其性質(zhì)

3-4.4笛卡爾積的性質(zhì)：當|A|=m，|B|=n時，|A×B|是多少？|A×B|=m×n3-4.4笛卡爾積的性質(zhì)：1.

非交換:A

B

B

A

(除非

A=B

A=

B=

)舉例:A={1},B={2}.A

B={<1,2>},B

A={<2,1>}.2.

非結(jié)合:(A

B)

C

A

(B

C)(除非

A=

B=

C=

)舉例:A=B=C={1}.(A

B)

C={<<1,1>,1>},A

(B

C)={<1,<1,1>>}.3.笛卡爾積分配律：〔對或運算滿足〕〔1〕

A(BC)=(AB)(AC)〔2〕

A(BC)=(AB)(AC)〔3〕

(BC)A=(BA)(CA)〔4〕

(BC)A=(BA)(CA)3-4.3

笛卡爾積及其性質(zhì)3.笛卡爾積分配律(證明(1))

A

(B

C)=(A

B)

(A

C).證明:

<x,y>,<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).#3-4.3

笛卡爾積及其性質(zhì)4.其他性質(zhì)：設A,B,C,D是任意集合,(1)

假設A,那么ABACBACABC〔即書上的定理3-4.2〕(2)

ACBDABCD.〔即書上的定理3-4.3〕(3)

AB=A=B=3-4.3

笛卡爾積及其性質(zhì)證明(1)假設A,那么ABACBC.證明:()假設B=,那么BC.設B,由A,設xA,y,yB，<x,y>AB<x,y>ACxAyCyC.

BC()假設B=,那么AB=AC.設B.<x,y>,<x,y>ABxAyBxAyC<x,y>ACABAC.#3-4.3

笛卡爾積及其性質(zhì)3-4.5推廣：n維笛卡爾積定義［n維笛卡爾積］：A1

A2

…

An={<x1,x2,…,xn>|x1

A1

x2

A2

…

xn

An}A

A

…

A

=An|Ai|=ni,i=1,2,…,n

|A1

A2

…

An|=n1

n2

…

nn.n維笛卡爾積性質(zhì)與2維笛卡爾積類似.

小結(jié)：本節(jié)介紹了序偶、有序n元組及笛卡爾積的概念。重點理解有序n元組及笛卡爾積的概念。作業(yè)：P104(1)b)(2)(5)第三章集合與關系〔SetsandRelations)3-5關系及其表示3-5.1關系的概念及記號兄弟關系、長幼關系、同學關系、鄰居關系，上下級關系等。在數(shù)學上有大于關系、小于關系，整除關系。例如：“3小于5〞，“x大于y〞，“點a在b與c之間〞。我們又知道序偶可以表達兩個客體、三個客體或n個客體之間的聯(lián)系，因此用序偶表達這個概念是非常自然的。例如：火車票與座位之間的對號關系。設X表示火車票的集合，Y表示座位的集合，那么對于任意的xX和yY，必定有x與y有“對號〞關系x與y沒有“對號〞關系。二者之一令R表示“對號〞關系，那么上述問題可以表示為xRy或xRy。亦可表示為<x,y>

R或<x,y>

R，因此我們看到對號關系是序偶的集合。3-5.1關系的概念及記號定義3-5.1［關系］：二元關系(binaryrelation)，簡稱關系，任一序偶的集合即確定了一個二元關系R，R中任一序偶<x,y>可記為<x,y>

R或xRy。不在R中的任一序偶<x,y>可記為<x,y>

R或xRy3-5.1關系的概念及記號例1:在實數(shù)中關系“≥〞可記作“≥〞={<x,y>|x,y是實數(shù)且x≥y}。例2:R1={<1,2>,<,>,<a,b>}

R1是二元關系.例3:A={<a,b>,<1,2,3>,a,1}

A不是關系.3-5.1關系的概念及記號

二元關系的記號：

設R是二元關系,那么<x,y>Rx與y具有R關系xRy。比照:xRy(中綴(infix)記號)

<x,y>R(后綴(suffix)記號)R(x,y)(前綴(prefix)記號)例如:2<15<(2,15)<2,15><。<1,2>R1R2。<5,4>R5R4。3-5.1關系的概念及記號X到Y(jié)的二元關系定義3-5.3令X和Y是任意兩個集合，直積XY的子集R稱為X到Y(jié)的二元關系。R是X到Y(jié)的二元關系RXYRP(XY)〔冪集〕假設|X|=m,|Y|=n,那么|XY|=mn,故|P(XY)|=2mn，即X到Y(jié)不同的二元關系共有2mn個3-5.1關系的概念及記號X到Y(jié)的二元關系(舉例)例:設A={a1,a2},B=,那么A到B的二元關系共有22×1=4個:R1=,R2={<a1,b>},R3={<a2,b>},R4={<a1,b>,<a2,b>}B到A的二元關系也有4個:R5=,R6={<b,a1>},R7={<b,a2>},R8={<b,a1>,<b,a2>}。

3-5.1關系的概念及記號X上的二元關系定義［X上的二元關系］:是XX的任意子集。R是X上的二元關系RXXRP(XX)。假設|X|=m,那么|XX|=m2,故|P(XX)|=2m2，即X上不同的二元關系共有2m2個。

3-5.1關系的概念及記號X上的二元關系(舉例)例1:設A={a1,a2},那么A上的二元關系共有16個:

R1=,R2={<a1,a1>},

R3={<a1,a2>},R4={<a2,a1>},

R5={<a2,a2>},R6={<a1,a1>,<a1,a2>},

R7={<a1,a1>,<a2,a1>},

R8={<a1,a1>,<a2,a2>},3-5.1關系的概念及記號R9={<a1,a2>,<a2,a1>},R10={<a1,a2>,<a2,a2>},R11={<a2,a1>,<a2,a2>},R12={<a1,a1>,<a1,a2>,<a2,a1>}，R13={<a1,a1>,<a1,a2>,<a2,a2>}，R14={<a1,a1>,<a2,a1>,<a2,a2>}，R15={<a2,a1>,<a2,a1>,<a2,a2>}，R16={<a1,a1>,<a1,a2>,<a2,a1>,<a2,a2>}。3-5.1關系的概念及記號例2:設A={a},

那么A上的二元關系共有2個:

R1=,R2={<a,a>}.例3:設A={a,b,c},

那么A上的二元關系共有29=512個!

3-5.1關系的概念及記號3-5.2

與二元關系有關的概念對任意集合R,可以定義:前域／定義域〔domain〕:domR={x|y(xRy)}值域〔range〕:ranR={y|x(xRy)}域〔field〕:FLDR=domRranR前域／定義域,值域,域圖示見書106頁例題1。定義域,值域,域(舉例)例:R1={a,b},R2={<c,d>,<e,f>},

R3={<1,2>,<3,4>,<5,6>}.當a,b不是序偶時,R1不是關系.domR1=

,ranR1=

,FLDR1=

domR2={c,e},ranR2={d,f},FLDR2={c,d,e,f}domR3={1,3,5},ranR3={2,4,6},

FLDR3={1,2,3,4,5,6}.3-5.2

與二元關系有關的概念3-5.3

一些特殊關系設A是任意集合,那么可以定義A上的：空關系(emptyrelation):恒等關系(identityrelation):IA={<a,a>|aA}全域關系(universalrelation):UA=AA={<x,y>|xAyA}此外，設AI,那么可以定義A上的：整除關系:DA={<x,y>|xAyAx|y}例:A={1,2,3,4,5,6},那么DA={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,2>,<2,4>,<2,6>,<3,3>,<3,6>,<6,6>}。3-5.3

一些特殊關系設AR,那么可以定義A上的：小于等于(lessthanorequalto)關系：LEA={<x,y>|xAyAxy}小于(lessthan)關系：LA={<x,y>|xAyAx<y}大于等于(greaterthanorequalto)關系，大于(greatthan)關系,…3-5.3

一些特殊關系設A為任意集合,那么可以定義P(A)上的:包含關系:：A={<x,y>|xAyAxy}真包含關系：A={<x,y>|xAyAxy}見P107例2和例33-5.3

一些特殊關系3-5.4關系的運算定理3-5.1：假設Z和S是從集合X到集合Y的兩個關系，那么Z和S的并、交、補、差仍是X到Y(jié)的關系。

證明見書108頁。3-5.5

二元關系的表示(1)序偶集合的形式表達(2)關系矩陣：設A={a1,a2,…,an},B={b1,b2,…,bm},RAB,那么R的關系矩陣MR=(rij)nm,其中rij=1,aiRbj或<ai,bj>R

0,aiRbj或<ai,bj>R例題：P103例題5例如:A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},那么110011MR1=101MR2=0010000003-5.5

二元關系的表示(3)關系圖：A={a1,a2,…,an}，B={b1,b2,…,bn}，RAB,首先在平面上做結(jié)點a1,a2,…,an，b1,b2,…,bn以“〞表示(稱為頂點)，假設aiRbj，那么從結(jié)點ai向結(jié)點bj畫有向邊<ai,bj>，箭頭指向bj，假設aiRbj,那么ai與bj之間沒有線段連接，這樣得到的圖稱為R的關系圖GR。P109例題73-5.5

二元關系的表示abcGR2abcGR1定義在集合A上的關系圖有所不同例如〔上例〕,A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},那么關系圖如下：3-5.5

二元關系的表示關系矩陣、關系圖(討論):當A中元素標定次序后,R

A

A的關系圖GR與R的序偶集合表達式可以唯一互相確定。R的序偶集合表達式，關系矩陣，關系圖三者均可以唯一互相確定。3-5.5

二元關系的表示第三章集合與關系(Sets&Relations)小結(jié):本節(jié)介紹了關系的定義、幾種特殊的關系及關系的表示。重點掌握關系的表示方法。作業(yè)：P109(2)(5)b)d)給出關系圖和關系矩陣〔1〕

自反性(reflexivity)〔2〕

反自反性(irreflexivity)〔3〕

對稱性(symmetry)〔4〕

反對稱性(antisymmetry)〔5〕

傳遞性(transitivity)3-6關系的性質(zhì)需要指出：從X到Y(jié)的關系R是XY的子集，即RXY，而XY〔XY〕〔XY〕所以R〔XY〕〔XY〕令Z=XY，那么RZZ因此，我們今后通常限于討論同一集合上的關系。3-6關系的性質(zhì)3-6.1自反性(reflexivity)定義3-6.1〔自反性reflexivity〕：設R為定義在A上的二元關系，即RAA,如果對于每一個xA，有xRx(<x,x>R)，那么稱二元關系R是自反的。R在A上是自反的(x)(xAxRx)R在A上是非自反的(x)(xA<x,x>R)。定理：

R是自反的

IA

RMR主對角線上的元素全為1GR的每個頂點處均有自環(huán)。自反性(舉例)：平面上三角形的全等關系，實數(shù)集中實數(shù)的小于等于關系，冪集上的集合的相等、包含關系，命題集合上的命題的等價、蘊含關系。3-6.1自反性(reflexivity)3-6.2

反自反性(irreflexivity)定義〔反自反性irreflexivity〕：設RAA,如果對于每一個xA，有<x,x>R，那么稱二元關系R是反自反的。R在A上是反自反的(x)(xA<x,x>R)。R在A上是非反自反的(x)(xAxRx)定理：R是反自反的IAR=MR主對角線上的元素全為0GR的每個頂點處均無自回路〔無環(huán)〕。反自反性(舉例)：數(shù)的大于關系，冪集上的集合之間的真包含關系。注意：非自反不一定是反自反的。即存在有關系既不是自反的也不是反自反的。3-6.2

反自反性(irreflexivity)3-6.3

對稱性(symmetry)

定義〔對稱性symmetry〕：設RAA,如果對于每個x,yA,每當xRy，就有yRx，那么稱集合A上的關系R是對稱的。R在A上對稱(x)(y)(xAyAxRyyRx).R非對稱(x)(y)(xAyAxRyyRx)定理：R是對稱的MR是對稱的GR的任何兩個頂點之間假設有邊,那么必有兩條方向相反的有向邊.對稱性(舉例)：平面上三角形的相似關系，人群中人之間的同學、同事、鄰居關系，冪集中集合相等的關系。命題集合上的命題的等價關系。3-6.3

對稱性(symmetry)

3-6.4反對稱性(antisymmetry)定義〔反對稱性antisymmetry〕：設RAA,如果對于每個x,yA,每當xRy和yRx，必有x=y，那么稱集合A上的關系R是反對稱的。R是反對稱的(x)(y)(xAyAxRyyRxx=y)(x)(y)(xAyAx≠yxRyyRx).R非反對稱(x)(y)(xAyAxRyyRxxy)定理：R是反對稱的在MR中,xixj(ijrij=1rji=0)在GR中,xixj(ij),假設有有向邊<xi,xj>,那么必沒有<xj,xi>。3-6.4反對稱性(antisymmetry)反對稱性(舉例)：

實數(shù)集中的小于等于關系、整數(shù)的整除關系，集合的包含關系、命題的蘊含關系。注意：非對稱不一定反對稱；可能有某種關系即是對稱的又是反對稱的。例如：A={1,2,3},S={<1,1>,<2,2>,<3,3>}S在A上即是對稱的又是反對稱的。

N={<1,2>,<1,3>,<3,1>}N在A上即不是對稱的又不是反對稱的。3-6.4反對稱性(antisymmetry)3-6.5

傳遞性(transitivity)定義〔傳遞性transitivity〕：設RAA,如果對于任意的x,y,zA,每當xRy，yRz時就有xRz，稱關系R在A上是傳遞的。R在A上是傳遞的(x)(y)(z)(xAyAzAxRyyRzxRz)R非傳遞(x)(y)(z)(xAyAzAxRyyRzxRz)。定理：R是傳遞的在GR中,xixjxk(ijk),假設有有向邊<xi,xj>和<xj,xk>,那么必有<xi,xk>。傳遞性(舉例)：實數(shù)集中的實數(shù)之間的小于等于、小于、等于關系;冪集上的集合之間的包含、真包含關系;命題集合上的命題的等價、蘊含關系。人群中人之間的同姓關系。3-6.5

傳遞性(transitivity)3-6.6

舉例例1：在N={0,1,2,…}上：

={<x,y>|x

N

y

N

x

y}自反,反對稱,傳遞

={<x,y>|x

N

y

N

x

y}自反,反對稱,傳遞<={<x,y>|x

N

y

N

x<y}反自反,反對稱,傳遞接上頁>={<x,y>|x

N

y

N

x>y}(大于關系)反自反,反對稱,傳遞D={<x,y>|x

N

y

N

x|y}(整除關系)反對稱,傳遞(

0|0)IN={<x,y>|x

N

y

N

x=y}(恒等關系)自反,對稱,反對稱,傳遞EN={<x,y>|x

N

y

N}=N

N(全域關系)自反,對稱,傳遞3-6.6

舉例例2：判斷以下關系所具有的性質(zhì)。A={a,b,c}R1={<a,a>,<a,b>,<b,c>,<a,c>},R2={<a,a>,<a,b>,<b,c>,<c,a>},R3={<a,a>,<b,b>,<a,b>,<b,a>,<c,c>},R4={<a,a>,<a,b>,<b,a>,<c,c>},R5={<a,a>,<a,b>,<b,b>,<c,c>},R6={<a,b>,<b,a>,<b,c>,<a,a>},R7=

3-6.6

舉例解答：R1={<a,a>,<a,b>,<b,c>,<a,c>}反對稱,傳遞R2={<a,a>,<a,b>,<b,c>,<c,a>}反對稱R3={<a,a>,<b,b>,<a,b>,<b,a>,<c,c>}自反,對稱,傳遞R4={<a,a>,<a,b>,<b,a>,<c,c>}對稱R5={<a,a>,<a,b>,<b,b>,<c,c>}自反,反對稱,傳遞R6={<a,b>,<b,a>,<b,c>,<a,a>}R7=〔空關系〕反自反，對稱，傳遞，反對稱.3-6.6

舉例

例6

設，下面分別給出集合A上三個關系的關系圖，試判斷它們的性質(zhì)。（2）非自反，也不是反自反，非對稱，反對稱，可傳遞。（3）是自反的，對稱的，可傳遞的，不是反自反，也不是反對稱。解（1）是自反的，非對稱，不是反對稱，不可傳遞但第三章集合與關系(Sets&Relations)小結(jié):本節(jié)介紹了關系的根本性質(zhì)及其判別方法。作業(yè)：P113〔3〕〔6〕3-7復合關系和逆關系3-7.1復合關系定義1[復合(合成)(composite)關系]:設R為X到Y(jié)的關系，S為從Y到Z上的關系，那么R°S稱為R和S的復合關系，表示為：R°S={<x,z>|xXzZ(y)(yY<x,y>R<y,z>S)}.3-7.2逆關系定義2[逆(inverse)關系]:設R是X到Y(jié)的二元關系，那么從Y到X的二元關系Rc定義為：Rc={<y,x>|<x,y>R}.整數(shù)集合上的“>〞關系的逆關系是“<〞關系。人群中的父子關系的逆關系是子父關系。容易看出(Rc)c=R3-7復合關系和逆關系例1:設R={<a,b>,<c,d>},S={<b,e>,<d,c>}.求:(1)Rc，Sc.(2)R°S,S°R解:(1)Rc={<b,a>,<d,c>}Sc={<e,b>,<c,d>}.(2)R°S={<a,e>,<c,c>}S°R={<d,d>}.例2:〔書上的例題2，第115頁〕3-7復合關系和逆關系定理1:設R1,R2,R3為關系，R1是X到Y(jié)的關系，R2是Y到Z的關系，R3是Z到W的關系那么(R1°R2)°R3=R1°(R2°R3)．證明:<x,w>,<x,w>(R1°R2)°R3z(zZx(R1°R2)zzR3w)z(zZy(yYxR1yyR2z)zR3w)zy(zZyYxR1yyR2zzR3w)yz(zZyYxR1y(yR2zzR3w))y(yYxR1yz(zZyR2zzR3w))y(yYxR1yy(R2°R3)w)xR1°(R2°R3)w<x,w>R1°(R2°R3)(R1°R2)°R3=R1°(R2°R3).#說明:本定理說明復合運算滿足結(jié)合律.3-7復合關系和逆關系

由復合關系滿足結(jié)合律，可以把關系R本身所組成的復合關系寫成：R°R，R°R°R，

，R°R°

°R(m個)，分別記作R(2)，R(3)，

，R(m)?？梢宰C明復合關系不滿足交換律。R1°R2

R2°R13-7復合關系和逆關系7-3.3關系矩陣的性質(zhì)：(1)MRc=(MR)T.(T表示矩陣轉(zhuǎn)置)(2)MR1°R2=MR1

MR2

(

表示布爾乘法,其中加法使用邏輯

,乘法使用邏輯

)3-7復合關系和逆關系3-7.4逆關系關系圖的性質(zhì)：關系Rc的圖形是將關系R圖形中弧的箭頭方向反置。3-7復合關系和逆關系定理2:設R、R1、R2都是從A到B的二元關系，那么有(1)(R1R2)c=R1cR2c(2)(R1R2)c=R1cR2c(3)(A×B)c=B×A(4)(~R)c=~Rc,這里~R＝A×B-R(5)(R1-R2)c=R1c-R2c注：證明(1)(4)(5)見書117頁。3-7復合關系和逆關系定理3:設R,S為二元關系,那么(R°S)c=Sc°Rc.證明:<x,y>,<x,y>(R°S)c<y,x>(R°S)z(yRzzSx)z(zRcyxScz)z(xSczzRcy)<x,y>Sc°Rc.3-7復合關系和逆關系定理4:設R為X上的二元關系，那么(1)R是對稱的R=Rc〔證明見書118頁〕(2)是反對稱的RRcIX〔留作練習〕定理5:[P119(2)]設R為X上的二元關系，那么(1)R是傳遞的(R°R)R(2)R是自反的IXR3-7復合關系和逆關系例題:設A={a,b,c},R1={<a,a>,<a,b>,<b,a>,<b,c>},R2={<a,b>,<a,c>,<b,c>},用MR1,MR2確定MR1c,MR2c,MR1°R1,MR1°R2,MR2°R1,從而求出它們的集合表達式.3-7復合關系和逆關系110110MR1=101MR1c=100000010011000MR2=001MR2c=100000110011MR1

R2=MR1

MR2=011000R1°R2

={<a,b>,<a,c>,<b,b>,<b,c>}.3-7復合關系和逆關系110110111MR1

R1=MR1

MR1=101

101=110000000000R1°R1

={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}.011110101MR2

R1=MR2

MR1=001

101=000000000000R2°R1

={<a,b>,<a,c>}.3-7復合關系和逆關系解:R1c={<a,a>,<a,b>,<b,a>,<c,b>}R2c={<b,a>,<c,a>,<c,b>}R1°R1

={<a,a>,<a,b>,<a,c>,<b,a>,<b,b>}.R1°R2

={<a,b>,<a,c>,<b,b>,<b,c>}.R2°R1

={<a,b>,<a,c>}.3-7復合關系和逆關系第三章集合與關系(Sets&Relations)小結(jié):本節(jié)主要介紹了關系的復合運算與逆運算。重點掌握關系的復合運算及其性質(zhì)、關系的逆運算的性質(zhì)。作業(yè)：P118(1)(2)(4) (8)3-8關系的閉包運算自反閉包r(R)(reflexivityclosure)對稱閉包s(R)(symmetryclosure)傳遞閉包t(R)(transitivityclosure)閉包的性質(zhì),求法,相互關系3-8.1自反閉包(reflexiveclosure)定義1[自反閉包]:

包含給定關系R的最小自反關系,稱為R的自反閉包,記作r(R).(1)r(R)是自反的;(2)R

r(R);(3)(

S)((R

S

S自反)

r(R)

S).3-8關系的閉包運算3-8.2對稱閉包(symmetricclosure)定義2[對稱閉包]:

包含給定關系R的最小對稱關系,稱為R的對稱閉包,記作s(R).(1)s(R)是對稱的;(2)R

s(R);(3)(

S)((R

S

S對稱)

s(R)

S).3-8關系的閉包運算3-8.3傳遞閉包(transitiveclosure)定義3[傳遞閉包]:

包含給定關系R的最小傳遞關系,稱為R的傳遞閉包,記作t(R).(1)t(R)是傳遞的;(2)R

t(R);(3)(

S)((R

S

S傳遞)

t(R)

S).3-8關系的閉包運算定理1:設RAA且A,那么(1)R自反r(R)=R;(2)R對稱s(R)=R;(3)R傳遞t(R)=R;證明:(1)RRR自反r(R)R又Rr(R),r(R)=R.(2)(3)完全類似.3-8關系的閉包運算*〔補充〕定理1:設R1R2AA且A,那么(1)r(R1)r(R2);(2)s(R1)s(R2);(3)t(R1)t(R2);證明:(1)R1R2r(R2)自反,r(R1)r(R2)(2)(3)類似可證.3-8關系的閉包運算*〔補充〕定理2:設R1,R2AA且A,那么(1)r(R1R2)=r(R1)r(R2);(2)s(R1R2)=s(R1)s(R2);(3)t(R1R2)t(R1)t(R2).證明:(1)利用補充定理1,r(R1)r(R2)r(R1R2).r(R1)r(R2)自反且包含R1R2,所以r(R1R2)r(R1)r(R2).r(R1R2)=r(R1)r(R2)3-8關系的閉包運算證明(2):利用補充定理1,

s(R1)

s(R2)

s(R1

R2).s(R1)

s(R2)對稱且包含R1

R2,所以

s(R1

R2)

s(R1)

s(R2).

s(R1

R2)=s(R1)

s(R2)證明(3):利用補充定理1,t(R1

R2)

t(R1)

t(R2).

反例:t(R1)

t(R2)不滿足傳遞性.3-8關系的閉包運算定理2:設RAA且A,那么(1)r(R)=RIA;(2)s(R)=RRc;(3)t(R)=RR2R3….比照:R自反IARR對稱R=RcR傳遞R2R3-8關系的閉包運算證明:(1)r(R)=R

IA;i)R

R

IA;ii)IA

R

IA

R

IA自反

r(R)

R

IA;iii)R

r(R)

r(R)自反

R

r(R)

IA

r(R)

R

IA

r(R)

r(R)=R

IA.3-8關系的閉包運算證明:(2)s(R)=R

Rc;i)R

R

Rc;ii)(R

Rc)c=R

Rc

R

Rc對稱

s(R)

R

Rc;iii)R

s(R)

s(R)對稱

R

s(R)

Rc

s(R)

R

Rc

s(R)

s(R)=R

Rc.3-8關系的閉包運算證明(3)之前，說明以下事實：復合運算對并運算滿足分配律R1

°(R2

R3)=(R1

°R2)(R1

°R3)(R1

R2)°R3=(R1

°R3)(R2

°R3)復合運算對交運算滿足弱分配律R1

°(R2

R3)

(R1°R2)(R1

°R3)(R1

R2)°R3

(R1°R2)(R1

°R3)3-8關系的閉包運算證明:(3)t(R)=R

R2

R3

….證明:i)先證t(R)

R

R2

R3

…;∵R

R

R2

R3

…;∵(R

R2

R3

…)2=R2

R3

…

R

R2

R3

…

R

R2

R3

…傳遞

∴

t(R)

R

R2

R3

…;ii)再證R

R2

R3

…

t(R)∵R

t(R)

t(R)傳遞

R

t(R)

R2

t(R)

R3

t(R)

…

R

R2

R3

…

t(R)

t(R)=R

R2

R3

….#3-8關系的閉包運算定理3：設X是含有n個元素的集合，R是X上的二元關系，那么存在一個正整數(shù)kn，使得t(R)=RR2R3…Rk證明：見P122。3-8關系的閉包運算例題1:設A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}.

求r(R),s(R),t(R).解:r(R)=R

IA={<a,a>,<b,b>,<c,c>,<d,d>,<a,b>,<b,a>,<b,c>,<c,d>}s(R)=R

Rc={<a,b>,<b,a>,<b,c>,<c,b>,<c,d><d,c>}t(R)=R

R2

R3

R4

={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}見P1233-8關系的閉包運算求傳遞閉包的另一種方法：當有限集X的元素較多時，矩陣運算很繁瑣，Warshall在1962年提出了R+的一個有效算法如下：〔1〕置新矩陣A=M〔2〕置i=1〔3〕對所有j如果A[j,i]=1，那么對k=1,2,…,nA[j,k]=A[j,k]+A[i,k]〔4〕i=i+1〔5〕如果in,那么轉(zhuǎn)到步驟〔3〕,否那么停止。3-8關系的閉包運算引出下面定理：閉包運算是否可以交換順序?即：(1)rs(R)=sr(R)?(2)rt(R)=tr(R)