1、第 三 篇 代數(shù)系統(tǒng)第五章 代數(shù)系統(tǒng)的一般性質(zhì)第六章 幾個典型的代數(shù)系統(tǒng)離散數(shù)學 第三篇代數(shù)系統(tǒng)引入這一部分在集合、關(guān)系和函數(shù)等概念基礎(chǔ)上，研究更為抽象的對象代數(shù)系統(tǒng)。所謂的代數(shù)系統(tǒng)是由集合和集合上定義若干個運算而組成的系統(tǒng)。稱之為代數(shù)系統(tǒng)。主要研究代數(shù)系統(tǒng)的性質(zhì)和特殊的元素；代數(shù)系統(tǒng)與代數(shù)系統(tǒng)之間的關(guān)系，如代數(shù)系統(tǒng)的同態(tài)和同構(gòu)。主要內(nèi)容如下：5.1 二元運算及其性質(zhì) 5.2 代數(shù)系統(tǒng) 5.3 同態(tài)與同構(gòu)6.1 半群 6.2 群 6.3 環(huán)與域離散數(shù)學 第三篇代數(shù)系統(tǒng)5.1.1 二元運算的基本概念定義5.1 設(shè)S為集合,函數(shù)f:SSS稱為S上的一個二元運算,簡稱為二元運算. f:NNN, f(

2、)xy例如: 普通的減法不是自然數(shù)集合上的二元運算,因為兩個自然數(shù)相減可能得負數(shù),而負數(shù)不屬于N.這時也稱集合N對減法運算不封閉.例5.1 1)自然數(shù)集N上的乘法是N上的二元運算,但除法不是.5.1 二元運算及其性質(zhì)2)整數(shù)集合Z上的加法、減法和乘法是Z上的二元運算,而除法不是.3)非零實數(shù)集R*上的乘法和除法都是R*上的二元運算,而加法、減法不是.4)設(shè)Mn(R)表示所有n階實矩陣的集合(n2), 即 則矩陣加法和 乘法都是Mn(R) 上的二元運算.5)S為任意集合,則,-,為S的冪集P(S)上的二元運算.6)S為集合,SS是S上的所有函數(shù)的集合, 則合成運算是SS上的二元運算.5.1 二元

3、運算及其性質(zhì)5.1 二元運算及其性質(zhì)5.1.1 二元運算的基本概念算符: 通常用,*,等符號表示二元運算, 稱為算符. 設(shè)f:SSS是S上的二元運算,對任意的x,yS,如x與y的運算結(jié)果是z, 即f()z,可利用算符簡記為xy=z5.1 二元運算及其性質(zhì)N元運算定義5.2 設(shè)S為集合,n為正整數(shù),則函數(shù) 稱為S上的一個n元運算, 簡稱為n元運算.例: 求一個數(shù)的相反數(shù)是實數(shù)集R上的一元運算;求一個數(shù)的倒數(shù)是非零實數(shù)集R*上的一元運算;在冪集合P(S)上, 如果規(guī)定全集為S, 那么求集合的絕對補運算可以看作是P(S)上的一元運算;在空間直角坐標系中求某一點(x,y,z)的坐標在x軸上的投影可以看

4、作是實數(shù)集R上的三元運算, 因為f()=x, 參加運算的是3個有序?qū)崝?shù), 結(jié)果也是實數(shù).5.1.1 二元運算的基本概念使用算符表示n元運算若f()=b, 則可記為(a1,a2,an)b前綴表示法： (a ) b 一元運算, (a1,a2)b 二元運算, (a1,a2,a3)b 三元運算.如果集合S是有窮集, S上的一元和二元運算也可以用運算表給出. 表5.1和5.2是一元和二元運算表的一般形式.注意: 本書所涉及的代數(shù)系統(tǒng)僅限于一、二元運算5.1 二元運算及其性質(zhì)5.1 二元運算及其性質(zhì)5.1.1 二元運算的基本概念例5.3 設(shè)S=1,2,3,4, 定義S上二元運算如下： xy =(xy)mo

5、d 5, x,yS, 求的運算表.解: (xy)mod 5是xy除以5的余數(shù), 得運算表如下: 1234112342241333142443215.1 二元運算及其性質(zhì)5.1.2 二元運算的性質(zhì)定義5.3 設(shè)為S上的二元運算,如果對任意的x,yS都有 xyyx, 則稱運算在S上是可交換的, 或者說. 在S上適合交換律.例如, 實數(shù)集上的加法和乘法都是可交換的, 但減法不可交換, 在冪集P(S)上的,都是可交換的,但相對補不是可交換的.例5.4 設(shè)Q是有理數(shù)集合,是Q上的二元運算,對任意的a,bQ, ab=a+bab, 問運算是否可交換.解: 因為 ab=a+bab= b+aba=ba 所以在有

6、理數(shù)上是可交換的5.1.2 二元運算的性質(zhì)定義5.4 設(shè)為S上的二元運算, 如果對任意的x,y,zS都有(xy)zx(yz), 則稱運算在S上是可結(jié)合的, 或者說, 在S上適合結(jié)合律.例: 普通的加法和乘法在N,Z,Q,R上都是可結(jié)合的; , 在冪集P(S)上也是可結(jié)合的; 矩陣加法和乘法在Mn(R)上是可結(jié)合的, 其中矩陣加法還是可交換的, 但矩陣乘法不是可交換的.5.1 二元運算及其性質(zhì)5.1.2 二元運算的性質(zhì)例5.6 設(shè)A=, 在A上定義兩個二元運算*, , 如下表所示. 問運算對于*運算可分配嗎？運算*對于運算呢？*解: 容易驗證對于*運算可分配, 但*運算對于運算不可分配.因為:*

7、()=*= (*)(*)= 5.1 二元運算及其性質(zhì)5.1.2 二元運算的性質(zhì)定義5.7 設(shè)和*是S上的兩個可交換的二元運算,如果對任意的x,yS都有 x*(xy)x, x(x*y)x, 則稱和*滿足吸收律.例如, 在冪集P(S)上和是滿足吸收律的.例5.7 設(shè)集合N為自然數(shù)全體, 在N上定義兩個二元運算和*, 對于任意x,yN, 都有 xymax(x,y), x*ymin(x,y)驗證和*滿足吸收律.解: 對于任意a,bN a(a*b)=max(a,min(a,b)=a a*(ab)=min(a,max(a,b)=b 因此,和*滿足吸收律5.1 二元運算及其性質(zhì)5.1 二元運算及其性質(zhì)5.1

8、.2 二元運算的性質(zhì)左幺元, 右幺元,幺元定義5.8 設(shè)為S上的二元運算, 如果存在元素el(或er)S使得對任何xS, 都有 elxx(或xer=x), 則稱el(或er)是S中關(guān)于運算的一個左幺元(或右幺元). 若eS關(guān)于既是左幺元, 又是右幺元, 則稱e為S上關(guān)于運算的幺元.5.1 二元運算及其性質(zhì)誰是幺元?自然數(shù)集合上的加法運算的幺元是誰?自然數(shù)集合上的乘法運算的幺元是誰?在Mn(R)上的矩陣加法的幺元是誰?在Mn(R)上的矩陣乘法的幺元是誰?在冪集P(S)上的運算的幺元是誰?在冪集P(S)上的運算的幺元是誰?R*是非零實數(shù)集, 任意的a,bR*有ab=a, 運算的幺元是誰?5.1.2

9、 二元運算的性質(zhì)定理: 給定集合A,*是A上的一個二元運算, 且集合A中元素的個數(shù)大于1. 如果運算*有幺元e和零元, 則e.證明: 用反證法, 設(shè)=e, 那么對于任意xA, 必有x=e*x=*x=e 于是, A中所有元素都是相同的, 這與A中含有多個元素相矛盾.5.1 二元運算及其性質(zhì)5.1 二元運算及其性質(zhì)5.1.2 二元運算的性質(zhì)左逆元, 右逆元, 逆元定義5.10 設(shè)為S上的二元運算, eS為運算的幺元. 對于任意的xS, 如果存在ylS(或yrS)使得yl xe(或xyre), 則稱yl(或yr)是x的左(或右)逆元. 若yS既是x的左逆元, 又是x的右逆元, 則稱y是x的逆元.自然

10、數(shù)集關(guān)于加法運算只有0有逆元0, 其他數(shù)無逆元.整數(shù)集關(guān)于加法運算的逆元為它的相反數(shù).Mn(R)上矩陣乘法的逆元是M-1.在冪集P(S)上運算的逆元, 只有 有逆元.5.1.2 二元運算的性質(zhì)左逆元, 右逆元, 逆元定理5.3 設(shè)為S上可結(jié)合的二元運算, e為該運算的幺元. 對于xS, 如果存在左逆元yl和右逆元yr, 則有ylyry, 即y是x的唯一的逆元.證明: ylyleyl(xyr)=(ylx)yreyryr 令 yl=yr=y,假設(shè)yS是x的逆元,則有 yyey(xy)(yx)yeyy. 由這個定理可知,對于可結(jié)合的二元運算來說,元素x的逆元如果存在則一定是唯一的.通常把這個唯一的逆

11、元記作x-1 .5.1 二元運算及其性質(zhì)5.1.2 二元運算的性質(zhì)定義5.11 設(shè)為S上的二元運算, 如果對任意的x,y,zS滿足以下條件(1)若xyxz且x不是零元, 則yz,(2)若yxzx且x不是零元, 則yz 就稱運算滿足消去律 例: 整數(shù)集合上加法和乘法, 冪集P(S)上運算和運算滿足消去律嗎? 運算滿足消去律嗎?5.1 二元運算及其性質(zhì)5.1.2 二元運算的性質(zhì)例5.8 對于下面給定的集合和該集合上的運算,指出該運算的性質(zhì), 并求出它的幺元, 零元和所有可逆元素的逆元.(1) Z+, x,yZ+, x*y=lcm(x,y), 即求x,y的最小公倍數(shù).(2) Q, x,y Q, x*

12、y=x+y-xy5.1 二元運算及其性質(zhì)解: (1)*運算可交換, 可結(jié)合, 是冪等的.xZ+, x*1=1*x=x, 所以1為幺元, 不存在零元, 只有1有逆元, 是它自己, 其它正整數(shù)沒有逆元.(2)*運算滿足交換律, 因為x,yQ, x*y=x+y-xy=y+x-yx=y*x*運算滿足結(jié)合律, 因為x,y,zQ，(x*y)*z=(x+y-xy)*z =x+y+z-xy-(x+y-xy)z=x+y+z-xy-xz-yz+xyz=x+y+z-yz- x(y+z-yz)=x+y+z-yz-x(y+z-yz)=x*(y+z-yz)=x*(y*z) 5.1 二元運算及其性質(zhì)*運算不是冪等的; 因為

13、2Q, 2*2=2+2-22=02*運算滿足消去律; x,y,zQ,x1(1為零元), 有x*y=x*z x+y-xy= x+z-xz y-z=x(y-z) (y-z)(x-1)=0 y=z(x1)由于*運算可交換, 右消去律顯然成立.xQ , x*0=x=0*x, 所以0是*的幺元;xQ, x*1=1=1*x, 所以1是*的零元xQ, 欲使x*y=0和y*x=0成立, 即x+y-xy=0解得: y=x/(x-1) (x1)從而有x-1=x/(x-1) (x1)5.1 二元運算及其性質(zhì)5.1.2 二元運算的性質(zhì)例5.9 設(shè)Aa,b,c, A上的二元運算*,如表所示 (1)說明運算*,是否滿足交

14、換律,結(jié)合律, 消去律, 冪等律.(2)求出運算*,的么元, 零元和所有可逆元素的逆元。*abcaabcbbcaccab5.1 二元運算及其性質(zhì)解: *適合交換律,結(jié)合律,消去律,但不適合冪等律;a么元是a,沒有零元;a-1a,b-1c,c-1b 適合交換律, 結(jié)合律,冪等律, 但不適合消去律; 么元是a, 零元是b, 只有a由逆元, a-1a不適合交換律, 適合結(jié)合律, 冪等律, 但不適合消去律; 沒有么元, 沒有零元, 也沒有可逆的元素.5.1 二元運算及其性質(zhì)abcaabcbbbbccbcabcaabcbabccabc5.2 代數(shù)系統(tǒng)代數(shù)系統(tǒng)的概念定義5.12 非空集合S和S上的k個運算

15、f1,f2, fk(其中fi為ni元運算,i=1,2,k)組成的系統(tǒng)稱為一個代數(shù)系統(tǒng), 簡稱代數(shù), 記作 .例如, , , 都是代數(shù)系統(tǒng), 其中為普通加法, 為普通乘法;是代數(shù)系統(tǒng), 其中和分別表示矩陣加法和矩陣乘法; 也是代數(shù)系統(tǒng), 它包含兩個二元運算和一個一元運算.5.2 代數(shù)系統(tǒng)代數(shù)系統(tǒng)的概念 代數(shù)常數(shù) 定義: 二元運算的幺元或零元, 對系統(tǒng)性質(zhì)起著重要的作用, 稱之為系統(tǒng)的特異元素, 或代數(shù)常數(shù). 為了強調(diào)這些特異元素, 通常將它們寫在代數(shù)系統(tǒng)的表達式中, 如5.2 代數(shù)系統(tǒng)子代數(shù)系統(tǒng)定義5.13 設(shè)V=是代數(shù)系統(tǒng), BS且B,如果B對 f1,f2,fk都是封閉的, 且B和S含有相同的

16、代數(shù)常數(shù), 則稱是V的子代數(shù)系統(tǒng), 簡稱子代數(shù).例如, 是的子代數(shù), 因為N對加法封閉, 且它們都具有相同的代數(shù)常數(shù)0. 注意: 不是的子代數(shù). 因為代數(shù)常數(shù)0不出現(xiàn)在N-0中.5.2 代數(shù)系統(tǒng)平凡的子代數(shù)、真子代數(shù)對任何代數(shù)系統(tǒng)V=, 其子代數(shù)一定存在.最大的子代數(shù)就是V本身.如果令V中所有的代數(shù)常數(shù)構(gòu)成的集合是B, 且B對V中所有的運算都是封閉的, 那么, B就構(gòu)成了V的最小的子代數(shù).這種最大與最小的子代數(shù)稱為V的平凡的子代數(shù)如果V的子代數(shù)V=滿足BS,則稱V是V的真子代數(shù).例5.11 設(shè)V=, 令nZ=nz|zZ, n為自然數(shù), 那么,證明是V的子代數(shù).證明: (1) 運算的封閉性 任取

17、nZ中的兩個元素nz1和nz2, 即 nz1,nz2Z. 則有nz1nz2=n(z1z2)nZ, 即nZ對運算是封閉的 (2) 相同的代數(shù)常數(shù) 0=n0nZ, 所以, nN是的子代數(shù).當n=1時, nZ就是V本身, 當n=0時,0Z=0是V的最小的子代數(shù), 而其他的子代數(shù)都是V的非平凡的真子代數(shù).5.2 代數(shù)系統(tǒng)5.2 代數(shù)系統(tǒng)積代數(shù)定義5.14: 設(shè)V1=,V2=是代數(shù)系統(tǒng), 和*為二元運算. V1和V2的積代數(shù)V1V2是含有一個二元運算的代數(shù)系統(tǒng), 即V1V2 =, 其中: S=S1S2, 且對任意的, S1S2有 =例: 設(shè)V1= , V2=, 其中和分別表示整數(shù)加法和矩陣乘法,那么V1

18、V2是 V1V2=. 對任意的如果原來的兩個代數(shù)系統(tǒng)分別含有代數(shù)常數(shù),比如說V1的代數(shù)常數(shù)為a1 , V2的代數(shù)常數(shù)為a2, 就是積代數(shù)V1V2中的代數(shù)常數(shù).例如, V1=,V2=那么積代數(shù)V1 V2 的代數(shù)常數(shù)就是 這時有V1V2=5.2 代數(shù)系統(tǒng)如果V1和V2中的二元運算都是可交換的(可結(jié)合的或冪等的), 則積代數(shù)中相應的二元運算也是可交換的(可結(jié)合的或冪等的);如果e1,e2分別為V1和V2的幺元, 那么就是積代數(shù)V1V2的幺元;若x1在V1中的逆元為x1-1, x2在V2中的逆元為x2-1,則在V1V2中, 的逆元就是.類似地,可以定義3個代數(shù)系統(tǒng)的積代數(shù). 例如, V=, 那么VVV

19、=ZZZ,*,并且對任意的,ZZZ有 *=5.2 代數(shù)系統(tǒng)5.3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu)同態(tài)定義5.15 設(shè)V1=,V2=是代數(shù)系統(tǒng), 和*是二元運算,如果存在映射:S1S2滿足對任意的x,y S1有 (xy)=(x)*(y),則稱是V1到V2的同態(tài)映射,簡稱同態(tài)例如,V1=,V2=,其中為普通加法,為模n加法,即x,yZn,有 xy=(xy)mod n,這里Zn=0,1,n-1. 令:ZZn, (x)= (x)mod n,則是V1到V2的同態(tài). 因為對任意x,yZ有(xy)=(xy)mod n=(x)mod n(y)mod n=(x)(y)又比如令:RR,(x)=ex,那么是到 的同態(tài),因為對

20、任意x,yR,下式成立 (xy) =exy=exey= (x)(y)5.3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu)同態(tài)象、同構(gòu)定義5.16 設(shè)是V1=到V2=的同態(tài), 則稱是V1在 下的同態(tài)象定義5.17 設(shè)是V1=到V2=的同態(tài),如果是滿射的, 則稱為V1到V2的滿同態(tài),記作 ;如果是單射的,則稱為V1到V2的單同態(tài);如果是雙射的, 則稱為V1到V2的同構(gòu),記作 .同態(tài)象、同構(gòu)例5.12 (1)V=, 給定aZ, 令a:ZZ, a(x)=ax, xZ, 那么易證, 任取z1,z2Z有 a(z1z2)=a(z1z2)=az1az2=a(z1)a(z2),所以a是V到自身的同態(tài), 也稱a為V的自同態(tài). 當a=0時,有zZ, 0(z)=0,稱0為零同態(tài),其同態(tài)象為 當a=1時,有zZ, 1(z)=z為Z的恒等映射,顯然是雙射,其同態(tài)象就是.這時