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

1、離散數(shù)學(xué)第五章第1頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五代數(shù)系統(tǒng)第五章代 數(shù) 結(jié) 構(gòu)1代數(shù)系統(tǒng)的引入2運(yùn)算及其性質(zhì)3半群4群與子群5阿貝爾群和循環(huán)群7*陪集與拉格朗日定理8同態(tài)與同構(gòu)9環(huán)與域第2頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五1代數(shù)系統(tǒng)的引入舉例：在一個集合上的運(yùn)算：將實(shí)數(shù)集合 R 上的每一數(shù) a0 映射成它的倒數(shù)1/a，就可以將該映射稱為在集合R 上的一元運(yùn)算；在集合R上，對任意兩個數(shù)所進(jìn)行的普通加法和乘法，都是在集合R上的二元運(yùn)算。對于集合R上的任意三個數(shù)的運(yùn)算，就是集合R上的三元運(yùn)算。第3頁，共72頁，2022年，5月20日，11點(diǎn)12分，星

2、期五1代數(shù)系統(tǒng)的引入定義:設(shè)Z是一個集合,f是一個函數(shù),f：ZnZ,則稱f為Z中的n元運(yùn)算,整數(shù)n稱為運(yùn)算的階（元,次）。若n=1,則稱f： ZZ為一元運(yùn)算； 若n=2,則f： Z2Z為二元運(yùn)算。本章主要討論一元運(yùn)算和二元運(yùn)算。例：（1）在整數(shù)I和實(shí)數(shù)R中,+,-,均為二元運(yùn)算,而對而言就不是二元運(yùn)算 ; （2）在集合Z的冪集(z)中,均為二元運(yùn)算,而“”是一元運(yùn)算；第4頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五定義:一個非空集合S連同若干個定義在該集合上的運(yùn)算f1,f2,.,fk所組成的系統(tǒng)就稱為一個代數(shù)系統(tǒng)，記作。一個代數(shù)系統(tǒng)需要滿足以下條件：有一個非空集合S；有一些建立在

3、集合S上的運(yùn)算；1代數(shù)系統(tǒng)的引入第5頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五定義:設(shè)*是集合S上的二元運(yùn)算,對任一x,yS有xyS則稱運(yùn)算在S上是封閉的。在f：Z2Z二元運(yùn)算的定義中,本身要求滿足運(yùn)算是封閉的。 例：（1）在集合A=1，2，3，4，5，1/2，1/3，1/4，1/5，做任意元素的倒數(shù)運(yùn)算；可以看作是：將集合A上的每一數(shù)a映射成他的倒數(shù)1/a； （2）在前例中,R,I集合中+,-,運(yùn)算； (z)的元素中, ,運(yùn)算等均為封閉的。 (3)在正整偶數(shù)的集合E中,對,+運(yùn)算是封閉的,在正整奇數(shù)的集合中,對運(yùn)算是封閉的,而對+運(yùn)算不是封閉的。 2運(yùn)算及其性質(zhì)第6頁，共72

4、頁，2022年，5月20日，11點(diǎn)12分，星期五在整數(shù)集合 I 上定義 如下：其中的+， 分別表示數(shù)的加法和乘法。 那么 是一個從 I2 到 I 的函數(shù)， 在集合 I 上是封閉的，（I， ） 就是一個代數(shù)系統(tǒng)。 2運(yùn)算及其性質(zhì)第7頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五 不封閉的例子：一架自動售貨機(jī)，能接受五角硬幣和一元硬幣，而所對應(yīng)的商品是桔子水、可樂和冰淇凌。當(dāng)投入上述硬幣的任何兩枚時，自動售貨機(jī)將按照表中供應(yīng)相應(yīng)的產(chǎn)品： 表格左上角的記號 * 可以理解為一個二元運(yùn)算的運(yùn)算符。這個例子中的二元運(yùn)算 * 不是集合五角硬幣 ，一元硬幣上的封閉運(yùn)算。*五角硬幣 一元硬幣五角硬幣

5、桔子水可口可樂一元硬幣可口可樂冰淇凌第8頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五2運(yùn)算及其性質(zhì)定義:設(shè)*是集合S上的二元運(yùn)算,對任一x,yS有xy=y x,則稱運(yùn)算在S上是可交換的（或者說在S上滿足交換律）。例：在整合集合 I 上定義運(yùn)算 ：對任何其中的 +， 分別表示數(shù)的加法和乘法。 那么 可以滿足交換律？第9頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五2運(yùn)算及其性質(zhì)定義:設(shè)*是集合S上的二元運(yùn)算,對任一x,y,z S都有（x y） z=x （y z）,則稱運(yùn)算在S上是可結(jié)合的（或者說*在S上滿足結(jié)合律）。EX：設(shè)A是一個非空集合， 是A上的二元運(yùn)算，對于任意

6、a，bA，有ab=b，證明：是滿足結(jié)合律的。證： 對于任意的a，b ，c A，（a b）c= b c= c而a（bc）=a c= c，（ab）c= a（bc） 是滿足結(jié)合律的第10頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五例：代數(shù)系統(tǒng)（N，+，）。其中+，分別代表數(shù)的加法和乘法。 對+是滿足分配律的.定義:設(shè)和是集合S上的二個二元運(yùn)算, 對任一x,y,z S有 x （y z）=（x y） （x z）； （y z） x=（y x） （z x）,則稱運(yùn)算對是可分配的（或稱對滿足分配律）。 2運(yùn)算及其性質(zhì)第11頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五2運(yùn)算及其性質(zhì)定

7、義:設(shè)*是S上的二元運(yùn)算,若對任一x S有x x=x,則稱滿足等冪律。討論定義：1)S上每一個元素均滿足xx=x,才稱在S上滿足冪等律；2)若在S上存在元素某一元素xS有x x=x,則稱x為S上的冪等元素；3)由此定義,若x是冪等元素,則有x x=x和xn=x成立。定義:設(shè)，是定義在集合S上的兩個可交換二元運(yùn)算，如果對于任意的x,yS，都有：x (x y)=x；x (xy)=x則稱運(yùn)算和運(yùn)算滿足吸收律。第12頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五2運(yùn)算及其性質(zhì)例：（1）在實(shí)數(shù)集合R中,+,是可交換,可結(jié)合的,對+是滿足分配律的,“0”對+是等冪元素,而其它不為等冪元素,在實(shí)

8、數(shù)集合R中,“-”法是不可交換,不可結(jié)合的；（2）在(z)中, ,均是可交換,可結(jié)合的, 對, 對均是可分配的； (z)中任一元素,對,均是等冪元素。滿足等冪律；而(z)中,對稱差是可交換,可結(jié)合的。除(s) =以外不滿足等冪律。 = ,而除以外的A (z)有A AA。第13頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五2運(yùn)算及其性質(zhì)下面定義特殊元素：幺元,零元和逆元。定義：設(shè)*是集合Z中的二元運(yùn)算,(1)若有一元素el Z,對任一x Z有el*x=x；則稱el為Z中對于*的左幺元； (2)若有一元素er Z,對任一x Z有x* er=x；則稱er為Z中對于*的右幺元。 (3)如果

9、Z中的一個元素 e,它既是左幺元,又是右幺元,則稱e為Z中關(guān)于運(yùn)算*的幺元.即對于任意xZ,有e*x=x*e.定理：若el和er分別是Z中對于*的左幺元和右幺元,則el= er = e，且e Z是唯一的。第14頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五2運(yùn)算及其性質(zhì) el和er分別是對*的左,右左元， 則有el * er = er = el 有el = er = e成立。 再證明幺元e是唯一的。用反證法：假設(shè)有二個不同的幺元e1和e2,則有e1* e2= e2= e1,這和假設(shè)相矛盾。若存在幺元的話一定是唯一的。例：（1）在實(shí)數(shù)集合R中,對+而言, e+=0；對而言, e*=1

10、 ；（2）在(E)中,對而言, e =E（全集合）；對而言, e =（空集）；（3）命題邏輯中，對而言，e =F（永假式）； 對而言， e =T（永真式）。第15頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五例：設(shè)代數(shù)系統(tǒng)（N，*），* 的定義為：對那么，（N，*）有沒有幺元？左幺元？右幺元？2運(yùn)算及其性質(zhì)解：對任何 ，因此 1 是右幺元。但 1 不是左幺元，因為所以（N，*）沒有左幺元，當(dāng)然也就沒有幺元。第16頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五定義：設(shè)*是對集合Z中的二元運(yùn)算， （1）若有一元素l Z，且對每一個x Z有 l *x= l ，則稱l 為Z中對

11、于*的左零元； （2）若有一元素r Z，且對每一個x Z有 x* r= r ，則稱r為Z中對于*的右零元。 (3)如果Z中的一個元素 ,它既是左零元,又是右零元,則稱為Z中關(guān)于運(yùn)算*的零元.對于任意xZ,有*x=x*=2運(yùn)算及其性質(zhì)下面介紹左零元，右零元，零元第17頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五2運(yùn)算及其性質(zhì)定理：若l和r分別是Z中對于*的左零元和右零元，則l = r =，且 Z是唯一的.證明：方法同幺元。例：（1）在實(shí)數(shù)集合R中，對而言,，L = r =0 （2）在(E)中，對而言， = ； 對而言， = E ；（3）命題邏輯中，對而言， =T ； 對而言， =

12、F。第18頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五2運(yùn)算及其性質(zhì)定義：設(shè)*是Z中的二元運(yùn)算，且Z中含幺元e，令x Z，（1）若存在一xlZ，能使xl *x= e，則稱xL是x的左逆元,并且稱x是左可逆的；（3）若元素x既是左可逆的，又是右可逆的，則稱x是可逆的，且x的逆元用x-1表示。（2）若存在一xr Z，能使x* xr = e，則稱xr是x的右逆元，并且稱x是右可逆的；下面介紹左逆元，右逆元，逆元第19頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五因此，關(guān)于逆元，下述結(jié)論是正確的：(1)只有當(dāng)幺元存在時，才考慮逆元。(2)逆元是“局部”的，也就是說，逆元是針對

13、具體元素而定的，有些元素可能有逆元，有些元素則可能沒有逆元。如果 a 和 b 都有逆元且 a b，則 a-1 和 b-1 也不相同。(3)設(shè) e 為幺元，只有當(dāng) a b = e 和 b a = e 同時成立時，b才能是 a 的逆元，如果只有一個成立，b 也不是 a 的逆元。2運(yùn)算及其性質(zhì)第20頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五2運(yùn)算及其性質(zhì)證明： （1）先證左逆元=右逆元： 設(shè)xL和xr分別是x Z的左逆元和右逆元，x是可逆的和*是可結(jié)合的（條件給出） xl *x=x* xr = e xl *x* xr =（ xl*x）* xr = e * xr= xr ； xl *x

14、* xr = xl*(x* xr) = xl* e = xl xr = xl定理：設(shè)Z是集合，并含有幺元e 。*是定義在Z上的一個二元運(yùn)算，并且是可結(jié)合的。若x Z是可逆的，則它的左逆元等于右逆元，且逆元是唯一的。第21頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五2運(yùn)算及其性質(zhì)（2）證明逆元是唯一的（若有的話）：假設(shè)x1-1和x2-1均是x的二個不同的逆元，則x1-1= x1-1*e= x1-1 *（x* x2-1 ）=（ x1-1 *x）* x2-1 = e * x2-1 = x2-1，這和假設(shè)相矛盾。x若存在逆元的話一定是唯一的。推論(x-1)-1 =x , e-1= e例：

15、（1）在實(shí)數(shù)集合R中，對“+”運(yùn)算，對任一xR有 x-1 =-x，x+（-x）=0，因為加法幺元為0.第22頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五2運(yùn)算及其性質(zhì) 對“”運(yùn)算，乘法幺元為1，則對任一x R有x-1 =1x（x0） x 1x =1定理：設(shè)是一個代數(shù)系統(tǒng),且集合A中的元素個數(shù)大于1,如果該代數(shù)系統(tǒng)中存在幺元e和零元，則 e。所以若是一個代數(shù)系統(tǒng),且|A|1,如果該代數(shù)系統(tǒng)有零元，則零元一定不存在逆元。*x=x*=。 第23頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五EX：設(shè)集合S=， ，定義在S上的一個二元運(yùn)算如下表所示，試指出代數(shù)系統(tǒng)（S，）中各個

16、元素的左、右逆元情況。 解：是幺元， 是 的左逆元 ， 是 的右逆元 ； 是 、 的左逆元， 、是 右逆元 ； 是 的左逆元 ， 是 的右逆元； 是 的左逆元， 是 的右逆元。第24頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五3 半群定義：一個代數(shù)系統(tǒng)， S為非空集合， 是S上的二元運(yùn)算，如果運(yùn)算是封閉的，則稱代數(shù)系統(tǒng)為廣群。定義：設(shè)是一代數(shù)系統(tǒng)，S為非空集合， 是S上的二元運(yùn)算，若(1)運(yùn)算是封閉的。(2) 運(yùn)算滿足結(jié)合律，則稱為半群。例： , , ,均為半群定義：對于*運(yùn)算，擁有幺元的半群稱為獨(dú)異點(diǎn).例： , 均為獨(dú)異點(diǎn) 而就不為獨(dú)異點(diǎn)。 第25頁，共72頁，2022年，5月

17、20日，11點(diǎn)12分，星期五3 半群例：設(shè)S為非空集合， (S)是S的冪集，則 ,均為獨(dú)異點(diǎn)。而，其中max(x1,x2)取二者之大值；，其中min(x1,x2)取二者之小值，均不為獨(dú)異點(diǎn)（不存在幺元）。則為獨(dú)異點(diǎn)，其中 e =0定義：設(shè)是一半群，TS，且*在T上是封閉的，那么也是半群，稱是 的子半群。第26頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五3 半群討論定義：（1）因為*在S上是可結(jié)合的，而TS且*在T上是封閉的，所以*在T上也是可結(jié)合的。 （2）由定義可知， SS ， 也是的子半群,為了和其它子半群相互區(qū)別，稱是S的“平凡子半群”;第27頁，共72頁，2022年，5月

18、20日，11點(diǎn)12分，星期五定義：設(shè)*是S上的二元運(yùn)算,對任一xS,則：x1=x, x2=x*x,xn=xn-1*x定理：設(shè)*是S上的二元運(yùn)算,且x S,對任一m,n I+有 （1）xmxn=xm+n （2）(xm)n=xmn3 半群 定理：設(shè) 是獨(dú)異點(diǎn)，則在關(guān)于運(yùn)算*的運(yùn)算表中一定沒有相同的行和列。第28頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五證明：（1） xmxn= (xm x) x x = (xm+1 x) x x n n-1 =.= xm+n （2）(xm)n= xm xm= xm+m xm xm=xmn n n-13 半群第29頁，共72頁，2022年，5月20日，

19、11點(diǎn)12分，星期五3 半群證明：因是半群，對任意的bS，由*的封閉性，b*bS，b3S，b4S，由于S是有限集，必有ij，使bi=bj設(shè)：p=j i，則bj=bp*bi，即： bi=bp*bi當(dāng)qi時，bq=bp*bq，又因p1，總可以找到k1，使kpi，對S中的bkp有bkp=bp*bkp=bp*(bp*bkp)=b2p*bkp =b2p*(bp*bkp)=b3p*bkp=.=bkp*bkp令a=bkp，則a*a=a。定理：如果半群的集合S為有限集，則必有aS，使a*a=a。第30頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五3 半群定理：設(shè)是獨(dú)異點(diǎn)，對于任意a，bS，且a，

20、b均有逆元，則a)(a-1)-1=ab)a*b有逆元，且(a*b)-1=b-1*a-1證明：a)因為a-1是a的逆元，即a* a-1= a-1*a=e 所以 (a-1)-1=a b)因為(a*b)*(b-1*a-1)= a*(b*b-1)*a-1=a*e*a-1=e 同理可證： (b-1*a-1) * (a*b)=e 所以 (a*b)-1=b-1*a-1第31頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群1.群的定義定義設(shè)是一代數(shù)系統(tǒng)，S是非空集合，*為S上的二元運(yùn)算，它滿足以下四個條件時，則稱為群（1）*運(yùn)算是封閉的；（2） *運(yùn)算是可結(jié)合的；（3）存在幺元e；（4）

21、S中每一個元素均有逆元。例：, ,等均為群（其中Z2 =0,1, Z3 =0,1,2 ），而,只是含幺半群(獨(dú)異點(diǎn))而不是群。第32頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群例：設(shè)M= 0,60,120,240,300,180表示平面上幾何圖形順時針旋轉(zhuǎn)的六種位置，定義一個二元運(yùn)算*，對M中任一元素a,b有a*b=圖形旋轉(zhuǎn)(a+b)的角度，并規(guī)定當(dāng)旋轉(zhuǎn)到360時即為0，試驗證是一個群。*0601201802403000060120180240300606012018024030001201201802403000601801802403000601202402403

22、00060120180300300060120180240第33頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群（1）運(yùn)算是封閉的（2）*是可結(jié)合的（3）幺元為0 ；（4）每一個元素均有逆元：(0 )-1= 0 , (60 )-1=300 ,(120 )-1=240 , (180 )-1= 180 , (240 )-1=12 0 ,(300 )-1= 60 是一個群。 第34頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群定義設(shè)是一個群，如果G是有限集合，則稱為有限群，并把|G|稱為群的階數(shù)，如果G為無限集合，則稱為無限群。例：為無限群，上例中為有限

23、群，群的階為|M| =6。 可以概括：廣群僅僅是具有一個封閉的二元運(yùn)算的非空集合；半群是一個具有結(jié)合運(yùn)算的廣群；獨(dú)異點(diǎn)是具有幺元的半群；群是每個元素都有逆元的獨(dú)異點(diǎn)。第35頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群2.群的性質(zhì)由群的定義可知:（1）群具有半群和獨(dú)異點(diǎn)所具有的所有性質(zhì)；（2）由于群中存在幺元，所以在群的運(yùn)算表中一定沒有相同的行（和列）.下面以定理形式介紹群的性質(zhì) 第36頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群定理1 若是一個群，則對任一a,bG有：存在唯一的元素x G ，使a * x= b；證明： （a）在G中存在x，使a

24、 * x= b成立。a * (a-1 * b) = (a * a-1 ) *b =e* b=b， 至少有一x = (a-1 * b)滿足a * x= b成立。 （b）下面證明這樣的x是唯一的。 若另有一解x1能使a* x1= b成立， 則有x1 =e * x1 = (a-1 * a) * x1 = a-1 * (a * x1) = a-1 * b， x = (a-1 * b)是滿足a * x= b的唯一元素，即x是唯一的。第37頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群定理2若是一個群，則對任一a,b,cG有： （1）a * b = a * c b = c（a是左可

25、消去的）（2）b * a = c * a b = c（a是右可消去的）。此定理說明群滿足消去律。定理3一個群中一定不存在零元。第38頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群證：假設(shè)a是群（U，）的等冪元素，（e是幺元）， 且ae，則a =a a ， 而e = a-1 a=a-1 (a a)=(a-1 a) a=e a=a 與ae矛盾 。 定義：設(shè)S是一個非空集合，從集合S到S的一個雙射稱為S的一個置換。定理4一個群中，除了幺元e之外，不存在其它等冪元素。第39頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群定理5：群的運(yùn)算表中的每一行或每一列

26、都是G的元素的一個置換。證明：首先，證明運(yùn)算表中的任一行或任一列所含G中的一個元素不可能多于一次。（反證法）如果對應(yīng)于元素aG的那一行中有兩個元素都是c，即有a*b1=a*b2=c，且b1b2 由可約性，得： b1b2，這與b1b2矛盾。第40頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群 其次，證明G中的每一個元素都在運(yùn)算表的每一行和每一列中出現(xiàn)。 考察對應(yīng)于元素aG的那一行，設(shè)b是G中的任一元素,由于b=a*(a-1*b)，所以b必定出現(xiàn)在對應(yīng)于a的那一行。 再由運(yùn)算表中沒有兩行（或兩列）是相同的， 所以， 的運(yùn)算表中的每一行都是G的元素的一個置換，且每一行都是不相

27、同的。 同樣，對于每一列結(jié)論同樣成立。第41頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群3.子群定義設(shè)是一個群，且SG是一個非空集合。若滿足下列三個條件，則稱是的子群：（1）e是的幺元，且eS； （保持幺元）（2）對任一 aS一定有a-1 S ； （保持逆元）（3）對任一a,bS一定有a*bS 。 （運(yùn)算的封閉性）討論定義：（1）任一群至少可找到二個子群，即和 ，為了以示區(qū)別稱此二子群為平凡子群；（2）除了平凡子群以外的子群稱為的真子群。第42頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五定理設(shè)是一個群，B是G的非空子集，如果B是一個有限集，那么，只要運(yùn)算

28、*在B上是封閉的，則必定是的子群。4 群與子群第43頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群證明：設(shè)bB，已知*在B上封閉，則b*b B，即b2 B， b2 *b B， 即： b3 B，于是b ， b2 ， b3均在B中。由于B是有限集，必存在正整數(shù)i和j，ij,使得：bi=bj即： bi=bi*bj-i由此可說明bj-i是中的幺元，且這個幺元也 在子集B中。如果j-i1，那么由bj-i=b*bj-i-1可知bj-i-1是b的逆元，且bj-i-1 B；如果j-i=1，那么由bi=bi*b可知b就是幺元，且以自身為逆元。因此， 是的一個子群。第44頁，共72頁，20

29、22年，5月20日，11點(diǎn)12分，星期五4 群與子群例：設(shè)G4=p=|pi0,1，是上的二元運(yùn)算，定義為，對任意X=，Y= G4，X Y=，其中的運(yùn)算表如圖所示：證明, 是群的子群。01001110第45頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群定理:設(shè)是一個群，S是G的非空子集，如果對于S中的任意元素a和b有a*b-1S，則是 的子群。證明：先證，G中的幺元e也是S中的幺元。 任取 aS， a*a-1S，而a*a-1e，eS 再證，每個元素都有逆元。 又e*a-1S，即a-1S。最后說明，*對S是封閉的。 a,b S，因b-1S， (b-1)-1 S第46頁，共7

30、2頁，2022年，5月20日，11點(diǎn)12分，星期五4 群與子群a*b=a*(b-1)-1 S，而(b-1)-1 b a*b S 是的子群例：設(shè)和都是群的子群，試證明也是的子群。第47頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五5 阿貝爾群和循環(huán)群定義如果群中運(yùn)算*是可交換的， 則稱該群為阿貝爾群（或稱為交換群）。例： 為阿貝爾群。例：離散函數(shù)代數(shù)系統(tǒng)是阿貝爾群。Z=1,2,3,4， F=f0 , f1 , f2 , f3 , f2 =1 2 3 43 4 1 2, f3 =1 2 3 44 1 2 3, f0 =1 2 3 41 2 3 41 2 3 42 3 4 1 f =第4

31、8頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五5 阿貝爾群和循環(huán)群由運(yùn)算表可見：（1）運(yùn)算是封閉的；（2）“ ”可結(jié)合； （3）幺元f0 ；（4）每一個元素均可逆; （5）以主對角線為對稱。 為阿貝爾群。 f0f1 f2 f3f0f0f1 f2 f3f1f1 f2 f3f0f2 f2 f3f0f1f3f3f0f1f2 第49頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五5 阿貝爾群和循環(huán)群定理設(shè)是一個群， 是阿貝爾群的充分必要條件是對任一a ,bG有 : (a*b)*(a*b) = (a*a)*(b*b)。證明：（1）充分性： (a*b)*(a*b) = (a*a)*

32、(b*b) 是阿貝爾群。對任一a ,bG有(a*b)*(a*b) = (a*a)*(b*b)成立， *是可結(jié)合的，且是可消去的， a*(a*b)*b = (a*a)*(b*b) =(a*b)*(a*b) =a*(b*a)*b 得a*b =b*a， 是阿貝爾群。第50頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五5 阿貝爾群和循環(huán)群（2）必要性： 是阿貝爾群 (a*b)*(a*b) = (a*a)*(b*b) 。阿貝爾群滿足交換律，對任一a ,bG有a*b =b*a ， (a*a)*(b*b) = a*(a*b)*b = a*(b*a)*b = (a*b)*(a*b) 。推論在阿貝爾

33、群中，對任一a ,bG有 (a*b) 1 =b-1*a-1 =a-1*b-1第51頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五5 阿貝爾群和循環(huán)群定義設(shè)是一個群，I 是整數(shù)集合，若存在一個元素gG，對于G中每一個元素a都能表示成gn的形式（n I），則稱是一個循環(huán)群，g稱為群的生成元。例： 60就是群的生成元，所以該群為循環(huán)群。第52頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五5 阿貝爾群和循環(huán)群定理每一個循環(huán)群必然是阿貝爾群。定理設(shè)是由元素gG生成的循環(huán)群，若 是n階的（即|G|=n），則gn=e ，且G=g1 , g2 , gn = e ，而且n是能使gn =

34、e的最小正整數(shù)。證明：設(shè)是一循環(huán)群，g為生成元， 對任一p,q G一定存在 i ,j I（整數(shù)）使得p=gi , q=gj， 則p*q = gi * gj = gi+j = gj * gi =q*p 。 循環(huán)群一定是阿貝爾群。第53頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五5 阿貝爾群和循環(huán)群例： 為一群,G中元素和*運(yùn)算見運(yùn)算表： c1=c ,c2=b ,c3=d ,c4=a(幺元); d1=d, d2=b, d3=c ,d4=a (幺元);而a1=a, a2=a, a3=a, a4 =a ; b1=b, b2=a ,b3=b ,b4=a ,由上可見：生成元c ,d的階為4，

35、等于群的階，即|G|的基數(shù)。*abcdaabcdbbadcccdbaddcab第54頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五6 拉格朗日定理Lagrange定理:對群G的任何子群H,|H|整除|G|.推論:(1)任一元aG生成的循環(huán)子群的階(即a的階)是群的階的因數(shù); (2)一個素數(shù)階的群必為循環(huán)群，并且除e外,每個元都是其生成元(因素數(shù)只有兩個因數(shù):1和自身); (3)素數(shù)階的群只有平凡子群:e和它自身.第55頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五1、定義：對兩個同類型代數(shù)系統(tǒng)(U，)，(V，*)，其中與 * 都是二元運(yùn)算。如果存在雙射f：UV，使得對x

36、1，x2U，都有 f（x1x2）= f（x1）*f（x2），就稱f是一個從（U，）到（V，*）的同構(gòu)映射，或說（U，）與（V，*）是同構(gòu)的。記作：（U，）（V，*）一、同構(gòu)同態(tài)和同構(gòu)是討論二個代數(shù)系統(tǒng)之間的關(guān)系。8 同構(gòu)與同態(tài) 第56頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五例：設(shè)A=a，b，c，d，在 A 上定義一個二元運(yùn)算“”，又設(shè)B=，在 A 上定義一個二元運(yùn)算 “*”，如下表：證明：（A，）和（B，*）是同構(gòu)證明：考察映射 f (a)=, f (b)=, f (c)=, f (d)=顯然，f 是一個從A到B的雙射，由表容易驗證 f 是由（A，）和（B，*）的同構(gòu)?？疾煊?/p>

37、射 g，使得 g (a)= , g(b)= , g (c)=, g (d)= ，g也是由（A，）和（B，*）的同構(gòu)。注：兩個代數(shù)系統(tǒng)是同構(gòu)，他們之間的同構(gòu)映射可以是不唯一的。abcdaabcdbbaaccbddcdabcd*第57頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五解：作映射 f：I2I，f(x) =2x，則 f 是雙射。對任何a，bI， f(a+b)=2(a+b)=2a+2b=f(a)+f(b)因此，V1 和 V2 同構(gòu)例： 設(shè)代數(shù)系統(tǒng)V1=（I，+），V2=（2I，+），其中I是整數(shù)集合，+ 運(yùn)算是一般的加運(yùn)算，V1 和 V2 是否同構(gòu)？8 同構(gòu)與同態(tài) 第58頁，共7

38、2頁，2022年，5月20日，11點(diǎn)12分，星期五定理2：如果（U，）滿足交換律，且（U，）（V，*），則（V，*）也滿足交換律。定理3：如果（U，*）滿足左（右）分配律，且（U，*）（V，），則（V，）也滿足左（右）分配律。 2、定理定理1：如果（U，）滿足結(jié)合律，且（U，）（V，*），則（V，*）也滿足結(jié)合律。8 同構(gòu)與同態(tài) 第59頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五定理4：如果（U，）存在單位元，且（U，）（V，*），則（V，*）也存在單位元。 定理5：設(shè)（U，）存在零元素，且（U，）（V，*），則（V，*）也存在零元素。定理6：若（U，）對每個xU，存在逆元素x-

39、1，且（U，）（V，*），則（V，*）中任一元素 y 必存在逆元素y-1。定理7：代數(shù)系統(tǒng)間的同構(gòu)關(guān)系是等價關(guān)系。 8 同構(gòu)與同態(tài) 第60頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五二、同態(tài) 如果將同構(gòu)的條件放寬一點(diǎn)，則可以得到比同構(gòu)范圍更廣的關(guān)系，希望放寬后的關(guān)系使兩個代數(shù)系統(tǒng)不一定要有相同的基數(shù)，但是能夠在一定意義上保持其性質(zhì)，為此引入同態(tài)、滿同態(tài)，單一同態(tài)概念。定義設(shè)U =和V =是二個代數(shù)系統(tǒng)，又設(shè)U到V存在一個映射 f : AB，對任意a1,a2A，若有f (a1a2) = f (a1) * f (a2)，則稱 f 是從代數(shù)系統(tǒng)U到V的同態(tài)映射。稱U同態(tài)于V。把稱為的一

40、個同態(tài)象。其中： f(A)=x|x=f(a)，aAB 8 同構(gòu)與同態(tài) 第61頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五 討論定義： （1）f : AB為同態(tài)函數(shù)，它不單是自變量和象點(diǎn)的對應(yīng)，還有自變量的運(yùn)算和象點(diǎn)運(yùn)算之間的對應(yīng)； （2）對同態(tài)講，二個代數(shù)系統(tǒng)的基數(shù)可以不相等，只要滿足函數(shù)的條件就行；8 同構(gòu)與同態(tài) （3）上述定義可以推廣到多個n元運(yùn)算的同一類型的代數(shù)系統(tǒng)中去。（4）一個代數(shù)系統(tǒng)到另一個代數(shù)系統(tǒng)可能存在多于一個同態(tài)。第62頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五例：設(shè)集合A=a，b，c，在A上定義運(yùn)算。如下表，那么， V1=（I+，+）， V2=

41、（A，），其中 I 是正整數(shù)集合，+ 運(yùn)算是普通的加法。V1 和V2是否同態(tài)？解：作映射 f ：IA，abcaabcbbabcacb是偶數(shù)是奇數(shù)同構(gòu)與同態(tài)8 同構(gòu)與同態(tài) 第63頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五例：給定二代數(shù)系統(tǒng) F =I , +，I為整數(shù)，“+”為一般加； G = Nm , +m ，其中， Nm = 0,1,2m-1 ,“+m ”為模m加法并定義成 x1 +m x2 = (x1 + x2) mod m 。對任一iI和mI +， (i) mod m 定義了除以m所得的非負(fù)余數(shù) 且0 (i) mod m m。8 同構(gòu)與同態(tài) 第64頁，共72頁，2022年，

42、5月20日，11點(diǎn)12分，星期五定義FG的一個函數(shù)：f : I Nm且有 f (i) = i ( mod m)， (其中iI ， f (i) Nm ), f (i1+i2) = (i1+i2) mod m = (i1 mod m) +m (i2 mod m) ，其中 i1I , i2I ； i1 mod m Nm , i2 mod m Nm 。則 f 是一同態(tài)函數(shù)：自變量和象點(diǎn)的對應(yīng)，并保持運(yùn)算的對應(yīng)。8 同構(gòu)與同態(tài) 第65頁，共72頁，2022年，5月20日，11點(diǎn)12分，星期五定義若 f : AB 是從U = 到 V = 的同態(tài)，于是有：（1）若 f 是滿射函數(shù)，則稱 f 是從U到V的滿同態(tài)；（2）若 f 是入射函數(shù)，則稱 f 是從U到V的單一同態(tài)；（3）若 f 是雙射函數(shù)，則稱 f 是從U到V的同構(gòu)。定義設(shè)V是一個代數(shù)系統(tǒng)，如果f是由V到V的同態(tài)，則稱f為自同態(tài)。如果g是V到V的同構(gòu)，則稱g為自同構(gòu)。8 同構(gòu)與同態(tài) 第66頁，共72頁，2022年，5月20日，1