離散數(shù)學課件第四章總結zhou1

總結第四章關系

重點是有序二元組<a,b>和兩個集合的笛卡爾積A×B。這兩個概念是二元關系這一概念建立的基礎。1.有序n元組和n個集合的笛卡爾積

2.二元關系（簡稱“關系”）的概念總結第四章關系3.二元關系的表示方法(1)集合的表示方法：枚舉法和構造法均可用來表示關系。(2)關系矩陣表示法，用來表示由有限集A到有限集B的關系。

(3)關系圖表示法4.集合A上關系的性質(1)自反與反自反：分別定義為對所有的，必須均有和不允許任何。(2)對稱：對任意，若有，則必須有同時出現(xiàn)在中。(3)反對稱：對任意，當a≠b時，<a,b>和<b,a>不能在中，則必有<a,c>也出現(xiàn)在中。(4)可傳遞：對任意三個元素a,b,c

A，若<a,b>,<b,c>出現(xiàn)R是不自反的＝x(xX∧<x,x>R)∧y(yX∧<y,y>?R)R是不對稱的=xy(xX∧yX∧<x,y>R∧<y,x>?R)∧zw(zX∧wX∧z≠w∧<z,w>R∧<w,z>R)（補充）如何利用關系矩陣和關系圖來判斷關系的性質（1）關系矩陣

1234若是對稱的，則關系矩陣關于主對角線對稱。若是反對稱的，則關系矩陣中，關于主對角線對稱的元素不同時為1。若是自反的，則關系矩陣的主對角線上的所有元素均為1。若是反自反的，則關系矩陣的主對角線上所有元素均為0。（2）關系圖

若是自反的，則關系圖中每一結點引出一個指向自身的自環(huán)。若是反自反的，則關系圖中每一結點均沒有自環(huán)。

若是對稱的，則在關系圖中，若兩結點之間存在有邊，則必存在兩條方向相反的邊。若是反對稱的，則在關系圖中，任意兩個不同的結點間至多只有一條邊。

若是可傳遞的，則在關系圖中，若每當有邊由指向，且又有邊由指向，則必有一條邊由指向?？偨Y第四章關系5.關系的運算

(4)當關系定義在有限集上時，可利用關系矩陣或關系圖求上述各種關系。

對集合A上給定的關系，求

(1)對集合A上給定的關系，求其逆關系。

(2)對給定的由集A到集B的關系和由集B到集C的關系，求其合成關系。

特殊情形：關系的冪。(3)關系的閉包運算和閉包的性質總結第四章關系6.集合A上幾類特殊的關系

(1)等價關系：具有自反，對稱和可傳遞性，它可導致對A的一個劃分。

(2)相容關系：具有自反，對稱性，它可導致對A的一個覆蓋。

(3)次序關系：具有可傳遞性的關系，提供了比較集合中各元素的手段。

偏序關系：具有自反，反對稱，可傳遞性。擬序關系：具有反自反，反對稱，可傳遞性。全序關系：任兩個元素都有關系的偏序。良序：每個子集都有最小元素的全序。字母序：研究序偶間關系的全序。

解

滿足上述條件的最小基數(shù)的關系

ρ2={<2,3>，<2,4>，<4,3>｝一般說，給定ρ1和ρ1°ρ2，不能唯一的確定ρ2

。例如ρ2=｛<2,3>，<2,4>，<4,3>，<0,0>，<3,3>｝也可以.3．給定集合{0,1,2,3,4}上的關系ρ1=｛<0,1>,<1,2>,<3,4>},ρ1oρ2=｛<1,3>，<1,4>，<3,3>｝,求一個基數(shù)最小的關系,使?jié)M足ρ2的條件.一般地說,若給定ρ1和ρ1oρ2

，ρ2

能被唯一地確定嗎?基數(shù)最小的ρ2能被唯一確定嗎？6.是集合上自反和傳遞的關系，試證明：證：，由關系復合的定義，存在，使得因傳遞，有可得另一方面，，因自反，由復合函數(shù)的定義，有可得綜合可得。證畢。7.有人說，集合A上的關系，如果是對稱的且可傳遞，則它也是自反的。其理由是，從對稱性傳遞性例設A＝｛1,2，3｝ρ＝｛<1,2>,<2,1>,<1,1>,<2,2>}錯!8.設集合，A上的關系，試問具有些什么性質？對，若x+y=10，則y+x=10，因此ρ是對稱的。解:因為2＋2≠10，所以ρ非自反。因為5＋5＝10，所以ρ不是反自反。因為2+8=10，也有8+2=10，所以ρ不是反對稱的。因為1+9=10，9+1=10，但1+1≠10，所以ρ是不可傳遞的。9.設是集合A上的等價關系，試問是否A上的等價關系？解:10.判斷題：假設R和S是集合A上的兩個等價關系，判斷下列關系是否是集合A上的等價關系？解：均不是11.設A={a,b,c,d}，對A上的下一等價關系寫出其導出的劃分。（1）12.設A={a,b,c,d}，對A的下一劃分，寫出其相對應的等價關系。（1）{

}<a,a>,<b,b>,<c,c>,<d,d>,<b,c>,<c,b>,<d,b>,<b,d>,<c,d>,<d,c>13.設R1和R2是集合X中的等價關系。試證明：當且僅當C1中的每一個等價類都包含在C2的某一個等價類之中，才有R1

R2.證明：設等價關系R1造成的集合X的劃分為C1={C11,C12,…,C1m},等價關系R2造成的集合X的劃分為C2={C21,C22,…,C2n}(充分性)任取C1中的一個等價類C1i，則必包含在C2的一個等價類里，設包含在C2j中，C1i

C2j。任取C1i中兩元素x，y，由等價類的性質知，xR1y。由C1i

C2j，可知若x,y∈C1i,則x,y∈C2j，即xR2y。由i,j,x,y取值的任意性知，R1

R2。(必要性)如果R1

R2，那么對任意的<x,y>∈R1→<x,y>∈R2永真，<x,y>∈R1等價于x,y落入C1的某個等價類C1i中，<x,y>∈R2等價于x,y落入C2的某個等價類C2j中，即若x,y∈C1i，則x,y∈C2j，由x,y的任意性可知，C1i

C2j,由i的任意性可知，C1中的每一個等價類都包含在C2的某一個等價類之中。得證。設Ｒ1和R2是集合Ｘ中的等價關系，并分別有秩r1和r2，試證明：Ｒ1∩R2也是集合X中的等價關系，它的秩至多是r1r2。而Ｒ1

R2不一定是集合X中的等價關系．（Ｒ1-R2，Ｒ1?R2也不一定是）證明：首先證明Ｒ1∩R2是等價關系1)(?x)(x∈X→<x,x>∈R1∩R2)=(?x)(?x∈X∨(<x,x>∈R1∧<x,x>∈R2))=(?x)((?x∈X∨<x,x>∈R1)∧(?x∈X∨

<x,x>∈R2))=(?x)(?x∈X∨<x,x>∈R1)∧(?x)(?x∈X∨<x,x>∈R2)=T∧T=T利用全稱量詞對與的可分配性自反性得證．再來證Ｒ1∩R2是對稱的用反證法，假設Ｒ1∩R2是不對稱的，即(?x)(?y)(x,y∈X∧<x,y>∈Ｒ1∩R2∧<y,x>?Ｒ1∩R2)=(?x)(?y)(x,y∈X∧<x,y>∈Ｒ1∧<x,y>∈Ｒ2∧(<y,x>?Ｒ1∨<y,x>?Ｒ2))=(?x)(?y)((x,y∈X∧<x,y>∈Ｒ1∧<x,y>∈Ｒ2∧<y,x>?Ｒ1)∨(x,y∈X∧<x,y>∈Ｒ1∧<x,y>∈R2∧<y,x>?Ｒ2))=(?x)(?y)(x,y∈X∧<x,y>∈Ｒ1∧<x,y>∈Ｒ2∧<y,x>?Ｒ1)∨(?x)(?y)(x,y∈X∧<x,y>∈Ｒ1∧<x,y>∈R2∧<y,x>?Ｒ2)(利用存在量詞對∨的可分配性)=F∨F=F即假設不成立，對稱性得證．使用反證法同樣可以證明Ｒ1∩R2是可傳遞的．即它是等價關系．再來證Ｒ1∩R2至多有r1r2個類因為對任意的x,y∈X和<x,y>∈R1∧

<x,y>∈R2＝x,y∈C1i

∧x,y∈C2j

其中i=1,2,┅,r1,j=1,2,┅,r2至多為r1r2證畢．例如令X={a,b,c,d}R1={<a,a>,<b,b>,<c,c>,<d,d>,<a,d>,<d,a>}R2={<a,a>,<b,b>,<c,c>,<d,d>,<b,c><c,b>,<b,d>,<d,b>,<c,d>,<d,c>}顯然R1和R2都是Ｘ上的等價關系，但R1

R2＝{<a,a>,<b,b>,<c,c>,<d,d>,<a,d>,<d,a>,<b,c>,<c,b>,<b,d>,<d,b>,<c,d>,<d,c>}不是等價關系，沒有<b,a>.在可傳遞性上出問題了。14.設R1和R2是集合A中的等價關系，考察的關系.解：由于R1和R2是集合A上的等價關系，很容易得出是集合A上的等價關系，于是是集合A關于等價關系的商集。１、(79頁第３題)R1,R2是集合Ｘ中的關系，試證明：(1)r(R1

R2)=r(R1)

r(R2)(2)s(R1

R2)=s(R1)

s(R2)(3)t(R1

R2)?t(R1)

t(R2)證明(1)左邊=r(R1

R2)

=R1

R2Ix右邊=r(R1)

r(R2)=R1Ix

R2Ix

=R1

R2Ix(1)式得證。證(2)左邊=s(R1

R2)=(R1

R2)

(R1

R2)?=R1

R2

R1?

R2?=(R1

R1?)(R2

R2?)=s(R1)

s(R2)(2)得證。證(3)t(R1

R2)?t(R1)

t(R2)t(R1

R2)=(R1

R2)

(R1

R2)2

┄

(R1

R2)n而(R1

R2)2=(R1

R2)o

(R1

R2)=((R1

R2)oR1)

((R1

R2)oR2)=R12

R2oR1

R1oR2

R22?R12

R22┅

(R1

R2)n?R1n

R2n于是有(R1

R2)

(R1

R2)2

┅

(R1

R2)n?R1

R12

┅

R1n

R2

R22

R22┅

R2n

即t(R1

R2)?t(R1)

t(R2)(3)得證．２、(85頁第１題)設｛Ａ1,Ａ2,

┄,Ａn｝是集合Ａ的劃分，試證明：｛Ａ1∩Ｂ，Ａ2∩Ｂ,┄,Ａn∩Ｂ｝是集合Ａ

∩Ｂ的劃分．證明：因為Ａ1?Ａ

Ａ2?Ａ

┄

Ａn?Ａ于是有Ａ1∩B?Ａ∩B

Ａ2∩B

?Ａ∩B

┄

Ａn∩B

?Ａ∩B

并且Ａ1∩B

Ａ2∩B

┄

Ａn∩B=(Ａ1

Ａ2

┄

Ａn)∩B=

A∩B.對任何(Ａi∩B)∩(Ａj∩B)=(Ａi∩Ａj)∩B=Φ∩B=Φ(i≠j)