離散數(shù)學(xué)備課筆記

離散數(shù)學(xué)

主講：袁永紅

第一篇緒言

1.計算機科學(xué)與離散數(shù)學(xué)

離散數(shù)學(xué)是了解和學(xué)習(xí)計算機科學(xué)、掌握和研究計算機科學(xué)的必需的理論基礎(chǔ)。

2.離散數(shù)學(xué)之特征

離散數(shù)學(xué)是數(shù)學(xué)的一個分支，它以離散量作為其主要研究對象，如自然數(shù)、真假值、字母表等。

3.離散數(shù)學(xué)的內(nèi)容

由于離散數(shù)學(xué)是以離散量作為其研究對象，故一切以離散現(xiàn)象作為其研究對象或作為其研究對象之一的數(shù)

學(xué)均可屬于離散數(shù)學(xué)，如集合論、代數(shù)結(jié)構(gòu)、數(shù)理邏輯、圖論等。

第二篇集合論

第一章集合論初步

1.1集合的基本概念

1.1.1集合及其元素

一些不同的確定的對象的全體稱為集合，而這些對象稱為集合的元素。

一般用帶標(biāo)號或不帶標(biāo)號的大寫字母表示集合，如A、M、XPB2等，一般用帶標(biāo)號或不帶標(biāo)號的小寫字

母表示集合的元素，如a-b2>x、y等。

常用Z或I表示整數(shù)集合，用R表示實數(shù)集合。

為了表示一個集合由哪些元素組成，一般將集合的元素全部列出(元素間以逗號隔開)并左右用花括號括

起，以表示由這些元素組成的集合.例如，集合A由元素a、b、c、d組成，則可寫成

A=}a,b,c,d}

集合中的元素本身可以是一個集合。例如集合{a,,{{a,c}}}有3個元素a、出}和{匕?}。

集合中的元素具有如下性質(zhì)：

(1)確定性。也就是說，對集合A,任一元素a或?qū)儆诖思?，或不屬于此集合，兩者必居其一。若一元?/p>

a屬于集合A,則用aeA表示，若不屬于A,則用aeA表示；

(2)唯一性。即元素在集合中最多只能出現(xiàn)一次。

注意：集合{a,{a撲中有兩個元素a和{a},這兩個元素并不相同，故并不違反唯一性。

(3)無序性。即集合{a,b}和集合{b,a}相同。

集合若由有限個元素組成，則稱有限集；集合若由無限個元素組成，則稱無限集.如自然數(shù)集即為無限集,

地球上人的集合則是有限集，特別地，對元素個數(shù)為零的集合稱做空集，記以0。

一個集合，如果它能包括人們所考慮的目標(biāo)之內(nèi)的所有元素，則此集合叫做全集，記以E。

前面已經(jīng)提到集合的表示法，即集合A由元素a、b、c、d組成，可寫為A={a,b,c,d},這種表示法稱為

“枚舉法”，也就是將集合所有元素一一列出.但有時也可只列出一部分元素，而其余部分可從前后關(guān)系

中很顯然地推出，如：

A={1,2,3,4,…}

表示全體自然數(shù)集合，又如：

A={1,2,3,-,100)

表示從1到100的1。。個自然數(shù)所構(gòu)成的集合.

前面所討論的集合表示法稱顯式表示法，集合還可用另一種方法表示即隱式表示法(也稱為描述法)，這

個方法是用一集合元素所具有的共同性質(zhì)來刻畫這個集合.如正偶數(shù)組成的集合A可寫成A={x|x是正偶

數(shù)}

1.1.2集合間的關(guān)系

集合間一般可有兩種關(guān)系：相等關(guān)系與包含關(guān)系。

定義L1如果集合A與集合B的元素相同，則稱這兩個集合是相等的，記以A=B;否則，稱這兩個集合

不相等，記以A*B。

定義L2集合A、B,如果當(dāng)aeA必有aeB,則稱B包含A,或稱A包含于B,或稱A是B的子集，

記以B2A或AqB。如果B2A且存在b,使得beB但beA,則稱B真包含A,或稱A真包含于B,或

稱A是B的真子集，記以BnA或AuB。

例1.4設(shè)2{0,1,2,…},A={1,2,3,…,100},則有A「N,并且有AuN。

例1.5設(shè)A={1,2,3},B={1,2,3},則有A=B。

例1.6設(shè)人={“1為正整數(shù)},B={j|j為正偶數(shù)},則有BeA,且BuA。

對于集合的相等與包含關(guān)系，可用一種圖即文氏圖表示。

文氏圖在表示集合相互間的關(guān)系時較為直觀、形象，故目前被廣泛應(yīng)用.在文氏圖中用一個平面中的區(qū)域

表示一個全集，而對包含于全集內(nèi)的集合用平面區(qū)域內(nèi)的圈表示之.這樣，全集內(nèi)的集合間關(guān)系就可用平

面區(qū)域內(nèi)圓之間的關(guān)系表示.對于相等、包含等關(guān)系可以很形象地用文氏圖表示，如圖1.1所示.

A=BB3AAz)B

圖L1相等與包含關(guān)系之文氏圖

對于相等與包含關(guān)系有下面的一些定理.

定理L1對任一集合A,必有0sA。

即空集是任何集合的子集。

注意：不能說空集是任何集合的真子集。因為空集不是空集的真子集。

定理1.2對任一集合A,必有EqA。

定理L4有集合A與B,則A=B的充分必要條件是A項B且B2A。

補例下列正確的有(ABD)。

A.0￡{0}B.0€{0}

C.{0}c{{0}}D.{0}e{{0}}

1.1.3集合代數(shù)

定義L3由集合A、B中所有元素合并組成的集合，稱為集合A與B的并集，記以AuB,而u稱為并運

算。

例1.7A={1,2,3,4},B={3,4,5,6},則

AUB={1,2,3,4,5,6}

定義L4由集合A、B所有的公共元素所組成的集合，稱為集合A與B的交集，記以AcB,而c稱為交

運算。

例1.8A={1,3,5,7,9},B={l,3,8,10},則

AcB={l,3}

定義1.5集合A、B若滿足AcB=0,則稱A與B是分離的，或稱A與B不相交。

定義L6由集合AB中所有屬于集合A而不屬于B的元素所組成的集合,稱為集合A對集合B的差集

記以A-B,而-稱差運算。

例1.9A={a,b,c,d,e,f},B={d,e,f,g,h},則

A-B={a,b,c}B-A={g,h}

定義1.7集合A的補集?A可定義為

~A=E-A

而?稱為補運算，它是集合論中的一元運算。

例L10設(shè)E={0,l,2,3,…},A={0,2,4,6,…},則

?A=E-A={1,3,5,7,…}

定義L8集合A、B的對稱差(或稱布爾和)A+B可定義為

A+B=(A-B)u(B-A)

而+稱為對稱差運算。(有些書上將+寫成8)

例1.11設(shè)人={1,2,3,4},B={3,4,5⑹,則

A+B={1,2,5,6}

由例中可以看出A+B即為A、B的所有非公共元素所組成的集合。

到此為止，定義了四種二元運算，即并運算、交運算、差運算和對稱差運算，以及一個一元運算：補運算.

這五種運算可用文氏圖表示，如圖1.2所示。

”8

A+B

圖1.2幾種集合運算的文氏圖

在這五種運算中，下面著重討論并、交、補三種運算的基本公式.

由定義可知，并、交運算滿足交換律，即

AuB=BuA

AcB=BcA

由定義可知，并、交運算滿足結(jié)合律，即

Au(BuC)=(AuB)uC

An(BnC)=(AnB)nC

由定義還可知，并、交運算滿足分配律，即

Au(BnC)=(AuB)n(AuC)

An(BuC)=(AnB)u(AnC)

由定義還可以得到有關(guān)空集、全集及補集的幾個公式，它包括同一律:

Au0=AAnE=A

互補律：

Au?A=EAn~A=0

零一律：

AuE=EAn0=0

等幕律：

AuA=AAcA=A

吸收律：

Au(AnB)=AAn(AuB)=A［要特別記憶］

雙補律：

?(?A)=A~E=0~0=E

德?摩根定律

~(AuB)=~An-B［要特別記憶］

~(AnB)=~Au-B［要特別記憶］

到此為止，得到了有關(guān)集合代數(shù)的21個公式，下面舉例說明這些公式的應(yīng)用。

例1.13設(shè)A、B、C為任意3個集合，已知AuB=AuC,AcB=AcC,試證B=C。

證明：B=Bn(AuB)

=Bn(AuC)

=(BnA)u(BnC)

=(AcC)u(BcC)

=(AuB)nC

=(AuC)nC

=C

例1.14化簡((AuBuC)c(AuB))c(A”AcC))。

解：((AuBuC)c(AuB))c(Au(AcC))

=(AuB)nA

=A

補例：化簡Au?(?AuB)

解：Au~(~A<JB)

=Au(~(~A)n~B)

=Au(An~B)

=A

補例：化簡An~(Au~B)

Ac?(A<J?B)

=Ac(?Ac?(?B))

=Ac(?AcB)

=(An~A)nB

=0nB

=0

1.2幕集、n元有序組及笛卡兒乘積

1.2.1暮集

定義L9由集合A的所有子集(包括空集及A本身)所組成的集合稱為A的募集，記以2A或p(A)。

例1.15A={a,b},則p(A)={0,{a},,A}。

例1.16A={1,2,3},則

p(A)={0,{l},{2},{3},{l,2},}l,3},{2,3},A}o

補例求下列情況下的P(A)。

(1)A=0(2)A={0}(3)A={0,{0}}

(4)A={a,0}(5)A={a,}(6)A={a,{a}}

解：⑴p(A)={0}

(2)p(A)={0,A}

(3)p(A)={0,{0},{{0}},A}

(4)p(A)={0,{a},{0},A}

⑸p(A)={0,{a},{},A}

(6)p(A)={0}{a},{{a}},A}

對于幕集有下面的定理.

定理L5若集合A為由n個元素所組成的有限集，則p(A)為有限且由2n個元素組成。

定義1.10兩個按一定次序排列的客體a、b組成一個有序序列，稱為有序偶，并記以(a,b),有些書上記

以<a,b>。

由定義可知，有序偶刻畫了兩個客體間的次序，它并不表示由兩個元素所組成的集合.在很多情況下客體

間的次序是很重要的，如在一個平面直角坐標(biāo)系中，點(x,y)一般并不與(y,x)相等。

有序偶(a,b)中的a、b分別稱為(a,b)的第一客體與第二客體。

定義111有序偶(a,b)與(c,d),如果有a=c,b=d,則說(a,b)與(c,d)是相等的。

由有序偶的相等性可以看出，兩個有序偶只有當(dāng)其兩個客體相同而且次序也相同時才相等。

將有序偶推廣，可以得到n元有序組。

定義1.12n個(n>l)按一定次序排列的客體a?、…、孤組成一個有序序列，稱為n元有序組，并記

以應(yīng)聲2,…,aj。

定義1.13n元有序組(a】例,…,aj與(bh,…耳)如果有

(i=l,2,--,n)

則說區(qū)聲2,…,aj與(也也,…,bj是相等的。

同樣，n元有序組01戶2,…,aj中的a,稱為此n元有序組的第i個客體(i=l,2,-,n)o

1.2.3笛卡兒乘積

設(shè)有兩個集合A與B,用A與B的元素組成有序偶，以A的元素作為有序偶的第一個客體，以B的元素

作為有序偶的第二個客體，用這種辦法所組成的所有有序偶的全體構(gòu)成一個集合，此集合稱為A與B的

笛卡兒乘積，可記為AXB。

由此可見，兩個集合A、B的笛卡兒乘積是以一些有序偶為元素所組成的集合，這些有序偶的第一個客體

取自集合A,第二個客體取自集合B,這樣，可以對笛卡兒乘積下一個形式化的定義.

定義L14集合A、B的笛卡兒乘積可表示為

AXB={(a,b)|aeA.beB；

定義L15集合A】、A2、…、An的笛卡兒乘積可表為

AiXA2X—XAn={(x1,x2—,xn)}XjeAi,i=<2「“,n}

n個集合A的笛卡兒乘積

AXAX-XA記作A\例如A2=AXA。

例1.21設(shè)A={1,2},B={a,b},C={a0},則

AXB={(l>a),(l,b),(2,a),(2)b)}

AXBXC={(l,a,a),(l,a,p),(l,b,a),(l,b,p),

(2,a,a),(2,a,p),(2,b,a),(2,b,p)}

AXA={(1,1),(1,2),(2,1),(2,2)}

注意：笛卡兒乘積中的元素最好按一定次序?qū)?，以免漏寫或多寫?/p>

第二章關(guān)系

2.1關(guān)系的基本概念

2.1.1關(guān)系及其定義

例2.1設(shè)一旅館有n個房間，每個房間可住兩個旅客，所以一共可以住2n個旅客。在旅館內(nèi)，旅客與房

間有一定關(guān)系，討論關(guān)系：“某旅客住在某房間”，用R表示這種關(guān)系，為討論方便起見，設(shè)n=3,此時

表示旅館共有3間房間，分別記以1、2、3,而此時旅館共住6個旅客，分別記以a、b、c、d、e,f,

這些旅客住房的示意圖如圖2.1所示。

1

圖2.1旅客住房示意圖

由圖2.1可以很清楚地看出，滿足R的所有關(guān)系如下：

aRl,bRl,cR2,dR2,eR3,fR3

由此可以看出：

⑴滿足R的關(guān)系pRq可看成是一個有序偶：(P,q),如上面aRl可寫成有序偶：(a,1)。

(2)滿足R的所有關(guān)系可看成是一個有序偶的集合，這個集合即可叫R,上例中R即為

R={(a,l),(b,l),(c,2),(d,2),(e,3),(f,3)}

(3)上面這種關(guān)系稱為二元關(guān)系，因為它僅牽涉到兩個客體間的關(guān)系.當(dāng)然，還可以有三元關(guān)系、四元關(guān)系

及多元關(guān)系存在。

可以用有序偶的集合定義一個關(guān)系亦即是說關(guān)系是一些有序偶的集合，下面對此做進一步說明。

⑷在上面的例子中若令人=也由6<1?3B={1,2,3},則此例中關(guān)系的每一元素均屬于AXB,亦即R是A

XB的子集，或可寫為RsAXB。此時稱此關(guān)系為從A到B的關(guān)系R,這樣，可以給出關(guān)系的正式定義：

定義2.1從集合A到集合B的一個關(guān)系R是AXB的一個子集。

關(guān)系R中有序偶笫一個客體所允許選取對象的集合稱為關(guān)系R的定義域，記以D(R),第二個客體所允許

選取對象的集合稱為關(guān)系R的值域，記以C(R)O

在特殊情況下，當(dāng)D(R)=C(R)時，并且此時設(shè)D(R)=C(R)=M,M為一集合，此時稱此關(guān)系為集合M上的

關(guān)系。

例2.2整數(shù)集Z上的“>”關(guān)系可定義如下：

>={(x,y)|xeZ,yeZ且x>y}

從此例可以看出：(35,24)€>,但(24,35混>,此關(guān)系中有序偶的笫一、第二客體均取自相同的集合Z,故

關(guān)系〉稱為集合Z上的關(guān)系。

與集合論中情況類似，如果從X到Y(jié)不存在某種關(guān)系R,則稱此種關(guān)系為空關(guān)系，如果X的每個元素到Y(jié)

的每個元素間均具有某種關(guān)系，則稱此關(guān)系為全關(guān)系.從X到Y(jié)的全關(guān)系即為XXY。

還可以用類似的方法定義多元關(guān)系.

定義2.2由集合X1、X2>-Xn,所確定的n元關(guān)系是X1XX2X…XXn的一個子集.由此定義可以看出，

n元關(guān)系是一些n元有序組的集合。

2.1.2關(guān)系的圖的表示法

通?？梢杂脠D來刻畫關(guān)系。

一個集合X={Xi,X2,…,xj上的關(guān)系R可用一關(guān)系圖表示之.集合X中元素可用圖中結(jié)點表示；關(guān)系R的

有序偶(X,,Xj)可用圖中從結(jié)點Xi到結(jié)點Xj的有向邊表示.這樣，即可將關(guān)系用圖表示。

這種表示方法可用下面例子說明.

例2.3設(shè)有6個程序pl、p2、…、p6,它們間有一定的調(diào)用關(guān)系R：plRp2、p3Rp4、p4Rp5、p5Rp2、

p2Rp6、p3Rpl,這個關(guān)系是集合P={pl,p2,…,p6}上的關(guān)系，并且有

R={(pl,p2),(p3,p4),(p4,p5),(p5,p2),(p2,p6),(p3,pl)}

對于這樣的一個關(guān)系可用一個圖表示之，這個圖如圖2.2所示。

P1

圖2.2程序間調(diào)用關(guān)系圖

有些書上用圓圈而不是實心圓點表示結(jié)點。

關(guān)系還可以用矩陣表示，在上例中可用下面的矩陣MR表示:

「010000-

000001

100100

MR=

000010

010000

_000000.

2.2關(guān)系的運算

2.2.1關(guān)系的交、并、補、差

由于關(guān)系是一些有序偶的集合，這樣，有關(guān)集合的運算如集合的交、并、補、差等在關(guān)系中也是適用的.例

如設(shè)X={a,b,c}，丫設(shè)1,2},且有從X到Y(jié)的關(guān)系R={(a,l),(b,2),(c,l)},S={(a,l),(b,l),(c,l)},此時則有

RuS={(a,l),(b,l),(b,2),(c,l)}

RnS={(a,l),(c,l)}

XXY={(a,l),(a,2),(b,l),(b,2),(c,l),(c,2)}

~R=(XXY)-R={(a,2),(b,l),(c,2)}

R-S={(b,2)}

上面這些關(guān)系的運算結(jié)果都建立了新的關(guān)系，而且也都是從X到Y(jié)的關(guān)系.以前有關(guān)集合運算的一些公式

在關(guān)系中也同樣適用。

除了上述的幾種運算以外，在關(guān)系中尚有兩種新的運算，它們是復(fù)合運算與逆運算，其結(jié)果所組成的關(guān)系

稱復(fù)合關(guān)系與逆關(guān)系，現(xiàn)分別介紹于下。

2.2.2復(fù)合關(guān)系

定義2.3設(shè)R是一個從X到Y(jié)的關(guān)系，S是一個從Y到Z的關(guān)系，則R與S的復(fù)合關(guān)系：RS可定義

為

R?S={(x,z)|xeX,zeZ,至少存在一個yeY有(x,y)eR且(y,z)eS}

這個復(fù)合關(guān)系是一個從X到Z的關(guān)系。

有些書上將符號“。”寫成“■”。

補例設(shè)1?={(1,2),(2,2),(3,4),(4,2)}

S={(1,3),(2,5),(3,1),(3,4),(4)4)}

求：R°S-?SoR、RoR、S°SO

解：RoS={(l,5M2,5),(3,4),(4,5)}

S?R={(1,4),(3,2),(4,2))

R°R={(1,2),(2,2),(3,2)(4,2)}

S?S={(1,1),(1,4),(3,3),(3)4).(4,4)}

定理2.1設(shè)R、S、T分別表示從X到Y(jié)、Y到Z、Z到U的關(guān)系,則有

(R<>S)=T=R°(S°T)

由于關(guān)系的復(fù)合運算滿足結(jié)合律，故可以將復(fù)合運算中的括號除去，亦即有

(R?S)?T=R°(S?T)=R°S?T

對于某個關(guān)系R自己與自己的復(fù)合運算是RoR,可以用R?表示，同理RoRoR可用R3表示，因此可以用

下面的方式來定義關(guān)系的騫。

定義2.4設(shè)有一個集合X上的關(guān)系R,則R11可定義如下：

(1)R』R;

(2)Rn+1=R%R

由定義，很容易就能知道

Rm°Rn=Rm+n

(Rm)n=Rmn

2.2.3逆關(guān)系

定義2.5設(shè)R是一個從X到Y(jié)的關(guān)系，B［lR={(x)y)|xeX,yeY},則從Y到X的關(guān)系R±

R-i={(y,x)|xwX,yeY)

稱為R的逆關(guān)系。

例2.6設(shè)X={1,2,3},Y={a,b,c},且設(shè)R是從X到Y(jié)的關(guān)系：

R={(l,a),(2,b),(3,c)}

則有從R的逆關(guān)系

Ri={(a,l),(b,2),(c⑶}

關(guān)系的逆關(guān)系滿足下面的定理.

定理2.2設(shè)R、S分別是從X到Y(jié)及Y到Z的關(guān)系，則有

⑴(R")-i=R

(2)(RoSJ^S-^R1［要特別記憶］

2.3關(guān)系的重要性質(zhì)

定義2.6在集合X上的關(guān)系R,如對任意xeX,有(x,x)eR,則稱R是自反的。

定義2.7在集合X上的關(guān)系R,如對任意xeX,有(x,x)eR,則稱R是反自反的。

例2.8在整數(shù)集Z上的關(guān)系是自反的，不是反自反的。

例2.9在整數(shù)集Z上的關(guān)系是反自反的，不是自反的。

例2.1。在集合X={1,2,3,4}上的關(guān)系R:

R={(1,1),(1,2),(3,4),(2,2),(4,2)}

此關(guān)系既不是自反的也不是反自反的，由此可知，一個關(guān)系的自反性與反自反性可以都不存在。

一個關(guān)系的自反性在圖形表示法中相當(dāng)于一個關(guān)系圖中的每個結(jié)點均有環(huán)出現(xiàn)，而一個關(guān)系的反自反性相

當(dāng)于一個關(guān)系圖中的每個結(jié)點均無環(huán)出現(xiàn)。

定義2.8在集合X上的關(guān)系R,如果有(x,y)eR,必有(y,x)eR,則稱R是對稱的。

定義2.9在集合X上的關(guān)系R,如果有(x,y)eR且x*y,必有(y,x)KR,則稱R是反對稱的。

例2.12在整數(shù)集Z上的關(guān)系及“V”均是反對稱的。

例2.13在集合X={1,2,3,4}上的關(guān)系R:

R={(1,2),(211),(3,4),(4,2)}

此關(guān)系既不是對稱的也不是反對稱的。

關(guān)系的對稱性在圖形表示中相當(dāng)于關(guān)系圖中兩個結(jié)點間如有有向邊相連，則一定有方向相反的兩條有向邊

連接；一個關(guān)系的反對稱性相當(dāng)于關(guān)系圖中兩個結(jié)點間如有有向邊相連則一定只有一條邊。

定義2.10在集合X上的關(guān)系R,對任意(x,y)eR且(y,z)eR,必有(x,z)eR,則稱R是傳遞的。

例2.15整數(shù)集Z上的“<"、關(guān)系均是傳遞的。

例2.17整數(shù)集Z上的關(guān)系是反自反、反對稱的，然而是傳遞的。

例2.18整數(shù)集Z上的“相等”關(guān)系是自反的、對稱的，同時又是傳遞的。

例2.19一些人所組成的集合上的“父子”關(guān)系是反自反、反對稱的，亦是非傳遞的。

例2.20用圖2.5所表示出來的在集合X={1,2,3}上的關(guān)系的5個圖形，從圖中可以清楚地看出：

⑴斤1⑵氏2⑶&3

圖2.5具有某些性質(zhì)的關(guān)系圖

(1)凡是自反的、對稱的，又是傳遞的(它是一個全關(guān)系)。

⑵R2是反自反的、反對稱的。

⑶Rs是對稱的。

⑷R’是自反的、反對稱的、傳遞的。

(5)Rs是反自反的、對稱的、反對稱的、傳遞的(它是一個空關(guān)系)。

2.4關(guān)系上的閉包運算

定義2.11設(shè)R是集合X上的一個關(guān)系，則R的自反(對稱、傳遞)閉包是一個滿足下列條件的關(guān)系R'：

(l)R'是自反的(對稱的、傳遞的)；

⑵R'2R；

⑶設(shè)R”是自反的(對稱的、傳遞的)且R”皂R,則必有R"郃'。

通常用r(R)表示R的自反閉包；用s(R)表示R的對稱閉包；用t(R)表示R的傳遞閉包。

例2.21整數(shù)集Z上的關(guān)系的自反閉包是關(guān)系；它的對稱閉包是關(guān)系；它的傳遞閉包

即是它自身。

定理2.3設(shè)R是集合X上的關(guān)系，則

r(R)=Ru{(x,x)|xeX}

定理2.4設(shè)R是集合X上的關(guān)系，則s(R)=RuRL

定理2.6設(shè)R是有限集合X上的關(guān)系，并設(shè)X有n個元素，則

t(R)=RuR2oR3u---uRn

傳遞閉包也可從關(guān)系圖中觀察得出。

補例設(shè)有集合A={1,2,3},A上的關(guān)系

R={(1,2),(2,1),(3,1)},求r(R),s(R)和t(R)。

解：r(R)=Ru{(l,l),(2,2),(3,3)}

={(1,2),(2.1),(3,1),(1,1),(2,2),(3,3)}

R?{⑵1),32),(1,3)}

s(R)=RuR-1={(l,2),(2,1),(3,1),(1,3)}

2

R={(1,1),(2,2),(3)2)}

R3={(1,2),⑵1),(3」)}

t(R)=RuR2uR3={(l,2),(2,l),(3,l),(1,1),(2,2),(3,2)}

2.5次序關(guān)系

定義2.12集合X上的關(guān)系R如果是自反的、反對稱的、傳遞的，則稱R在X上是偏序的或稱R是集合

X上的偏序關(guān)系。而稱集合X為R的偏序集，用(X,R)表示。

一般地用符號表示偏序(注意，此符號在這里并不表示為小于或等于)。

例2.26由集合A所組成的密集p(A)上的關(guān)系'七”是自反的、反對稱的又是傳遞的，故它是偏序的。

例2.27整數(shù)集Z上的(不是偏序的符號)是偏序關(guān)系。

例2.28集合X={2,3,6,8}上的“整除”關(guān)系R={(2,2),(2,6),(2,8),(3,3),(3,6),(6,6),(8,8)卜是偏序的。

定義2.16設(shè)集合X上有一個偏序關(guān)系“V”且設(shè)Y是X的一個子集，則

(1)如果存在一個元素yeY對每個y'eY均有y'Vy,則稱y是Y的最大元素；如果均有y<y',則稱

y是Y的最小元素。

(2)如果存在一個元素yeY且在Y中不存在元素y'有y*y'并且yVy',則稱y是Y的極大元素；如果

Y中不存在元素y'有y*y'并且y'<y,則稱y是Y的極小元素。

(3)如果存在一個元素xeX,對每個yeY均有y<x,則稱x是Y的上界；如果均有x<y,則稱x是Y的

下界。

(4)如果xeX是Y的上界且對每一個Y的上界x'均有x<x',則稱x是Y的上確界(或稱最小上界)；如

果x是Y的下界且對每一個Y的下界x'均有x'<x,則x是Y的下確界(或稱最大下界)。

這個定義所確定的最大元素，極大元素、上界、上確界(相應(yīng)地：最小元素、極小元素、下界、下確界)

等4個概念是有明確區(qū)別的，不能混淆。當(dāng)然，有時它們所代表的元素有些是相同的，但這并不影響它們

之間概念的不同。

例2.35集合A={a,b,c}的募集

p(A)={0,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}

上的‘七”關(guān)系是一個偏序關(guān)系。

(1)設(shè)8={匕,3,內(nèi),(:},{川,{曲0},則它沒有最大元素，但它有極大元素：{a,b},{b,c}；它的上界與上確界

是相同的即是{a,b,c},它的最小元素、極小元素、下界及下確界均相同即為0。

⑵設(shè)B={{a},{c}},則它的最大元素沒有，極大元素是{a}和{c},上界是{a,c}和{a,b,c},上確界是{a,c},它的

最小元素沒有，極小元素是匕}和{c},下界是0,下確界也是0。

為了說明與研究偏序關(guān)系，用一種圖形的方法協(xié)助分析與研究是有益的，此種圖稱為哈斯圖，哈斯圖的畫

法可描述如下：

對一個集合X上的偏序關(guān)系，對其X中的每個元素可用結(jié)點表示。如x,ywX,且x<y,則在圖中將結(jié)點

x畫于結(jié)點y的下面，如x與y間不存在另一個z有：x<z且z?y,則在x與y間用一線連接，由此所

得到的圖即為哈斯圖。

例2.37集合X={2,3,6,12,24,36}上的“整除”關(guān)系R是偏序的，它可用哈斯圖表示(如圖2.8所示)。

圖2.8X上“整除”關(guān)系的哈斯圖

例2.38A={a,b},則p(A)上的'七”關(guān)系是偏序關(guān)系，它的哈斯圖如圖2.9所示。

S力,c}

圖2.9p(A)上U關(guān)系的哈斯圖

哈斯圖對尋找最大(小)元素、極大(小)元素、上(下)界、上(下)確界等有很明顯的作用.如例2.37

中的圖2.8,可以很明顯地看出集合X沒有最大元素，極大元素為24和36,同樣地也沒有上界與上確界。

它的極小元素是2和3,但沒有最小元素、下界、下確界。

補例：已知集合A={1,2,3,4,6,8,9,12,24}

及其上的整除關(guān)系R,試畫出哈斯圖，并求：

⑴集合A上的最大元、最小元、極大元、極小元。

(2)集合B=[4,8,12}上的最大元、最小元、極大元、極小元。

(3)集合B={4,8,12}上的上界、下界、上確界(最小上界/下確界(最大下界)。

解：哈斯圖見黑板。

(1)集合A上的最大元無，最小元為1,極大元有24和9,極小元有1。

(2)集合B上的最大元無，最小元為4,極大元有8和12,極小元有4。

(3)集合B的上界有24,下界有1、2和4,上確界(最小上界)為24,下確界(最大下界)為4。

2.6相容關(guān)系(不要求)

2.7等價關(guān)系

定義2.20一個在集合X上的關(guān)系R如果它是自反的、對稱的、傳遞的，則稱此關(guān)系為等價關(guān)系。

例2.48設(shè)有一個整數(shù)集Z上的關(guān)系R:

R={(x,y)|x-y能被3整除}

這個關(guān)系是等價關(guān)系，因為有

⑴對每個aeZ,認(rèn)為a-a能被3整除，所以是自反的；

(2)對a,beZ,如果a-b能被3整除，則b-a也能被3整除，所以是對稱的；

(3)對a,b,ceZ,如果有a-b,b-c均能被3整除，則a-c=(a-b)+(b-c)也能被3整除，所以是傳遞的。

將這個例子推廣到一般，可得到下面的例子.

例2.49設(shè)Z是整數(shù)集，Z上的關(guān)系R:

R={(x,y)|x-y能被m整除}

這個關(guān)系是等價關(guān)系，其中m是任一正整數(shù)，這也就是說，滿足這個關(guān)系R的x,y用m除后有相同的余

數(shù)，所以也叫同余關(guān)系或叫以m為模的同余關(guān)系。

定義2.21設(shè)S是一個集合，AI,A2,…Am是它的子集，如果它們滿足下列條件：

(1)所有Aj間均是分離的，亦即對所有i,j(i=l,2,…,m,j=l,2,…,m),如iwj,則A「Aj=0;

⑵A1uA2u---oAm=S

則集合A={A],A2,…,A?J稱為S的一個劃分，而A1,A2,…,Am稱為這個劃分的塊。

定義2.22設(shè)R是集合X上的等價關(guān)系，對任一個xeX可以構(gòu)造一個X的子集[X]R,稱為x對于R的等

價類：

[x]R={y|yeX且xRy}

由此定義可知，[X]R是X內(nèi)所有與x有等價關(guān)系R的元素所構(gòu)成的集合。對于這種集合，它有下列幾個性

質(zhì)：

(1)xe[x]R

(2)如ye[x]R,則必[Y]R=[X]R

⑶若ye[y]R,但y￡[x]R,則必有[X]R與[yk是分離的。

由上面這3個性質(zhì)可知，集合X上的等價關(guān)系R所構(gòu)成的類，它們兩兩互不相交而且覆蓋住整個集合X,

故它們構(gòu)成X的一個劃分，而每個類是這個劃分的塊，由此有定理如下。

定理2.11集合X上的等價關(guān)系R所構(gòu)成的類產(chǎn)生一個集合X的劃分，此劃分叫X關(guān)于R的商集，記以

X/Ro

由此定理可知商集X/R是一個集合，它的元素是X上的元素所構(gòu)成的類。

例2.50設(shè)I是整數(shù)集，R={(x,y)|x,yel,x-y能被3整除},由上所述可知R是一個等價關(guān)系。

在I上的這種等價關(guān)系R所構(gòu)成的類分別為

[0]R={-,-6,-3,0,3,6,-}

[1]R={-,-5,-2,1,4,7,-)

[2]R={I,-4,-1,2,5,8「?}

而商集I/R={[0]R,⑴R,⑵目

擴充之，可以作I上的關(guān)系R={(x,y)|x,yeI,x-y被m所整除},其中m為正整數(shù)，它也是一個等價關(guān)系。

在I上的這種等價關(guān)系R所構(gòu)成的類分別為

Q]R={…，-2m,-m,0,m,2m，…}

[1卜={…,-2m+1,-m+1,1,m+1,2m+1,---}

[2]R={…,-2m+2,-m+2,2,m+2,2m+2,…}

[m-l]R={"-,-m+l,-l,m-1,2m-1,3m-1,???}

這些類稱為模m的剩余類，商集

I/R={[0]R,[l]R,[2]R,-,[m-l]R}

反之，任給一個集合的劃分可產(chǎn)生一個等價關(guān)系。

定理2.12任一個集合X上的一個劃分C可產(chǎn)生一個等價關(guān)系。

例2.51設(shè)R是集合X={0,1,2,3,5,6,8}上的以3為模的同余關(guān)系，它的關(guān)系圖如圖2.12所示,

05

0

圖2.12X上以3為模的同余關(guān)系的關(guān)系圖

由此圖可以很清楚地看出這個關(guān)系是個等價關(guān)系。

由等價關(guān)系所構(gòu)成的等價類在圖中即是等價關(guān)系圖中的完全圖。由上例中可看出等價關(guān)系R有三類，它們

分別是

⑼R={0,3,6}

[1]R={1}

[2]R={2,5,8)

X/R={⑼⑵R}={{0,3,6},{1},{2,5,8}}

第三章函數(shù)

3.1函數(shù)的基本概念

函數(shù)又叫映射，它建立了從一個集合到另一個集合的一種對應(yīng)關(guān)系。設(shè)有集合X與Y,如果有一種對應(yīng)關(guān)

系f,使X的任一元素x能與Y中的一個惟一的元素y相對應(yīng)，則這個對應(yīng)關(guān)系f叫從X到Y(jié)的函數(shù)或叫

從X到Y(jié)的映射。x所對應(yīng)的Y內(nèi)的元素y叫x的像，而x則叫y的像源。上述函數(shù)可以表示成f:X-Y；

或?qū)懗蓎=f(x)□

考察圖3.1所表示的函數(shù)，函數(shù)f建立了從X到Y(jié)的一種關(guān)系，這種關(guān)系可表達如下：

XY

f={(X1,y1),(x2,y2),(x3)yJ,(x4,yJ,(x5,y5)}

但是這種關(guān)系有其特殊性，從圖中可以看出：

(1)X的每個元素為均對應(yīng)Y的一個元素%,即是說，關(guān)系f的元素(x“yj對所有x(i=l,2,3,4,5)均出現(xiàn);

⑵X的每個元素Xi均僅對應(yīng)Y的一個元素％,即是說，關(guān)系f的元素(x?yj對每個Xi(i=l,2,3,4,5)均只能

出現(xiàn)一次；

(3)反之，Y中的元素不一定都需要有一個X中的元素與之對應(yīng)，如圖中丫3,y,就沒有一定的局與之對應(yīng)，

同樣，對于Y中的某些元素可以允許多個不與之對應(yīng)，如圖中y1即有三個X中的元素與其對應(yīng)，它們是

X”x3,X4o

由此，可用關(guān)系的概念定義函數(shù)，將函數(shù)看成是某種特殊的關(guān)系。

定義3.1一個函數(shù)或映射f:X->Y是一個滿足下列兩個條件的關(guān)系：

(1)對每個xeX,必存在yeY,使得(x,y)ef----存在性條件。

⑵對每個xeX也只存在一個ysY,使得(x,y)ef------惟一性條件。

補例：集合X={1,2,3},Y={a,b},下列從X到Y(jié)上的關(guān)系中哪些是函數(shù)(或映射)？

R1={(l,a),(2,b),(3,b)}

R2={(l,a),(2,a),⑶a)}

R3={(l,a),(l,b)}

R4={(l,a),(l,b),(2,a),(3,b)}

Rs={(l,b),⑵a)}

解：電和Rz是函數(shù)(或映射)。

這樣，就可用關(guān)系的一些概念與性質(zhì)研究函數(shù)。

與關(guān)系一樣，一個函數(shù)f：X-Y有定義域與值域，一般用Df表示DH),用Cf表示C(f)。由定義可知，對

于函數(shù)f：X-Y,D產(chǎn)X,CfCYo

若f={(x1,y1),施山),(X3,yJ,%,y1),施萬5)}

則Df={x1,x2,x3,x4,x5}

cf={yi,y2,y5}

定義3.2一個函數(shù)f:X-Y,如果Cf=Y,則稱為從X到Y(jié)的滿射(或稱為從X到Y(jié)上的函數(shù))；否則，就

稱為從X到Y(jié)的內(nèi)射(或稱為從X到Y(jié)內(nèi)的函數(shù))。

定義3.3一個函數(shù)f:XfY,如果對任一i,j若x.Xj,則有f(xJ*f(Xj),則此函數(shù)稱為從X到Y(jié)的單射

(或稱為從X到Y(jié)的一對一函數(shù))；否則，叫多對一函數(shù)。

定義3.4一個函數(shù)f:X-Y,如果它是從X到Y(jié)的一對一函數(shù)，則此函數(shù)稱為X與Y間的雙射(或稱為

一一對應(yīng)映射)。

若X=Y則上述函數(shù)稱為X的變換。

補例：集合X={1,2,3},Y={a,b},下列從X到Y(jié)上的映射的性質(zhì)(單射、滿射、雙射)？

R1={(l)a),(2,b),(3,b)}

Ri={(l,a),(2,a),(3,a)}

解：電不是單射，是滿射，不是雙射。

R2不是單射，不是滿射，不是雙射。

補例：集合X={1,2},Y={a,b,c},下列從X到Y(jié)上的映射的性質(zhì)(單射、滿射、雙射)？

R1={(l,a),(2,b)}

R1={(l,a),(2,a)}

解：凡是單射，不是滿射，不是雙射。

R2不是單射，不是滿射，不是雙射。

補例：集合X={1,2,3},Y={a,b,c},下列從X到Y(jié)上的映射的性質(zhì)(單射、滿射、雙射)？

R1={(l,c),(2,b))(3,a)}

Ri={(l,a),⑵a)\3,a)}

解：凡是單射，是滿射，是雙射。

R2不是單射，不是滿射，不是雙射。

3.2復(fù)合函數(shù)、反函數(shù)、多元函數(shù)

定義3.5設(shè)函數(shù)f:X-Y,g:Y-Z,它們所組成的復(fù)合函數(shù)或稱復(fù)合映射g。。也是一個函數(shù)h:X-Z,

即

h=gof:{(x,z)|xeX,zeZ且至少存在一個yeY,有y=f(x),z=g(y){o

與復(fù)合關(guān)系一樣，復(fù)合函數(shù)定義了函數(shù)的復(fù)合運算。函數(shù)的復(fù)合運算滿足結(jié)合律，亦即

h0(g0f)=(hog)of=hog°f

補例：已知函數(shù)f(x)=2x+l,g(x)=x2,求：

fog,g°f,f=f,g°go

解：f-g(x)=f(x2)=2x2+1

g?f(x)=g(2x+l)=(2x+l)2

f°f(x)=f(2x+l)=2(2x+l)+l=4x+3

g°g(x)=g(x2)=(x2)2=x4

補例：已知函數(shù)f:X->X={(l,2),(2,3),(3,l)}

g:X->X={(l,3),(2,2),(3,l))

求g°f和fogo

解：gof:XfX

={(1,2),(2,3),(3,1)H(1,3),(2,2),(3)1)}注意順序

={(1,2),(2,1),(3,3)}

f°g:X-*X

={(1,3),(2,2),(3(1)H(1,2),(2,3),(3,1))注意順序

={(1,1),(2,3),(3,2)}

在關(guān)系中，任一個關(guān)系均存在逆關(guān)系，但對函數(shù)而言就有所不同了，每個函數(shù)不一定都有反函數(shù)。

一個函數(shù)存在反函數(shù)的條件是此函數(shù)是一一對應(yīng)的。

定義3.6設(shè)f:X-Y是一一對應(yīng)的函數(shù)，則f所構(gòu)成的逆關(guān)系稱為f的逆映射或稱為f的反函數(shù)，記以f：

Y—X

3.3常用函數(shù)介紹(不要求)

補例：設(shè)f：A->B,g：B-C都是一對一映射，請問復(fù)合映射g4是否一定是一對一映射？請證明或舉出

反例。

解：gd一定是一對一映射，證明如下：

'''g:B—*C是一對一映射

...對任意ceC,至多存在一個

beB,使得g(b)=c

又:A—>B是一■對一?映射

至多存在一個

aeA,使得f(a)=b

..?對任意ceC,至多存在一個

aeA,使得g4(a)=c

g°f一定是一對一映射。

補例：設(shè)f：A-B,g：B-C都是滿射，請問復(fù)合映射gd是否一定是滿射？請證明或舉出反例。

解：gof一定是滿射，證明如下：

Tg:B-C是滿射

???對任意cwC,至少存在一個

beB,使得g(b)=c

又:A-B是滿射

..?至少存在一個

aeA,使得f(a)=b

，對任意ceC,至少存在一個

aeA,使得g4(a)=c

，gof一定是滿射。

補例：設(shè)f：A-B,g:B-C都是雙射，請問復(fù)合映射g4是否一定是雙射？請證明或舉出反例。

解：gd一定是雙射，證明如下：

???g:B->C是雙射

，對任意ceC,存在唯一

beB,使得g(b)=c

又:A->B是雙射

???存在唯一

aeA,使得f(a)=b

，對任意ceC,存在唯一

aeA,使得gof(a)=c

??.gof一定是雙射。

第三篇代數(shù)系統(tǒng)

代數(shù)系統(tǒng)是用代數(shù)運算構(gòu)造數(shù)學(xué)模型的方法，所謂代數(shù)運算方法即是在集合上建立滿足一定規(guī)則的運算系

統(tǒng)，并對該系統(tǒng)做定性的研究。由于此種方法是在集合上通過構(gòu)造手段生成，因此也可稱為代數(shù)結(jié)構(gòu)。

本篇一共分為3章，其中第五章主要介紹代數(shù)系統(tǒng)的一般理論，第六章介紹代數(shù)系統(tǒng)中的最常用的系統(tǒng)一

一群，通過對群的介紹可以使讀者對代數(shù)系統(tǒng)中具體系統(tǒng)有一定的認(rèn)識和理解，最后第七章介紹群以外的

其他代數(shù)系統(tǒng)，它們包括環(huán)、域、格及布爾代數(shù)等。

笫五章代數(shù)系統(tǒng)基礎(chǔ)

5.1代數(shù)系統(tǒng)的一般概念

一個代數(shù)系統(tǒng)需要同時滿足下面3個條件：

⑴有一個非空集合S;

(2)有一些建立在集合S上的運算；

(3)這些運算在集合S上是封閉的。

下面對這3個條件作一些必要的說明。

集合S給出了代數(shù)系統(tǒng)所研究的客體的范圍。

在此，運算的概念具有一定的廣泛性與抽象性，它不僅包括日常所有的加減乘除等算術(shù)運算，也包括較為

抽象的運算，如圖形的放大/縮小運算，字符串的“并置”運算，它也包括任意定義的運算。在集合S上

的運算可以有多個，運算符一般可以用“?！北硎荆部梢杂?*"、“△”等表示.有時也可用“+”、“X”

等表示，但此時“+”、“X”的含義不一定即是普通算術(shù)運算中“加”與“乘”的含義.所有這些運算

符的含義可以根據(jù)不同的定義而具有不同的意義。

集合S申的元素經(jīng)某運算后它的結(jié)果仍在S中，則稱此運算在集合S上是封閉的。

一個在集合S上具有運算“?！钡拇鷶?shù)系統(tǒng)可以寫為(S,。)。

例5.1一個在整數(shù)集I上且?guī)в屑臃ㄟ\算的系統(tǒng)構(gòu)成了一個代數(shù)系統(tǒng)(1,+)。因為它有一個集合

1={…,-3,-2,-1,0,1,2,3,…}且有集合I上的運算“+”，這個加法運算對I是封閉的，由此它構(gòu)成了一個代

數(shù)系統(tǒng)(1,+)。

例5.2一個在實數(shù)集R上且?guī)в袃蓚€二元運算“+”與“X”的系統(tǒng)構(gòu)成了一個代數(shù)系統(tǒng).因為R是一個

集合，在R上兩個運算它們均是封閉的，故構(gòu)成了一個代數(shù)系統(tǒng)(R,+,X)。

定義5.1如果兩個代數(shù)系統(tǒng)有相同個數(shù)的運算符，每個相對應(yīng)的運算符有相同的元數(shù)，則稱這兩個代數(shù)系

統(tǒng)具有相同的類型。

例5.5代數(shù)系統(tǒng)(N,+)與代數(shù)系統(tǒng)(I,X)是相同類型的，因為它們都有一個二元運算符。

例5.6代數(shù)系統(tǒng)(I,+,X)與(N,+)的類型是不相同的，因為它們的運算符的個數(shù)不同。

定義5.2兩個代數(shù)系統(tǒng)(S,。)與(S',*)若滿足下列條件：

(I)S，aS；

⑵aeS',beS",則a*b=a°b

則稱(S',*)是(S,。)的子系統(tǒng)或子代數(shù)。

這個定義還可推廣至多個運算符的情況。

例5.7設(shè)E是所有偶數(shù)所組成的集合，則代數(shù)系統(tǒng)(E,+)是(1,+)的一個子系統(tǒng)。

注意：設(shè)A是所有奇數(shù)所組成的集合，“+”是集合A上的加法運算，則(A,+)不是(1,+)的一個子系統(tǒng)。因

為運算+對集合A不封閉，故(A,+)不是代數(shù)系統(tǒng)，更不是(L+)的一個子系統(tǒng)。

5.2代數(shù)系統(tǒng)常見的一些性質(zhì)

下面討論代數(shù)系統(tǒng)常見的幾個性質(zhì)，一些特定的代數(shù)系統(tǒng)均具有這些性質(zhì)中的某一些性質(zhì)，下面所討論的

代數(shù)系統(tǒng)中的運算均假設(shè)為二元運算。

1.結(jié)合律

一個代數(shù)系統(tǒng)(S,。)，如果對S內(nèi)的任意元素a、b、c均有aUboc)=(aob)oc

則稱此代數(shù)系統(tǒng)的運算“?！睗M足結(jié)合律。

一個代數(shù)系統(tǒng)的某運算符如果滿足結(jié)合律，則此運算符進行運算時與運算先后次序無關(guān)，此時運算符所進

行的任何運算均不需設(shè)置括號，如：

a0(b℃)=(a°b)℃=a°b℃

整數(shù)集上的運算不滿足結(jié)合律，這可以從一個簡單示例中看出：

例5.85-(2-1)=4但是(5-2)-1=2所以5-(2-1)#=(5-2)-1

2.交換律

一個代數(shù)系統(tǒng)(S,。)，如果對S內(nèi)的任意元素a、b均有aob=boa

則稱此代數(shù)系統(tǒng)的運算“?！睗M足交換律。

集合的并運算和交運算滿足交換律，差運算不滿足交換律。

3.分配律

代數(shù)系統(tǒng)若具有兩個運算時，則分配律建立了這兩個運算間的某種聯(lián)系。

設(shè)一代數(shù)系統(tǒng)(S,。,*),如果對S內(nèi)的任意3個元素a、b、c均有ao(b*c)=(aob)*(aoc)

則稱此代數(shù)系統(tǒng)中的運算“。”對運算“*”滿足第一分配律。

同理，如有a*(b℃)=(a*b)°(a*c)

則稱此代數(shù)系統(tǒng)中的運算“*”對運算“?！睗M足第一分配律。

如有(b*c)oa=(boa)*(coa)

則稱此代數(shù)系統(tǒng)中的運算“?！睂\算“*”滿足第二分配律。

如有(b(>c)*a=(b*aHc*a)

則稱此代數(shù)系統(tǒng)中的運算“*”對運算“。”滿足第二分配律。

4.單位元紊(或稱單位元)

代數(shù)系統(tǒng)(S,。)若存在一個元素leS,對任一個xeS,均有kx=xr=x,則稱此元素為對于運算“?！钡膯?/p>

位元素。

注意：單位元素的符號“1”不一定具有自然數(shù)1的含義，它僅僅是單位元素的符號表示。

例5.10在實數(shù)集上的代數(shù)系統(tǒng)(R,+,X)的“義”運算的單位元素為1,“+”運算的單位元素為0,因為

xX】=lXx=x;x+0=0+x=Xo

定理5.2一個代數(shù)系統(tǒng)(S,。)的運算“產(chǎn)的單位元素若存在則