第五章 代數(shù)系統(tǒng)

第三編代數(shù)系統(tǒng)本篇用代數(shù)方法來研究數(shù)學(xué)結(jié)構(gòu),故又叫代數(shù)結(jié)構(gòu),它將用抽象的方法來研究集合上的關(guān)系和運(yùn)算。代數(shù)的概念和方法已經(jīng)滲透到計算機(jī)科學(xué)的許多分支中,它對程序理論,數(shù)據(jù)結(jié)構(gòu),編碼理論的研究和邏輯電路的設(shè)計已具有理論和實踐的指導(dǎo)意義。本篇討論一些典型的代數(shù)系統(tǒng)及其性質(zhì)。第五章代數(shù)結(jié)構(gòu)

§5.1 代數(shù)系統(tǒng)概述§5.2 運(yùn)算及其性質(zhì)§5.3 半群§5.4 群與子群第五章代數(shù)結(jié)構(gòu)教學(xué)目的及要求：深刻理解和掌握代數(shù)系統(tǒng)的基本概念和運(yùn)算。教學(xué)內(nèi)容：代數(shù)系統(tǒng)的引入、運(yùn)算及性質(zhì)、半群、群與子群。教學(xué)重點：群的概念及運(yùn)算?！?.1代數(shù)系統(tǒng)概述1、代數(shù)運(yùn)算的定義定義1：設(shè)A是個非空集合，A×A到A的一個映射f，f：A×A→A稱為A上的一個二元代數(shù)運(yùn)算，簡稱二元運(yùn)算；A到A的一個映射f，f：A→A稱為A上的一個一元代數(shù)運(yùn)算，簡稱一元運(yùn)算。類似可定義n元運(yùn)算。通常用°,?,·，+，×等符號來表示二元或一元運(yùn)算符?！?.1代數(shù)系統(tǒng)概述1、代數(shù)運(yùn)算的定義例如：f是A上的二元運(yùn)算，即A×A→A的映射。

x,y∈A,f(<x,y>)=z∈A，用公式表示為：x?y=z注：映射有存在性和唯一性的要求，運(yùn)算當(dāng)然也要滿足該要求?！?.1代數(shù)系統(tǒng)概述1、代數(shù)運(yùn)算的定義例1：（1）在實數(shù)集合R上定義二元運(yùn)算?，

x，y∈R，x?y=y則2?3=3，0.5?(-1/4)=-1/4，50?0=0，0*50=50§5.1代數(shù)系統(tǒng)概述1、代數(shù)運(yùn)算的定義例1：（2）在正整數(shù)集合Z+上的二元運(yùn)算?，+

x，y∈Z+，x?y=x，y的最大公約數(shù)，x+y=x，y的最小公倍數(shù)6?8=2，6+8=24§5.1代數(shù)系統(tǒng)概述1、代數(shù)運(yùn)算的定義例1：（3）在實數(shù)集合R上定義除法運(yùn)算，這不是一個代數(shù)運(yùn)算，因0不能作為除數(shù)，運(yùn)算的存在性不滿足。例1：（4）在實數(shù)集合R上求平方根運(yùn)算，不是一個代數(shù)運(yùn)算。-9不存在平方根，存在性不滿足。9有兩個平方根：3和-3，唯一性不滿足。但在R+上求平方根運(yùn)算，是一個一元運(yùn)算。§5.1代數(shù)系統(tǒng)概述1、代數(shù)運(yùn)算的定義例2：（1）自然數(shù)集合N上的乘法是N上的二元運(yùn)算。（2）整數(shù)集合Z上的加法、減法、乘法是Z上的二元運(yùn)算，但除法不是Z上的運(yùn)算。（3）設(shè)Mn(R)表示所有n階(n≥2)實矩陣的集合，矩陣加法和乘法都是Mn(R)上的二元運(yùn)算。（4）在集合Z的冪集(z)中，，，

均為二元運(yùn)算，而“~”是一元運(yùn)算；§5.1代數(shù)系統(tǒng)概述1、代數(shù)運(yùn)算的定義例2：（5）{命題公式}中,∨,∧均為二元運(yùn)算,而“

”為一元運(yùn)算（6）{雙射函數(shù)}中,函數(shù)的復(fù)合運(yùn)算是二元運(yùn)算；§5.1代數(shù)系統(tǒng)概述2、表示二元或一元運(yùn)算的方法（1）公式法（2）運(yùn)算表：在有限集上可以將結(jié)果一一列出來定義運(yùn)算，簡便明了的方法就是畫出運(yùn)算表。二元運(yùn)算的運(yùn)算表一元運(yùn)算的運(yùn)算表

°a1

a2

…

an°aia1a2..ana1°a1

a1°a2

…

a1°ana2°a1

a2°a2

…

a2°an......an°a1

an°a2

…

an°an

a1a2..an

°a1

°a2..

°an§5.1代數(shù)系統(tǒng)概述2、表示二元或一元運(yùn)算的方法（2）運(yùn)算表：例3

A=P({a,b}),

,～分別為對稱差和絕對補(bǔ)運(yùn)算，（{a,b}為全集）

的運(yùn)算表～的運(yùn)算表

{a}{a,b}

X

～X

{a}{a,b}

{a}{a,b}{a}

{a.b}{a,b}

{a}{a,b}{a}

{a}{a,b}{a,b}{a}

§5.1代數(shù)系統(tǒng)概述3、運(yùn)算的封閉性[定義5-1.1]若對給定集合中的元素進(jìn)行運(yùn)算,而產(chǎn)生的象點仍在該集合中,則稱此集合在該運(yùn)算的作用下是封閉的。例4：（1）在正整偶數(shù)的集合E中,對×,+運(yùn)算是封閉的；在正整奇數(shù)的集合中,對×運(yùn)算是封閉的,而對+運(yùn)算不是封閉的。

（2）在集合R,I中+,-,×運(yùn)算；在(Z)的元素中∪,∩,~運(yùn)算等均為封閉的?！?.1代數(shù)系統(tǒng)的引入4、代數(shù)系統(tǒng)[定義5-1.2]一個非空集合A連同若干個定義在該集合上的運(yùn)算f1,f2,….,fk所組成的系統(tǒng)就稱為一個代數(shù)系統(tǒng)，記作<A,f1,f2,….,fk>。實例：（1）<N,+

>,<Z,+,·>,<R,+,·>是代數(shù)系統(tǒng)，+和·分別表示普通加法和乘法.（2）<Mn(R),+,·>是代數(shù)系統(tǒng)，

+和·分別表示n階(n≥2)實矩陣的加法和乘法.§5.1代數(shù)系統(tǒng)的引入[定義5-1.2]一個非空集合A連同若干個定義在該集合上的運(yùn)算f1,f2,….,fk所組成的系統(tǒng)就稱為一個代數(shù)系統(tǒng)，記作<A,f1,f2,….,fk>。實例：（3）<Zn,

,

>是代數(shù)系統(tǒng)，Zn＝{0,1,…,n

1}，

和

分別表示模n的加法和乘法，對于x,y∈Zn，

x

y=(x＋y)modn，x

y=(xy)modn（4）<(Z),∪,∩,~>也是代數(shù)系統(tǒng)，∪和∩為并和交，~為絕對補(bǔ)§5.2運(yùn)算及其性質(zhì)[定義5-2.1]設(shè)*是集合A上的二元運(yùn)算，對任一x,y

A有x

y∈A，則稱

運(yùn)算在A上是封閉的。例1：A={x｜x=2n，n∈N}，問<A，*>運(yùn)算封閉否，<A，+>，<A，/>呢？解：

2r，2s∈A，2r

*2s=2r+s∈A（ｒ＋ｓ∈Ｎ）∴<A，*>運(yùn)算封閉2，4∈A，2+4

A，∴<A，+>運(yùn)算不封閉2，4∈A，2/4

A，∴<A，/>運(yùn)算不封閉§5.2運(yùn)算及其性質(zhì)[定義5-2.2]設(shè)*是集合A上的二元運(yùn)算，對任一x,y

A有x

y=y

x，則稱

運(yùn)算在A上是可交換的（或者說

在A上滿足交換律)。[定義5-2.3]設(shè)*是集合A上的二元運(yùn)算,對任一x,y,z

A都有（x

y）

z=x

（y

z）,則稱

運(yùn)算在A上是可結(jié)合的（或者說*在A上滿足結(jié)合律）?！?.2運(yùn)算及其性質(zhì)[定義5-2.4]設(shè)

和

是集合A上的兩個二元運(yùn)算,對任一x,y,z

A有x

（y

z）=（x

y）

（x

z）；（y

z）

x=（y

x）

（z

x），則稱運(yùn)算

對

是可分配的（或稱

對

滿足分配律）。[定義5-2.5]設(shè)，是定義在集合A上的兩個可交換二元運(yùn)算，如果對于任意的x,yA，都有： x(xy)=x；x(xy)=x則稱運(yùn)算和運(yùn)算滿足吸收律。§5.2運(yùn)算及其性質(zhì)[定義5-2.6]設(shè)*是A上的二元運(yùn)算,若對任一x

A有x

x=x,則稱

滿足等冪律。討論定義：1)A上每一個元素均滿足x

x=x,稱

在A上滿足冪等律；2)若在A上存在元素x

A有x

x=x,稱x為A上的冪等元；3)由此定義,若x是冪等元素,則有x

x=x和xn=x成立?！?.2運(yùn)算及其性質(zhì)例Z,Q,R分別為整數(shù)、有理數(shù)、實數(shù)集；Mn(R)為n階實矩陣集合,n

2；P(B)為冪集；AA為A到A，|A|

2。集合運(yùn)算交換律結(jié)合律冪等律Z,Q,R普通加法+有有無普通乘法

有有無Mn(R)矩陣加法+有有無矩陣乘法

無有無P(B)并

有有有交有有有相對補(bǔ)無無無對稱差有有無AA函數(shù)復(fù)合°無有無§5.2運(yùn)算及其性質(zhì)集合運(yùn)算分配律吸收律

Z,Q,R普通加法+與乘法

對+可分配無+對不分配Mn(R)矩陣加法+與乘法

對+可分配無+對不分配P(B)并

與交

對

可分配有

對

可分配交

與對稱差

對可分配無對不分配例Z,Q,R分別為整數(shù)、有理數(shù)、實數(shù)集；Mn(R)為n階實矩陣集合,n

2；P(B)為冪集；AA為A到A，|A|

2.§5.2運(yùn)算及其性質(zhì)下面定義特異元素：幺元,零元和逆元。

[定義5-2.7]設(shè)*是集合A中的二元運(yùn)算,

(1)若有一元素el

A,對任一xA有el*x=x；則稱el為A中對于*的左幺元(左單位元素)；

(2)若有一元素erA,對任一xA有x*er=x；則稱er為A中對于*的右幺元（右單元元素）?！?.2運(yùn)算及其性質(zhì)[定理5-2.1]若el和er分別是A中對于*的左幺元和右幺元,則對于每一個xA，可有el=er=e和e*x=x*e=x，則稱e為A中關(guān)于運(yùn)算*的幺元，且eA是唯一的。證明：∵el和er分別是對*的左,右幺元，則有el*er=er=el

∴有el=er=e成立。

（2）幺元e是唯一的。用反證法：假設(shè)有兩個不同的幺元e1和e2,則有e1*e2=e2=e1,這和假設(shè)相矛盾。∴若存在幺元的話一定是唯一的?！?.2運(yùn)算及其性質(zhì)例：（1）在實數(shù)集合R中，對+而言，e+=0；對×而言，e*=1；（2）在(E)中，

而言，e

=E（全集合）；對

而言，e

=

（空集）；（3）{雙射函數(shù)}中,對“

”而言，

e

=Ix（恒等函數(shù)）；（4）{命題邏輯}中，對∨而言，e∨

=F（永假式）；對∧而言，e∧

=T（永真式）。

§5.2運(yùn)算及其性質(zhì)[定義5-2.8]設(shè)*是對集合A中的二元運(yùn)算，（1）若有一元素θlA，且對每一個xA有θl*x=θl，則稱θl為A中對于*的左零元；

（2）若有一元素θr

A，且對每一個xA有x*θr=θr

，則稱θr為A中對于*的右零元?！?.2運(yùn)算及其性質(zhì)[定理]若θl和θr分別是A中對于*的左零元和右零元，于是對所有的xA，可有θl=θr=θ，能使θ*x=x*θ=θ。在此情況下，θA是唯一的，并稱θ是A中對*的零元。

證明：方法同幺元。例：（1）在實數(shù)集合R中，對×而言，θl=θr=0（2）在(E)中，對

而言，θ

=

；對

而言，θ

=E；（3）{命題邏輯}中，對∨而言，θ∨=T；對∧而言，θ∧

=F。§5.2運(yùn)算及其性質(zhì)[定義5-2.9]設(shè)*是A中的二元運(yùn)算，且A中含幺元e，令xA，

（1）若存在一xlA，能使xl*x=e，則稱xl是x的左逆元,并且稱x是左可逆的；

（2）若存在一xr

A，能使x*xr=e，則稱xr是x的右逆元，并且稱x是右可逆的；

（3）若元素x既是左可逆的，又是右可逆的，則稱x是可逆的，且x的逆元用x-1表示。§5.2運(yùn)算及其性質(zhì)[定理5-2.4]設(shè)A是集合，并含有幺元e。*是定義在A上的一個二元運(yùn)算，并且是可結(jié)合的。若xA是可逆的，則它的左逆元等于右逆元，且逆元是唯一的。證明：（1）先證左逆元=右逆元：設(shè)xl和xr分別是xA的左逆元和右逆元，∵x是可逆的和*是可結(jié)合的（條件給出）∴xl*x=x*xr=e

∵xl*x*xr=（xl*x）*xr=e*xr=xr；xl*x*xr=xl*(x*xr)=xl*e=xl

∴xr=xl§5.2運(yùn)算及其性質(zhì)（2）證明逆元是唯一的（若有的話）：假設(shè)x1-1和x2-1均是x的二個不同的逆元，則x1-1=x1-1*e

=

x1-1*（x*x2-1）=（x1-1*x）*x2-1

=e*x2-1=x2-1，這和假設(shè)相矛盾。

∴x若存在逆元的話一定是唯一的?！?.2運(yùn)算及其性質(zhì)[推論](x-1)-1=x,e-1=e

證明：∵x-1*x=(x-1)-1*（x-1）=x*x-1=e

∴有(x-1)-1=x

∵e-1*e=e=e*e∴有e-1=e

實例分析集合運(yùn)算單位元零元逆元Z,Q,R普通加法+0無x的逆元

x普通乘法

10x的逆元x

1(x-1屬于給定集合)Mn(R)矩陣加法+

無X

逆元

X矩陣乘法

E

X的逆元X

1（X是可逆矩陣）P(B)并

B

的逆元為

交B

B的逆元為B對稱差

無X的逆元為X和E分別表示n階全0矩陣和單位實數(shù)矩陣§5.2運(yùn)算及其性質(zhì)[定義]設(shè)°為集合S上二元運(yùn)算，如果對于任意元素x,y,z

S,x

θ，都有

x°

y=x

°z

y=z,

y°

x=z

°x

y=z成立，則稱°運(yùn)算滿足消去律。例如，普通加法和乘法滿足消去律，矩陣加法滿足消去律，矩陣乘法不滿足消去律.集合的并和交運(yùn)算也不滿足消去律，例如{1}{1,2}={2}

{1,2}，但是{1}{2}.例題分析例設(shè)°

運(yùn)算為Q

上的二元運(yùn)算，

x,y

Q,x

°

y=x+y+2xy,(1)判斷°

運(yùn)算是否滿足交換律和結(jié)合律，并說明理由.(2)求出°運(yùn)算的單位元、零元和所有可逆元素的逆元.解(1)°運(yùn)算可交換.任取x,y

Q,x

°

y=x+y+2xy=y+x+2yx=y

°

x,°運(yùn)算可結(jié)合，任取x,y,z

Q,(x

°

y)

°

z=(x+y+2xy)+z+2(x+y+2xy)z

=x+y+z+2xy+2xz+2yz+4xyzx

°(y

°

z)=x+(y+z+2yz)+2x(y+z+2yz

=x+y+z+2xy+2xz+2yz+4xyz(2)設(shè)°

運(yùn)算的單位元和零元分別為e和

，則對于任意x有x°

e=x成立，即x+e+2xe=x

e=0由于°運(yùn)算可交換，所以0是幺元.給定x，設(shè)x的逆元為y,則有x

°

y=0成立，即x+y+2xy=0

(x

=

1/2)是x的逆元,x

1/2.例題分析(續(xù))對于任意x有x

°

=

成立，即

x+

+2x

=

x+2x

=0

=

1/21/2為零元.例題分析(續(xù))下面是三個運(yùn)算表(1)說明哪些運(yùn)算是可交換的、可結(jié)合的、冪等的.(2)求出每個運(yùn)算的單位元、零元、所有可逆元素的逆元.

a

b

c

°a

b

c

a

b

cabcc

a

b

a

b

cb

c

aabca

a

ab

b

bc

c

cabca

b

c

b

c

cc

c

c解(1)

滿足交換律、結(jié)合律；°滿足結(jié)合律、冪等律；

●滿足交換律、結(jié)合律.(2)

的單位元為b,沒有零元，a

1=c,b

1=b,c

1=a

°的單位元和零元都不存在，沒有可逆元素.

●的單位元為a，零元為c,a

1=a.b,c不是可逆元素§5.3半群[定義5-3.1]一個代數(shù)系統(tǒng)<S,*>，S為非空集合，*是S上的二元運(yùn)算，如果運(yùn)算*是封閉的，則稱代數(shù)系統(tǒng)<S,*>為廣群。[定義5-3.2]設(shè)<S,*>是一代數(shù)系統(tǒng)，S為非空集合，*是S上的二元運(yùn)算，若 (1)*運(yùn)算是封閉的。 (2)*運(yùn)算滿足結(jié)合律，則稱<S,*>為半群。

例：<N,+>,<N,

>,<IE

,+>,<I

E,>均為半群§5.3半群[定義5-3.3]對于*運(yùn)算，擁有幺元的半群<M,*>稱為含幺半群。（幺半群，獨異點）。例：<N,+,0>,<N,,1>均為含幺半群，而<N-{0}，+>就不為幺半群。例：設(shè)A為非空集合，

(A)是A的冪集，則<

(A),,>,<

(A),,A>均為含幺半群。而<I,max>，其中max(x1,x2)取二者之大值；<I,min>，其中min(x1,x2)取二者之小值，均不為幺半群（不存在幺元）。<N,max>則為含幺半群，其中e=0

§5.3半群[定理5-3.1]設(shè)<S,*>是一半群，BS，且*在B上是封閉的，那么<B,*>也是半群，稱<B,*>是<S,*>的子半群。討論定義：

（1）因為*在S上是可結(jié)合的，而BS且*在B上是封閉的，所以*在B上也是可結(jié)合的。（2）由定義可知，∵SS，∴<S,*>也是<S,*>的子半群（子含幺半群）。為了和其它子半群相互區(qū)別，稱<S,*>是<S,*>的“平凡子半群”;§5.3半群[定義]設(shè)<S,*,e>是一個含幺半群，BS，且*在B上是封閉的，則<B,*,e>也是一個含幺半群，稱<B,*,e>是<S,*,e

>的子含幺半群。討論定義：

（1）在幺半群中，由于幺元e的存在，∴保證在運(yùn)算表中一定沒有相同的行和列。

設(shè)任一x1,x2

Z，且x1

x2，則e*x1=x1e*x2=x2；

（2）在<Z,*,e>中若存在零元的話，上述性質(zhì)繼續(xù)存在?！?.3半群例：半群<{0,1},*>是<{,0,1},*>的子半群，而不是子含幺半群。

*運(yùn)算由運(yùn)算表定義：

10100010*1011000010

10

*由運(yùn)算表可見：<{0,1},*>中幺元為1，而在<{,0,1},*>中幺元為

。§5.3半群

[定理5-3.2]如果半群<S,*>的載體S為有限集，則必有aS，使a*a=a。（有限半群一定含冪等元）證明：因<S,*>是半群，對任意的bS， 由*的封閉性，b*bS，b3S，b4S，… 由于S是有限集，必有i<j，使bi=bj 設(shè)：p=j－i，則bj=bp*bi，即：bi=bp*bi

當(dāng)q≥i時，bq=bp*bq， 又因p≥1，總可以找到k≥1，使kp≥i，對S中的bkp有bkp=bp*bkp=bp*(bp*bkp)=b2p*bkp =b2p*(bp*bkp)=b3p*bkp=….=bkp*bkp 令a=bkp，則a*a=a?！?.3半群[定理5-3.3]設(shè)<S,*>是獨異點，則在關(guān)于運(yùn)算*的運(yùn)算表中任何兩行或兩列都是不相同的。

證明：設(shè)獨異點<S,*>的幺元是e，

對任意的a，bS且a≠b∵a*e≠b*e，∴<S,*>運(yùn)算表中a，b兩行不同。由a，b的任意性，運(yùn)算表中任兩行不同?！遝*a≠e*b，∴<S,*>運(yùn)算表中a，b兩列不同。由a，b的任意性，運(yùn)算表中任兩列不同?！?.3半群[定理5-3.4]設(shè)<S,*>是獨異點，對于任意a，bS，且a，b均有逆元，則a)(a-1)-1=ab)a*b有逆元，且(a*b)-1=b-1*a-1證明：a)因為a-1是a的逆元，即 a*a-1=a-1*a=e 所以(a-1)-1=a b)因為(a*b)*(b-1*a-1)=a*(b*b-1)*a-1=a*e*a-1=e同理可證：(b-1*a-1