离散数学课件

集合集合的概念集合用於把對象組織在一起,通常一個集合中的元素都有相似的性質.集合不能精確定義.集合可以描述為:一個集合把世間萬物分成兩類,一些對象屬於該集合,是組成這個集合的成員,另一些對象不屬於該集合.可以說,由於一個集合的存在,世上的對象可分辨地分成兩類,世上任一對象或屬於該集合或不屬於該集合,二者必居其一,也只居其一.表示集合的描述法我們用第一章的知識作為工具來描述和研究集合.集合描述法S={a|P(a)},其中a在全總個體域中變化;P(a)是謂詞,其含義是:a

S

當且僅當

P(a)是真.採用集合描述法是使用謂詞演算工具的基礎.集合包含關係的性質①(外延公理)

對任意集合A和B都有A=B

當且僅當

AB∧BA特別AA②(傳遞性)

對任意集合A,B和C都有AB∧BC

AC③

對任意集合A都有

A和AU全集與空集的概念為方便起見,我們所討論的全部集合和元素是限於某一論述域中.即使這個論述域有時沒有明確地指出,但表示集合元素的變元只能在該域中取值.此論述域常用U表示,並稱為全集.沒有元素的集合稱為空集,記為

.由定義知:對任意集合A成立AA;AU;A;.全集與空集在本章中起重要作用,要求掌握它們的基本性質.注意區分關係

與

表示集合的元素與集合本身的從屬關係

表示兩個集合之間的包含關係.

例如對於集合

A={a,b,c},{a}是

A

的子集表示為{a}

A;

a

是

A

的元素表示為

a

A.注意:不要寫成{a}

A

或

a

A.

{a}a,但

a

{a}.

{}是一元集,而不是空集;|{}|=1;|

|=0.

集合之間的相等關係等價於互為子集合.習題2.1#9:若A,B,C都是集合且A

B

和

B

C,A

C

可能嗎?A

C常真嗎?解

A

C可能,例如,對任意集合

A;B={A,{0}};C={A,B}有

A

B,B

C

和

A

C.A

C不常真,例如:A=;B={

,0};C={1,B}有

A

B

和

B

C,但

AC.注:

是可傳遞的;而不是可傳遞的.習題2.1#10(b):A,B,C都是集合,(A

B∧B

C)AC不成立證:舉反例證明,令A={0};B={{0}};C={{0}}.則

A

B∧B

C,但

A

C,即(A

B∧B

C)

AC不成立.(注:B=C,但

B

C)§2.1的作業佈置#1(c);#2(b),(d);#4提示:先給出各集合所含元素後再回答.#10(a);#13(a),(b),(c),(d),(e),(f).羅素悖(bei)論在命題定義時,某些‘自稱謂’的陳述句可能產生自相矛盾的結論.例如,某人說:‘我正在說謊’(另例見習題2.1#8).為簡單起見,不列入我們討論範圍.在集合定義時存在類似的現象.羅素給出下列經典例子:S={A|A

A}這個定義不滿足“世上任一對象或屬於或不屬於該集合

S,二者必居其一”的要求.因為,考慮

S

自身時,若

SS,則由

S

的定義有

S

S,這顯然矛盾;若

S

S,則由

S

的定義有

SS,也得出矛盾.集合上的運算設A,B為全總個體域

U

任意子集,x為

U

中元素①A

和

B

的並是下列集合

A∪B={x|xA∨xB};②A

和

B

的交是下列集合

A∩B={x|xA∧xB};A

和

B

稱為是不相交的,如果

A∩B=.③A

和

B

的差是下列集合

A-B={x|xA∧x

B}.

集合的並,交和差運算的文氏圖ABA並BABA-BABA交B注意集合運算與邏輯運算的對應關係令A,B為全集U的任意子集;令A(x)

xA;B(x)

xB,T(x)

xU;F(x)

x,則

A∪B={x|A(x)∨B(x)};

A∩B={x|A(x)∧B(x)};x

A

¬A(x);A-B={x|A(x)∧¬B(x)},U-A={x|¬A(x)};A

B

x(xA

xB);xT(x)為真,xF(x)為假(U,分別對應於永真,永假命題T,F).用謂詞演算證明集合論公式例1:A∪B={x|A(x)∨B(x)}={x|B(x)∨A(x)}=B∪A.例2:A∩A={x|A(x)∧A(x)}={x|A(x)}=A§2.2的作業佈置#1(b),(c),(d);#2(a),(c);#4(a)(i);#6(b);#11(a);#12(d),(e)#18(c).§2.2#6(a):若

CA

且

CB,則

C

A∪B證:(CA)∧(CB)

x(xA

xC)∧x(xB

xC)

x(¬(xA)∨(xC))∧x(¬(xB)∨(xC))

x((¬(xA)∧¬(xB))∨(xC))

量詞分配形式,分配律

x((¬((xA)∨(xB))∨(xC))摩根

x(x(A∪B)

xC)

C

A∪B注:此結論的意義是:A∪B是同時包含

A和

B

的最小集合.另證:已知(CA)∧(CB)

即

x(xA

xC)∧

x(xB

xC)∵xA∪B(xA)∨(xB)xC∴

x(x(A∪B)

xC)

C

A∪B得證(CA)∧(CB)

CA∪B並、交、差運算的性質祥見定理2.2-1,2.2-2和

2.2-3.這些性質對應於第一章有關∧,∨和¬

的性質.用謂詞演算證明集合論公式定理2.2-3(k):

A

B

A∪B=B.證:

若

A

B,則對任意

x,

xA

xB.

∴對任意

x,

xA∪B

xB,即A∪BB.另一方面,由(i)B

A∪B.得證

A∪B=B.集合A的補運算,記為AU-AAUAAA的補U集合補運算的性質①A=U-A={x|¬A(x)};(A)=A.¬¬A(x)=A(x)②A∪A=U,A∩A=.證A∪A={x|A(x)∨¬A(x)}={x|T(x)}=U.A(x)∨¬A(x)T(x)③A存在而且唯一.

(由①及¬A(x)唯一推出)④

=U,U=.

(由¬F=T或¬T=F推出)⑤(A∪B)=A∩B;(A∩B)=A∪B.

用摩根律:

¬(A(x)∨B(x))=¬A(x)∧¬B(x)⑥A∩B=A-B.(A-B={x|A(x)∧¬B(x)}=A∩B

)習題2.2

#11(b)

對任意集合A,B,證明:A∪(B-A)=A∪B解:A∪(B-A)=A∪(B∩A)=(A∪B)∩(A∪A

)

分配律

=(A∪B)∩U排中律

=A∪B同一律集合的並和交運算的擴張①設D是一個集合,如果給定D的任一元素d,就能確定一個集合

Ad,那麽d叫做

Ad的索引,C={Ad|dD}叫做集合的加索引搜集,而D叫做索引集.②設C為加索引搜集,C的成員的並∪S

CS={x|

S(S

C∧xS}可表示為:∪dD

Ad={x|

d(d

D∧xAd}.③如果,C≠,C的成員的交∩S

CS={x|

S(S

C

xS}可表示為:

∩dDAd={x|

d(d

D

xAd}.集合並和交運算擴張的例①C={Ad|d{1,…,n}}={A1,…,An},則

C

的成員的並∪S

CS

可以表示為:∪1≤d≤n

Ad

或A1∪…∪An②C={Ad|dN={0,1,2,…}}={A0,A1,A2,…},則

C

的成員的交∩S

CS

可以表示為:∩d

NAd

或A0∩A1∩A2∩…注:C={Ad|dR},則

C

的成員的交表為∩d

R

Ad

不能列舉習題2.2#17

證明下列分配律的推廣:B∩(∪S

C

S)=∪S

C

(B∩S)解:x

B∩(∪S

CS)

(xB)∧(x

∪S

CS)

(xB)∧S(SC∧xS)

S(xB∧SC∧xS)轄域擴張

S(SC∧x(B∩S)

交換結合

x∪S

C(B∩S)同理可證:摩根定理的推廣(#16).習題1.6作業中出現的一些問題#11(a)

如果xy=0,那麼x=0或y=0xy(P(x,y,0)E(x,0)∨E(y,0))#11(c)

如果y=1,則對一切x,xy=x

y(E(y,1)

xP(x,y,x))

#11(i)x=y和x<y不能同時出現

¬(xy(E(x,y)∧G(y,x))xy¬(E(x,y)∧G(y,x))#15(f):有某個質數其平方和是偶數

x(P(x)∧E(x2))習題1.7#3證明:

P(x)∧xQ(x)x(P(x)∧Q(x))解:P(x)∧xQ(x)P(x)∧Q(x)

Q1x(P(x)∧Q(x))Q2個別錯誤解:P(x)∧xQ(x)xP(x)∧xQ(x)?

x(P(x)∧Q(x))用反了

(見p43量詞分配形式③)習題1.8#7證明:

苏格拉底论证是有效的解:設M(x):x是人,D(x):x是要死的,

個體常元a:蘇格拉底要證:x(M(x)D(x))∧M(a)D(a)

步驟斷言根據

.

1x(M(x)D(x))P2M(a)D(a)T,1,US3M(a)

P4D(a)T,2,3,假言推理習題1.8#8(b)證明:

x(P(x)∧Q(x))xP(x)無效解:舉反例設論述域:{1,2},P(x):x為偶數,Q(x):x為質數,則

x(P(x)∧Q(x))為真,xP(x)P(1)∧P(2)為假,x(P(x)∧Q(x))xP(x)無效錯解:1x(P(x)∧Q(x))P

2P(y)∧Q(y)T,1,ES

3P(y)T,2,簡化式

4

xP(x)T,3,UG?兩集合的環和(對稱差)兩集合的環和(對稱差)定義為下列集合:A

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

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

=(A-B)∪(B-A)=(A∪B)∩(A

∪B

)

分配律等

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

摩根律

=(A∪B)

(A∩B)其中,謂詞

A(x)的含義是:

xA.對稱差的文氏圖ABA與B的對稱差A

B=(A

B)∪(B

A)=(A∪B)

(A∩B)A∩B兩集合環和的(對稱差)性質①A

B=(A∪B)-(A∩B)

=(A∪B)∩(A∩B)=(A∪B)∩(A’∪B’)②A

B=BA;AA=(A∪A)-(A∩A)=;

A

B

=(A’∪B’)∩(A∪B)=A

B③(A

B)C=A

(BC)結合律④C∩(A

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

分配律注意:不同於所列出的公式未必成立.A(BC),(A

B)C的文氏圖ABC

都是由屬於三集中的任意兩個而不屬於所有三個的一切元素組成.習題2.2#20(c)

A,B,C是任意集合,證明:C

∩(A

B)=(C∩A)

(C∩B)解:C∩(AB)=C∩(A∪B)∩(A

∪B

)=(A∪B)∩(C∩(A

∪B

))

交換,結合律

=(A∪B)∩(C∩(C’∪A

∪B

))

分配律,C∩C’=

及同一律

=(C∩(A∪B))∩((C’∪A

)∪(C’∪B

))=((C∩A)∪(C∩B))∩((C∩A)∪(C∩B))

=(C∩A)

(C∩B)集合A的冪集

集合A的冪集

(A)是A所有子集的集合:(A)={B|BA}.

例:三元集

A={1,2,3}的冪集

(A)是{,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}={S000,S100,S010,S001,S110,S101,S011,S111}(A)與所有3位二進位數的集合:{000,001,010,011,100,101,110,111}的元素間存在一一對應關係,故其元素共有

23=8

個.n元集冪集與n位二進位數集一一對應(A)的元素的表示.考慮3元集

A={a1,a2,a3},則

(A)={sijk|i,j,k{0,1}},

這裏,ausijk,當且僅當sijk的第u個腳標為1.

所以,(A)與3位二進位串的集合間存在一一對應關係,由此得證

(A)的元素個數是23.一般地,n元集的冪集的元素個數是2n(因此人們也把A的冪集記為2A).有限集的計數對有限集合

A,B,成立下列基數公式:①|A∪B|=|A|+|B|-|A∩B|②|A∩B|min(|A|,|B|)③|AB|=|A|+|B|-2|A∩B|④|A-B||A|-|B|⑤|(A)|=

2|A|注:

上述公式的正確性不難從有關文氏圖推出(以①,③為例).ABA∩B|AB|=|A|+|B||A∩B||AB|=|A|+|B|2|A∩B|自然數的定義—皮亞諾公設按皮亞諾公設自然數集

N

可定義如下:①0N②如果nN,則恰有一個n的後繼nNn=n+1③0不是任何自然數的後繼④如果n=m,則

n=m⑤(極小性條款)

如果S是N的子集使

①

0S

和

②

若nS,則

nS,那麼,S=N注:每元有唯一後繼;除0外每元只有一個直接前趨.數學歸納法第一原理利用極小性條款可得到以自然數集N為論述域的

xP(x)形式的斷言為真的數學歸納法第一原理的證明過程.令S={n|P(n)}為N的子集,如果

①

P(0)為真;②n(P(n)P(n+1))為真,那麼,對一切

nN,P(n)為真.∵S=N由此得證數學歸納法第一原理的過程如下(基礎)先證

P(0)是真(歸納)再證明

n(P(n)P(n+1))為真.

為此,須先假設對任意

nN,P(n)為真(歸納假設)並由此再推出

P(n+1)為真.數學歸納法第二原理數學歸納法第二原理證明

xP(x)為真的過程如下：首先,證P(0)為真.其次,對正整數n,假設

k(k<nP(k))為真(歸納假設)並由此再推出P(n)為真.證:只需證數學歸納法第二原理實際上等價於數學歸納法第一原理即可.前者的歸納假設顯然包含後者,故前者成立必有後者成立;另外,從歸納法的實際進程分析,不難看出:後者成立也必有前者成立.試證:1+2+…+n=n(n+1)/2大數學家

Gauss

在讀小學時就能巧妙地回答了老師提出的下列數學難題:1+2+…+100=?他的思路可以解釋如下:1+2+…+100=100+(1+99)+(2+98)+…+(49+51)+50=5050若令S=1+2+…+n,則

2S=(1+(n-1))+(2+(n-2))+…+((n-1)+1)+(n+n)=n(n+1).∴1+2+…+n

=

S

=

n(n+1)/2.數學歸納法第一原理證明舉例§2.3#7:對一切正整數n成立(1+2+…+n)2=13+23+…+n3⑴證:n=1時⑴成立:(1)2=13.設n時

⑴

成立,則(1+2+…+n+(n+1))2=(1+2+…+n)2+2(1+2+…+n)(n+1)+(n+1)2=13+23+…+n3+2(n(n+1)/2)(n+1)+(n+1)2=13+23+…+n3+n(n+1)2+(n+1)2=13+23+…+n3+(n+1)3故由數學歸納法第一原理推出⑴成立.注:用了公式:1+2+…+n=n(n+1)/2數學歸納法第二原理應用舉例

習題2.3#6:今有3分和5分票值的郵票,試證:用這兩種郵票足以組成多於8分的任意郵資.證:只需證對任意整數

n≥8,存在非負整數p,q使n=3p+5q⑴當

n=8,9,10時

⑴

已成立:8=3+5;9=3

3+5

0;10=3

0+5

2設

n≥8+3,且對滿足

8≤k<n的正整數k,⑴

成立:k=3p+5q,則n-3=k=3p+5qn=3p+5q+3=3(p+1)+5q故由數學歸納法第二原理推出

⑴

恒成立.集合的笛卡爾乘積

集合

A1,…,An的笛卡爾乘積定義為下列

n

重組的集合:A1An={

a1,…,an

|

aiAi,1in}.(記AA=An)舉例如下:

①令

R

為所有實數的集,則RR表通常的實平面;

RRR表通常的3維實空間.②{a,b}{1,2,3}={a,1,a,2,a,3,b,1,b,2,b,3}{1,2,3}{a,b}

={1,a,1,b,2,a,2,b,3,a,3,b}顯然,二者不相等,故笛卡爾乘積不滿足交換律.集合的笛卡爾乘積的運算性質①集合的笛卡爾乘積運算不滿足交換律②集合的笛卡爾乘積在交,並,差與對稱差上都滿足分配律.(定理2.5-1,習題#6(d)(e))③A=A=對任何集A成立.

無元存在例(A∩B)C

=(AC)∩(BC)

定理2.5-1(d)證:x,y(A∩B)Cx(A∩B)∧yC定義

xA∧xB∧yC定義

xA∧xB∧yC∧yC

等冪律

(xA∧yC)∧(xB∧yC)交換結合

x,y(AC)∩(BC)定義集合笛卡爾乘積的元素個數集合A1,…,An的笛卡爾乘積:A1An={

a1,…,an

|

aiAi,1in}

的一般元

a1,…,an

中,每個

ai有|Ai|種可能取值,1in,故共有|A1|∙∙∙|An|個不同的

n

重組

a1,…,an

.

|A1An|=|A1|∙∙∙|An|.2.5習題的作業佈置#2(a),(c);#3;#4提示:

x,y(A∩B)(C∩D)x(A∩B)∧y(C∩D)

x,y(AC)∩(BC)習題2.5#5A,B是任意集合,證明:AB=BA

A=∨B=∨A=B解:‘

’顯然(此時AB=BA=或AA).‘

’

當AB=BA時,若¬(A=∨B=∨A=B),則由摩根律知A∧B∧AB,故

ab(aA∧bB∧(aB∨bA)從而

a,b(AB-BA)=

,得出矛盾.

2.5習題#6(a)A,B是任意集合

(A∪B)(C∪D)=(AC)∪(BD)不成立證:

作反例:令A={1},B={2},C={3},D={4},則(A∪B)(C∪D)={1,2}{3,4}={{1,3,1,4,2,3,2,4}(AC)∪(BD)={1,3}∪{2,4})={{1,3,2,4}∴(A∪B)(C∪D)(AC)∪(BD)第三章二元關係§3.1基本概念§3.2關係的合成§3.3關係上的閉包運算§3.4次序關係§3.5等價關係和劃分§3.1基本概念

如果說,數學的研究對象是集合的話,

那麼,研究集合的結構主要是研究關係.

關係概念的應用非常廣泛,尤其在計算科學中起著重要作用.關係的概念定義:AB

的子集

R

叫做

A

到

B

的一個2元關係;A1An的子集

R

叫做A1An上的一個n元關係.若x,yR,則稱x與y有關系R,並記為xRy.例1:A={a,b,c,d};B={e,f,g};則R={a,g,d,e}是一個2元關係,且有aRg;dRe.注:因一般地

x,y

y,x,故一般地xRy

yRx.二元關係的圖示

一般二元關係的圖示如圖3.1-1所示.

集合A上的二元關係也可用有向圖表示.例如A={1,2,3,4,5}上關係

R={1,2,2,2,3,2,3,4,4,3}的圖示為12354二元關係的前域,陪域,定義域,值域

R為A到B的一個2元關係時,稱A為R的前域,稱B為R的陪域.

集合D(R)={x|y(x,yR}稱為R的定義域;R(R)={y|x(x,yR}稱為R的值域.

一般常有D(R)A,R(R)B.

對於例1中的關係:R={

a,g,d,e}有

D(R)={a,d};R(R)={g,e}.再如A={1,2,3,4,5}上關係

R={1,2,2,2,3,2,3,4,4,3}有

D(R)={1,2,3,4};R(R)={2,3,4}.一些重要關係

若

R=A1An,

則

R

稱為全域關係;若

R=

則

R

稱為空關係.

設

S

和

R都是

A

到

B

的關係,則

R∪S,R∩S,

R-S,R

分別稱為

R與

S

的並關係,交關係,差關係和

R

的補關係.例如:x(R∩S)y

(xRy)∧(xSy);xRy

¬(xRy);x(R-S)y

x(R∩S)y

(xRy)∧¬(xSy)等.這樣一來,從已知關係可以派生出各種新關係.

A上的2元關係

IA={x,x|xA}稱為相等關係.定義域,值域的一些性質①D(R∪S)=D(R)∪D(S);②D(R∩S)

D(R)∩D(S);③R(R∪S)=

R(R)∪R(S);④R(R∩S)

R(R)∩R(S).證①

xD(R∪S)

y(x(R∪S)y)

y(xRy∨xSy)

y(xRy)∨y(xSy)量詞分配

xD(R)∨xD(S)

xD(R)∪D(S)②D(R∩S)D(R)∩D(S).證:

xD(R∩S)

y(x(R∩S)y)

y(xRy∧xSy)

y(xRy)∧y(xSy)量詞分配

xD(R)∧xD(S)

xD(R)∩

D(S)注:D(R∩S)

D(R)∩

D(S)一般不成立.例如,習題3.1#5中的關係R,S,就使上式不成立.關係的幾個重要特性

對於A上的任意關係

R

定義下列特性:R

在

A

中自反

x(xRx);取論述域為AR

在

A

中反自反

x(¬(xRx));R

在

A

中對稱

xy(xRy

yRx);R

在

A

中反對稱

xy(xRy∧yRx

x=y);R

在

A

中傳遞

xyz(xRy∧yRz

xRz)習題3.1的作業佈置#2(d);#3(a),(c);#5;#8(b);#9只做P1,P3;#11

(c).提示:添加最少元素到

R3上使之變成是傳遞關係.習題3.1#7(b)

证明:A上有2|A

A|個2元關係因為AA有多少個子集,便有多少個A上的2元關係,所以,A上的2元關係的個數是:|(AA)|=2|AA|=2|A|·|A|即2的|A|2次方.一般地,A上的m元關係的個數是2的|A|m次方.關係矩陣的概念(重要)

若R為A={a1,,am}到

B={b1,,bn}的一個關係,則

A,B元素排定之後,mn

矩陣MR={rij}稱為

R

的關係矩陣,其中,rij=1,當

aiRbj;rij=0,當

¬(aiRbj).

例1:A={a,b,c,d};B={e,f,g};則R={a,g,d,e}的關係矩陣為:

習題3.1#3(b)求關係矩陣:A={0,1,2,3},R={x,y

|

x2∧y1}

解:R={x,y

|x=0,1,2;y=1,2,3}={0,1,0,2,0,3,1,1,1,2,1,3,2,1,2,2,2,3}.

R的關係矩陣是:空關係與全域關係的關係矩陣

空關係的關係矩陣為全0

矩陣:

M

=0.

全域關係

AB

的關係矩陣為全1矩陣,記為

J.

相等關係IA的關係矩陣為單位矩陣:MIA=E.基於R與MR互相唯一決定,可用關係矩陣有效地刻畫關係的許多性質

對於有限集A上的任意關係R與SR=SMR=MS;令MR=(rij),MS=(sij)RSMR

MS(即)

ij(rij

sij)ij(rij=1sij=1).R在A中自反

IA

R(MR對角元全為1)R在A中反自反

R∩IA=(MR對角元全為0)

R在A中對稱

MR為對稱矩陣

(MRT=MR)R在A中傳遞

RRRMRMR

MRij(ijrijrji=0)

R在A中反對稱

習題3.1#8(d)R={a,b,b,c,c,a,d,d}只有反對稱性

R為4元集A={a,b,c,d}上關係

R的關係圖R的關係矩陣利用關係矩陣立即得出R只有反對稱關係.dcab習題3.1#10:整數集I上五個二元關係=,,,II,的有關特性

自反反自反對稱反對稱傳遞.

=

II

本次作業存在的一些問題習題2.1#13:確定下列命題的真與假(a)

為真,因為為任何集的子集(b)

為假,因為

沒有元素(c)

{}為真,因

為任何集A的子集

x(xxA)(d){}為真(e){a,b}{a,b,{{a,b}}}為真(f){a,b}{a,b,{{a,b}}}為假§2.2#6(b):若

CA

且

CB,則

C

A∩B證:(CA)∧(CB)x(xC

xA)∧x(xC

xB))x((xC

xA)∧(xC

xB))x(xC

xA∧B)

C

A∧B注:此結論的意義是:A∩B是同時被A和B包含的最大集合.習題§2.2#18:求已知集合的冪集(c)設A={a},求A和(A)的冪集合解:(A)={,{a}};((A))={,{},{{a}},{,{a}}.注:有人寫了三個,忘記了2元集的冪集基數等於

22=4.二已知關係RAB和SBC的合成關係記為RS

RS={a,c|aA∧cC∧b(bB∧a,bR∧b,cS}

RS是從A到C的關係,換句話說,RS可視為關係R和S的一種運算---‘合成乘積’.

R(R)∩D(S)=

RS=;

特別

R=R

=

.

例1:若論述域為全體男人,

xRyx是y的兄弟;xSyx是y的父親,則aRSca是c的叔伯;

aSSca是c的祖父;aSRca是c的父親.

例1(c)A={1,2,3,4,5}

R={1,2,3,42,2}S={4,2,2,5,3,1,1,3}RS={1,5,3,22,5}SR={4,2,3,2,1,4}

(RS)R={3,2}

RSSR注:

即使

A=B=C

時,合成乘積一般也不是可交換的.對A到B任意關係R有IAR=RIB=

Ra,bIARaA∧bB∧c(cA∧a,cIA∧c,bR)aA∧bB∧a,bR(因a=c)a,bR

IAR=R同理可證:RIB=Ra,bRIBaA∧bB∧c(cB∧a,cR∧c,bIB)a,bR成立合成在並上的分配律:

R1(

R2∪R3)=(R1R2)∪(

R1R3)a,cR1(R2∪R3)b(a,bR1∧b,c(R2∪R3))

b(a,bR1∧(b,cR2∨b,cR3))

b((a,bR1∧b,cR2)

∨(a,bR1∧b,cR3))分配律

a,cR1R2∨a,cR1R3a,cR1R2∪R1R3成立合成在交上的分配形式:

R1(

R2∩R3)

(R1R2)∩(

R1R3)a,cR1(R2∩R3)b(a,bR1∧b,c(R2∩R3)b(a,bR1∧(b,cR2∧b,cR3))

b((a,bR1∧b,cR2)

∧(a,bR1∧b,cR3))等冪律等

b(a,bR1∧b,cR2)∧b(a,bR1∧b,cR3)a,cR1R2∧a,cR1R3a,cR1R2∩R1R3成立合成運算的結合律:

(R1R2)R3=R1(R2R3)a,d(R1R2)R3c(a,cR1R2∧c,dR3)c(b(a,bR1∧b,cR2)∧c,dR3)cb(a,bR1∧b,cR2∧c,dR3)

擴充

bc(a,bR1∧b,cR2∧c,dR3)

參看p.43,(vii)⑤ba,bR1∧c(b,cR2)∧c,dR3))

b(a,bR1∧(b,dR2R3))a,dR1(R2R3)n元集A上二元關係R

的k次冪:Rk=RRR

約定:

R0=IA

R1=R=R0R1=R1R0;

當n3,由結合律得:Rn=Rn-iRi,i=0,1,2,…,n;RkRj=RjRk=Rk+j;(Rk)j=Rkj,k,j=0,1,2,…

看p.99的例2.A上二元關係k次冪的圖論意義

先看R2的關係圖與R的關係圖之間的聯繫a,cR2,的充要條件是:存在b使

a,bR和b,cR等價於,在R的圖形上有從a到c的長度為2的路徑.

一般地,對任意正整數k2,a,cRk,的充要條件是:在R的圖形上有從a到c的長度為k的路徑.習題3.2#6

(改了一點)acbdefgabgacdefgR1={a,b,a,c,c,d,c,e,d,f,d,g}R2={a,d,a,e,c,f,c,g}R3={a,f,a,g}Rk=,k=4,5,….bR2IA=R0RcfgbaeR3dn元集A上二元關係R冪的迴圈性質

對A上任一關係都存在不大於2的n2次方的ij,使得Ri=Rj;定理3.2-4雀巢原理

若存在最小整數j:0i<j使Ri=Rj(對例2,i=2,j=4),記論述域為自然數集N,d=j-i,則①k(Ri+k=Rj+k)②km(Ri+md+k=Ri+k)(Ri+k=Rj+k=Ri+(j-i)+k=Ri+d+k

再用一次Ri+k=Ri+d+k=Ri+d+d+k=Ri+2d+k等等)③令S={R0,R1,…,Rj-1}(可證jn+1,見定理3.3-8),則k(kNRkS)習題3.2的作業佈置#1;#9(b);#10.習題3.2#9(a)R1,R2,R3為A上二元關係,且R1

R2.試證:R1R3

R2R3.證:若R1R3為空集,則R1R3=R2R3;否則,a,cR1R3

b(a,bR1∧b,cR3)b(a,bR2∧b,cR3)∵R1R2

a,cR2R3ac(a,cR1R3

a,cR2R3)二元集{T,F}

{1,0}上的布爾運算①T∨F

F∨T

T∨T

T,F∨F

F;1∨0=0∨1=1∨1=1,0∨0=0②T∧F

F∧T

F∧F

F,T∧T

T;1∧0=0∧1=0∧0=0,1∧1=1③¬T

F,¬F

T;¬1=0,¬0=1④配合∨,∧的其他性質(結合律分配律等)可計算更複雜的式子例如:(1∧0)∨(1∧1)∨(0∧0)=0∨1∨0=1.注{0,1}關於上述兩個運算構成二元數域.(0,1)-矩陣(域{0,1}上)的布爾運算對於

mn(0,1)-矩陣

MR=(rij),MS=(sij)定義下列運算:

¬MR=(¬rij);MR∨MS=(rij

sij);MR∧MS=(rij

sij);當

m=n

時定義:MRMS=(∨1kn(rik

skj))例:對全0矩陣0,全1矩陣J有0∧M=M∧0=0;J∨M=J∨J=J;零律

0∨M=M;J∧M=M.

同一律

用關係矩陣的運算研究關係的運算

令

MR

=(rij),MS=(sij)表示有限集

A

到

B

的兩個關係

R,S

的矩陣,則

MR=¬MR=(¬rij);MR∪S=MR∨MS=(rijsij);MR∩S=MR∧MS=(rijsij);MRS=MR∧MS

=(rij

¬sij).

當

A=B(R,S為A上關係)時MRS

=

MRMS

=(∨1kn(rikskj))借助關係矩陣導出的一些結論

R為A上傳遞關係

RRR

MR2MR證:R為A上傳遞關係

aRbbRcaRc

a,cRRa,cR

RRR

關係的合成運算滿足結合律(定理3.2.2)設

R(ST)有意義(則(RS)T有意義)並用

MX記關係X的矩陣,則有

MR(ST)=MRMST=MR(MSMT);M(RS)T=MRSMT=(MRMS)MT但由高等代數課知:二元數域{0,1}上的矩陣乘法滿足結合律:

MR(MSMT)=(MRMS)MT故MR(ST)=M(RS)T由此得證R(ST)=(RS)T3.2習題#3

證明:若R是有限集A上空關係或全域關係,則R2=R.若

R

為空關係,則MR=0;MRR=MRMR=00=0,

從而

R2也為空關係,得證R2=R.若

R

為全域關係,則

MR=J;MRR=JJ=J,從而R2

也為全域關係,得證

R2=R.習題3.2#9(a)

R1,R2,R3為A上二元關係,且R1

R2.試證:R1R3

R2R3.解1:若R1R3為空集,則

R1R3=R2R3;否則,有

a,cR1R3

b(a,bR1∧b,cR3)b(a,bR2∧b,cR3)∵R1R2

a,bR2R3解2(矩陣方法證):令M1,M2,M3,M13,M23分別表示R1,R2,R3,R1R3,R2R3的矩陣,則M1M2蘊涵M13=M1M3M2M3=M23

給出R1R3R2R3從A到B的二元關係R的逆關係R~={a,b|b,aR}

a,bR(即aRb)

b,aR~(即bR~a)

~

是關係的一元運算

例

~=

;~=

;~=

;(AB)~=

BA

MR~=MRT;

即

S=R~

MS=

MRT

R

在

A

上對稱

R~=

R

MRT=

MR(對稱矩陣)特別,A

上相等關係,全域關係,空關係的逆關係都是自身(∵矩陣

E,0,J

都是對稱矩陣).二元關係R的逆關係R~的若干性質①(R~)~=R;(∵(MRT)T=MR)②(RS)~=S~R~;(∵(MRMS)T=MSTMRT)③對於A到B的任意關係R,S都有(R∪S)~=R~∪S~;把上式中的集合運算∪代替為∩,-,’,等運算仍然成立(定理3.3-2).(∵(MR∪S)T

=(MR∨MS)T=MRT∨MST=MR~∪S~)④R

SR~

S~(∵MRMS

MRTMST)A上二元關係R的閉包運算定義3.3-2:具有自反(對稱,傳遞)性的包含

R

的最小關係稱為

R

的自反(對稱,傳遞)閉包,記為

r(R)(s(R),t(R)).具體來說,自反關係

R

的自反閉包

r(R)是這樣的自反關係:r(R)

R,且對任意自反關係

W

R,必有

W

r(R).對稱閉包,傳遞閉包

s(R),t(R)可類似地加以說明.A

上二元關係

R

的閉包舉例設

A={1,2,3},R={2,2,2,3,3,1}.為求

r(R),只要在

R

上添加使之成為自反關係的最少新元素即可r(R)={2,2,2,3,3,1,1,1,3,3}為求

s(R),只要在

R

上添加使之成為對稱關係的最少新元素即可

s(R)={2,2,2,3,3,1,3,2,1,3}為求

t(R),只要在

R上添加使之成為傳遞關係的最少新元素即可

t(R)={2,2,2,3,3,1,2,1}A上二元關係R閉包運算的性質

R是自反的,當且僅當r(R)=

R;

R是對稱的,當且僅當s(R)=

R;

R是傳遞的,當且僅當t(R)=

R.證:充分性顯然.

必要性:若

R是自反(對稱,傳遞)的,則

R也是包含

R的最小自反(對稱,傳遞)關係,所以r(R)(s(R),t(R))=

R.A上二元關係R閉包的公式①r(R)=

R∪IA(Mr(R)=MR∨E)

(∵R在A上自反IAA∴包含A的最小自反關係是R∪IA)②s(R)=

R∪R~(包含

R的對稱關係是包含

R∪R~的對稱關係,並且

R∪R~是對稱關係((R∪R~)~=R~∪(R~)~=R~∪R).③t(R)=∪1i<Ri可證:t(R)=∪1inRi,n=|A|(定理3.3-8)證明:t(R)=∪1i<Ri

W

①先證W

t(R).由t(R)的定義知R1t(R).今證:i(i>1∧Rit(R)

Ri+1t(R)).事實上,a,bRi+1

c(a,cRi∧c,bR)

c(a,c,c,bt(R))

a,bt(R)(t(R)是傳遞的)由歸納法得i(iI+Rit(R),即

Wt(R)②次證

t(R)

W.由t(R)的定義只須證

W為傳遞關係即可.設a,b,b,cW,則存在s,tI+使a,bRs∧b,cRt,由此得a,c

RsRt

=

Rs+t

W,得證t(R)=

W.整數集I上一些關係的閉包①r(<)

;(∵r(<)

<∪II

<∪=

)s(<)

;(∵s(<)

<∪>

)t(<)

<;(∵

<

是傳遞的)②r(

)

II(全域關係);(∵r(

)

∪II

∪=

II)S(

)

;(∵

是對稱的)T(

)II

(∵ijk(ik∧kj),即II

(

)(

)

又

(

)(

)

II)③r()

∪II

II;

s()

∪~∪;t()∪1i<

i

.④令

R

為後繼關係:

xRy

y

=

x+1,則

t(R)

<.證:a,ct(R)k(k1∧a,cRk)c=a+k

a<c§3.3的作業佈置#4;#6除原題要求外,還要另求

R+和

R*;#7(b).習題3.3#7(c)

已知A={1,2,3},R={1,2,2,3,3,1},求r(R),s(R),t(R)解:r(R)=R∪IA

={1,2,2,3,3,1,1,1,2,2,3,3},s(R)=R∪R~={1,2,2,3,3,1,1,3,2,1,3,2},t(R)=R∪R2∪IA

(∵

R3=IA,R4=R,R5=R2,…)

={1,2,2,3,3,1,1,3,2,1,3,2,1,1,2,2,3,3}=

AA全域關係閉包還可進一步作閉包運算

r(r(R))=r(R);(∵r(R)是自反的)

r(s(R))=R∪R~∪IA=s(r(R));

r(t(R))=t(R)∪IA=t(r(R))=∪0inRi

通常用

R+,R*

分別表示傳遞閉包

t(R),自反傳遞閉包

r(t(R)),此二關係在電腦科學中十分有用.習題3.3#8

(注:MR+=Mt(R),MR*=E∪Mt(R))MR=Mr(R)=Ms(R)=MR2

==MR3=MR4=…Mt(R)=10100011101010101010011110101011101100111111111010101010

101010101010101110101010偏序集與偏序關係的概念

①A上關係R稱為偏序關係,如果R是自反的,反對稱的,和傳遞的;此時,A,R稱為偏序集合,並常把A,R記為A,

;把aRb記為a

b.②A,R是偏序集

A,R~是偏序集.

稱A,R~為A,R的對偶偏序集,常把A,

的對偶偏序集記為A,

.偏序集與偏序關係的例子

①對實數集

R

的任意子集

A

與實數上的小於等於關係:,A,

是偏序集;其對偶偏序集為

A,

;xx;

xy∧yx

x=y;

xy∧yz

xz②對任意集A,(A),

是偏序集;其對偶偏序集為

(A),

;x

x;

x

y∧y

x

x=y;

x

y∧y

z

x

z③令AI+,對任意m,nA,m|n表示m整除n的關係(即m為n的整數倍:有正整數k滿足n=km),A,|

是偏序集.證:取論述域為I+

自反顯然m(mAm|m);

再由

mn(m|nmn)推出

反對稱

mn(m|n∧n|mm=n);

傳遞

mnk(m|n∧n|kuv(k=un∧n=vm)mnk(m|n∧n|km|k)表示有限偏序集的Hasse圖Hasse圖用下列最簡潔的方式表示偏序集:①

因偏序集的每一元與自己有關系蘊涵每點都有自回路,故自回路可以不明顯地畫出.②

因偏序集有傳遞性,即

aRb∧bRc

aRc,故只要表示出

aRb

和

bRc之後就可以不必再表示

aRc.③

約定用以

a,b為端點的直線代替箭頭表示

aRb,只要把點

a

放在點

b

的下方即可.Hasse圖舉例

①({a,b}),

②{2,4,6,8,12},|

{a,b}{a}{b}128642偏序集

A,

的子集B的極,最大(小)元y是B的最大元

yB∧x(xBxy)y是B的極大元

yB∧(x(xB∧xy∧yx)y是B的最小元

yB∧(xByx)y是B的極小元

yB∧(x(xB∧xy∧xy)例:A

=

{2,4,6,8,12},|

A的極大元是:12,8;A無最大元;A上最小元是:2若B={12,6,4},則B的最大元是:12;B無最小元.注:最大(小)元是極大(小)元;極大(小)元可存在可不存在,且不一定唯一.128642偏序集子集B的極,最大(小)元性質①最大,最小元至多有一個.證:令

y,y為

B

的最大(小)元,則有

yy和yy,從而由反對稱性推得

y=y.②易見:當

B

有最大(最小)元

y

時,此最大(小)元也是

B

唯一的極大(極小)元.(∵最大(小)元

y

必為極大(小)元,若還有極大(小)元

y

y,則

y()y與y為極大(小)元矛盾.)偏序集

A,

的子集B的上,下界

aA是B的一個上界,如果

b(bBba)

aA是B的一個下界,如果

b(bBab)

aA是B的最小上界,記為

lub(B),如果

B每個上界

a

都滿足

aa

aA是B的最大下界,記為

glb(B),如果

B每個下界

a都滿足

aa注:①由A反對稱性立即推出最小上界,最大下界的唯一性.②易見:

B的最小上(最大下)界

y

為

B

的最大(小)元當且僅當yB

例:

R,

的子集

B1

={x|0<x<1};B2

={x|0x<+}

①0為

B1的最大下界;1為

B1的最小上界;

B1有無窮多上界(x(x1x為

B1

的上界));B1

有無窮多下界(x(x0x為

B1的下界));但0(1)不屬於

B1,故不是

B1的最小(大)元.②0為

B2

的最小元,故也是最大下界;

B2有無窮多下界(x(x0x為

B1的下界));但

B2

沒有上界,更沒有最小上界.線序集與良序集

偏序集

A,

稱為線序集,如果它的任意二元素都可比較:ab(a,bAab∨ba)

線序集

A,

稱為良序集,如果它的任意子集都有最小元:

B(BAB有最小元)線序集與良序集舉例

R,

(

是實數的大小關係)是線序集,因為任二實數均可比較.

({a,b}),

不是線序集,因為{a}與{b}不可比較.

R,

不是良序集,因開區間(0,1)沒有最小元.

N,

是良序集(若N

的子集

B

無最小元,則

glb(B)=

dB,故d+1B,並且x(xBxd+1),得證d+1=glb(b),從而d+1是B最小元,矛盾.)線序集性質

偏序集的任何子集也是偏序集,即

A,

為偏序時有,

B(BAB,

為偏序).(因偏序公理在更大範圍A內已成立)

線序集的任何子集也是線序集,即

A,

為線序時,

B(BAB,

為線序).(A任二元素均可比較蘊涵B任二元素均可比較)

因偏序是傳遞的,故線序集

A

滿足三分律:xy(x,yAx<y∨x=y∨x>y)當xy時,x<y∧x>y

x=y§3.4的作業佈置#1;#5(d),(e),(f);#6.習題3.4#5abac(a)是偏序,但不是線序(a,b不可比較),更不是良序(b)是偏序,線序,良序(c)不是偏序(非自反),更不是線序,良序bab集合A上的二元關係R稱為是等價關係,如果R是自反的,對稱的和傳遞的

例①任何集合上的相等關係是等價關係.與相等類似的人際間的等價關係還可以舉出不少.例如對於安大數學學院全體學生的集合A來說,下列關係都是等價關係:同專業關係;同年級關係,同寢室關係;同年齡關係;同鄉關係等等.②

空集合上的任何二元關係是等價關係;任何集合上的全域關係是等價關係.例③對已知正整數k和a,bI,若

k|(a-b),則稱a與b模k同餘,記為ab(mod

k).在I的任一子集A上,模k同餘關係是等價關係.證;A=時結論顯然成立.否則a(aAk|(a-a)},即a(aAaa(mod

k));ab(mod

k)

ba(m