離散第講代數(shù)結(jié)構(gòu)

離散第講代數(shù)結(jié)構(gòu)第1頁，共31頁，2023年，2月20日，星期二2逆元舉例eg10.<Z,+>每一個元都有逆元(0為單位元)<Z+,>只有1有逆元(1為單位元)<Zn,+n>，Zn={0,1,...,n-1}，+n模n加法(0為單位元)<Zn,*n>，Zn={0,1,...,n-1}，*n模n乘法(1為單位元)第2頁，共31頁，2023年，2月20日，星期二3常用運算特異元素第3頁，共31頁，2023年，2月20日，星期二4逆元的特殊作用b°a=c°a°

a-1°

a-1b°

e=c°eb=c第4頁，共31頁，2023年，2月20日，星期二5消去律定義9.11設(shè)A為集合，°為A上二元運算，若?a,b,c∈A,（1）a°b=a°c∧a≠θ?b=c(左消去律)（2）b°a=c°a∧a≠θ?b=c(右消去律)則稱°運算滿足消去律。第5頁，共31頁，2023年，2月20日，星期二6消去律實例Z,Q,R，+，×滿足消去律Mn(R),矩陣+滿足消去律，矩陣×不滿足消去律P(B),⊕滿足消去律，∪、∩、?不滿足消去律設(shè)Zn={0,1,…,n-1}，其中n是正整數(shù)，

V=<Z5,>表示模5乘法的代數(shù)系統(tǒng)，V中的運算滿足消去律。V=<Z4,>？第6頁，共31頁，2023年，2月20日，星期二7代數(shù)系統(tǒng)在集合上定義若干個運算而組成的系統(tǒng)，常稱為代數(shù)系統(tǒng)。

定義9.12：一個非空集合A連同若干個定義在該集合上的運算o1,o2,...,ok所組成的系統(tǒng)就稱為一個代數(shù)系統(tǒng)，記作<A,o1,o2,...,ok>第7頁，共31頁，2023年，2月20日，星期二88同類型的代數(shù)系統(tǒng)定義9.13：如果兩個代數(shù)系統(tǒng)中運算的個數(shù)相同，對應(yīng)運算的元數(shù)相同，且代數(shù)常數(shù)的個數(shù)也相同，則稱這兩個代數(shù)系統(tǒng)具有相同的構(gòu)成成分，也稱它們是同類型的代數(shù)系統(tǒng).

例

V1=<R,+,?,-,0,1>V2=<P(B),∪,∩,～,,B>第8頁，共31頁，2023年，2月20日，星期二99實例同類型的代數(shù)系統(tǒng)僅僅是構(gòu)成成分相同，不一定具有相同的性質(zhì).

V1

V2+和?可交換,可結(jié)合∪和∩可交換,可結(jié)合?對+可分配∪和∩互相可分配+和?不遵從冪等律∪和∩都有冪等律+和?沒有吸收律∪和∩有吸收律+和?都有消去律∪和∩一般沒有消去律V1=<R,+,?,-,0,1>V2=<P(B),∪,∩,～,,B>第9頁，共31頁，2023年，2月20日，星期二10子代數(shù)定義9.14設(shè)V=<A,o1,o2,…,or>是代數(shù)系統(tǒng)，B是A的非空子集.若B對于V中的所有運算封閉（含代數(shù)常數(shù)在內(nèi)），則稱V’=<B,o1,o2,…,or

>為V的子代數(shù)，若B?A,子代數(shù)V’稱為V的真子代數(shù).平凡子代數(shù)：V是V的平凡子代數(shù).第10頁，共31頁，2023年，2月20日，星期二1111子代數(shù)實例<N,+

>是<Z,+

>的子代數(shù)，<N,+,0

>是<Z,+,0>的子代數(shù)<Z+,+,0

>不是<Z,+,0>的子代數(shù)注意代數(shù)常數(shù)一定要在子代數(shù)中出現(xiàn)！第11頁，共31頁，2023年，2月20日，星期二1212積代數(shù)的定義定義9.15：設(shè)V1=<A,°>和V2=<B,*>是同類型的代數(shù)系統(tǒng),°和*為二元運算，在集合A×B上定義二元運算?,?<a1，b1>,<a2，b2>∈A×B,有<a1，b1>?<a2，b2>=<a1°a2,b1*

b2>.

稱V=<A×B,?>為V1與V2的積代數(shù)，記作

V1×

V2.這時也稱V1和V2的因子代數(shù).第12頁，共31頁，2023年，2月20日，星期二1313積代數(shù)舉例例9.9：設(shè)V1和V2分別為模3和模2加的代數(shù)系統(tǒng)，給出V1×

V2的運算表，并說明它的運算是否具有交換律與結(jié)合律，是否具有單位元。V1×

V2={<0,0>,<0,1>,<1,0>,<1,1>,<2,0>,<2,1>}第13頁，共31頁，2023年，2月20日，星期二14運算表<0,0><0,1><1,0><1,1><2,0><2,1><0,0><0,0><0,1><1,0><1,1><2,0><2,1><0,1><0,1><0,0><1,1><1,0><2,1><2,0><1,0><1,0><1,1><1,1><2,0><2,0><2,1><2,1>第14頁，共31頁，2023年，2月20日，星期二1515積代數(shù)與因子代數(shù)性質(zhì)定理9.5：設(shè)V1=<A,°>和V2=<B,*>是同類型的代數(shù)系統(tǒng),V1×

V2=<A×B,?>是它們的積代數(shù).(1)如果°和*運算是可交換（可結(jié)合、冪等）的，那么?運算也是可交換（可結(jié)合、冪等）的；

(2)如果e1和

e2（θ1和θ2

）分別為°和*運算的單位元(零元)，那么<e1,e2>（<θ1,θ2>)也是?運算的單位元(零元)；

(3)如果x和

y分別為°和*運算的可逆元素，那么<x,y>也是

?運算的可逆元素，其逆元就是<x-1,y-1>。第15頁，共31頁，2023年，2月20日，星期二1616積代數(shù)性質(zhì)推廣積代數(shù)的定義可以推廣到具有多個運算的同類型代數(shù)系統(tǒng)。在具有兩個不同運算的情況下，積代數(shù)也保留因子代數(shù)中的分配律和吸收律等性質(zhì)，但是消去律是個例外。第16頁，共31頁，2023年，2月20日，星期二1717舉例例9.10：設(shè)Zn={0,1,…,n-1},其中n是正整數(shù)，V1=<Z5,>,V2=<Z3,>分別表示模5和模3乘法的代數(shù)系統(tǒng).那么V1和

V2中的運算滿足消去律?？紤]積代數(shù)<Z5×

Z3,>,這里的運算不滿足消去律.因為在V1×

V2

中有<2,0><0,2>=<0,0>=<2,0><0,0>,<2,0>不是零元，在上式中用消去律將它消去，就得到<0,2>=<0,0>,顯然這是錯誤的。第17頁，共31頁，2023年，2月20日，星期二18同態(tài)與同構(gòu)

討論兩個代數(shù)系統(tǒng)之間的關(guān)系性質(zhì)同類型的兩個代數(shù)系統(tǒng)可能有著共同的運算V=<Z2Z2,>,*eabceeabcaaecbbbceaccbae第18頁，共31頁，2023年，2月20日，星期二19同態(tài)定義9.16：設(shè)<A,*>，<B,·>是兩個代數(shù)系統(tǒng)，f是從A到B的一個映射，s.t.對a1,a2∈A，有f(a1*a2)=f(a1)·f(a2)，則稱f為由A到B的一個同態(tài)映射，稱A同態(tài)于B，記作AB，稱f(A)為A的一個同態(tài)像，其中f(A)={x|x=f(a),a∈A}B。第19頁，共31頁，2023年，2月20日，星期二20說明同態(tài)映射必須對所有的運算保持等式，包括0元運算在內(nèi)，例如則f不是V的自同態(tài)，因為不保持0元運算第20頁，共31頁，2023年，2月20日，星期二21同態(tài)和映射的比較回憶映射的性質(zhì)：①A中的每一個元都有象

②象唯一③可多對一同態(tài)：①映射②保持運算第21頁，共31頁，2023年，2月20日，星期二22同態(tài)舉例eg1:<Z,>若只對運算結(jié)果的正負感興趣，則此代數(shù)系統(tǒng)運算結(jié)果的特征可由另一代數(shù)系統(tǒng)<B,⊙>來描述，其中B＝{正，負，零}，⊙符合平常的正負運算規(guī)律。定義f:ZB

n(n>0)正

0零

n(n<0)負顯然，a,b∈Z,有f(ab)=f(a)⊙f(b)此時，f為從<Z,>到<B,⊙>的一個同態(tài)。第22頁，共31頁，2023年，2月20日，星期二23同構(gòu)定義:設(shè)f是從A到B的一個同態(tài)，如果f是從A到B的一個滿射，則f稱為滿同態(tài)(注意此時f(A)=B)；如果f是從A到B的一個單射，則稱f為單一同態(tài)；如果f是雙射，則f稱為同構(gòu)映射，并稱A與B是同構(gòu)的，記作A≌B第23頁，共31頁，2023年，2月20日，星期二24同構(gòu)舉例eg2:f:RR+

x5x

則f是從<R,+>,<R+,>的一個單一同態(tài)eg3:f:NNk

xxmodk

則f是從<N,+>到<Nk,+k>的一個滿同態(tài)eg4:f:ZnZ

mnm

則f是從<Z,+>到<nZ,+>的一個同構(gòu)

第24頁，共31頁，2023年，2月20日，星期二25同構(gòu)的意義同構(gòu)是個很重要的概念，形式上不同的代數(shù)結(jié)構(gòu)，若同構(gòu)，則可抽象地把它們看作是本質(zhì)上相同的，只是記代的符號不同而已。

*同構(gòu)的逆仍為同構(gòu)

第25頁，共31頁，2023年，2月20日，星期二26自同構(gòu)定義:從A到A的同態(tài)f稱為A的自同態(tài)，若f為同構(gòu)，則稱為自同構(gòu)。定理:設(shè)G是代數(shù)系統(tǒng)的集合，則G中代數(shù)系統(tǒng)之間的同構(gòu)關(guān)系是等價關(guān)系第26頁，共31頁，2023年，2月20日，星期二27同態(tài)的性質(zhì)同態(tài)的合成仍舊是同態(tài)同態(tài)像是映到的代數(shù)系統(tǒng)的子代數(shù)滿同態(tài)映射（在同態(tài)像中）保持原代數(shù)系統(tǒng)的下述性質(zhì)：交換、結(jié)合、冪等、分配、吸收單位元、零元、逆元消去律不一定保持第27頁，共31頁，2023年，2月20日，星期二28實例1(1)V=<Z,+>,fc:Z→Z,fc(x)=cx,c為給定整數(shù)c=0,零同態(tài);c=±1，自同構(gòu);其它c,單自同態(tài)第28頁，共31頁，2023年，2月20日，星期二29實例2(2)V=<Z6,⊕>,fk:Z6→Z6,fk(x)=(kx)mod6,k=0,1,2,3,4,5k=0,f0

零同態(tài);k=1,f1

恒等映射，自同構(gòu)k=2,f2={<0,0>,<1,2>,<2,4>,<3,0>,<4,2>,<5,4>},k=3,f3={<0,0>,<1,3>,<2,0>,<3,3>,<4,0>,<5,3>}k=4,f4={<0,0>,<1,4>,<2,2>,<3,0>,<4,4>,<5,2>}k=5,f5={<0,0>,<1,5>,<2,4>,<3,3>,<4,2>,<5,1>}自同構(gòu)第29頁，共31頁，2023年，2月20日，星期二30實例3(3)可以推廣到fk:Zn→Zn