離散數(shù)學(集合論)

集合論離散數(shù)學1集合論十九世紀下半葉，康托爾創(chuàng)立了著名的集合論，在集合論剛產(chǎn)生時，曾遭到許多人的猛烈攻擊。但不久這一開創(chuàng)性成果就為廣大數(shù)學家所接受了，并且獲得廣泛而高度的贊譽。數(shù)學家們發(fā)現(xiàn)，從自然數(shù)與康托爾集合論出發(fā)可建立起整個數(shù)學大廈。因而集合論成為現(xiàn)代數(shù)學的基石。2當時德國數(shù)學家康托爾試圖回答一些涉及無窮量的數(shù)學難題，例如“整數(shù)究竟有多少？”“一個圓周上有多少點？”0—1之間的數(shù)比1寸長線段上的點還多嗎？”等等。而“整數(shù)”、“圓周上的點”、“0—1之間的數(shù)”等都是集合，因此對這些問題的研究就產(chǎn)生了集合論。31903年，一個震驚數(shù)學界的消息傳出：集合論是有漏洞的！這就是英國數(shù)學家羅素提出的著名的羅素悖論?？梢哉f，這一悖論就象在平靜的數(shù)學水面上投下了一塊巨石，而它所引起的巨大反響導致了第三次數(shù)學危機。4羅素悖論把所有集合分為2類，第一類中的集合以其自身為元素，第二類中的集合不以自身為元素，假令第一類集合所組成的集合為P，第二類所組成的集合為Q，于是有：P={A∣A∈A}Q={A∣A?A}問，Q∈P還是Q∈Q？若Q∈P，那么根據(jù)第一類集合的定義，必有Q∈Q，但是Q中任何集合都有A?A的性質(zhì)，因為Q∈Q，所以Q￠Q，引出矛盾。若Q∈Q，根據(jù)第一類集合的定義，必有Q∈P，而顯然P∩Q=?，所以Q?Q，還是矛盾。5理發(fā)師悖論

在某個城市中有一位理發(fā)師，他的廣告詞是這樣寫的：“本人的理發(fā)技藝十分高超，譽滿全城。我將為本城所有不給自己刮臉的人刮臉，我也只給這些人刮臉。我對各位表示熱誠歡迎！”來找他刮臉的人絡繹不絕，自然都是那些不給自己刮臉的人?？墒牵幸惶?，這位理發(fā)師從鏡子里看見自己的胡子長了，他本能地抓起了剃刀，你們看他能不能給他自己刮臉呢？如果他不給自己刮臉，他就屬于“不給自己刮臉的人”，他就要給自己刮臉，而如果他給自己刮臉呢？他又屬于“給自己刮臉的人”，他就不該給自己刮臉。6它對數(shù)學家說：“解決我，不然我將吞掉你的體系！”7羅素悖論使得數(shù)學基礎問題第一次以最迫切的需要的姿態(tài)擺到數(shù)學家面前，導致了數(shù)學家對數(shù)學基礎的研究。而這方面的進一步發(fā)展又極其深刻地影響了整個數(shù)學。如圍繞著數(shù)學基礎之爭，形成了現(xiàn)代數(shù)學史上著名的三大數(shù)學流派。從1900年到30年這三十年間，許多數(shù)學家就數(shù)學的哲學基礎這一問題展開了討論，并形成了不同的數(shù)學基礎學派，主要有邏輯主義、形式主義和直覺主義三大學派8集合論部分第3章集合的基本概念和運算第4章二元關系和函數(shù)9第3章集合的基本概念和運算3.1集合的基本概念3.2集合的基本運算3.3集合中元素的計數(shù)103.1集合的基本概念

集合的定義與表示集合與元素集合之間的關系冪集11集合的基本概念1.集合：若干個（有限或無限）固定事物的全體元素表示方法：列舉法A={a,b,c,d}

描述法B={x|x∈Z,3<x≤6}…12集合與元素的關系Ａ＝｛a，｛b，c｝，d

｝aA｛b,c｝

AbA131.子集合：2.真子集：3.集合相等：集合之間的關系A

B

x(x

A

x

B)包含A

B

A

B

A

B真包含14n元集，m元子集含有n個元素的集合簡稱n元集,它的含有m個(m≤n)元素的子集稱為它的m元子集.例題3.2:A={a,b,c},求A的全部子集.0元子集,即空集,只有1個

.1元子集,即單元集,個{a},,{c}2元子集個

{a,b},{a,c}{b,c}3元子集1個{a,b,c}n元集的集合個數(shù)為:

15冪集定義P(A)={B|B

A}

設A={a,b,c},則P(A)={,{a},,{c},{a,b},{a,c},{b,c}{a,b,c}}計數(shù):如果|A|=n，則|P(A)|=2n

16空集和全集全集：如果所涉及的集合都是某個集合的子集,則稱這個集合為全集,記作E.空集：不含任何元素的集合,記為17第3章集合的基本概念和運算3.1集合的基本概念3.2集合的基本運算3.3集合中元素的計數(shù)183.2集合的基本運算集合基本運算的定義

文氏圖（JohnVenn）集合運算的算律恒等式的證明19集合基本運算的定義并

A

B={x|x

A

x

B

}交

A

B={x|x

A

x

B}相對補

A

B={x|x

A

x

B}對稱差

A

B=(A

B)

(B

A)=(A

B)(A

B)

絕對補

A=E

A

20文氏圖表示21例題A={1,2,3},B={1,4},C={3}AB={1,2,3,4}=BAAB={1}=BAA-B={2,3}B-A={4}C-A=

AB={2,3}{4}={2,3,4}對稱差的等價定義為AB=(AB)-(AB)當兩個集合的交集是空集時,稱他們是不交的.22關于運算的說明運算順序：和冪集優(yōu)先，其他由括號確定并和交運算可以推廣到有窮個集合上，即

A1

A2

…An={x|x

A1

x

A2

…

x

An}

A1

A2

…An={x|x

A1

x

A2

…

x

An}23

交換A

B=B

AA

B=B

AA

B=B

A結(jié)合(A

B)C=A

(B

C)(A

B)C=A

(B

C)(A

B)C=A

(B

C)冪等A

A=AA

A=A集合運算的算律吸收律的前提：

、可交換24

與

與

分配A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)吸收A

(A

B)=AA

(A

B)=A25集合運算的算律（續(xù)）

D.M律A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)

(B

C)=B

C

(B

C)=B

C雙重否定

A=A26

E補元律A

A=A

A=E零律A

=

A

E=E同一律A

=AA

E=A否定

=E

E=27第3章集合的基本概念和運算3.1集合的基本概念3.2集合的基本運算3.3集合中元素的計數(shù)28集合的基數(shù)與有窮集合包含排斥原理有窮集的計數(shù)3.3集合中元素的計數(shù)29集合A的基數(shù)：集合A中的元素數(shù)，記作cardA注：||=0;有窮集

A：cardA=|A|=n，n為自然數(shù).有窮集的實例：

A={a,b,c},cardA=|A|=3；

B={x|x2+1=0,x

R},cardB=|B|=0無窮集的實例：

N,Z,Q,R,C等集合的基數(shù)與有窮集合30

解：

2的倍數(shù)是：2，4，6，8，10，12，14，16，18，20。共10個；例1

求不超過20的正整數(shù)中2或3的倍數(shù)的個數(shù)。因為6，12，18在兩類中重復計數(shù)，應減去。3的倍數(shù)是：3，6，9，12，15，18。共6個；故答案是：10+6-3=13容斥原理31

對于求兩個有限集合A和B的并的元素數(shù)目，我們有即具有性質(zhì)A或B的元素的個數(shù)等于具有性質(zhì)A的元素個數(shù)和具有性質(zhì)B的元素個數(shù)減去同時具有性質(zhì)A和B的元素個數(shù)。(1)定理1容斥原理32ABA∩BU3.1

容斥原理33AB

CA∩BA∩B∩CB∩CA∩CU3.1

容斥原理34定理23.1

容斥原理35同理可推出：利用數(shù)學歸納法可得一般的定理：3.1

容斥原理36(4)定理3設A1,A2,…,An是有限集合，則3.1

容斥原理37(5)容斥原理指的就是（4）和（5）式。用來計算有限集合的并或交的元素個數(shù)。3.1

容斥原理38包含排斥原理定理設S為有窮集，P1,P2,…,Pm

是m種性質(zhì)，Ai是S

中具有性質(zhì)Pi

的元素構成的子集，i=1,2,…,m.則S

中不具有性質(zhì)P1,P2,…,Pm的元素數(shù)為39S中至少具有一條性質(zhì)的元素數(shù)為推論40解：S={x

|xZ,1x

1000},

如下定義S

的3個子集A,B,C：

A={x

|x

S,5|x

}，

B={x

|x

S,6|x

}，

C={x

|x

S,8|x

}例1求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個？應用41對上述子集計數(shù)：

|S|=1000,|A|=

1000/5

=200,|B|=1000/6=133，

|C|=1000/8

=125,

|A

B|=1000/30

=33,|B

C|=1000/40

=25,|B

C|=1000/24

=41,|A

B

C|=1000/120

=8,代入公式

N=1000

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

8=600例1（續(xù)）42文氏圖法

求1到1000之間（包含1和1000在內(nèi)）既不能被5和6整除，也不能被8整除的數(shù)有多少個？43例2

24名科技人員，每人至少會1門外語.英語：13；日語：5；德語：10；法語：9英日：2;英德：4；英法：4；法德：4會日語的不會法語、德語求：只會1種語言人數(shù)，會3種語言人數(shù)x+2(4-x)+y1+2=13x+2(4-x)+y2=10x+2(4-x)+y3=9x+3(4-x)+y1+y2+y3=19x=1,y1=4,y2=3,y3=2

44二元關系和函數(shù)離散數(shù)學45第4章二元關系與函數(shù)4.1集合的笛卡兒積與二元關系4.2關系的運算4.3關系的性質(zhì)4.4關系的閉包4.5等價關系和偏序關系4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復合和反函數(shù)464.1集合的笛卡兒積和二元關系

有序?qū)Φ芽▋悍e及其性質(zhì)二元關系的定義二元關系的表示47有序?qū)Χx

由兩個客體x和y，按照一定的順序組成的二元組稱為有序?qū)?，記?lt;x,y>實例：點的直角坐標(3,

4)有序?qū)π再|(zhì)有序性<x,y>

<y,x>（當x

y時）

<x,y>與<u,v>相等的充分必要條件是

<x,y>=<u,v>

x=u

y=v例1<2,x+5>=<3y

4,y>，求x,y.解3y

4=2,x+5=y

y=2,x=3

48有序n元組定義一個有序n(n3)元組<x1,x2,…,xn>是一個有序?qū)?，其中第一個元素是一個有序n-1元組，即

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

當n=1時,<x>形式上可以看成有序1元組.實例

n維向量是有序

n元組.49笛卡兒積定義設A,B為集合，A與B的笛卡兒積記作A

B，即A

B={<x,y>|x

A

y

B

}例2A={1,2,3},B={a,b,c}

A

B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}

B

A={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}50笛卡兒積的性質(zhì)不適合交換律

A

B

B

A(A

B,A

,B

)不適合結(jié)合律

(A

B)

C

A

(B

C)(A

,B

)對于并或交運算滿足分配律

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)若A或B中有一個為空集，則A

B就是空集.

A

=

B=

若|A|=m,|B|=n,則|A

B|=mn

51性質(zhì)的證明證明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).52例題解(1)任取<x,y><x,y>

A

C

x

A

y

C

x

B

y

D

<x,y>

B

D

例3(1)證明A=B

C=D

A

C=B

D

(2)A

C=B

D是否推出A=B

C=D?為什么？(2)不一定.反例如下：

A={1}，B={2},C=D=

,則A

C=B

D但是A

B.53二元關系的定義定義如果一個集合滿足以下條件之一：（1）集合非空,且它的元素都是有序?qū)Γ?）集合是空集則稱該集合為一個二元關系,簡稱為關系，記作R.如<x,y>∈R,可記作xRy；如果<x,y>

R,則記作xy實例：R={<1,2>,<a,b>},S={<1,2>,a,b}.R是二元關系,當a,b不是有序?qū)r，S不是二元關系根據(jù)上面的記法，可以寫1R2,aRb,ac等.

54從A到B的關系與A上的關系定義設A,B為集合,A×B的任何子集所定義的二元關系叫做從A到B的二元關系,當A=B時則叫做A上的二元關系.例4A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=

,R4={<0,1>}.那么R1,R2,R3,R4是從A到B的二元關系,R3和R4同時也是A上的二元關系.計數(shù)|A|=n,|A×A|=n2,A×A的子集有個.所以A上有個不同的二元關系.55A上重要關系的實例設A為任意集合，

是A上的關系，稱為空關系EA,IA分別稱為全域關系與恒等關系，定義如下：

EA={<x,y>|x∈A∧y∈A}=A×A

IA={<x,x>|x∈A}如,A={1,2},則

EA={<1,1>,<1,2>,<2,1>,<2,2>}

IA={<1,1>,<2,2>}

56A上重要關系的實例（續(xù)）小于等于關系LA,整除關系DA,包含關系R

定義：

LA={<x,y>|x,y∈A∧x≤y},A

R，R為實數(shù)集合

DB={<x,y>|x,y∈B∧x整除y},B

Z*,Z*為非0整數(shù)集

R

={<x,y>|x,y∈A∧x

y},A是集合族.57實例例如A={1,2,3},B={a,b},則

LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

A=P(B)={

,{a},,{a,b}},則A上的包含關系是R

={<

,

>,<

,{a}>,<

,>,<

,{a,b}>,<{a},{a}>,<{a},{a,b}>,<,>,<,{a,b}>,<{a,b},{a,b}>}

58關系的表示表示方式：關系的集合表達式、關系矩陣、關系圖關系矩陣：若A={a1,a2,…,am}，B={b1,b2,…,bn}，R是從A到B的關系，R的關系矩陣是布爾矩陣MR=[rij]m

n,其中

rij

=1

<ai,bj>

R.關系圖：若A={x1,x2,…,xm}，R是從A上的關系，R的關系圖是GR=<A,R>,其中A為結(jié)點集，R為邊集.如果<xi,xj>屬于關系R，在圖中就有一條從xi

到xj

的有向邊.注意：關系圖適于表示A上的關系

59實例A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的關系矩陣MR和關系圖GR如下：60第4章二元關系與函數(shù)4.1集合的笛卡兒積與二元關系4.2關系的運算4.3關系的性質(zhì)4.4關系的閉包4.5等價關系和偏序關系4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復合和反函數(shù)61基本運算定義定義域、值域、域逆、合成、限制、像基本運算的性質(zhì)冪運算定義求法性質(zhì)4.2關系的運算62關系的基本運算定義定義域、值域

和域

domR={x|

y(<x,y>

R)}

ranR={y|

x(<x,y>

R)}

fldR=domR

ranR

例1R={<1,2>,<1,3>,<2,4>,<4,3>},則

domR={1,2,4}

ranR={2,3,4}

fldR={1,2,3,4}63關系的基本運算定義（續(xù)）逆與合成

R

1={<y,x>|<x,y>

R}

R°S={<x,y>|

z(<x,z>

S

<z,y>

R)}例2R={<1,2>,<2,3>,<1,4>,<2,2>}

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}

R

1={<2,1>,<3,2>,<4,1>,<2,2>}

R°S

={<1,2>,<1,4>,<3,2>,<3,3>}S°R={<1,3>,<2,2>,<2,3>}64限制與像定義

F在A上的限制

F?A={<x,y>|xFy

x

A}A在F下的像

F[A]=ran(F?A)實例R={<1,2>,<2,3>,<1,4>,<2,2>}

R?{1}={<1,2>,<1,4>}

R[{1}]={2,4}R[{1,2}]={2,3,4}注意：F?A

F,F[A]ranF

65關系基本運算的性質(zhì)定理1設F是任意的關系,則(1)(F

1)

1=F(2)domF

1=ranF,ranF

1=domF66定理2設F,G,H是任意的關系,則

(1)(F°G)°H=F°(G°H)(2)(F°G)

1=G

1°F

1關系基本運算的性質(zhì)（續(xù)）

67A上關系的冪運算設R為A上的關系,n為自然數(shù),則R的n次冪定義為：

(1)R0={<x,x>|x∈A

}=IA

(2)Rn+1=Rn°R

68冪的求法對于集合表示的關系R，計算Rn

就是n個R右復合.矩陣表示就是n個矩陣相乘,其中相加采用邏輯加.例3設A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次冪,分別用矩陣和關系圖表示.解R與R2的關系矩陣分別為69同理，R0=IA,R3和R4的矩陣分別是：因此M4=M2,即R4=R2.因此可以得到

R2=R4=R6=…,R3=R5=R7=…

冪的求法（續(xù)）70R0,R1,R2,R3,…的關系圖如下圖所示冪的求法（續(xù)）71定理4設R是A上的關系,m,n∈N,則

(1)Rm°Rn=Rm+n

(2)(Rm)n=Rmn

冪運算的性質(zhì)（續(xù)）72內(nèi)容提綱集合的笛卡爾積與二元關系關系的運算關系的性質(zhì)關系的閉包等價關系和偏序關系函數(shù)的定義和性質(zhì)函數(shù)的復合和反函數(shù)734.3關系的性質(zhì)自反性反自反性對稱性反對稱性傳遞性74定義自反性反自反性對稱性反對稱性傳遞性定義xA,有<x,x>RxA,有<x,x>R若<x,y>R則<y,x>R若<x,y>R,且xy,則<y,x>R若<x,y>R且<y,z>R則<x,z>R關系矩陣特點主對角線的元素全為1主對角線的元素全為0矩陣為對稱矩陣如果rij=1,且xy則rji=0關系圖特點圖中每個節(jié)點都有環(huán)圖中每個節(jié)點都沒有環(huán)如果兩個頂點之間有邊,一定是一對方向相反的邊.如果兩個頂點之間有邊,一定是一條有向邊.如果xi到xj有邊，xj到xk有邊，則xi到xk一定有邊．75關系性質(zhì)判別

自反反自反對稱反對稱傳遞表達式IA

RR∩IA=

R=R

1

R∩R

1

IA

R

R

R76實例例1A={1,2,3},R1,R2,R3是A上的關系,其中

R1＝{<1,1>,<2,2>}R2＝{<1,1>,<2,2>,<3,3>,<1,2>}R3＝{<1,3>}R1既不是自反也不是反自反的R2自反,R3反自反,77實例例2設A＝{1,2,3},R1,R2,R3和R4都是A上的關系,

其中

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

不對稱、也不反對稱.78實例例3設A＝{1,2,3},R1,R2,R3是A上的關系,其中

R1＝{<1,1>,<2,2>}

R2＝{<1,2>,<2,3>}

R3＝{<1,3>}

R1和R3是A上的傳遞關系

R2不是A上的傳遞關系79實例例4判斷下圖中關系的性質(zhì),并說明理由.(2)反自反，不是自反的；反對稱，不是對稱的；是傳遞的.(1)不自反也不反自反；對稱,不反對稱；不傳遞.(3)自反，不反自反；反對稱，不是對稱；不傳遞.804.4關系的閉包閉包定義閉包的構造方法集合表示矩陣表示圖表示81閉包定義定義

設R是非空集合A上的關系,R的自反（對稱

或傳遞）閉包是A上的關系R

,使得R

滿足以下條件：（1）R

是自反的（對稱的或傳遞的）（2）R

R

（3）對A上任何包含R的自反（對稱或傳遞）關系R

有R

R

.

一般將R的自反閉包記作r(R),對稱閉包記作s(R),傳遞閉包記作t(R).82閉包的構造方法定理1設R為A上的關系,則有

(1)r(R)=R∪R0(2)s(R)=R∪R

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

說明：對于有窮集合A(|A|=n)上的關系,(3)中的并最多不超過Rn.

若R是自反的，則r(R)=R;若R是對稱的，則

s(R)=R;若R是傳遞的，則t(R)=R.83設關系R,r(R),s(R),t(R)的關系矩陣分別為M,Mr,Ms和Mt,則

Mr

=M+EMs=M+M’

Mt=M+M2+M3+…E是和M同階的單位矩陣,M’是M的轉(zhuǎn)置矩陣.注意在上述等式中矩陣的元素相加時使用邏輯加.閉包的構造方法（續(xù)）84閉包的構造方法（續(xù)）設關系R,r(R),s(R),t(R)的關系圖分別記為G,Gr,Gs,Gt

,則Gr,Gs,Gt

的頂點集與G的頂點集相等.除了G的邊以外,以下述方法添加新邊：

考察G的每個頂點,如果沒有環(huán)就加上一個環(huán)，最終得到Gr

.考察G的每條邊,如果有一條xi到xj

的單向邊,i≠j,則在G中加一條xj

到xi的反方向邊，最終得到Gs.考察G的每個頂點xi,找從xi出發(fā)的每一條路徑，如果從xi到路徑中任何結(jié)點xj

沒有邊，就加上這條邊.當檢查完所有的頂點后就得到圖Gt

.85實例例1設A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>},R和r(R),s(R),t(R)的關系圖如下圖所示.

Rr(R)s(R)t(R)864.5等價關系與偏序關系等價關系的定義與實例等價類及其性質(zhì)商集與集合的劃分等價關系與劃分的一一對應偏序關系偏序集與哈斯圖偏序集中的特定元素87一、等價關系的定義與實例定義

設R為非空集合上的關系.如果R是自反的、對稱的和傳遞的,則稱R為A上的等價關系.設R是一個等價關系,若<x,y>∈R,稱x等價于y,記做x～y.

實例

設A={1,2,…,8},如下定義A上的關系R：

R={<x,y>|x,y∈A∧x≡y(mod3)}其中x≡y(mod3)叫做x與y模3相等,即x除以3的余數(shù)與y除以3的余數(shù)相等.88等價關系的驗證驗證模3相等關系R為A上的等價關系,因為

x∈A,有x≡x(mod3)

x,y∈A,若x≡y(mod3),則有y≡x(mod3)

x,y,z∈A,若x≡y(mod3),y≡z(mod3),

則有x≡z(mod3)自反性、對稱性、傳遞性得到驗證89A上模3等價關系的關系圖設A={1,2,…,8},

R={<x,y>|x,y∈A∧x≡y(mod3)}

90二、等價類及性質(zhì)定義設R為非空集合A上的等價關系,

x∈A，令

[x]R

={y|y∈A∧xRy

}稱[x]R

為x關于R的等價類,簡稱為x的等價類,簡記為[x].實例A={1,2,…,8}上模3等價關系的等價類：

[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}91等價類的性質(zhì)

定理1

設R是非空集合A上的等價關系,則

(1)

x∈A,[x]是A的非空子集.

(2)

x,y∈A,如果xRy,則[x]=[y].

(3)

x,y∈A,如果xy,則[x]與[y]不交.

(4)∪{[x]|x∈A}=A，即所有等價類的并集就是A.

92實例A={1,2,…,8}上模3等價關系的等價類：

[1]=[4]=[7]={1,4,7}，

[2]=[5]=[8]={2,5,8}，

[3]=[6]={3,6}

以上3類兩兩不交，

{1,4,7}{2,5,8}{3,6}={1,2,…,8}93三、商集定義

設R為非空集合A上的等價關系,以R的所有等價類作為元素的集合稱為A關于R的商集,記做A/R,

A/R={[x]R

|x∈A

}實例

A={1,2,…,8},A關于模3等價關系R的商集為

A/R={{1,4,7},{2,5,8},{3,6}}

A關于恒等關系和全域關系的商集為：

A/IA

={{1},{2},…,{8}}

A/EA

={{1,2,…,8}}94集合的劃分定義

設A為非空集合,若A的子集族π(π

P(A))

滿足下面條件：

(1)

π(2)

x

y

(x,y∈π∧x≠y→x∩y=

)(3)∪π=A

則稱π是A的一個劃分,稱π中的元素為A的劃分塊.95例題例1設A＝{a,b,c,d},

給定π1,π2,π3,π4,π5,π6如下：

π1={{a,b,c},ceswqcw}，π2={{a,b},{c},i42sqke}

π3={{a},{a,b,c,d}},π4={{a,b},{c}}

π5={

,{a,b},{c,d}},π6={{a,{a}},{b,c,d}}

則π1和π2

是A的劃分,其他都不是A的劃分.96四、等價關系與劃分的一一對應商集A/R就是A的一個劃分

不同的商集對應于不同的劃分

任給A的一個劃分π,如下定義A上的關系R：

R={<x,y>|x,y∈A∧x

與y在π的同一劃分塊中}則R為A上的等價關系,且該等價關系確定的商集就是π.例2給出A＝{1,2,3}上所有的等價關系97等價關系與劃分之間的對應π1,π2和π3分別對應等價關系R1,R2和R3.

R1={<2,3>,<3,2>}∪IA，R2={<1,3>,<3,1>}∪IA

R3={<1,2>,<2,1>}∪IAπ4對應于全域關系

EA，π5對應于恒等關系

IA98五、偏序關系定義非空集合A上的自反、反對稱和傳遞的關系，稱為A上的偏序關系，記作?.設?為偏序關系,如果<x,y>∈?,則記作x?y,讀作x“小于或等于”y.

實例集合A上的恒等關系IA是A上的偏序關系.

小于或等于關系,整除關系和包含關系也是相應集合上的偏序關系.99相關概念x與y可比：設R為非空集合A上的偏序關系,

x,y

A,x與y可比

x?y

∨y?x.

全序關系：

R為非空集合A上的偏序,

x,y

A,x與y都是可比的，則稱R為全序（或線序）實例：數(shù)集上的小于或等于關系是全序關系整除關系不是正整數(shù)集合上的全序關系100覆蓋：設R為非空集合A上的偏序關系,x,y∈A,如果x?y且不存在z

A

使得x?z?y,則稱y覆蓋x.實例：{1,2,4,6}集合上的整除關系,2覆蓋1,4和6覆蓋2.4不覆蓋1.

相關概念（續(xù)）101六、偏序集與哈斯圖定義

集合A和A上的偏序關系?一起叫做偏序集,記作

<A,?>.實例：整數(shù)集和小于等于關系構成偏序集<Z,≤>，冪集P(A)和包含關系構成偏序集<P(A),R

>.哈斯圖：利用偏序的自反、反對稱、傳遞性簡化的關系圖特點：每個結(jié)點沒有環(huán)，兩個連通的結(jié)點之間的序關系通過結(jié)點位置的高低表示，位置低的元素的順序在前，具有覆蓋關系的兩個結(jié)點之間連邊102哈斯圖實例例4<{1,2,3,4,5,6,7,8,9},R整除><P({a,b,c}),R

>103A={a,b,c,d,e,f,g,h}

R={<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,<d,f>,<e,f>,<g,h>}∪IA

哈斯圖實例（續(xù)）例5已知偏序集<A,R>的哈斯圖如右圖所示,試求出集合A和關系R的表達式.

104七、偏序集的特定元素定義設<A,?>為偏序集,B

A,y∈B.(1)若

x(x∈B→y?x)成立,則稱y為B的最小元.(2)若

x(x∈B→x?y)成立,則稱y為B的最大元.(3)若

x(x∈B∧x

?y)成立,則稱y為B的極小元.(4)若

x(x∈B∧y

?x)成立,則稱y為B的極大元.

105求最大，最小，極大，極小元106定義

設<A,?>為偏序集,B

A,y

A.(1)若

x(x∈B→x?y)成立,則稱y為B的上界.

(2)若

x(x∈B→y?x)成立,則稱y為B的下界.

(3)令C＝{y|y為B的上界},則稱C的最小元為B的最小上界或上確界.

(4)令D＝{y|y為B的下界},則稱D的最大元為B的最大下界或下確界.偏序集的特定元素(續(xù))107求上界，下界，上確界，下確界108第4章二元關系與函數(shù)4.1集合的笛卡兒積與二元關系4.2關系的運算4.3關系的性質(zhì)4.4關系的閉包4.5等價關系和偏序關系4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復合和反函數(shù)1094.6函數(shù)的定義與性質(zhì)函數(shù)的定義函數(shù)定義從A到B的函數(shù)函數(shù)的像函數(shù)的性質(zhì)函數(shù)的單射、滿射、雙射性構造雙射函數(shù)110一、函數(shù)定義定義

設F為二元關系,若

x∈domF

都存在唯一的y∈ranF

使xFy

成立,則稱F為函數(shù).對于函數(shù)F,如果有xFy,則記作y=F(x),并稱y為F在x的值.例1F1={<x1,y1>,<x2,y2>,<x3,y2>}

F2={<x1,y1>,<x1,y2>}

F1是函數(shù),F2不是函數(shù)

111函數(shù)相等定義

設F,G為函數(shù),則

F=G

F

G∧G

F

如果兩個函數(shù)F和G相等,一定滿足下面兩個條件：

(1)domF

=domG

(2)

x∈domF

=domG

都有F(x)=G(x)

實例函數(shù)

F(x)=(x2

1)/(x+1),G(x)=x

1不相等,因為domF

domG.

112從A到B的函數(shù)定義

設A,B為集合,如果

f為函數(shù)

domf

=A

ranf

B,則稱f為從A到B的函數(shù),記作f：A→B.實例

f：N→N,f(x)=2x是從N到N的函數(shù)

g：N→N,g(x)=2也是從N到N的函數(shù)

113B上A定義

所有從A到B的函數(shù)的集合記作BA,讀作“B上A”，符號化表示為

BA={f|f：A→B}計數(shù)：

|A|=m,|B|=n,且m,n>0,|BA|=nm.A=

,則BA=B

={

}.

A≠

且B=

,則

BA=

A=

.

114實例例2設A={1,2,3},B={a,b},求BA.

解BA={f0,f1,…,f7},其中

f0={<1,a>,<2,a>,<3,a>},f1={<1,a>,<2,a>,<3,b>}

f2={<1,a>,<2,b>,<3,a>}，f3={<1,a>,<2,b>,<3,b>}

f4={<1,b>,<2,a>,<3,a>}，f5={<1,b>,<2,a>,<3,b>}

f6={<1,b>,<2,b>,<3,a>},f7={<1,b>,<2,b>,<3,b>}

115函數(shù)的像定義設函數(shù)f：A→B,A1

A.

A1在f下的像：

f(A1)={f(x)|x∈A1}

函數(shù)的像

f(A)

注意：函數(shù)值f(x)∈B,而像f(A1)

B.例3

設f：N→N,

且

令A={0,1},B={2},那么有

f(A)=f({0,1})={f(0),f(1)}={0,2}116二、函數(shù)的性質(zhì)定義設f：A→B,

（1）若ranf

=B,則稱f：A→B是滿射的.

（2）若

y∈ranf

都存在唯一的x∈A使得f(x)=y,則稱f：A→B是單射的.

（3）若f：A→B既是滿射又是單射的,則稱f：A→B是雙射的f

滿射意味著：

y

B,都存在x

A

使得

f(x)=y.f單射意味著：f(x1)=f(x2)

x1=x2

117實例例4判斷下面函數(shù)是否為單射,滿射,雙射的,為什么?

(1)f：R→R,f(x)=

x2+2x

1

(2)f：Z+→R,f(x)=lnx,Z+為正整數(shù)集

(3)f：R→Z,f(x)=

x

(4)f：R→R,f(x)=2x+1

(5)f：R+→R+,f(x)=(x2+1)/x,其中R+為正實數(shù)集.

118解(1)f：R→R,f(x)=

x2+2x

1

在x=1取得極大值0.既不單射也不滿射.(2)f：Z+→R,f(x)=lnx

單調(diào)上升,是單射.但不滿射,ranf={ln1,ln2,…}.(3)f：R→Z,f(x)=

x

滿射,但不單射,例如f(1.5)=f(1.2)=1.

(4)f：R→R,f(x)=2x+1

滿射、單射、雙射,因為它是單調(diào)的并且ranf=R.(5)f：R+→R+,f(x)=(x2+1)/x

有極小值f(1)=2.該函數(shù)既不單射也不滿射.

實例（續(xù)）119常函數(shù)、恒等函數(shù)、單調(diào)函數(shù)

1.

設f：A→B,若存在c∈B

使得

x∈A

都有

f(x)=c,則稱f：A→B是常函數(shù).2.稱A上的恒等關系IA為A上的恒等函數(shù),對所有的x∈A

都有IA(x)=x.3.設f：R→R，如果對任意的

x1,x2∈R，x1<x2,就有f(x1)

f(x2),則稱f為單調(diào)遞增的；如果對任意的x1,x2∈A,x1<x2,就有f(x1)<f(x2),則稱f為嚴格單調(diào)遞增的.

類似可以定義單調(diào)遞減和嚴格單調(diào)遞減的函數(shù).120第4章二元關系與函數(shù)4.1集合的笛卡兒積與二元關系4.2關系的運算4.3關系的性質(zhì)4.4關系的閉包4.5等價關系和偏序關系4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復合和反函數(shù)1214.7函數(shù)的復合與反函數(shù)函數(shù)的復合函數(shù)復合的定理函數(shù)復合的性質(zhì)反函數(shù)反函數(shù)存在的條件反函數(shù)的性質(zhì)122函數(shù)復合的定理定理

設F,G是函數(shù),則F°G也是函數(shù),且滿足

(1)dom(F°G)={x|x∈domF

F(x)∈domG}

(2)

x∈dom(F°G)有F°G(x)=G(F(x))

例如：

G:RR,G(x)=x+1,

F