離散數(shù)學(xué)07抽象代數(shù)

抽象代數(shù)AbstractAlgebra

本部分所要探討的數(shù)學(xué)結(jié)構(gòu)是由集合上定義若干運(yùn)算而組成的系統(tǒng)——稱為代數(shù)系統(tǒng)(代數(shù)結(jié)構(gòu))。

抽象代數(shù)主要內(nèi)容第7章

抽象代數(shù)第8章

群第9章布爾代數(shù)

相對古典代數(shù)而言,抽象代數(shù)也稱為近世代數(shù)(ModernAlgebra),由于其研究對象是由對象集合及運(yùn)算組成的數(shù)學(xué)結(jié)構(gòu)，即代數(shù)結(jié)構(gòu),因此,抽象代數(shù)也被稱為代數(shù)結(jié)構(gòu)或代數(shù)系統(tǒng)。抽象代數(shù)對計(jì)算機(jī)科學(xué)的發(fā)展有著重大的理論和實(shí)踐意義,如在程序理論、語義學(xué)、數(shù)據(jù)結(jié)構(gòu)和編碼理論,以及邏輯電路設(shè)計(jì)的研究,此外，抽象代數(shù)還被廣泛用于物理學(xué)、生物學(xué)以及社會(huì)科學(xué)中。本章將探討代數(shù)結(jié)構(gòu)的數(shù)學(xué)描述以及一般代數(shù)結(jié)構(gòu)的基本性質(zhì)。后續(xù)兩章將深入討論群、布爾代數(shù)等典型的代數(shù)結(jié)構(gòu)及其應(yīng)用。第7章抽象代數(shù)

本章內(nèi)容提要：

1.抽象代數(shù)概述

2.代數(shù)結(jié)構(gòu)及其性質(zhì)

3.同態(tài)與同構(gòu)

第7章抽象代數(shù)重點(diǎn)：代數(shù)結(jié)構(gòu)的判定與構(gòu)造代數(shù)結(jié)構(gòu)關(guān)系：同態(tài)、同構(gòu)特殊關(guān)系：同余關(guān)系抽象代數(shù)的創(chuàng)始人是兩位英年早逝的青年數(shù)學(xué)家，阿貝爾與伽羅瓦。阿貝爾,是挪威青年數(shù)學(xué)家,鄉(xiāng)村牧師之子,幼年喪父,家貧。多獨(dú)創(chuàng)性成果,但大都未受重視,貧病而逝。去逝后3天,柏林大學(xué)寄來教授聘書,讓后人嘆息！后人曾評價(jià)說：“他工作不是為自己，而是為他熱愛的科學(xué)”。2001，在阿貝爾誕生200周年之際，挪威王國政府宣布，設(shè)立面向國際的“阿貝爾數(shù)學(xué)獎(jiǎng)”。

7.1抽象代數(shù)概述NielsAbel

AstatueofAbelinOslo伽羅瓦,是法國青年數(shù)學(xué)家,其父親是自由主義思想家,母親亦受了良好教育,中學(xué)時(shí)就對數(shù)學(xué)產(chǎn)生強(qiáng)烈興趣,他兩次投考巴黎綜合技術(shù)學(xué)院而未被錄取，后進(jìn)入巴黎高師學(xué)習(xí),提出“群”的概念。但其論文未被數(shù)學(xué)家柯西、泊松等接受。跟大多數(shù)數(shù)學(xué)家不問政治不同，伽羅瓦是一個(gè)非常激進(jìn)的革命者，后因政治原因入獄。最后與人決斗受傷而去逝。在其決斗前幾天,寫下了其主要研究成果,直到40年后,其成果才被世人所接受。后有著名數(shù)學(xué)家評價(jià)說：“伽羅瓦的去逝使數(shù)學(xué)的發(fā)展推遲了幾十年”。從伽羅瓦的工作以后，代數(shù)學(xué)結(jié)束了解方程的歷史，進(jìn)入研究新的數(shù)學(xué)對象——群、環(huán)、域的抽象代數(shù)的發(fā)展階段。

7.1抽象代數(shù)概述EvaristeGalois

ThisistakenfromaFrenchstampAdrawingdonein1848frommemorybyEvariste'sbrother.7.2.1代數(shù)運(yùn)算例7.1

(1)設(shè)A={a,b,c}是一個(gè)非空集合,P(A)={φ,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}7.2代數(shù)結(jié)構(gòu)及其性質(zhì)在P(A)上并∪運(yùn)算的結(jié)果均在P(A)中φ{(diào)a}{c}{a,b}{a,c}{b,c}{a,b,c}φ{(diào)a}{c}{a,b}{a,c}{b,c}{a,b,c}∪φ{(diào)a}{a}{a,b}{a,c}{a,b}{a,c}{a,b,c}{a,b,c}{a,b}{b,c}{a,b}{a,b,c}{b,c}{a,b,c}{a}{c}{a,c}{b,c}{c}{a,b,c}{a,c}{b,c}{a,b,c}{a,b}{a,b}{a,b}{a,b,c}{a,b}{a,b,c}{a,b,c}{a,b,c}{c}{a,b}{a,c}{a,c}{a,b,c}{a,c}{a,b,c}{a,c}{a,b,c}{a,b,c}{b,c}{a,b,c}{b,c}{b,c}{a,b,c}{a,b,c}{b,c}{a,b,c}{a,c}{b,c}{a,b,c}{a,b,c}{a,b,c}{a,b,c}{a,b,c}{a,b,c}{a,b,c}{a,b,c}{a,b,c}7.2.1代數(shù)運(yùn)算7.2代數(shù)結(jié)構(gòu)及其性質(zhì)A上乘法*的結(jié)果在A中，B上加法+的結(jié)果在B中13971397*1397197133971397例7.1

(2)A={1,3,9,7},A上模10乘法*運(yùn)算表如下01230123+0123023011230123

B={0,1,2,3},B上模4加法+運(yùn)算表如下7.2.1代數(shù)運(yùn)算例7.1

(3)設(shè)Mn(R)是全體n×n實(shí)矩陣的集合,考慮Mn(R)中普通的矩陣乘法*,則對于任意兩個(gè)n×n實(shí)矩陣A、B,根據(jù)矩陣乘法法則可得到Mn(R)中惟一的一個(gè)n×n實(shí)矩陣C作為A乘B的結(jié)果。我們記C=A*B。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)上述示例中,雖然是對不同集合給出的不同運(yùn)算,但它們都具有這樣一個(gè)共同的特點(diǎn)：它們都是某個(gè)給定的集合S(S分別為上述二例中的P(A)和Mn(R))中的任意一個(gè)或一對有序取出的元素,根據(jù)這個(gè)法則可在S中找到惟一的一個(gè)元素與之對應(yīng)。由此,我們可以抽象出在一個(gè)集合上的二元代數(shù)運(yùn)算的概念。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)定義7.1

設(shè)S是一個(gè)非空集合。如果有一個(gè)法則,它對S中任意兩個(gè)有序元素a與b,在S中都有一個(gè)惟一確定的元素c與它們對應(yīng),則稱這個(gè)法則是集合S中一個(gè)二元代數(shù)運(yùn)算。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)一般地,容易得到n元運(yùn)算的定義：設(shè)S是一個(gè)非空集合。如果有一個(gè)法則,它對S中任意n個(gè)有序元素a1,a2,…,an,在S中都有一個(gè)惟一確定的元素d與它們對應(yīng),則稱這個(gè)法則是集合S中一個(gè)n元代數(shù)運(yùn)算。根據(jù)上述定義，可以看到，如果這個(gè)法則是S的一個(gè)代數(shù)運(yùn)算，則該法則其實(shí)就是S上的一個(gè)映射(或函數(shù))：Sn→S,n稱為這個(gè)運(yùn)算的階。對于集合S的一個(gè)n元運(yùn)算f,若(a1,a2,…,an)∈Sn在f下的像是c,即f(a1,a2,…,an)→c,則記為c=f(a1,a2,…,an)。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)7.2代數(shù)結(jié)構(gòu)及其性質(zhì)

其他例子：A={0,1}，A上邏輯非、析取、合取運(yùn)算∨01001111∧01000101?0110

一元運(yùn)算

二元運(yùn)算以上二元運(yùn)算使用運(yùn)算表。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)設(shè)I為全體整數(shù)集合,n是正整數(shù),規(guī)定In到I的映射為f：(a1,a2,…,an)→a1,對于任意(a1,a2,…,an)∈In,則f是一個(gè)n元運(yùn)算。其中f(a1,a2,…,an)=a1。上述代數(shù)運(yùn)算的表示方法稱為解析公式法,也就是用函數(shù)來表示運(yùn)算。

練習(xí)1

通常數(shù)的乘法運(yùn)算是否可看作下列集合上的二元運(yùn)算？請說明理由。（1）A={1,2}

（2）B={x|x是素?cái)?shù)}（3）C={x|x是偶數(shù)}（4）D={2n|n∈N}

7.2代數(shù)結(jié)構(gòu)及其性質(zhì)設(shè)R為實(shí)數(shù)集合，它關(guān)于普通乘法*是R上的代數(shù)運(yùn)算。R-{0}是全體非零實(shí)數(shù)集合,對任意a,b∈R-{0},也有a*b∈R-{0}。因此，普通乘法*還是R-{0}上的代數(shù)運(yùn)算。

R關(guān)于普通加法+是R上的代數(shù)運(yùn)算。對任意a,b∈R-{0},但不一定a+b∈R-{0}，例如2+（-2）=0。因此，普通加法+不是R-{0}上的代數(shù)運(yùn)算。定義7.2

設(shè)S上有n元運(yùn)算*（n為正整數(shù)），S′

S,若對任意a1,a2,…,an∈S′，有*(a1,a2,…,an)∈S′,則稱S上的*運(yùn)算對S′封閉，或稱為S′在*下是封閉的。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)練習(xí)2

A={x｜x=2n，n∈N}，問<A，

>是否封閉，<A，+>，<A，/>呢？

解

2r，2s∈A，2r

2s=2r+s∈A（r+s∈N）∴<A，

>運(yùn)算封閉

2，4∈A，2+4

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

2，4∈A，2/4

A，∴<A，/>運(yùn)算不封閉7.2代數(shù)結(jié)構(gòu)及其性質(zhì)對于A上兩種二元運(yùn)算ο和*：

若對于任意a,b∈A有：aοb=bοa,則稱ο在A上是可交換的(或稱ο滿足交換律)。若對于任意a∈A有：aοa=a,則稱ο在A上是滿足冪等律的。若對于任意a,b,c∈A有：當(dāng)aοb=aοc時(shí)，有b=c,則稱ο在A上是可左可消去的(或稱ο滿足左消去律)，若ο在A上是滿足左可消去律與右可消去律，則稱ο在A上是可消去的(或稱ο滿足消去律)。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)若對于任意a,b,c∈A,有：aο(b*c)=(aοb)*(aοc);(b*c)οa=(bοa)*(cοa)。

則稱ο對于*是可分配的(或稱ο滿足分配律)。若對于任意a,b,c∈A有：aο(bοc)=(aοb)οc,則稱ο為在A上是可結(jié)合的(或稱ο滿足結(jié)合律)。若集合A上的二元運(yùn)算*滿足結(jié)合律,則我們常用a*b*c來表示(a*b)*c=a*(b*c)。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)于是,進(jìn)一步可令an=a*a*…*a,an讀作a的n次冪。可以通過如下遞歸定義得到：(1)a1=a;(2)an+1=an*a。利用數(shù)學(xué)歸納法,不難證明下列公式:(1)

am*an=am+n;(2)

(am)n=amn。其中，m，n∈I+。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)全體n×n實(shí)矩陣的集合Mn(R)上普通的矩陣乘法*滿足結(jié)合律，但不滿足交換律。因?yàn)橐话阌校篈*B≠B*A，Mn(R)上矩陣乘法*對加法+滿足分配律。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)設(shè)A=｛1,2,…,m｝,m是一個(gè)正整數(shù)。A2到A的映射定義為：f：(i,j)→max｛i,j｝,(i,j)∈A2則f是A上的一個(gè)二元運(yùn)算,顯然,f滿足交換律、結(jié)合律。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)7.2代數(shù)結(jié)構(gòu)及其性質(zhì)

邏輯聯(lián)結(jié)詞合取、析取、蘊(yùn)含以及等價(jià)都是真值集合{0,1}上的二元代數(shù)運(yùn)算。合取、析取、等價(jià)運(yùn)算滿足交換律、結(jié)合律。合取對析取滿足分配律。析取對合取也滿足分配律。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)13971397*1397197133971397A={1,3,9,7},A上模10乘法*運(yùn)算表如下乘法*運(yùn)算滿足交換律、結(jié)合律、消去律037.2代數(shù)結(jié)構(gòu)及其性質(zhì)01230000*00123024012303B={0,1,2,3,4,5},B上模6乘法*運(yùn)算表如下450005042045434524034221乘法*運(yùn)算滿足交換律、結(jié)合律但不滿足消去律，例如2*1=2=2*4，但1≠4

練習(xí)3

實(shí)數(shù)集R上的下列二元運(yùn)算是否滿足交換律和結(jié)合律？（1）r1*r2=r1+r2-r1r2（2）r1οr2=(r1+r2)/27.2代數(shù)結(jié)構(gòu)及其性質(zhì)

7.2.2

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

定義7.3

設(shè)S是一個(gè)非空集合,f1,f2,…,fn是S上的n個(gè)代數(shù)運(yùn)算,則S與n個(gè)運(yùn)算所組成的結(jié)構(gòu)稱為代數(shù)結(jié)構(gòu)或代數(shù)系統(tǒng),記為<S;f1,f2,…,fn>。根據(jù)上述定義,一個(gè)代數(shù)結(jié)構(gòu)需滿足如下兩個(gè)條件：(1)有一個(gè)非空集合S,稱為載體;(2)一些定義在載體S上的運(yùn)算。若S為有限集，則該稱代數(shù)結(jié)構(gòu)為有限代數(shù)結(jié)構(gòu)。

7.2代數(shù)結(jié)構(gòu)及其性質(zhì)

例7.5

前面的例子分別列舉了如下代數(shù)結(jié)構(gòu)：<P(A);∪,∩>,<Mn(R);*，+>,<{0,1};

,

,

,

>。這些代數(shù)結(jié)構(gòu)均是具體代數(shù)結(jié)構(gòu)。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)

定義7.4

設(shè)V=<S;*1,*2,…,*n>,S′

S,如果運(yùn)算*1,*2,…,*n在S′上封閉，則稱<S′;*1,*2,…,*n>為V的子代數(shù)結(jié)構(gòu)，簡稱為V的子代數(shù)(Subalgebra)。根據(jù)上述子代數(shù)的定義，代數(shù)結(jié)構(gòu)V上運(yùn)算滿足的性質(zhì)，其子代數(shù)結(jié)構(gòu)也滿足。設(shè)R為實(shí)數(shù)集合，它關(guān)于普通乘法*是R上的代數(shù)運(yùn)算。R-{0}是全體非零實(shí)數(shù)集合,對任意a,b∈R-{0},也有a*b∈R-{0}。因此，普通乘法*還是R-{0}上的代數(shù)運(yùn)算。因此，<R-{0},*>是<R,*>子代數(shù)結(jié)構(gòu)。

R關(guān)于普通加法+是R上的代數(shù)運(yùn)算。對任意a,b∈R-{0},但不一定a+b∈R-{0}，例如2+（-2）=0。因此，普通加法+不是R-{0}上的代數(shù)運(yùn)算。因此，<R-{0},+>不是<R,+>子代數(shù)結(jié)構(gòu)7.2代數(shù)結(jié)構(gòu)及其性質(zhì)

練習(xí)4

設(shè)V=<I;+,·>，其中I表示整數(shù)集，+和分別表示通常數(shù)的加法和乘法運(yùn)算。對下面I的每個(gè)子集，確定它是否能構(gòu)成V的子代數(shù)？為什么？（1）H1={2n+1|n

I}（2）H2={-1,0,1}（3）H3={2n|n

I}7.2代數(shù)結(jié)構(gòu)及其性質(zhì)

7.2.3

代數(shù)結(jié)構(gòu)的特殊元素

1.單位元

定義7.5

設(shè)ο是集合A上的二元運(yùn)算，如果存在一個(gè)元素el∈A，使得對于任意的a∈A滿足elοa=a，則稱el是A上關(guān)于運(yùn)算ο的左單位元；如果存在一個(gè)元素er∈A，使得對于任意的a∈A有aοer=a，則稱er是A上關(guān)于運(yùn)算ο的右單位元；如果存在一個(gè)元素e∈A，使得對于任意的a∈A有eοa=aοe=a，則稱e是A上關(guān)于運(yùn)算ο的單位元。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)如例7.1中，P(A)上交運(yùn)算的單位元為A,而并運(yùn)算的單位元為

。Mn(R)上乘運(yùn)算的單位元為單位矩陣。以后代數(shù)結(jié)構(gòu)的單位元常常用e來表示。記a0=e。

Mn(R)上加運(yùn)算的單位元為零矩陣。

7.2代數(shù)結(jié)構(gòu)及其性質(zhì)

定理7.1

設(shè)ο是集合A上的二元運(yùn)算，又設(shè)el和er分別是ο的左單位元和右單位元，則el=er=e，且e是ο的惟一的單位元。

7.2代數(shù)結(jié)構(gòu)及其性質(zhì)

2.逆元

定義7.6

設(shè)ο是集合A上有單位元e的二元運(yùn)算，對于元素a∈A，如果存在一元素al-1∈A，使得al-1οa=e，則稱a是左可逆的，并稱al-1是a的一個(gè)左逆元；如果存在一元素ar-1∈A，使得aοar-1=e，則稱元素a是右可逆的，并稱ar-1是a的一個(gè)右逆元；如果存在一元素a-1∈A，使得a-1οa=aοa-1=e，則稱元素a關(guān)于運(yùn)算ο是可逆的，而稱a-1是a的一個(gè)逆元。7.2代數(shù)結(jié)構(gòu)及其性質(zhì)

定理7.2

設(shè)ο是集合A上的具有單位元e且可結(jié)合的二元運(yùn)算，如果元素a∈A有左逆元和右逆元，則其左、右逆元相等，并且若令al-1=ar-1=a-1，則a-1就是a惟一的逆元。由逆元的定義我們得知，如果a∈A有逆元a-1，則aοa-1=a-1οa=e，因此(a-1)-1=a(即a是a-1的逆元)。例如，每一個(gè)實(shí)數(shù)r∈R均有一個(gè)關(guān)于加法運(yùn)算的逆元-r，每一個(gè)非零實(shí)數(shù)r∈R，均有一個(gè)關(guān)于乘法運(yùn)算的逆元1/r。顯然，對于任何二元運(yùn)算，單位元是可逆的，其逆元就是單位元本身。

7.2代數(shù)結(jié)構(gòu)及其性質(zhì)

3.零元

定義7.7

設(shè)ο是集合A上的二元運(yùn)算，如果存在一個(gè)元素zl∈A，使得對于所有的a∈A，有zlοa=zl，則稱zl是A上關(guān)于運(yùn)算ο的左零元；如果存在一個(gè)元素zr∈A，使得對于所有的a∈A均有aοzr=zr，則稱zr是A上關(guān)于運(yùn)算ο的右零元；如果存在一個(gè)元素z∈A，使得對于所有的a∈A均有zοa=aοz=z，則稱z是A上關(guān)于運(yùn)算ο的零元(ZeroElement)。

7.2代數(shù)結(jié)構(gòu)及其性質(zhì)7.2代數(shù)結(jié)構(gòu)及其性質(zhì)1為單位元，沒有零元13971397*1397197133971397

A={1,3,9,7},A上模10乘法*運(yùn)算表如下01230123+0123023011230123

B={0,1,2,3},B上模4加法+運(yùn)算表如下0為單位元，沒有零元037.2代數(shù)結(jié)構(gòu)及其性質(zhì)01230000*00123024012303B={0,1,2,3,4,5},B上模6乘法*運(yùn)算表如下4500050420454345240342210為零元，1為單位元。

與單位元的可逆性不同，零元一般是不可逆的。例如，R上關(guān)于一般乘法運(yùn)算存在零元0，但0是不可逆的。但是否存在其零元可逆的代數(shù)結(jié)構(gòu)呢？設(shè)該代數(shù)結(jié)構(gòu)單位元為e,零元為z，零元可逆，設(shè)a為z的逆元，則：zοa=e且

zοa=z,故z=e。 若還存在其他元素b,則可以由z=zοb=eοb=b知，該代數(shù)結(jié)構(gòu)只有一個(gè)元素，即：<{a};ο>,其中，aοa=a。

7.2代數(shù)結(jié)構(gòu)及其性質(zhì)

定理7.3

若ο是集合A上的二元運(yùn)算，又設(shè)zl和zr分別是ο的左零元和右零元，則zl=zr=z，且z是ο的惟一的一個(gè)零元。

7.2代數(shù)結(jié)構(gòu)及其性質(zhì)4.冪等元定義7.8

設(shè)ο是集合A上的二元運(yùn)算，如果aοa=a，則稱a是A上的二元運(yùn)算ο的一個(gè)冪等元(Idempotentelement)。顯然，單位元和零元均是冪等元。

7.2代數(shù)結(jié)構(gòu)及其性質(zhì)7.2代數(shù)結(jié)構(gòu)及其性質(zhì)例7.8代數(shù)結(jié)構(gòu)A=<{a，b，c};ο>、B=<{a，b，c};*>。分析A、B是否存在單位元、零元、逆元。

*abcaaabbabccaccοabcaabbbabccaba從代數(shù)結(jié)構(gòu)