離散數(shù)學(xué)之代數(shù)系統(tǒng)篇

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

第34章代數(shù)結(jié)構(gòu)

本章將從引入一般代數(shù)系統(tǒng)出發(fā)，研究如群、環(huán)、域等這樣一些代數(shù)系統(tǒng)，

而這些代數(shù)系統(tǒng)中的運算所具有的性質(zhì)確定了這些代數(shù)系統(tǒng)的數(shù)學(xué)結(jié)構(gòu)。

§3-1-1代數(shù)系統(tǒng)的概念

在計算機科學(xué)中，常用代數(shù)系統(tǒng)去描述機器可計算函數(shù)，研究運算的復(fù)雜性，

分析程序設(shè)計語言的語義等。

由非空集合和該集合上的一個或多個運算所組合的系統(tǒng)，常稱為代數(shù)系統(tǒng)，有

時簡稱為代數(shù)。在研究代數(shù)系統(tǒng)之前，首先考察一個非空集合上運算的概念，如

將有理數(shù)集合Q上的每一個數(shù)a的映射成它的整數(shù)部分［?］；或者將Q上的每一

個數(shù)a映射成它的相反數(shù)-a,這兩個映射可以稱為集合Q上的一元運算；而在集

合Q上，對任意兩個數(shù)所進行的普通加法和乘法都是集合Q上的二元運算，也可以

看作是將Q中的每兩個數(shù)映射成一個數(shù)；至于對集合Q上的任意三個數(shù)打，必，冷，

代數(shù)式打2+小，心2和X1+X2+X3分別給出了Q上的兩個三元運算，它們分別將Q中

三個數(shù)映射成Q中的一個數(shù)。上述這些例子有一個共同的特征，那就是其運算的結(jié)

果都是在原來的集合中，我們稱那些具有這種特征的運算是封閉的，簡稱閉運算。

相反地，沒有這種特征的運算就是不封閉的。

很容易舉出不封閉運算的例子，設(shè)N是自然數(shù)集，Z是整數(shù)集，普通的減法是

NxN到Z的運算，但因為兩個自然數(shù)相減可以不是自然數(shù)，所以減法運算不是自然

數(shù)集N上的閉運算。

定義3-L1.1設(shè)A和B都是非空集合，n是一個正整數(shù)，若是A"到B的一個映

射，則稱是A到B的一個〃元運算。當(dāng)B=A時，稱是A上的"元運算（”-aryoperation）,

簡稱A上的運算。并稱該〃元運算在A上是封閉的。

例3-LL1（1）求一個數(shù)的倒數(shù)是非零實數(shù)集R*上的一元運算。

（2）非零實數(shù)集R"上的乘法和除法都是R*上的二元運算，而加法和減法不是。

（3）S是一非空集合，5$是S到S上的所有函數(shù)的集合，則復(fù)合運算。是SS上的

二元運算。

（4）空間直角坐標(biāo)系中求點（x,y,z）的坐標(biāo)在x軸上的投影可以看作實

數(shù)集R上的三元運算/1（X,y,z）=x,因為參加運算的是有序的3個實數(shù)，而結(jié)果也

是實數(shù)。

通常用等。，?，*,……等表示二元運算，稱為算符。若/:SXS-S是集合

S上的二元運算，對任意x,yS,如果x與y運算的結(jié)果是z,即/(x，y)=z,可利用

運算。簡記為，xoy=zo

類似于二元運算，也可以使用算符來表示〃元運算。如〃元運算

fCa/,如…，%)=6可簡記為

o(41，42，........，a〃)=b

n=\時。(?|)=b是一元運算

〃=2時-O(田，。2)=b是二兀運算

"=3時o(4|,a2,a3)=b是二兀運算

這些相當(dāng)于前綴表示法，但對于二元運算用得較多的還是四。"2=。，以下所

涉及的n元運算主要是一元運算和二元運算。

若集合X={xi，也，……，X"}是有限集，X上的一元運算和二元運算也可用

運算表給出。表3-1-1.1和3-1-12分別是一元運算和二元運算的一般形式。

表3-1-1.1表3-1-1.2

SiO(Si)os.S2…”Sn

Si。⑸)s,S1OS1S1OS2-SQSn

ssS2OS1

2o(S2)2S2OS21S2°Sn

例

3-1-1.2

SnOSi

Sn。⑸)S?S?oS2-Sn°Sn

設(shè)集合s

={0,1},給出S的幕集(P(S)上求補運算?和求對稱差運算的運算表，其中

全集是S

解所求運算表如表3-1-L3和表3-1-1.4所示。

表3-1-1.3表3-1-1.4

Si?(Si){0){1}{0,1}

{0.1}{0){1}{0,1}

{0}{1}{0}{0){0,1}{1}

{1}{0}{1}{1}{0,1}{0}

{011}{0,1}{011}{1}{0}

定義3-1-1.2一個非空集合A連同若干個定義在該集合上的運算力，

力，...，1A所組成的系統(tǒng)稱為一個代數(shù)系統(tǒng)(algbraicsystem)。記作VA,力，

于2,...，°

如果對集合S,由S的嘉集(P(S)以及該幕集上的運算“U”、"C

組成一個代數(shù)系統(tǒng)〈①(S),u,n,?＞，S|￡＜?(s),Si的補集?s尸s-Si也

常記為1O又如整數(shù)集Z以及Z上的普通加法“+”組成一個系統(tǒng)＜Z,+＞o值

得注意的是，雖然代數(shù)系統(tǒng)有許多不同的形式，但它們可能有一些共同的運算。

例如，考察上述代數(shù)系統(tǒng)VZ,+＞。很明顯，在這個代數(shù)系統(tǒng)中，關(guān)于加法

運算，具有以下二個運算規(guī)律，即對于任意的無，y,ZWZ,有

⑴x+y=y+x佼換律)

(2)(x+y)+z=x+(y+z)(結(jié)合律)

又如，設(shè)S是集合，。(S)是S的基集，則代數(shù)系統(tǒng)(＜?(S),U＞和〈7

(S),。＞中的口、。都適合交換律，結(jié)合律，即他們與＜Z,+＞有類似的運

算性質(zhì)。

§3-1-2代數(shù)系統(tǒng)的運算及其性質(zhì)

對給定的集合，我們可以相當(dāng)任意地在這個集合上規(guī)定運算使它成為代數(shù)系

統(tǒng)。但我們所研究的是其運算有某些性質(zhì)的代數(shù)系統(tǒng)。在前面考察幾個具體的代

數(shù)系統(tǒng)時一，已經(jīng)涉及到我們所熟悉的運算的某些性質(zhì)。這一節(jié)，主要討論一般二

元運算的一些性質(zhì)。

定義3-1-2.1設(shè)是定義在集合S上的二元運算，如果對于任意的x,yCS,

都有則稱二元運算是可交換的或稱運算滿足交換率(commutativelaw)。

例3-1-2.1設(shè)Z是整數(shù)集，△,☆分別是Z上的二元運算，其定義為，對

任意的a,6GZ,a/\b—ab—a-h,3b=ab—a+b,問Z上的運算/\,☆

分別是否可交換？

解：因為a/\b=ab—a—b-ba-b—a=bAa對Z中任意元素a,b成

立，所以運算△是可以交換的。

又因為對Z中的數(shù)0,1,Oiirl=0X1-0+1=1,1☆0=lX0—1+0=-1,

所以，O+lWl+O,從而運算☆是不可交換的。

定義3-1-2.2設(shè)*是定義在集合S上的二元運算，如果對于S上中的任意

元素x,y,z都T,(x*y)*z=x*(y*z)，則稱二元運算*是可以結(jié)合的或稱

運算*滿足結(jié)合律(associativelaw)。

例3-1-2.2設(shè)Q是有理數(shù)集合，。，*分別是Q上的二元運算，其定義為，

對于任意的a,bGQ,aob=a,aoh=a—2h,證明運算。是可結(jié)合的并說明

運算*不滿足結(jié)合律。

證明：因為對任意的mb,c-GQ,

(aOb')oc=aoc=a

ao(hoc)=aoh=a

所以Caob)oc=ao(boc),即得運算。是可以結(jié)合的。

又因為對Q中的元0,1

(0*0)*1=0*1=0—2=2

0*(0*1)=0*(—2)=0—2X(—2)=4

所以，(0*0)*120*(0*1),從而運算*不滿足結(jié)合律。

對于滿足結(jié)合律的二元運算，在-一個只有該種運算的表達式中，可以去掉標(biāo)

記運算順序的括號。例如，實數(shù)集上的加法運算是可結(jié)合的，所以表達式Q+y)

+可簡寫為x+y+"+v。

若VS,。＞是代數(shù)系統(tǒng)，其中。是S上的二元運算且滿足結(jié)合律，〃是正整

數(shù)，a@S,那么，aoaoa...oa是S中的~■個元素，稱其為a的〃次幕，

記為a"。

關(guān)于a的累，用數(shù)學(xué)歸納法不難證明以下公式

a八機o—an=a4機+〃(za/n)xn=a_mn

其中機，〃為正整數(shù)。

定義3-1-2.3設(shè)。，*是定義在集合S上的兩個二元運算，如果對于任意

的x,y,z《S,都有xo(y*z)=(xoy)*(xoz)

(y*z)ox=(yox)*(zox)

則稱運算。對運算*是可分配的，也稱。對運算*滿足(適合)分配律(distributive

law)。

例3-1-2.3設(shè)集合A={0,1},在A上定義兩個二元運算。和*如表3-1-2.1

和表3-1-2.2所示。試問運算*對運算。和運算。對運算*分別是否是可分配的？

表3-1-2.1表3-1-2.2

［表3-122

O0*01

_____0_01000

110101

解：容易

驗證運算*對運算。是可分配的，但運算。對運算*是不滿足分配律的。因

1O(0*1)=101=1而(1。0)*(1O1)=1*0=0

所以，。對*不滿足分配律。

定義3-1-2.4設(shè)。和*是集合S上的兩個可交換的二元運算，如果對任意

x,yS的都有x*(尤。y)=xxo(x*y)=x

則稱運算。和*滿足吸收律(absorptivelaw)。

例3-1-2.4設(shè)(P(S)是集合S上的塞集，集合的并“”和交“”是

①(S)上的兩個二元運算，驗證運算和運算滿足吸收律。

解：對任意A,B0(S),由集合相等及和的定義可得

A(AB)=AA(AB)=A

因此，和滿足吸收律。

定義3-1-2.5設(shè)*是集合S上的二元運算，如果對于任意的xS,都有x

*x=x,則稱運算*是等塞的，或稱運算*滿足基等律(ildempotentlaw)。

例3-1-2.5設(shè)Z是整數(shù)集，在Z上定義兩個二元運算。和*,

對于任意x,yZ,xoy=max(x,y)；x*y=min(x,y)

驗證運算*和。都是幕等的

解：對于任意的xZ,有

xox=max(x,x)=x；x*x=min(x,x)=x

因此運算*和運算。都是等事的。

定義3-1-2.6設(shè)。是定義在集合S上的一個二元運算，如果有一個元素，

使得對于任意元素xS都有則稱e為S中關(guān)于運算。的左幺元(leftidentiy)；女果有

一個元素，使對于任意的元都有，則稱為S中關(guān)于運算。的右幺元(rightidentity)；

如果S中有一個元素e,它既是左幺元又是右幺元，則稱e是S中關(guān)于運算。的

幺元(identity)。

在整數(shù)集Z中加法的幺元是0,乘法的幺元是1；設(shè)S是集合，在S的事集

①(S)中，運算的幺元是①，運算的幺元是S。

對給定的集合和運算，有些存在幺元，有些不存在幺元。

例如，R*是非零的實數(shù)的集合，。是R*上如下定義的二元運算，對任意的元

素a,bR*,aob=b則R*中不存右幺元；但對任意的aR*對所有的/求*都有

aoh=b

所以，R"的任一元素a都是運算。的左幺元，R*中的運算。有無窮多左幺元,

沒有右幺元和幺元。

又如，在偶數(shù)集合中，普通乘法運算沒有左幺元，右幺元和幺元。

定理3-1-2.1設(shè)*是定義在集合S上的二元運算，和分別是S中關(guān)于運算

*的左幺兀和右幺兀，則有e=e=e

月.e為S上關(guān)于運算*的唯一的幺元。

證明：因為和分別是S中關(guān)于運算*的左幺元和右幺元，所以

把e=e記為e,假設(shè)S中存在ei，則有e=e*e=e

所以，e是S中關(guān)于運算*的唯一幺元。

定義3-1-2.7設(shè)*是定義在集合S上的一個二元運算，如果有一個元S,

使得對于任意的元素xA都有*m，則稱為S中關(guān)于運算*的左零元；如果有一

元素S,對于任意的元素xS都有x*=,則稱為S中關(guān)于運算*的右零元；如果

S中有一元素，它既是左零元又是右零元，則稱為S中關(guān)于運算*的零元

(zero.element)o

例如，整數(shù)集Z上普通乘法的零元是0,加法沒有零元；S是集合，在S的

事集0(S)中，運算的零元是S,運算的零元是①，在非零的實數(shù)集R*上定義運算

*，使對于任意的元素。,〃R*,有a*b=a

那么，R*的任何元素都是運算*的左零元，而R"中運算*沒有右零元，也

沒有零元。

定理3-1-2.2設(shè)是集合S上的二元運算，和分別是S中運算。左零元和右

零元，則有==且是S上關(guān)于運算。的唯一的零元。

這個定理的證明與定理3-1-2.1類似。

定理3-1-2.3設(shè)VS,*＞是一個代數(shù)系統(tǒng)，其中*是S上的一個二元運

算，且集合S中的元素個數(shù)大于1,若這個代數(shù)系統(tǒng)中存在幺元e和零元，則e。

證明：(用反證法)若e=,那么對于任意的xS,必有x=e*x=*x==e,

于是S中所有元素都是相同的，即S中只有一個元素，這與S中元素大于1矛

盾。所以，e。

定義3-1-2.8設(shè)VS,*＞是代數(shù)系統(tǒng)，其中*是S上的二元運算，eS是S

中運算*的幺元。對于S中任一元素x,如果有S中元素y使y*x=e,則稱y

為x的左逆元；若有S中元素y使x*y=e,則稱y為x的右逆元；如果有S

中的元素y,它既是x的左逆元，又是x右逆元，則稱y是x的逆元(inverse)?

例如，自然數(shù)集關(guān)于加法運算有幺元0且只有0有逆元，0的逆元是0,其

它的自然數(shù)都沒有加法逆元。設(shè)Z是整數(shù)集合，則Z中乘法幺元為1,且只有一

1和1有逆元，分別是一1和1；Z中加法的幺元是0,關(guān)于加法，對任何整數(shù)x,

x的逆元是它的相反數(shù)一X,因為(-x)+x=0=x+(—X)O

例3-1-2.6設(shè)集合A={a,a,a,a,a,a},定義在A上的一-個二元運算*如表

3-1-2.3所示，試指出代數(shù)系統(tǒng)VA,*＞中各元素的左、右逆元的情況

表3-123

解：由表可知，a是幺元，a的逆元是a,a的左逆元和右逆元都是a,即a

和a互為逆元；a的左逆元是念，而右逆元是a，a有兩個右逆元a和a,a有左

逆元a,但a沒有右逆元。

一般地，對給定的集合和其上的一個二元運算來說，左逆元、右逆元、逆元

和幺元、零元不同，如果幺元和零元存在，一定是唯一的，而左逆元、右逆元、

逆元是與集合中某個元素相關(guān)的，一個元素的左逆元不一定是右逆元，一個元素

的左(右)逆元可以不止一個，但一個元素若有逆元則是唯一的。

定理3-1-2.4設(shè)〈S,*〉是一個代數(shù)系統(tǒng)，其中*是定義在S上的一個

可結(jié)合的二元運算，e是該運算的幺元，對于x《S,如果存在左逆元”和右元素

和右元素孫，則有

yi=yr=y

月.y是x的唯一的逆元。

證明：y=y*e=y*(x*y)=(y*x)*y=e*y=y令y=y=y,則y是x

的逆元，假設(shè)也是x的逆元，

則有yi1*e=y\*(x*y)=(y\*x)*y=e*y=y

所以，y是x的唯一的逆元。

由這個定理可知，對于可結(jié)合的二元運算來說，元素x的逆元如果存在則是

唯一的，通常把x的唯一的逆元記為

例如，若N和Z分別表示自然數(shù)集和整數(shù)集，x為普通乘法，則代數(shù)系統(tǒng)＜

N,x＞中只有幺元1有逆元，＜Z,x＞中只有-1和1有逆元，若十為普通的

加法，則代數(shù)系統(tǒng)

＜Z,+＞中所有元素都有逆元。

例3-1-2.7對于代數(shù)系統(tǒng)＜NQ+后〉，其中k是正整數(shù)，N={O,1,…,hl},

+是定義在N上的?！┘臃ㄟ\算，定義如下：對任意的x,yGN,

x+y,若x+y＜k;

%+*y=〈...

x+y-k,若x+y＞/:.

試問是否每個元素都有逆元？

解：容易驗證，+是一個可結(jié)合的二元運算，N中關(guān)于運算+的幺元是0,

N中每個元素都有唯一的逆元，即0的逆元是0,每個非零元x的逆元是k-X。

定理3-1-2.5設(shè)VS,*＞是代數(shù)系統(tǒng)，其中*是S上可結(jié)合的二元運算，

S有單位元e,若S中的每個元有右逆元，則這個右逆元也是左逆元，從而是該

元唯一的逆元。

證明：對任一元素a￡S,由條件可設(shè)b,cGS,b是。的右逆元，c是b

的右逆元。

因為6*(a*b)=b*e=b,所以

e=b*c=(b*(a*b))*c

=b*((a*b)*c)

=b*(a*(b*c))

=b*(a*e)=h*a

因此，b也是。的左逆元

從而由定理3-1-24知，匕是a的唯一逆元，由“GS的任意性知定理成立。

若vs,。＞是代數(shù)系統(tǒng)，其中。是有限非空集合S上的二元運算，那么該運

算的部分性質(zhì)可以從運算表直接看出，例如

1.當(dāng)且僅當(dāng)運算表中每個元素都屬于S中，運算。具有封閉性。

2.當(dāng)且僅當(dāng)運算表關(guān)于主對角線對稱時，運算。具有可交換性。

3.當(dāng)且僅當(dāng)運算表的主對角線上的元素與它所在行(列)的表頭相同時，

運算。具有幕等性。

4.S關(guān)于運算。有幺元e,當(dāng)且僅當(dāng)表頭e所在的列與左邊一列相同且表中

左邊一列e所在的行與表頭一行相同。

5.S關(guān)于運算。有零元。，當(dāng)且僅當(dāng)表頭9所在的列和表中左邊一列0所在

的行都是。。

6.設(shè)S關(guān)于運算。有幺元，當(dāng)且僅當(dāng)位于a所在的行與人所在的列交叉點

上的元素以及b所在的行與?所在的列交叉點上的元素都是幺元時，。與6互逆

0

代數(shù)系統(tǒng)＜S,?！抵幸粋€元素是否有左逆元或右逆元也可從運算表中觀察出

來，但運算是否滿足結(jié)合律在運算表上一般不易直接觀察出來。

§3-1-3半群與含幺半群

半群及含幺元群是特殊的代數(shù)系統(tǒng)，在計算機科學(xué)領(lǐng)域中，如形式語言，自

動機理論等方面，它們已得到了卓有成效的應(yīng)用。

定義3-1-3.1設(shè)＜S,*＞是一個代數(shù)系統(tǒng)，*是5上的一個二元運算，

如果運算*是可結(jié)合的，即對任意的WS,都有(x*y)*z=x*(y*z),則

稱代數(shù)系統(tǒng)VS,*＞為半群(semigroup)。

半群中的二元運算也叫乘法，運算的結(jié)果也叫積。

由定義易得，＜N,+＞,＜N,x＞是半群，其中N是自然數(shù)集，“+”，“x”

分別是普通的加法和乘法。A是任一集合，①(A)是A的基集，則〈①(A),U＞,

＜＜P(A),都是半群。

例3-1-3.1設(shè)5=僅/1},5上的一個二元運算的定義如表3-1-3.1所示，

驗證＜S,＞是半群。

表3-1-3.1

oabc

aabc

babc

解：由表cabC3-1-3.1知運算。

在S上是封閉的而且對任意打,無2

es有"所以＜S,O＞是代數(shù)系統(tǒng)，且a,。,C都是左幺元，

從而對任意的x,y,zGS都有xo(yoz)=xoz=z=yoz=(xoy)。工因此，

運算。是可結(jié)合的，是半群。

例3-1-3.2設(shè)k是一個非負整數(shù)，集合定義為&={xlx是整數(shù)且X2。，

那么,VSk,+＞是半群，其中+是普通的加法運算。

解：因為上是非負整數(shù)，易知運算+在也上是封閉的，而且普通加法運算

是可結(jié)合的，所以＜1,+＞是半群。

易知，代數(shù)系統(tǒng)VZ,—＞,VR-{0},/＞都不是半群,這里“一”和“/”分

別是普通的減法和除法。

定理3-1-3.1設(shè)VS,*＞是半群，B是S的非空子集，且二元運算*在B

上封閉的，即對任意的a/WB有a*6B。那么，＜B,*＞也是半群。通常稱＜B,*

＞是＜5,*＞的子半群(sub-semigroup)

證明：因為運算*在S上是可以結(jié)合的，而B是S的非空子集且*在B是

上的封閉的，所以*在B上也是可結(jié)合的，因此，VB,*＞是半群。

例3-1-2.3設(shè)?表示普通的乘法運算，那么V{—1,1},?＞,＜[-1,1],

?＞和

＜2,?＞都是半群＜R,?＞的子半群。

解：首先，運算?在R上是封閉的，且是可結(jié)合的，所以＜1＜,?＞是半群。

其次，運算?在{-1,1},[—1,1]和Z上都是封閉的，{-1,1}」—1,1]和Z都是

R的非空子集，由定理3-1-3.1可知＜{-1,1},?＞、＜[-1,1],?＞和＜Z,

?＞都是＜R,?＞的子半群。

定義3-1-3.2半群VS,。＞中的任一元素a的方幕。定義為

a=a,a=aoa(M是大于等于1的整數(shù))

可以證明，對于任意的aS和任意正整數(shù)機,〃都有

aoa=a

(a)=a

若a=a，則稱a為基等元素(idempotentelement)o

定理3T-3.2設(shè)VS,*＞是半群，若S是一有限集，則S中有基等元。

證明：因為＜S,*＞是半群，對于任意yS的由運算*的封閉性可知,y=y*yS,

y=y*y=y*yS,因為S是有限集，所以必定存在正整數(shù)i,/使得且y=y

記機=j-i,則有y=y*y從而對任意〃＞i,

y=y*y=y*yy=y*y因為，〃2，1,所以總可以找至此＞1,

使得女機2i對于S中的元素y,

就有y=y*y=y*y*y

==y*(y*y)=???=y^yo

所以a=y是S中的基等兀。

定義3T-3.3若半群＜S,。〉的運算。滿足交換律，則稱＜S,。〉是一個可

交換半群。

在可交換半群VS,。》中，有3。。)=。昉其中〃是正整數(shù)，a,bS。

定義3-1-3.4含有幺元的半群稱為含幺半群或獨異點(monoid)。

例如，代數(shù)系統(tǒng)＜R,?＞是含幺半群，其中R是實數(shù)集，?是普通乘法，這

是因為

＜1^,?＞是半群，且1是R關(guān)于運算?的幺元。

另外代數(shù)系統(tǒng)〈｛-1，1｝，*＞,＜[-1,1J,?＞,和＜Z,?＞都是具有幺

元1的半群。因此它們都是含幺半群。

設(shè)集合A=｛1,2,3，…｝則VA,+＞是半群但不含幺元。所以它不是含

幺半群。

例3-1-3.4設(shè)￡是非空有限字母表，￡*是￡中的有限個字母組成的符號串

的集合，符號串中字母的個數(shù)“叫做這個符號串的長度，當(dāng)加=0是用符號人表

示，叫做空串。在X*上定義連接運算貝2=。如若=5￡乂1,=GROUP,

=SEMIGROUPo

代數(shù)系統(tǒng)〈￡*,。〉是含幺半群，且幺元是A。

定理3-1-3.3設(shè)S是至少有兩個元的有限集且VS,*＞是一個含幺半群，

則在關(guān)于運算*的運算表中任何兩行或兩列都是不相同的。

證明：設(shè)S中的關(guān)于運算*的幺元是e。因為對于任意a,bS的且ah是，

總有

e-ab-e^ba^e-ab-b*e

所以在運算*表中不可能有兩行和兩列是相同的。

定理3-1-3.4設(shè)是含幺半群，對于任意的，當(dāng)均有逆元時，有

(1)

(2)有逆元，且。

證明：(1)因是的逆元，所以，從而由逆元的定義及唯一性得。

(2)因為

同理可證

所以，由逆元的定義及唯一性得。

例3-1-3.5設(shè)是整數(shù)集合，是任意正整數(shù)，是由模的同余類組成的集合，

在上分別定義兩個二元運算+,”和X,”如下：

對任意的

試證明時，在這兩個二元運算的運算表中任何兩行或兩列都不相同。

證明：考察非空集合上二元運算和x,”，

(1)由運算+,”和X,”的定義易得，運算+,“和X,”在上都是封閉的且都是可結(jié)

合的，所以，，都是半群。

(2)因，所以是中的幺元；因為，所以是中的幺元。

由上知，代數(shù)系統(tǒng)，都是含幺半群。從而由定理3-1-3.3知，中的兩個運算,

的運算表的任何兩行或兩列都是不相同的。

下面表3-1-3.2和表3-1-3.3分別給出時，和的運算表，在這兩個運

算表中沒有兩行或兩列時相同的。

表3-1-3.2

4-,rmrnr?im

roiroirn⑵Hl

rnni⑵Hlroi

⑵⑵F31roirn

「31mmirn⑵

表3-1-3.3

Xiroirnr?iRI

101101roiroi101

mroirn⑵「31

F21roi⑵rm⑵

mroini171「11定

義

3-1-3.5設(shè)是含幺半群的子半群，且的幺元，則稱為的子含幺半群（submonoid）。

由定義可得，子含幺半群也是含幺半群。

例3-1-3.6代數(shù)系統(tǒng)，中運算“”如表3-1-3.4所示。

易得是含幺半群且幺元為0;是的子半群且有幺元表3-1-3.4

1,從而是含幺半群，但不是的子含幺半群。

V01

證明：設(shè)是可換含幺半群且幺元為，，因為所以又001

因為對任意，有111

所以從而運算在上是封閉的，故是的子含幺半群。

如是含幺半群，中所有幕等元的集合為，所以是的子含幺半群。

§3-1-4群與子群

群是一種較為簡單的代數(shù)系統(tǒng)，只有一個二元運算。當(dāng)然這一運算還應(yīng)滿足

一定的條件。正是由于這些條件使我們能夠利用這種運算系統(tǒng)去描述事物的對稱

性和其他特性。群的理論在數(shù)學(xué)和包括計算機科學(xué)在內(nèi)的其他學(xué)科的許多分支中

發(fā)揮了重要的作用，本節(jié)主要介紹群與子群的一些基本知識。

定義3-1-4.1設(shè)是一個代數(shù)系統(tǒng)，其中是非空集合，是上的一個二元運算,

如果

（1）運算。是封閉的；

（2）運算。是可結(jié)合的；

（3）中有幺元；

（4）對每個元素，中存在的逆元；

則稱是一個群（Group）或簡稱是群。

由定義可得群一定是含幺半群，反之不一定成立。

例3-1-4.1若集合，定義二元運算。為，則是半群。事實上，由運算。的定

義可得，適合群定義的條件(1),(2),又是的幺元，的逆元是，所以是群。

例3-1-4.2有理數(shù)集關(guān)于普通加法構(gòu)成群，幺元是，，的逆元是；類似地

若是整數(shù)集，則是群；但是只含幺元的半群而不是群。

例3-1-4.3設(shè)，二元運算“?！庇杀?-1-4.1給出，則是一個群。

表3-1-4.1

Oabc

aabc

bbca

ccab

事實上，運算在上是封閉的，是單位元，，但結(jié)合律是否成立不易從表上看

出，驗證適合結(jié)合律比較麻煩，需要驗證33=27次。但是，由于第一行、第一列

分別與表頭的行列相同，故有，對任意的成立。這樣，驗證結(jié)合律的三個元中只

要出現(xiàn)，則必然是可結(jié)合的。因此，我們只要對不包含的任意三個元驗證可結(jié)合

性即可，因而只需驗證23=8次。這里，我們只驗證一個，其余留作練習(xí)。

因此，是一個群。

定義3T-4.2設(shè)是一個群，如果是有限集，則稱是有限群(finitegroup),中

的元素個數(shù)稱為的階(order)記為，如果是無限集，則稱為無限群(infinitegroup),

也稱的階為無限。

如上面例3-1-4.1和例3-1-4.3中的群都是有限群，階數(shù)分別為1和3,例

3-1-4.2中的群和都是無限群。

下面是群的一些基本性質(zhì)

定理3-H4.1在群中，個元素的連乘積，經(jīng)任意加括號計算所得的結(jié)果相

同。

證明：我們證明任意加括號得到的乘積都等于從左到右依次加括號計算所

得的結(jié)果，即等于

采用數(shù)學(xué)歸納法，當(dāng)時，定理顯然成立?，F(xiàn)在假設(shè)對小于或等于個元素的連

乘積定理成立，則對個元素的連乘，，對任意加括號，不妨設(shè)最后時將與相乘，

下面對分三種情況討論。

（1）,這時按歸納假設(shè)有

（2）,這時利用結(jié)合律和歸納假設(shè)可得

P=（?i?！?。4T）°（氏。4+1）

=（（?i?！?。*）。4）。4+1

=（???（（?!°a2）oa3）--oak）ak+l

（3）這時用歸納假設(shè)，再對p的表達式用結(jié)合律和歸納假設(shè)，我們有

由數(shù)學(xué)歸納法原理知定理成立。

由這個定理知，在群中個元的連乘任意加括號進行計算所得最后結(jié)果是一樣

的，故可以將其簡記為而不致誤解。特別當(dāng)時可表示為。

由定理3-24.1的證明知，這個定理的結(jié)論在半群中成立。

與定理3-1-3.5類似，我們有以下結(jié)論

定理3-1-4.2設(shè)是群，則中任意個元有，對群中任一元素，我們約定

為正整數(shù)

我們?nèi)菀椎玫揭韵陆Y(jié)果

定理3-1-4.3若是群，則對任一元素和任意整數(shù)有

（1）

（2）

定理3-1-4.4在群中成立消去律，即對，

（1）若,則，

（2）若，則。

證明：（1）因為是群，，所以，存在的逆元，用從左邊乘兩邊，可得

所以

（2）的證明與（1）類似。

定理3-1-4.5設(shè)是一個群，則對任意的有

（1）存在唯一的元素，使；

（2）存在唯一的元素，使。

證明：因為，所以至少有一個是滿足。若是中另一個滿足方程的元素，

則。由定理3-14.4知。因此，是中唯一滿的元素。

（2）與（1）同理可證。

定理3-1-4.6是群，，則是幕等元當(dāng)且僅當(dāng)是的幺元。

證明：因為，所以是的事等元。

現(xiàn)設(shè)，，若，貝IJ

與矛盾。

由定理3-14.4知，有限群的運算表中，設(shè)有兩行（或兩列）是相同的。為

進一步考察群的運算表的性質(zhì)，下面引進置換的概念。

定義3-1-4.3設(shè)是一個非空集合，從到的一個雙射稱為的一個置換

（permutation）。

例如對集合，是到的一個映射使得，，，，，則是到的一個雙射從而是的一個

置換。也可用下表表示，

即表中上一行為按任何次序?qū)懗黾现械娜吭?，而在下一行寫出上一?/p>

相應(yīng)元素的象。

定理3-1-4.7有限群的運算表中的每一行或每一列都可由中的元素經(jīng)一

個置換得到。

證明：設(shè)有限群，由的運算表的構(gòu)造知，表中的第行元素為，，…，，且集

合是的子集，因為中消去律成立，所以當(dāng)時，，從而。

作到的映射，。則是的一個置換，所以的運算表中的第行可由的元素通過置

換得到。對列的情形類似可證。

現(xiàn)在介紹子群。

定義3-1-4.4設(shè)是一個群，是的非空子集，如果也構(gòu)成群，則稱是的子群

（subgroup）o

定理3-1-4.8設(shè)是群的子群，則的幺元就是的幺元，中任意元在中的逆元

就是在中的逆元。

證明：設(shè)和分別是和的幺元，為在中逆元，則

又因為對任意，有

設(shè)是群，是的幺元，由子群的定義可得，都是的子群，稱為的平凡子群(trivil

subgroup)e若是的子群且，，則稱為的真子群(propersubgroup)。

例3-1-4.4是整數(shù)加群，，證明是的一個子群。

證明：因為，所以；

(1)對于任意的，可設(shè)，，，，，所以，即在上是封閉的；

(2)運算在上可結(jié)合，從而在上可結(jié)合；

(3)的幺元0在中也是的幺元；

(4)對與任意，有，，而

所以，使，是在中的逆元，所以是群，從而是的子群。

實際上，群的非空子集構(gòu)成子群的條件可以簡化如下。

定理3-1-4.9設(shè)是群，是的非空子集，則關(guān)于運算是的子群的充分必要

條件是：

(2)對任意的，有；

(2)對任意的，有。

證明：必要性顯然成立。

充分性條件(1)說明運算在上是封閉的；由于中的運算是可結(jié)合的，所

以中運算是可結(jié)合的；對任意，由條件(2)知，，再由條件(1),易得是的單位

元，是在中的逆元，所以是群，從而是的子群。

定理3T-4.10設(shè)是一個群，是的非空子集，則關(guān)于運算是的子群的充分

必要條件是：對任意的有。

證明：必要性易得

充分性任取，由條件，即，又因為，所以，這說明，若，貝I」，由條件可得

根據(jù)定理3-148,是的子群。

定理3T-4.11設(shè)是一個群，是的一個有限非空子集，則關(guān)于運算是群的

子群的充分必要條件是：對任意的有。

證明：必要性由子群的定義可得

充分性設(shè)是中的任一元素，由條件，，…，因為是有限集，所以必存在正

整數(shù)和，使，，不妨設(shè)，則這說明是中的幺元，這個幺元也在子集中。

如果，那幺由知是的逆元且。如果，那么由知就是幺元且的逆元就是?？傊?/p>

對任意元素，有。所以由定理3-1-4.9知是的子群。

例3-1-4.5設(shè)是群，，求證是的一個子群。

證明：設(shè)是群的幺元，貝IJ,又對任意的和任意的，有，，所以，從而。故。

由定理3-1-4.10知，是群的子群。這個子群稱為群的中心。

例3-1-4.6設(shè)和都是群的子群，試證也是的子群。

證明：設(shè)是群的幺元，則因，都是的子群，所以，，從而。對任意的，有

.且，由，都是的子群，得且，所以，故是群的子群。

例3-1-4.7設(shè)是群，是的一個固定元，，則是的子群。

事實上，得幺元，對中的任意元和，由定理3-1-4.10知是的子群。

§3-1-5交換群與循環(huán)群置換群

這一節(jié)討論幾種具體的群，這種討論不但能加深我們對群的認識，而且這幾

種群本身在理論上和應(yīng)用上都是非常重要的。

定義3-1-5.1如果群中的運算。是可交換的，則稱該群為交換群

(commutativegroup),或稱為阿貝爾(Abel)群。

例如，，，，都是交換群。

例3-1-5.1設(shè)集合，在上定義一個雙射函數(shù)：，，，，并構(gòu)造符合函數(shù)：對，

若用表示上的恒等映射，即，則有，設(shè)并構(gòu)造集合。求證，是一個交換群。

證明：上的運算的運算表由表3-1-5］給出?？梢娚系倪\算是封閉的，由

的定義可得，運算是可結(jié)合的。是的幺元，

表3-1-5.1

O01a2a3

QO

00123

QQOGQ

11230

OaOOo

2231

QQQQ

33()12

QCTaoQ

的逆元是自身，和互為逆元，的逆元是它自身。由表3-I-5.1的對稱性知,

上的運算是可交換的，所以是一個交換群。

例3-1-5.3設(shè)是一個大于1的整數(shù)，為所有階非奇(滿秧)矩陣的集合，

表示矩陣的乘法，則是一個不可交換群。

事實上，任意兩個階非奇矩陣相乘后還是一個階非奇矩陣，所以上的運算是

封閉的；矩陣的乘法運算是可結(jié)合的；〃階單位矩陣是中的幺元；任意一個非奇

的階矩陣有唯一的階逆矩陣也是非奇的且，但中的運算不是可換的，因此是一個

群，但不是交換群。

定理3-1-5.1設(shè)是一個群，則是交換群的充分必要條件是，對任意的，有

證明：必要性設(shè)是交換群，則對任意的有

因此

充分性若對任意，

則

所以即得

因此，群是交換群。

例3-1-5.2設(shè)是群，是的幺元，若對任意，都有，則是交換群。

證明：對任意的，由條件，所以，，，又所，從而，故是交換群。

定義3-1-5.2設(shè)是群，若中存在一個元素，使得中任意元素都是的暴，

即對任意的都有整數(shù)使，則稱為循環(huán)群(cyclicgroup),元素稱為循環(huán)群的生成元

(generator)o

例3-1-5.3是由1生成的無限階循環(huán)群。

例3-1-5.4設(shè)是整數(shù)集，是一正整數(shù)，是由模的剩余類組成的集合，上

的二元運算定義為：對，

則是以山為生成元的循環(huán)群。

證明：由例3-1-3.5知，是含幺半群，幺元為［0］,又中，［0］的逆元是，

時:的逆元是，所以是群，又任意，有，所以是以［1］為生成元的循環(huán)群。稱為

模的剩余類加群。

定理3-1-5.2任何一個循環(huán)群都是交換群。

證明：設(shè)是一個循環(huán)群，是它的一個生成元，那幺，對任意，必有使得，，

所以因此，是一個交換群。

對于有限循環(huán)群，有下面的結(jié)論。

定理3-1-5.3設(shè)是一個由元素生成的循環(huán)群且是有限群，如果的階是，

即，則且其中是的幺元，是使的最小正整數(shù)（稱為元素的階）。

證明：因為是有限群，，所以，存在正整數(shù)s使，假設(shè)對某個正整數(shù)使，

那幺，由于是一個生成的循環(huán)群，所以中任何元素都能寫成的形式。又，其中且。

這樣就有，所以中每個元素都能寫成的形式，這樣中最多有個不同的元素，與

且矛盾，所以是不可能的。

下面證明是互不相同的，用反證法，若其中，就有且上面已經(jīng)證明這是不可

能的。所以，是互不相同的，又，所以，，因為，，所以。

例3-1-5.5在模4的剩余類加群中，試說明［1］和⑶都是生成元。

解：因為，

所以山是循環(huán)群的生成元。

又因為

所以，［3］也是循環(huán)群的生成元。

從例3-1-5.5知，一個循環(huán)群的生成元可以不是唯一的。

下面討論另一類重要的群一一置換群。

對于一個具有個元素的集合，將上所有個不同的置換所組成的集合記為。

定義3-1-5.3設(shè)，上的二元運算和使對，和都表示對的元素先作置換接

著再作置換所得到的置換。二元運算和分別稱為左復(fù)合和右復(fù)合。

例3-1-5.6設(shè)，中的元素

則

因為都是上的雙射變換，所以它們都有逆變換并II是置換。如的逆置換

易得是使中每個元素映射到自身的置換。

為確定起見，我們在下面只對左復(fù)合進行討論。

定理3-1-5.4是一個群，其中是置換的左復(fù)合運算。

證明：首先證二元運算在上是封閉的，對任意的，若，，則因都是上的

雙射變換，所以

從而

因而是上的單射。

對，因是上的雙射變換，所以存在使，又是上的雙射變換，所以存在使，從

而，即得是上的滿射變換。故。

其次證明二元運算在上是可結(jié)合的且有幺元。

于，，記，，。

則,由于,

所以，，

同樣地，由于，

所以，，

因此，

如果將S中的每個元素映射成它自身的變換，記為，則是雙射變換，所以，

且對于任一個元素，都有，因此S"中存在幺元，稱它為置換(identicalpermutation)。

最后，對于任意的，因為b是S上的雙射變換，因此它有逆變換且也是S

上的雙射變換，所以，由于，。將映射成當(dāng)且僅當(dāng)將y映射成為x,所以，是。

在〈中的逆元，故(是群。

定義3T-5.4的任何一個子群，稱為集合S上的一個置換群(permutation

group)特別地，置換群稱為n次對稱群(symetricgroup)。

例3-1-5.7設(shè)寫出S的對稱群以及S上的其它置換群，并指出它們是否是

循環(huán)群？是否是交換群？

解：S的對稱群為，

其中如圖3-1-5.1所示，S3上左復(fù)合運算。如表3-1-52所示。

由表3-1-5.2可見，S3上的二元運算。不是可交換的，如

所以不是交換群，更不是循環(huán)群；容易得到S上的換群還有，，，，，它們都是

循環(huán)群，從而都是交換群。

表3-1-5.2

O

rrrr.c、r、rr.c「

rrr.f\■f\cf\、f\?f\=

rr.f\<t\t\Cf\1f\c，\

fTc<"、c<、?t'I\r<、1I\c

ECcCvfTiCcfTnCi

rr,f\4r\\C/\1f\，t\

rx「

§3-1-6陪集與拉格朗日定理

我們已經(jīng)討論了利用集合上的等價關(guān)系對集合進行劃分（分解），本節(jié)研究

利用子群來對群進行劃分（分解），從而研究群的一些性質(zhì)。

我們從推廣＜Z,+＞中“模相同余”的概念開始，易知，對a,bZ,,因此在

群中，，推廣到一般的群，我們有

定義3-1-6.1設(shè)是群的子群，。，bG如果，則稱。與。有二元關(guān)系RL（模

H左同余）。

即。

定理3T-6.1設(shè)vH,。＞是群＜G,。＞的子群，

則（1）RL是G上的一個等價關(guān)系；

（2）對任意其中是a所在的等價類，稱為H的左陪集（leftcoset）；

（3）=（即aH與H之間存在雙射

證明：（1）設(shè)a,b,cG,因為G的幺元eH,使a=a