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

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

主講：袁永紅

第一篇緒言

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

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

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

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

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

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

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

第二篇集合論

第一章集合論初步

1.1集合的基本概念

1.1.1集合及其元素

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

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

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

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

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

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

A=}a,b,c,d}

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

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

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

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

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

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

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

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

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

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

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

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

中很顯然地推出，如：

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

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

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

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

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

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

數(shù)}

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

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

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

不相等，記以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。

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

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

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

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

A=BB3AAz)B

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

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

定理L1對(duì)任一集合A,必有0sA。

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

注意：不能說(shuō)空集是任何集合的真子集。因?yàn)榭占皇强占恼孀蛹?/p>

定理1.2對(duì)任一集合A,必有EqA。

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

補(bǔ)例下列正確的有(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稱為并運(yùn)

算。

例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稱為交

運(yùn)算。

例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對(duì)集合B的差集

記以A-B,而-稱差運(yùn)算。

例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的補(bǔ)集?A可定義為

~A=E-A

而?稱為補(bǔ)運(yùn)算，它是集合論中的一元運(yùn)算。

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

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

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

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

而+稱為對(duì)稱差運(yùn)算。(有些書上將+寫成8)

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

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

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

到此為止，定義了四種二元運(yùn)算，即并運(yùn)算、交運(yùn)算、差運(yùn)算和對(duì)稱差運(yùn)算，以及一個(gè)一元運(yùn)算：補(bǔ)運(yùn)算.

這五種運(yùn)算可用文氏圖表示，如圖1.2所示。

”8

A+B

圖1.2幾種集合運(yùn)算的文氏圖

在這五種運(yùn)算中，下面著重討論并、交、補(bǔ)三種運(yùn)算的基本公式.

由定義可知，并、交運(yùn)算滿足交換律，即

AuB=BuA

AcB=BcA

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

Au(BuC)=(AuB)uC

An(BnC)=(AnB)nC

由定義還可知，并、交運(yùn)算滿足分配律，即

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

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

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

Au0=AAnE=A

互補(bǔ)律：

Au?A=EAn~A=0

零一律：

AuE=EAn0=0

等幕律：

AuA=AAcA=A

吸收律：

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

雙補(bǔ)律：

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

德?摩根定律

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

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

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

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

證明：B=Bn(AuB)

=Bn(AuC)

=(BnA)u(BnC)

=(AcC)u(BcC)

=(AuB)nC

=(AuC)nC

=C

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

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

=(AuB)nA

=A

補(bǔ)例：化簡(jiǎn)Au?(?AuB)

解：Au~(~A<JB)

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

=Au(An~B)

=A

補(bǔ)例：化簡(jiǎn)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

補(bǔ)例求下列情況下的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}

對(duì)于幕集有下面的定理.

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

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

以<a,b>。

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

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

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

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

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

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

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

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

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

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

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

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

1.2.3笛卡兒乘積

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

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

笛卡兒乘積，可記為AXB。

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

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

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

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

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

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

n個(gè)集合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個(gè)房間，每個(gè)房間可住兩個(gè)旅客，所以一共可以住2n個(gè)旅客。在旅館內(nèi)，旅客與房

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

表示旅館共有3間房間，分別記以1、2、3,而此時(shí)旅館共住6個(gè)旅客，分別記以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可看成是一個(gè)有序偶：(P,q),如上面aRl可寫成有序偶：(a,1)。

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

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

(3)上面這種關(guān)系稱為二元關(guān)系，因?yàn)樗鼉H牽涉到兩個(gè)客體間的關(guān)系.當(dāng)然，還可以有三元關(guān)系、四元關(guān)系

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

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

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

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

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

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

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

在特殊情況下，當(dāng)D(R)=C(R)時(shí)，并且此時(shí)設(shè)D(R)=C(R)=M,M為一集合，此時(shí)稱此關(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的每個(gè)元素到Y(jié)

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

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

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

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

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

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

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

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

這種表示方法可用下面例子說(shuō)明.

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

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

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

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

P1

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

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

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

「010000-

000001

100100

MR=

000010

010000

_000000.

2.2關(guān)系的運(yùn)算

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

由于關(guān)系是一些有序偶的集合，這樣，有關(guān)集合的運(yùn)算如集合的交、并、補(bǔ)、差等在關(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)},此時(shí)則有

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)系的運(yùn)算結(jié)果都建立了新的關(guān)系，而且也都是從X到Y(jié)的關(guān)系.以前有關(guān)集合運(yùn)算的一些公式

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

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

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

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

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

為

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

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

有些書上將符號(hào)“?！睂懗伞啊觥?。

補(bǔ)例設(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ù)合運(yùn)算滿足結(jié)合律，故可以將復(fù)合運(yùn)算中的括號(hào)除去，亦即有

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

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

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

定義2.4設(shè)有一個(gè)集合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是一個(gè)從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,如對(duì)任意xeX,有(x,x)eR,則稱R是自反的。

定義2.7在集合X上的關(guān)系R,如對(duì)任意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)系既不是自反的也不是反自反的，由此可知，一個(gè)關(guān)系的自反性與反自反性可以都不存在。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⑴斤1⑵氏2⑶&3

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

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

⑵R2是反自反的、反對(duì)稱的。

⑶Rs是對(duì)稱的。

⑷R’是自反的、反對(duì)稱的、傳遞的。

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

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

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

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

⑵R'2R；

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

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

例2.21整數(shù)集Z上的關(guān)系的自反閉包是關(guān)系；它的對(duì)稱閉包是關(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個(gè)元素，則

t(R)=RuR2oR3u---uRn

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

補(bǔ)例設(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如果是自反的、反對(duì)稱的、傳遞的，則稱R在X上是偏序的或稱R是集合

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

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

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

例2.27整數(shù)集Z上的(不是偏序的符號(hào))是偏序關(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上有一個(gè)偏序關(guān)系“V”且設(shè)Y是X的一個(gè)子集，則

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

y是Y的最小元素。

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

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

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

下界。

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

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

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

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

之間概念的不同。

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

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

上的‘七”關(guān)系是一個(gè)偏序關(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。

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

法可描述如下：

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

x畫于結(jié)點(diǎn)y的下面，如x與y間不存在另一個(gè)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)系的哈斯圖

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

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

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

補(bǔ)例：已知集合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上的最大元無(wú)，最小元為1,極大元有24和9,極小元有1。

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

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

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

2.7等價(jià)關(guān)系

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

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

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

這個(gè)關(guān)系是等價(jià)關(guān)系，因?yàn)橛?/p>

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

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

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

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

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

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

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

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

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

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

⑵A1uA2u---oAm=S

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

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

價(jià)類：

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

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

質(zhì)：

(1)xe[x]R

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

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

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

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

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

X/Ro

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

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

在I上的這種等價(jià)關(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,⑵目

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

在I上的這種等價(jià)關(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}

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

定理2.12任一個(gè)集合X上的一個(gè)劃分C可產(chǎn)生一個(gè)等價(jià)關(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)系圖

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

由等價(jià)關(guān)系所構(gòu)成的等價(jià)類在圖中即是等價(jià)關(guān)系圖中的完全圖。由上例中可看出等價(jià)關(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ù)又叫映射，它建立了從一個(gè)集合到另一個(gè)集合的一種對(duì)應(yīng)關(guān)系。設(shè)有集合X與Y,如果有一種對(duì)應(yīng)關(guān)

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

從X到Y(jié)的映射。x所對(duì)應(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)系可表達(dá)如下：

XY

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

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

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

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

出現(xiàn)一次；

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

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

X”x3,X4o

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

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

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

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

補(bǔ)例：集合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)系一樣，一個(gè)函數(shù)f：X-Y有定義域與值域，一般用Df表示DH),用Cf表示C(f)。由定義可知，對(duì)

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

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

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

cf={yi,y2,y5}

定義3.2一個(gè)函數(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一個(gè)函數(shù)f:XfY,如果對(duì)任一i,j若x.Xj,則有f(xJ*f(Xj),則此函數(shù)稱為從X到Y(jié)的單射

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

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

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

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

補(bǔ)例：集合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不是單射，不是滿射，不是雙射。

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

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

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

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

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

補(bǔ)例：集合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。。也是一個(gè)函數(shù)h:X-Z,

即

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

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

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

補(bǔ)例：已知函數(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

補(bǔ)例：已知函數(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)系中，任一個(gè)關(guān)系均存在逆關(guān)系，但對(duì)函數(shù)而言就有所不同了，每個(gè)函數(shù)不一定都有反函數(shù)。

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

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

Y—X

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

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

反例。

解：gd一定是一對(duì)一映射，證明如下：

'''g:B—*C是一對(duì)一映射

...對(duì)任意ceC,至多存在一個(gè)

beB,使得g(b)=c

又:A—>B是一■對(duì)一?映射

至多存在一個(gè)

aeA,使得f(a)=b

..?對(duì)任意ceC,至多存在一個(gè)

aeA,使得g4(a)=c

g°f一定是一對(duì)一映射。

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

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

Tg:B-C是滿射

???對(duì)任意cwC,至少存在一個(gè)

beB,使得g(b)=c

又:A-B是滿射

..?至少存在一個(gè)

aeA,使得f(a)=b

，對(duì)任意ceC,至少存在一個(gè)

aeA,使得g4(a)=c

，gof一定是滿射。

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

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

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

，對(duì)任意ceC,存在唯一

beB,使得g(b)=c

又:A->B是雙射

???存在唯一

aeA,使得f(a)=b

，對(duì)任意ceC,存在唯一

aeA,使得gof(a)=c

??.gof一定是雙射。

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

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

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

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

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

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

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

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

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

⑴有一個(gè)非空集合S;

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

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

下面對(duì)這3個(gè)條件作一些必要的說(shuō)明。

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

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

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

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

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

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

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

一個(gè)在集合S上具有運(yùn)算“。”的代數(shù)系統(tǒng)可以寫為(S,。)。

例5.1一個(gè)在整數(shù)集I上且?guī)в屑臃ㄟ\(yùn)算的系統(tǒng)構(gòu)成了一個(gè)代數(shù)系統(tǒng)(1,+)。因?yàn)樗幸粋€(gè)集合

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

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

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

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

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

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

例5.5代數(shù)系統(tǒng)(N,+)與代數(shù)系統(tǒng)(I,X)是相同類型的，因?yàn)樗鼈兌加幸粋€(gè)二元運(yùn)算符。

例5.6代數(shù)系統(tǒng)(I,+,X)與(N,+)的類型是不相同的，因?yàn)樗鼈兊倪\(yùn)算符的個(gè)數(shù)不同。

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

(I)S，aS；

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

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

這個(gè)定義還可推廣至多個(gè)運(yùn)算符的情況。

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

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

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

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

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

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

1.結(jié)合律

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

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

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

行的任何運(yùn)算均不需設(shè)置括號(hào)，如：

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

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

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

2.交換律

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

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

集合的并運(yùn)算和交運(yùn)算滿足交換律，差運(yùn)算不滿足交換律。

3.分配律

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

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

則稱此代數(shù)系統(tǒng)中的運(yùn)算“?！睂?duì)運(yùn)算“*”滿足第一分配律。

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

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

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

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

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

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

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

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

位元素。

注意：?jiǎn)挝辉氐姆?hào)“1”不一定具有自然數(shù)1的含義，它僅僅是單位元素的符號(hào)表示。

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

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

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