離散數(shù)學(xué)：代數(shù)系統(tǒng)的基本概念

1第三篇代數(shù)系統(tǒng)23近世代數(shù)

一般意義下，代數(shù)被認(rèn)為是對(duì)符號(hào)的操作。代數(shù)的發(fā)展以其內(nèi)容和研究問題的方法的不同分為兩個(gè)歷史階段：古典代數(shù)：“每個(gè)符號(hào)總是代表一個(gè)數(shù)”；近世代數(shù)：在任意性質(zhì)的元素上所進(jìn)行的代數(shù)運(yùn)算作為研究的基本對(duì)象。 代數(shù)系統(tǒng)又稱作代數(shù)結(jié)構(gòu)，是近世代數(shù)或抽象代數(shù)研究的中心問題。

代數(shù)系統(tǒng)的知識(shí)模塊主要討論：

代數(shù)系統(tǒng)的構(gòu)成

代數(shù)系統(tǒng)的產(chǎn)生

代數(shù)系統(tǒng)間的關(guān)系

幾類重要的代數(shù)系統(tǒng)4

代數(shù)系統(tǒng)的知識(shí)模塊

5

教材離散數(shù)學(xué)左孝凌李為鑑劉永才編著上海科學(xué)技術(shù)文獻(xiàn)出版社

參考離散數(shù)學(xué)題解付艷芬編石油大學(xué)離散數(shù)學(xué)教程耿素云屈婉玲王捍貧北京大學(xué)出版社DiscreteMathematicsandItsApplications

KennethRosenMcGrawHillCompaniesMOOC學(xué)院：/coursestatic/course_6447.html6第五章代數(shù)系統(tǒng)代數(shù)系統(tǒng)的基本概念1半群與含幺半群（獨(dú)異點(diǎn)）2群（阿貝爾群與循環(huán)群）3子群與陪集4同態(tài)與同構(gòu)5環(huán)與域671.n元運(yùn)算定義1：設(shè)A是非空集合，一個(gè)從An到B的映射f:AnB稱為集合A上的一個(gè)n元運(yùn)算，其中n是自然數(shù)，稱為運(yùn)算的元數(shù)或階。 若BA，則稱該n元運(yùn)算是封閉的。特別的：當(dāng)n=1時(shí)，稱f為一元運(yùn)算；

當(dāng)n=2時(shí)，稱f為二元運(yùn)算。8設(shè)A是非空集合，函數(shù)f：A×A→A稱為A上的二元運(yùn)算，簡稱為二元運(yùn)算.8

二元運(yùn)算舉例（1）加法、乘法是自然數(shù)集合N上的二元運(yùn)算，減法和除法不是.（2）加法、減法和乘法是整數(shù)集合Z上的二元運(yùn)算，而除法不是.（3）乘法、除法是非零實(shí)數(shù)集R*上的二元運(yùn)算，加法、減法不是.（4）設(shè)S={a1,a2,…,an},aiaj=ai為S上二元運(yùn)算.（5）S為任意集合，則∪、∩、－、

為P(S)上的二元運(yùn)算.（6）SS為S上的所有函數(shù)的集合，則合成運(yùn)算為SS上的二元運(yùn)算.（7）設(shè)Mn(R)表示所有n階(n≥2)實(shí)矩陣的集合，即則矩陣加法和乘法都是Mn(R)上的二元運(yùn)算.9設(shè)A是非空集合，函數(shù)f：A→A稱為A上的一元運(yùn)算，簡稱為一元運(yùn)算.（1）求相反數(shù)是整數(shù)集合Z，有理數(shù)集合Q和實(shí)數(shù)集合R上的一元運(yùn)算.

（2）求倒數(shù)是非零有理數(shù)集合Q*，非零實(shí)數(shù)集合R*上的一元運(yùn)算.

（3）求共軛復(fù)數(shù)是復(fù)數(shù)集合C上的一元運(yùn)算.

（4）在冪集P(S)上規(guī)定全集為S，則求絕對(duì)補(bǔ)運(yùn)算~是P(S)上的一元運(yùn)算（5）設(shè)S為集合，令A(yù)為S上所有雙射函數(shù)的集合，ASS，求一個(gè)雙射函數(shù)的反函數(shù)為A上的一元運(yùn)算.（6）在n(n≥2)階實(shí)矩陣的集合Mn(R)上，求轉(zhuǎn)置矩陣是Mn(R)上的一元運(yùn)算.10

一元運(yùn)算舉例11可以用，?，?，~，

，

，

等符號(hào)表示二元或一元運(yùn)算，稱為算符.公式表示一元運(yùn)算的算符通常放在運(yùn)算對(duì)象前面，如~a，–2；二元運(yùn)算的算符通常放在運(yùn)算對(duì)象中間，如(ai,aj)寫成aiaj；n元運(yùn)算的算符通常放在運(yùn)算對(duì)象前面，如f(a1,a2,…,an)。n元運(yùn)算的表示12運(yùn)算表表示有窮集上的一元和二元運(yùn)算n元運(yùn)算的表示13

代數(shù)系統(tǒng)的組成代數(shù)載體(如實(shí)數(shù)集、整數(shù)集)運(yùn)算法則如＋、－×………特異元素如×中的1和0代數(shù)系統(tǒng)2.代數(shù)系統(tǒng)142.代數(shù)系統(tǒng)定義2：一個(gè)非空集合A，連同定義在A上的若干個(gè)運(yùn)算f1,f2,…,fk，組成的系統(tǒng)稱為一個(gè)代數(shù)系統(tǒng)，記為<A,f1,f2,…,fk>。

常見代數(shù)系統(tǒng)舉例<I+,+>正整數(shù)集合上的加法運(yùn)算<R,+,->實(shí)數(shù)集上的加、減P(S),∪,∩,~>集合S的冪集上的并、交、補(bǔ)<P,*>P：石油大學(xué)的學(xué)生，*：是一個(gè)抽象運(yùn)算，P1*P2的運(yùn)算結(jié)果是P1和P2中年齡較小者2.代數(shù)系統(tǒng)定義2：一個(gè)非空集合A，連同定義在A上的若干個(gè)運(yùn)算f1,f2,…,fk，組成的系統(tǒng)稱為一個(gè)代數(shù)系統(tǒng)，記為<A,f1,f2,…,fk>。<N,＋>,<Z,＋,·>,<R,＋,·>是代數(shù)系統(tǒng)，+和·分別表示普通加法和乘法.<Mn(R),＋,·>是代數(shù)系統(tǒng)，＋和·分別表示n階(n≥2)實(shí)矩陣的加法和乘法.<Zn,,>是代數(shù)系統(tǒng)，Zn＝{0,1,…,n-1}，和分別表示模n的加法和乘法，對(duì)于x,y∈Zn，xy=(x＋y)modn，xy=(xy)modn<P(S),,,~>也是代數(shù)系統(tǒng)，和為并和交，~為絕對(duì)補(bǔ)<P,*>P：石油大學(xué)的學(xué)生，*：是一個(gè)抽象運(yùn)算，P1*P2的運(yùn)算結(jié)果是P1和P2中年齡較小者15

常見代數(shù)系統(tǒng)舉例163.代數(shù)系統(tǒng)中的運(yùn)算性質(zhì)1）*是定義在A上的二元運(yùn)算，對(duì)于A中任意元素x,y，都有x*y∈A，則稱*在A上是封閉的。 例：加、減運(yùn)算在整數(shù)集合上是封閉的；

除在整數(shù)集合上是不封閉的；

減在自然數(shù)集合上也是不封閉的。2）*是定義在A上的二元運(yùn)算，對(duì)于A中任意元素x,y，都有x*y=y*x，則稱*在A上是可交換的。3）*是定義在A上的二元運(yùn)算，對(duì)于A中任意元素x,y,z都有(x*y)*z=x*(y*z)，則稱*在A上是可結(jié)合的。 例：加運(yùn)算在正整數(shù)集合上是可交換的、可結(jié)合的；

減運(yùn)算在正整數(shù)集合上是不可交換的、不可結(jié)合。17例1：設(shè)Q是有理數(shù)集，*是Q上的二元運(yùn)算，對(duì)于Q上的任意元素a,b，有a*b=a+b-a?b，問*是否可交換、可結(jié)合？(注：+、-、?是普通的加減乘運(yùn)算)證明：

(1)∵對(duì)Q上的任意元素a,b，有

a*b=a+b-a?b=b+a-b?a=b*a ∴*可交換

(2)取任意的a,b,c∈Q (a*b)*c=(a*b)+c-(a*b)?c=(a+b-a?b)+c-(a+b-a?b)?c =a+b-a?b+c-a?c-b?c+a?b?c a*(b*c)=a+(b*c)-a?(b*c)=a+(b+c-b?c)-a?(b+c-b?c) =a+b-a?b+c-a?c-b?c+a?b?c=(a*b)*c ∴*可結(jié)合184）*是定義在A上的二元運(yùn)算，若對(duì)于A中任意元素x,都有x*x=x，則稱*在A上是等冪的。 例：對(duì)任意集合A，有A∪A=A，A∩A=A，∪和∩在全集上是等冪的。19例

Z,Q,R分別為整數(shù)、有理數(shù)、實(shí)數(shù)集；Mn(R)為n階實(shí)矩陣集合,n2；P(B)為冪集；AA為從A到A的函數(shù)集，|A|2集合運(yùn)算交換律結(jié)合律冪等律Z,Q,R普通加法+普通乘法有有有有無無Mn(R)矩陣加法+矩陣乘法有無有有無無P(B)并交相對(duì)補(bǔ)對(duì)稱差有有無有有有無有有有無無AA函數(shù)符合無有無5）*是定義在A上的二元運(yùn)算，也是定義在A上的二元運(yùn)算，若 x*(yz)=(x*y)(x*z)， (yz)*x=(y*x)(z*x)，

則稱*對(duì)是可分配的。例：∪對(duì)∩是可分配的，∩對(duì)∪是可分配的；

×對(duì)+是可分配的；+對(duì)×是不可分配的注意：定義中的順序，*對(duì)是可分配的，對(duì)*不一定是可分配的。20216）*和是A上可交換的二元運(yùn)算，若x*(xy)=x，x(x*y)=x，則稱*和滿足吸收律。 例：∪和∩滿足吸收律。注意：

*和都是可交換的，兩個(gè)式子要同時(shí)成立。例2：在自然數(shù)集上定義如下兩個(gè)運(yùn)算*和

x*y=max{x,y}xy=min{x,y}，則*，是否滿足吸收律？解：x*y=y*x，xy=yx即*和可交換

x*(xy)=max(x,xy)=max(x,min(x,y))=x x(x*y)=min(x,x*y)=min(x,max(x,y))=x

所以，*和滿足吸收律。例Z,Q,R分別為整數(shù)、有理數(shù)、實(shí)數(shù)集；Mn(R)為n階實(shí)矩陣集合,n2；P(B)為冪集；AA為從A到A的函數(shù)集，|A|222

集合

運(yùn)算分配律吸收律Z,Q,R普通加法+與乘法對(duì)+可分配+對(duì)不分配無Mn(R)矩陣加法+與乘法對(duì)+可分配+對(duì)不分配無P(B)并與交

對(duì)可分配對(duì)可分配有

交與對(duì)稱差

對(duì)可分配無237)

a,b,cA，若a*b=a*c(b*a=c*a)，則b=c，則稱*滿足左（右）消去律，若*滿足左消去律又滿足右消去律則稱*滿足消去律。 例：代數(shù)系統(tǒng)<I,+>,<R,+>,<I,

>,<R,>滿足消去律<Mn(R),+>滿足消去律,<Mn(R),>不滿足消去律244.代數(shù)常元定義3：設(shè)*是集合A上的二元運(yùn)算若elA，對(duì)于xA

，都有el*x=x，則稱el為A中關(guān)于運(yùn)算*的左幺元；若erA，對(duì)于xA

，都有x*er=x，則稱er為A中關(guān)于運(yùn)算*的右幺元；若eA，對(duì)于xA

，都有e*x=x*e=x，則稱e為A中關(guān)于運(yùn)算*的幺元。例：代數(shù)系統(tǒng)<I,+>中，0是I中關(guān)于+的幺元，

<I+,+>中沒有幺元，<I,>中1是I中關(guān)于乘法的幺元 ∴幺元與集合有關(guān)，與運(yùn)算有關(guān)。

幺元25定理1：*是A上的二元運(yùn)算，且在A中有關(guān)于*的左幺元el和右幺元er，則el=er=e，且A中幺元是唯一的。證明：

(1)er=el

*er

=el=e (2)設(shè)e’也是A中關(guān)于*的幺元，則e*e’=e

又∵

e是A中關(guān)于*的幺元，∴e*e’=e’ ∴e=e’26定義4：設(shè)*是集合A上的二元運(yùn)算若lA，對(duì)于xA

，都有l(wèi)*x=l

，則稱l為A中關(guān)于運(yùn)算*的左零元；若rA，對(duì)于xA

，都有x*r=r

，則稱r為A中關(guān)于運(yùn)算*的右零元；若A，對(duì)于xA

，都有*x=x*=，則稱為A中關(guān)于運(yùn)算*的零元。例：代數(shù)系統(tǒng)<I,+>是否有零元？

<I,>中0是I中關(guān)于乘法的零元

零元27定理2：*是A上的二元運(yùn)算，且在A中有關(guān)于*的左零元l和右零元r，則l=r=

，且A中零元是唯一的。證明：(1)

r=

l

*

r=

l= (2)設(shè)’也是A中關(guān)于*的零元，則

*’=’

又∵

是A中關(guān)于*的零元，∴

*’=

∴=’定理3：設(shè)<A,*>是一個(gè)代數(shù)系統(tǒng)，且|A|>1，若<A,*>中存在幺元e和零元，則e≠。證明：假設(shè)

=e，則 對(duì)于A中任意元素，有x=e*x=*x==e

即A中所有元素都是，也都是e，所有元素都相同， ∴|A|=1與已知矛盾，假設(shè)錯(cuò) ∴e≠28例3：寫出下列代數(shù)系統(tǒng)中關(guān)于運(yùn)算的幺元、零元，并判斷是否有等冪性。代數(shù)系統(tǒng)幺元零元等冪性<I+,+><I

,><P(S)

,∩><P(S)

,∪><I+,max>×××10×S??S1×29定義5：設(shè)代數(shù)系統(tǒng)<A,*>，e是關(guān)于*的幺元，若對(duì)A中一個(gè)元素a，存在著A中的某個(gè)元素b，使得b*a=e成立，則稱b為a的左逆元；使得a*b=e成立，則稱b為a的右逆元；使得b*a=e=a*b成立，則稱b為a的逆元，記為b=a-1。例：

<I,+>中，0是幺元，對(duì)I中任意元素x，

有-x+x=0=x+(-x) ∴x-1=-x (-x)-1=x注意：幺元和零元是對(duì)代數(shù)系統(tǒng)而言，

例如：0是<I,+>中I關(guān)于+的幺元；逆元是對(duì)系統(tǒng)中某個(gè)具體元素而言，

例如：<I,+>中元素1的逆元是-1。

逆元30例4：集合S={a,b,c,d,e}，定義在S上二元運(yùn)算*的運(yùn)算表如下，指出<S,*>中各元素的左右逆元情況。解：a是幺元；

b有兩個(gè)左逆元c和d，右逆元是c，逆元是c；

c的左、右逆元都是b，逆元是b；b和c互為逆元；

d的左逆元是c，右逆元是b；

e沒有左逆元，右逆元是c。*abcdeaabcdebbdacdccababddacdceedace31

注意若a是b的逆元，則b也是a的逆元，即a與b互為逆元；若b是a的左逆元，則a是b的右逆元；一個(gè)元素左逆元不一定等于它的右逆元；一個(gè)元素可以只有一個(gè)左(右)逆元，沒有右(左)逆元；或者有多個(gè)左逆元，多個(gè)右逆元；或者既沒有左逆元，也沒有右逆元。32定理4：設(shè)代數(shù)系統(tǒng)<A,*>，這里*是定義在A上的一個(gè)二元運(yùn)算，A中存在幺元e，且每一個(gè)元素都有左逆元。如果*是可結(jié)合的運(yùn)算，那么，這個(gè)代數(shù)系統(tǒng)中任何一個(gè)元素的左逆元必定也是該元素的右逆元，且每個(gè)元素的逆元是唯一的。證明：設(shè)aA,且bA是a的左逆元，cA是b的左逆元。

a*b=(e*a)*b =((c*b)*a)*b =(c*(b*a))*b =c*((b*a)*b) =c*b=e ∴b也是a的右逆元設(shè)元素a有兩個(gè)逆元b和d，則b=b*e =b*(a*d) =(b*a)*d =e*d=d ∴a的逆元是唯一的。33<A,*>是代數(shù)系統(tǒng)，*是A上的二元運(yùn)算，那么該運(yùn)算的有些性質(zhì)可以從運(yùn)算表中直接看出。方法如下：1)*有封閉性，當(dāng)且僅當(dāng)運(yùn)算表中的每個(gè)元素都屬于A；2)*有可交換性，當(dāng)且僅當(dāng)運(yùn)算表關(guān)于主對(duì)角線對(duì)稱；3)*有等冪性，當(dāng)且僅當(dāng)每個(gè)對(duì)角線元素與它所在行（列）的表頭元素相同；4)A中關(guān)于*有零元，當(dāng)且僅當(dāng)該元素對(duì)應(yīng)的行和列中的元素都與該元素相同；5)A中關(guān)于*有幺元，當(dāng)且僅當(dāng)該元素對(duì)應(yīng)的行和列依次與運(yùn)算表的行和列一致；6)設(shè)A中有幺元，a和b互逆，當(dāng)且僅當(dāng)位于a所在行，b所在列的對(duì)應(yīng)元素以及b所在行，a所在列的對(duì)應(yīng)元素都是幺元。