離散數學第1頁第9章

代數系統介紹9.1二元運算及其性質9.2代數系統9.3幾個經典代數系統第2頁9.1二元運算及其性質一、二元運算定義(定義9.1)設S為集合，函數f:S×SS稱為S上二元運算，簡稱為二元運算。

怎樣判斷一個運算是否為集合S上二元運算？S中任意兩個元素均能夠進行這種運算，且運算結果是唯一。S中任意兩個元素運算結果都屬于S，即S對該運算是封閉。第3頁9.1二元運算及其性質例1：第4頁9.1二元運算及其性質例2：例3：S為任意集合，則在f:P(A)×P(A)P(A)上，、、、是否為二元運算？第5頁9.1二元運算及其性質二、n元運算定義(定義9.2)設S為集合，n為正整數，則函數

f：S×S×……×SS稱為S上一個n元運算，簡稱為n元運算。（1）當n=1時，則函數f:SS為S上一元運算，如(x)=y（2）當n=2時，則函數f:S×SS為S上二元運算。

(x，y)=z（3）當n=3時，則函數f:S×S×SS為S上三元運算。

(x，y，z)=t第6頁9.1二元運算及其性質例4：在整數集合Z、有理數集合Q、實數集合R上，一個數相反數、倒數是否為這些集合上一元運算？例5：在冪集P(S)上，假如要求全集為S，則求集合絕對補運算～是否為P(S)上一元運算？第7頁9.1二元運算及其性質例6：設S={1,2},給出P(S)上運算～和運算表，其中全集為S。ai~ai

{1,2}{1}{1}{2}{2}{1,2}

P(S)={,{1},{2},{1,2}}

{1}{2}{1,2}

{1}{2}{1,2}{1}{1}

{1,2}{2}{2}{2}{1,2}

{1}{1,2}{1,2}{2}{1}

第8頁9.1二元運算及其性質例7：設S={1,2,3,4},定義S上二元關系以下：

x

y=(x*y)mod5x,yS。 求運算列表。

123411234224133314244321第9頁9.1二元運算及其性質三、二元運算主要性質設為S上二元運算.假如對于任意x,yS都有

xy=yx則稱運算在S上是可交換,或者說運算在S上適合交換律.（1）交換律（定義9.3）注:對于二元運算矩陣來說,二元運算滿足交換律,則二元運算矩陣關于主對角線對稱。第10頁9.1二元運算及其性質設為S上二元運算.假如對于任意x,y,zS都有

(xy)z=x(yz)則稱運算在S上是可結合,或者說運算在S上適合結合律.（2）結合律（定義9.3）注:整數集Z、自然數集N、有理數集Q、實數集R上加法和乘法都是可結合；矩陣加法和乘法也是可結合；集合、、也是可結合；函數復合運算也是可結合。第11頁9.1二元運算及其性質設為S上二元運算,假如對于任意xS都有

xx=x則稱運算在S上適合等冪律.（3）冪等律（定義9.3）集合、是復合等冪律。第12頁9.1二元運算及其性質設和*是S上兩個二元運算,假如對于任意x，y，zS有

x*(yz)=(x*y)(x*z)(左分配律) (yz)*x=(y*x)(z*x)(右分配律)則稱運算*對是可分配，也稱*對適合分配律。（4）分配律（定義9.4）第13頁9.1二元運算及其性質設和*是S上兩個可交換二元運算,假如對于任意x，yS有

x*(xy)=x x(x*y)=x則稱運算*和滿足吸收律。（5）吸收律（定義9.5）比如：冪集P(S)上和運算滿足吸收律。即A,BP(S)

有 A(AB)=A A(AB)=A第14頁9.1二元運算及其性質四、單位元和幺元設為S上二元運算,假如存在(或)S使得對于任何xS都有

x=x(或x=x)則稱(或)是S中關于運算一個左幺元(或右幺元)。若eS關于運算既是左幺元又是右幺元，則稱e為S上關于運算幺元。幺元定義（定義9.6）第15頁9.1二元運算及其性質例8：自然數集N上加法

幺元，幺元是

。自然數集N上乘法

幺元，幺元是

。自然數集N上除法

幺元，幺元是

。冪集P(S)上運算

幺元，幺元是

。冪集P(S)上運算

幺元，幺元是

。第16頁9.1二元運算及其性質設為S上二元運算,，分別為運算左幺元和右幺元，則有

==e且e為S上關于運算唯一幺元。單位元和幺元唯一定理（定理9.1）第17頁9.1二元運算及其性質四、零元設為S上二元運算,假如存在(或)S使得對于任何xS都有

x=(或x=)則稱(或)是S中關于運算一個左零元(或右零元)。若S關于運算既是左零元又是右零元，則稱為S上關于運算零元。零元定義（定義9.6）第18頁9.1二元運算及其性質例9：自然數集N上加法

零元，零元是

。自然數集N上乘法

零元，零元是

。自然數集N上除法

零元，零元是

。冪集P(S)上運算

零元，零元是

。冪集P(S)上運算

零元，零元是

。第19頁9.1二元運算及其性質設為S上二元運算,，分別為運算左零元和右零元，則有

==且為S上關于運算唯一零元。零元唯一定理（定理9.2）第20頁9.1二元運算及其性質設為S上二元運算,e，分別為運算幺元和零元，假如S最少有兩個元素，則e。幺元與零元定理證實：假設e=,則xS有

x=ex=x=

則x==e,S中只有一個元素 又因為S中最少有兩個元素，矛盾 所以：e 第21頁9.1二元運算及其性質五、逆元逆元定義（定義9.6）設為S上二元運算,eS為運算幺元，對于xS，假如存在使得

則稱是x左逆元（或右逆元）。若yS既是x左逆元又是x右逆元，則稱y是x逆元。假如x逆元存在，則稱x是可逆。第22頁9.1二元運算及其性質逆元唯一定理（定理9.3）設為S上可結合二元運算,eS為運算單位元，對于xS，假如存在左逆元和右逆元則有

則y是x唯一逆元。第23頁9.1二元運算及其性質六、消去律（定義9.7）設為S上二元運算,假如對于任意x,y,zS滿足以下條件：

(1)若xy=xz且x，則y=z。

(2)若yx=zx且x，則y=z。那么稱運算滿足消去律，其中(1)稱作左消去律，(2)稱作右消去律。第24頁9.1二元運算及其性質例10：設是字母有窮集，稱為字母表，中有限個字母組成序列稱為上串，對任何串，串中字母個數叫做串長度，記作||，長度是0串叫空串，記作，對任給自然數k，令它是上全部長度為k串集合，尤其：串連接運算：第25頁第九章

代數系統普通性質9.1二元運算及其性質9.2代數系統9.3幾個經典代數系統第26頁9.2代數系統一、代數系統定義(定義9.8)非空集合S和S上k個運算f1,f2……fk(其中fi為ni元運算，i=1，2,…，k)組成系統稱為一個代數系統，簡稱代數，記作<S,f1,f2……fk>。判斷代數系統方法： 判斷該系統中每個運算是否為n元運算。第27頁9.2代數系統例11：<N,+>、<N,+,->、<Z,+,->、<Z,+,,×>是否為代數系統？<P(S),,>,<P(S),,->是否為代數系統？第28頁9.2代數系統二、特異元素、代數常數定義代數系統中對于給定二元運算存在幺元或零元，而且它們對該系統性質起著主要作用，稱之為該系統特異元素或代數常數。比如：

<Z,+,0>、<Z,*,1>、<P(S),,,,S,>第29頁9.2代數系統三、子代數系統、子代數定義(定義9.13)設V={S,f1,f2,……,fk}是代數系統，BS且B，假如B對f1,f2,……,fk都是封閉，且B和S含有相同代數常數，則稱<B,f1,f2,……,fk>是V子代數系統，簡稱子代數。比如：

v1=<N,+,0> v2=<Z,+,0>第30頁9.2代數系統例12：設V=<Z,+,0>，令

nZ={nz|zZ}.n為自然數，那么，<nZ,+,0>是否為V子代數？第31頁9.2代數系統四、平凡子代數與真子代數定義對任何代數系統V={S,f1,f2,……,fk}，最大子代數就是V本身。假如令V中全部代數常數組成集合是B，且B對V中全部運算都是封閉，則，B就組成了V最小子代數。這種最小和最大子代數稱為V平凡子代數。假如代數系統V子代數V’={B,f1,f2,……,fk}，滿足

BS，則稱V’為V真子代數。第32頁9.2代數系統五、積代數定義（定義9.14）設V1=<S1,

>,V2=<S2,*>是代數系統，和*為二元運算。V1和V2積代數V1×V2是含有一個二元運算代書系統，即V1×V2=<S,>,其中S=S1×S2,對任意<x1,y1>,<x2,y2>S1×S2有

<x1,y1><x2,y2>=<x1x2,y1*y2>第33頁9.2代數系統例13：設V1=<Z,+,0>，V2=<Z,*,1>,求V1與V2積代數。V1×V2=<Z×Z,,<0,1>>,其中：

<x1,y1>

<x2,y2>=<x1+x2,y1*y2>第34頁9.2代數系統六、同態定義(定義9.15)設V1=<S1,

>,V2=<S2,*>是代數系統，

和*是二元運算。假如存在映射：S1S2，若x，yS1都有

(x

b)=(x)*(y)則稱是V1到V2同態映射，簡稱同態。第35頁9.2代數系統例14：(1)G1=<Z,+>，G2=<Zn,

>,令

：ZZn，(x)=(x)modn

則是否為G1到G2同態？第36頁9.2代數系統例15：(2)G1=<R,+>，G2=<R+,

>,令

：RR+

，(x)=ex

則是否為G1到G2同態？第37頁9.2代數系統七、同態象定義(定義9.16)設

是V1=<S1,

>到V2=<S2,*>同態，則稱<(S1),*>是V1在下象。第38頁9.2代數系統八、滿同態、單同態、同構和自同態(定義9.17)(1)若：G1G2是滿射，則稱為滿同態，這時也稱

G2是G1同態像，記作。(2)若：G1G2是單射，則稱為單同態。(3)若：G1G2是雙射，則稱為同構，記作。(4)若G1=G2，則稱是群G自同態。第39頁9.2代數系統例16：設V=<R+,

>，其中為普通成法。對任意xR+令1(x)=|x|，2(x)=2x,3(x)=x2,4(x)=1/x,5(x)=-x,則分析他們是否為V到V同態，假如是，則分別為何同態。第40頁第九章代數系統介紹9.1二元運算及其性質9.2代數系統9.3幾個經典代數系統半群與群第41頁(1)半群與群一、半群定義(定義9.13)（1）設V=<S,

>是代數系統，

為二元運算，假如

是可結合，則稱V為半群。（2）設V=<S,

>是半群，若eS是關于運算單位 元，則稱V是含幺半群，也叫獨異點。有時也將獨異點V記作<S,

,e>。第42頁(1)半群與群例1：(1)<Z,+>,<N,+>,<Q,+>,<R,+>都是半群，其中+表示普通加法。(2)<,>是半群，其中是有窮字母表，表示連接運算。(3)<P(B),>是半群，也是獨異點，其中為集合對稱差運算。(4)<Zn,>是半群，其中Zn={0,1,……,n-1},表示模n加法。第43頁(1)半群與群二、冪運算定義半群V=<S,

>，對于任意xS，要求：

普通乘法冪、關系冪等都遵照這個冪運算規則。冪運算運算規則：對獨異點有：第44頁(1)半群與群三、子半群定義半群子代數叫做子半群，獨異點子代數叫做子獨異點。若V=<S,

>是半群，TS，只要T對V中運算封閉，那么<T,>就是V子半群。而對獨異點V=<S,,e>來說，TS，不但T對V中運算封閉，而且eT，這時<T,,e>才組成V子獨異點。第45頁(1)半群與群例2：設獨異點V1=<Z,+,0>，V2=<nZ,+,0>,V2是否為V1子獨異點？第46頁(1)半群與群四、積半群設V1=<S1,

>，V2=<S2,*>是半群（或獨異點），則V1×V2=<S1×S2,>也是半群，且：

<a,b>，<c,d>S1×S2，<a,b><c,d>=<ac,b*d>稱V1×V2

為V1和V2積半群。若V1和V2是獨異點，其單位元為e1和e2，則<e1,e2>是V1×V2中單位元。所以V1×V2也是獨異點。第47頁(1)半群與群五、半群同構(1)設V1=<S1,

>，V2=<S2,*>是半群，

:S1S2。若對任意

x，yS1有

(xy)=(x)*(y)

則稱為半群V1到V2同態映射，簡稱為同態。(2)設V1=<S1,,e1>，V2=<S2,*,e2>是獨異點，

:S1S2。若對任意x，yS1有

(xy)=(x)*(y)且(e1)=e2

則稱為獨異點V1到V2同態映射，簡稱為同態。第48頁(1)半群與群例3：設半群V1=<S,

>，獨異點V2=<S,,e>。其中為矩陣乘法，e為2階單位矩陣。令則是半群V1=<S,

>到本身同態，稱V1自同態。但不是獨異點

V2=<S,

,e>自同態。第49頁(1)半群與群六、群定義(定義9.14)設<G,

>是代數系統，

為二元運算。假如運算是可結合，存在單位元eG，而且對于G中任何元素x都有G，則稱<G,>為群。第50頁(1)半群與群例6：(1)<Z,+>,<N,+>,<Q,+>,<R,+>，其中+表示普通加法。(2)<,>其中是有窮字母表，表示連接運算。(3)<P(B),>，其中為集合對稱差運算。(4)<Zn,>，其中Zn={0,1,……,n-1},表示模n加法。第51頁(1)半群與群例7：設G={e,a,b,c},

為G上二元運算,它由一下運算表給出。判斷<G,>是否為群?

eabceeabcaaecbbbceaccbae第52頁(1)半群與群例8：設<G1,>,<G2,*>是群,在G1×G2上定義二元運算以下：

<a,b>,<c,d>G1G2,<a,b><c,d>=<ac,b*d>

稱<G1×G2,>是G1與G2直積。則<G1×G2,>是否是群？第53頁(1)半群與群七、群相關概念定義(1)若群G是有窮集，則稱G是有限群，不然稱為無限群。群G基數稱為群G階。(2)只含單位元群稱為平凡群。(3)若群G中二元運算是可交換，則稱G為交換群或

阿貝爾群。第54頁(1)半群與群八、群冪次定義注：半群和特異點不一樣，群中元素能夠定義負整數次冪。設G是群，aG，nZ，則an次冪第55頁(1)半群與群九、元素階、無限階元設G是群，aG，使得等式成立最小正整數k稱為a階，記作|a|=k，這是也稱a為k階元。若不存在這么正整數k，則稱a為無限階元。第56頁(1)半群與群十、群中元素階性質<G,*>為群，aG，且|a|=r。設k是整數，則例：設G是群，a，bG是有限階元。證實第57頁(1)半群與群十一、群冪運算定理(定理9.4)設G是群，則G中冪運算滿足：第58頁(1)半群與群十二、方程唯一解定理(定理9.5)G為群，

a,bG，方程ax=b和ya=b在G中有解且有唯一解。例9：設群G=<P({a,b}),

>，其中

為集合對稱差運算。解以下方程：

{a}X=，Y{a,b}={b}第59頁(1)半群與群十三、群中二元運算消去律(定理9.6)G為群，則G中適合消去律，即對任意a,b,cG有(1)若ab=ac，則b=c。(2)若ba=ca，則b=c。例10：設G為群，a,bG，k，證實第60頁(1)半群與群例11：設G為群，a，bG，且證實ab=ba。第61頁(1)半群與群十四、子群定義(定義9.15)設群<G,*>，H是G非空子集，假如H關于G中運算*組成群，則稱H是G子群，記作HG。若H是G子群，HG，則稱H是G真子群，記作H<G。注：

G和｛e｝是G平凡子群。第62頁(1)半群與群十五、子群判定定理一(定理9.8)設G是群，H是G非空子集。如對任意x,yH都有xy-1H則H是G子群。第63頁(1)半群與群例：設G為群，ａＧ，令 Ｈ＝｛ａｋ｜ｋＺ｝即ａ全部冪組成集合，則求證Ｈ是Ｇ子群。第64頁(1)半群與群十六、循環群定義(定義9.16)設G是群，若存在aG使得

G={|kZ}則稱G是循環群，記作G=<a>，稱a為G生成元。注：(1)任何素數階群都是循環群。

(2)循環群生成元可能不止一個。第65頁(1)半群與群例13：(1)G=<Z,+>是否為循環群？(2)G=<R,+>是否為循環群？(3)G=<R,×>是否為循環群？(4)G=<Zn,

>，是模n加法，則G是否為循環群？(5)G={P(A),

}是否為循環群？(6)G={nZ,+}是否為循環群？第66頁(1)半群與群例14：設A={1,2,3,4,5},<P(A),

>組成群，其中為集合對稱差。（1）求解群方程{1,3}X={3,4,5}

（2）令B={1,4,5}，求由B生成循環子群<B>第67頁(1)半群與群十七、循環群生成元求法設G=<a>是循環群。（1）若G是無限循環群，則G只有兩個生成元，即a和（2）若G是n階循環群，則G含有(n)個生成元。對于任何小于等于n且與n互素正整數r，是G生成元。第68頁(1)半群與群例15：(1)設G={e,a,……,a11}是12階循環群，則它生成元有幾個，分別是什么？(2)G=<Z9,

>是模9整數加群，則它生成原有幾個，分別是什么？(3)G=<3Z,+>，則G上生成元有幾個，分別是什么？第69頁(1)半群與群十八、循環群子群求法（1）設G=<a>是循環群，則其全部子群均為循環群（2）設G=<a>是無限循環群，則G子群除｛e｝外都是無限循環群。（3）設G=<a>是n階循環群，則對n每個正因子d，G恰好含有一個d階子群。第70頁(1)半群與群例16：G=<Z,+>是無限循環群，其生成元為1和－1，則列出G全部循環子群。<10>={0}=0Z<11>={……，-1,0,1,……}=Z<12>={……-4，-2,0,2,4,……}=2Z<1n>={……-2n，-n,0,n,2n,……}=nZ……第71頁(1)半群與群例17：G=<Z12,

>是12階循環群，列出G全部子群。<112/12>=Z12<112/6>={0,2,4,6,8,10}<112/4>={0,3,6,9}<112/3>={0,4,8}<112/2>={0,6}12正因子為：1,2,3,4,6,12<112/1>={0}第72頁(1)半群與群例18：設G1=<a2>={e,a2,a-2,a4,a-4,……}是無限循環群，則G1子群是什么？<(a2)0>={e}<(a2)m>=<a2m>={e,a2m,a-2m,a4m,a-4m,……}m是正整數第73頁(1)半群與群例19：設G2=<a2>是9階循環群，則G2子群是什么？<(a2)9/9>=<a2>=G2<(a2)9/3>={e,a6,a12}9正因子有：1,3,9<(a2)9/1>={e}第74頁(1)半群與群十九、置換定義(定義9.17)設S=