離散數(shù)學(xué)第五章第一節(jié)

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

人們?cè)谘芯楷F(xiàn)實(shí)世界中的現(xiàn)象或過(guò)程時(shí)，常常要將它們抽象為一定的數(shù)學(xué)模型。選擇適當(dāng)?shù)臄?shù)學(xué)結(jié)構(gòu)在建立數(shù)學(xué)模型中占有重要的地位。本章討論的代數(shù)系統(tǒng)是集合S上定義了關(guān)系R而形成的簡(jiǎn)單關(guān)系結(jié)構(gòu)<S,R>的推廣。它首先把關(guān)系R限制為集合S上的一個(gè)函數(shù)f，進(jìn)而再推廣到S上兩個(gè)(或更多個(gè))函數(shù)f,g所形成的結(jié)構(gòu)<S,f,g>?？疾爝@些函數(shù)f,g在S上的運(yùn)算性質(zhì)和聯(lián)系，就形成了各類代數(shù)系統(tǒng)。1第五章目錄第5-1講代數(shù)系統(tǒng)的概念第5-2講半群和群第5-3講阿貝爾群和循環(huán)群第5-4講陪集與拉格郎日定理第5-5講同態(tài)與同構(gòu)第5-6講環(huán)和域簡(jiǎn)介2第5-1講代數(shù)系統(tǒng)1.n元運(yùn)算2.代數(shù)系統(tǒng)的概念3.二元運(yùn)算的性質(zhì)4.二元運(yùn)算的特異元素5.課堂練習(xí)6.第5-1講作業(yè)31、n元運(yùn)算

為定義代數(shù)系統(tǒng)，先引入運(yùn)算的概念。

例如f：NNN，f(<x,y>)=x＋y（這里＋表示普通的加法運(yùn)算）就是自然數(shù)集合N上的二元運(yùn)算。而普通的減法不是自然數(shù)集合N上的二元運(yùn)算，因?yàn)閮蓚€(gè)自然數(shù)相減可能得負(fù)數(shù)，而負(fù)數(shù)不是自然數(shù)。這時(shí)稱N對(duì)減法運(yùn)算不封閉。定義1對(duì)集合A，一個(gè)從An到B的映射，稱為集合A上的一個(gè)n元運(yùn)算。如果BA，則稱該運(yùn)算是封閉的。驗(yàn)證一個(gè)運(yùn)算是否為集合A上的n元運(yùn)算主要考慮兩點(diǎn)：（1）A中任意n個(gè)元素都可以進(jìn)行這種運(yùn)算，且運(yùn)算的結(jié)果是唯一的。（2）A中任意n個(gè)元素的運(yùn)算結(jié)果都屬于A，即A對(duì)該運(yùn)算是封閉的。

42、代數(shù)系統(tǒng)的概念例1

設(shè)S={1,2,3,4},定義S上的二元運(yùn)算如下：xy=(xy)mod5,x,yS則<S,>構(gòu)成一個(gè)代數(shù)系統(tǒng)。運(yùn)算還可用表格的形式來(lái)定義，稱為運(yùn)算表：定義2一個(gè)非空集合A及定義在A上的k個(gè)運(yùn)算f1，f2，...fk所組成的系統(tǒng)就稱為一個(gè)代數(shù)系統(tǒng)，。記作<A，f1，f2，...fk>。從表中可以看出，運(yùn)算在S上是封閉的，且滿足交換律和結(jié)合律。有類似性質(zhì)的代數(shù)系統(tǒng)如<I,+>,<I,*>,<(S),>等，這里I表示整數(shù)集合，(S)表示集合S的冪集。而+、*表示通常的加、乘運(yùn)算。表示并運(yùn)算。53、二元運(yùn)算的性質(zhì)（1）定義4設(shè)*為A上的二元運(yùn)算，如果對(duì)任意x,yA,都有x*y=y*x，則稱二元運(yùn)算*在A上是可交換的。

例如，實(shí)數(shù)集合上的加法和乘法是可交換的，但減法不可交換。冪集P(A)上的、、都是可交換的，但是相對(duì)補(bǔ)運(yùn)算不可交換。定義3設(shè)*是定義在集合A上的二元運(yùn)算，如果對(duì)任意x,yA，都有x*yA，則稱運(yùn)算*在A上封閉。定義5設(shè)*為A上的二元運(yùn)算，如果對(duì)于任意的x,y,zA都有(x*y)*z=x*(y*z)，則稱運(yùn)算*在A上是可結(jié)合的。

例如普通的加法和乘法在自然數(shù)集N、整數(shù)集Z、有理數(shù)集Q、實(shí)數(shù)集R和復(fù)數(shù)集C上都是可結(jié)合的。63、二元運(yùn)算的性質(zhì)（2）定義6設(shè)和*是集合A上的兩個(gè)二元運(yùn)算，如果對(duì)任意的x,y,zA,有x*(yz)=(x*y)(x*z)(yz)*x=(y*x)(z*x)則稱運(yùn)算*對(duì)是可分配的。

例如，實(shí)數(shù)集R上的乘法對(duì)加法是可分配的，而在冪集P（S）上和是互相可分配的。定義7設(shè)和*是A上兩個(gè)可交換的二元運(yùn)算，如果對(duì)于任意的x,yA都有x*(xy)＝x；x(x*y)＝x則稱和*滿足吸收律。

例如冪集P(A)上的和運(yùn)算滿足吸收律。73、二元運(yùn)算的性質(zhì)（3）定義8設(shè)為A上的二元運(yùn)算，如果對(duì)于任意的xA都有xx=x，則稱該運(yùn)算適合等冪律。

例如，任何集合A上的并和交運(yùn)算適合等冪律。如果s中的某些x滿足xx=x，則稱x為運(yùn)算的等冪元。

例如，普通數(shù)的加法和乘法不適合等冪律，但0是加法的冪等元，0和1是乘法的等冪元。84、二元運(yùn)算的特異元素（1）定義9設(shè)為A上的二元運(yùn)算，如果存在el(er)A,使得對(duì)任意xA都有elx=x（xer=x）則稱el(er)是A中關(guān)于運(yùn)算的一個(gè)左幺元（右幺元）。若eA關(guān)于運(yùn)算既是左幺元又是右幺元，則稱e為A上關(guān)于運(yùn)算的幺元。在自然數(shù)集N上，0是加法的幺元，1是乘法的幺元。練習(xí)指出冪集P(S)上，運(yùn)算和運(yùn)算的幺元。解：

運(yùn)算的幺元是，運(yùn)算的幺元是S94、二元運(yùn)算的特異元素（2）定理1設(shè)為A上的二元運(yùn)算，el,er分別為運(yùn)算的左幺元和右幺元，則el=er=e，且e為A上關(guān)于運(yùn)算的唯一的幺元。證：因（er為右幺元）el=eler=er（el為左幺元）所以el＝er。令el＝er=e，則e是A中的幺元。假設(shè)e’是A中的另一個(gè)幺元，則有e‘＝ee’＝e，所以e是A中關(guān)于運(yùn)算的唯一的幺元。練習(xí)設(shè)S={,,,}，*運(yùn)算由下表定義,指出*運(yùn)算是否有左右幺元?解：

和都是S中關(guān)于*運(yùn)算的左幺元,*運(yùn)算沒(méi)有右幺元。104、二元運(yùn)算的特異元素（3）定義10設(shè)為A上的二元運(yùn)算，若存在元素θl（θr）A使得對(duì)于任意xA有θlx=θl(x

θr

=θr)則稱θl（θr）是A上關(guān)于運(yùn)算的左零元（右零元）。若θA關(guān)于運(yùn)算既是左零元又是右零元，則稱θ為S上關(guān)于運(yùn)算的零元。例如自然數(shù)集合上0是普通乘法的零元，而加法沒(méi)有零元。練習(xí)指出冪集P(S)上，運(yùn)算和運(yùn)算的零元。解：

運(yùn)算的零元是S，運(yùn)算的零元是。114、二元運(yùn)算的特異元素（4）定理2設(shè)為A上的二元運(yùn)算，θl和θr分別為運(yùn)算的左零元和右零元，則有θl=θr=θ，且θ是A上關(guān)于運(yùn)算的唯一零元。證：設(shè)θl和θr分別為運(yùn)算的左零元和右零元，所以θl=θlθr=θr令θl=θr=θ，則θ是A上關(guān)于運(yùn)算的零元。

假設(shè)θ'也是A中的零元，則有θ'＝θθ'＝θ，所以θ是A中關(guān)于運(yùn)算的唯一的零元。定理3設(shè)為A上的二元運(yùn)算，e和θ分別為運(yùn)算的幺元和零元，如果A至少有兩個(gè)元素，則eθ。證：用反證法。假設(shè)e=θ，則對(duì)xA有x=xe=xθ=θ,此式說(shuō)明A中只有唯一的元素θ,與A中至少含有兩個(gè)元素矛盾。124、二元運(yùn)算的特異元素（5）定義11設(shè)為A上的二元運(yùn)算，eA為運(yùn)算的幺元，對(duì)于xA，如果存在yl（yr）使得ylx=e（xyr=e）,則稱yl（yr）是x的左逆元（右逆元）。若yS既是x的左逆元又是x的右逆元，則稱y是x的逆元。如果x的逆元存在，則稱x是可逆的。例如，在整數(shù)集合Z上加法的幺元是0。對(duì)任何整數(shù)，它的加法逆元都存在，即它的相反數(shù)-x。對(duì)于給定的集合和二元運(yùn)算來(lái)說(shuō)，逆元與幺元及零元不同，如果幺元或零元存在，一定是唯一的。而逆元能否存在，與元素有關(guān)。有的元素有逆元，有的元素沒(méi)有逆元，不同的元素對(duì)應(yīng)著不同的逆元。134、二元運(yùn)算的特異元素（6）定理4設(shè)為A上可結(jié)合的二元運(yùn)算，e為該運(yùn)算的幺元，對(duì)于xA，如果存在左逆元yl和右逆元yr，則有yl=yr=y，且y是x的唯一的逆元。證：設(shè)yl和yr是x的左右逆元,由ylx=e和xyr=e，得yl=yle=yl(xyr)=(ylx)yr=eyr=yr令yl=yr=y，則y是x的逆元。假若y'A也是x的逆元，則y'=y'e=y'(xy)=(y'x)y=ey=y所以y是x唯一的逆元。145、課堂練習(xí)（1）練習(xí)1設(shè)代數(shù)系統(tǒng)<A,*>，其中A={a,b,c}，A上的二元運(yùn)算*定義如下表：解：有些運(yùn)算性質(zhì)可直接從運(yùn)算表看出：*運(yùn)算是封閉的，因?yàn)楸碇忻總€(gè)元素都屬于A。*運(yùn)算可交換，因運(yùn)算表關(guān)于主對(duì)角線對(duì)稱。*運(yùn)算不等冪，因運(yùn)算表主對(duì)角線有的元素與所在行列表頭元素不同。*運(yùn)算有零元c，因?yàn)閏所在行列中的元素都是與它相同。*運(yùn)算有幺元a，因?yàn)閍所在行列中的元素依次與表頭行列一致。a和b均以自身為逆元，因?yàn)閍、b所在行和列交匯處的元素為幺元。

試分析*運(yùn)算的封閉性、交換性、等冪性。A中關(guān)于*是否有幺元和零元？如有幺元，每個(gè)元素是否有逆元？如有，求出逆元。155、課堂練習(xí)（2）練習(xí)2設(shè)Nk={0,1,2,…k-1},在Nk定義運(yùn)算+k如下：對(duì)任意x,yNk解：因?yàn)閷?duì)任意xNk,x+0=x<k,所以x+k0=0+kx=x+0=x，故0是幺元。對(duì)任意xNk，令x+