離散數(shù)學(xué)(第15章)陳瑜.ppt

《離散數(shù)學(xué)(第15章)陳瑜.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)(第15章)陳瑜.ppt（224頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

陳瑜,Email：chenyu.inbox@,離散數(shù)學(xué),計(jì)算機(jī)學(xué)院,2019/12/16,計(jì)算機(jī)學(xué)院,2/224,,第15章：半群與群15.1半群,2019/12/16,計(jì)算機(jī)學(xué)院,3/224,,群是一種特殊的代數(shù)系統(tǒng)，是最重要的代數(shù)系統(tǒng)之一。群的理論廣泛應(yīng)用于數(shù)學(xué)、物理、化學(xué)以及很多人們不太熟悉的領(lǐng)域如社會學(xué)等。對計(jì)算機(jī)科學(xué)而言，群在自動(dòng)化理論、形式語言、語法分析、編碼理論等方面都有直接應(yīng)用，并顯示出其強(qiáng)大功能。上一章中已經(jīng)給出了半群的定義，它要求運(yùn)算是可結(jié)合的。許多常見的代數(shù)系統(tǒng)都是半群，甚至是含幺半群。下面是一些典型的半群例子。,2019/12/16,計(jì)算機(jī)學(xué)院,4/224,,群是一種特殊的代數(shù)系統(tǒng)，是最重要的代數(shù)系統(tǒng)之一。群的理論廣泛應(yīng)用于數(shù)學(xué)、物理、化學(xué)以及很多人們不太熟悉的領(lǐng)域如社會學(xué)等。對計(jì)算機(jī)科學(xué)而言，群在自動(dòng)化理論、形式語言、語法分析、編碼理論等方面都有直接應(yīng)用，并顯示出其強(qiáng)大功能。上一章中已經(jīng)給出了半群的定義，它要求運(yùn)算是可結(jié)合的。許多常見的代數(shù)系統(tǒng)都是半群，甚至是含幺半群。下面是一些典型的半群例子。,2019/12/16,計(jì)算機(jī)學(xué)院,5/224,,例：滿足封閉、可結(jié)合、有幺元0的條件，因而是含幺半群。另外，它還滿足可換性，每個(gè)元x∈R都有加法逆元-x，因此，也是一個(gè)可換群。滿足封閉、可結(jié)合、有幺元1，因此是含幺半群。注意，因?yàn)?無乘法逆元，所以只能是含幺半群。,2019/12/16,計(jì)算機(jī)學(xué)院,6/224,,例設(shè)Mm,n表示全休m行n列矩陣構(gòu)成的集合，+是矩陣加法，那么滿足封閉、可結(jié)合的條件，元素全為0的m行n列矩陣是幺元，因此是含幺半群。此外，Mm,n中每個(gè)矩陣Am,n都有加法逆矩陣-Am,n，因而還滿足逆元條件。,2019/12/16,計(jì)算機(jī)學(xué)院,7/224,,例設(shè)F是由定義在非空集合S上的全體函數(shù)構(gòu)成的集合，即F={f:S→S}。對于函數(shù)的復(fù)合運(yùn)算“?”，滿足封閉性和可結(jié)合性，所以是半群。此外，定義在S上的恒等函數(shù)Is是的幺元，所以又是含幺半群。,2019/12/16,計(jì)算機(jī)學(xué)院,8/224,,例設(shè)∑是非空有限字母表，∑*是由定義在∑上的全體有限長字母串構(gòu)成的集合，或叫做∑上全體字的集合。在∑*上定義運(yùn)算為字的連接“?”，則滿足封閉和可結(jié)合的條件，并且空字是系統(tǒng)的幺元，所以是一個(gè)含幺半群。半群或含幺半群在計(jì)算機(jī)科學(xué)中有廣泛的應(yīng)用，尤其在從編譯技術(shù)發(fā)展起來的形式語言與自動(dòng)機(jī)理論領(lǐng)域，含幺半群是很重要的的內(nèi)容之一。下面是半群的一個(gè)簡單的應(yīng)用例子。,,2019/12/16,計(jì)算機(jī)學(xué)院,9/224,,例設(shè)一個(gè)簡單的液晶顯示電子表僅有顯示時(shí)、分的兩個(gè)功能，有0、1兩個(gè)按鍵。按1鍵時(shí)由正常狀態(tài)轉(zhuǎn)入調(diào)分狀態(tài)，此時(shí)按0鍵m次可以調(diào)增分?jǐn)?shù)m；再按1鍵則轉(zhuǎn)入調(diào)時(shí)狀態(tài)，此時(shí)按0鍵n次，則時(shí)數(shù)增加n；最后再按1鍵回復(fù)到正常狀態(tài)。這一調(diào)節(jié)過程如圖(b)所示。,,,(a),(b),2019/12/16,計(jì)算機(jī)學(xué)院,10/224,,上面的調(diào)分和調(diào)時(shí)過程可表示為:,,,或由符號1和0組成的形如10m10n1的字符串集，即字母表∑={0，1}上的一個(gè)語言L={10m10n1|m，n≥0}。這種字母串可以被電子表中的微處理器(可以看成是一個(gè)小小的計(jì)算機(jī))識別并執(zhí)行，其動(dòng)作原理就是圖15-1.1(b)所示的狀態(tài)圖，稱為一個(gè)有限自動(dòng)機(jī)，它反映了電子表依令而行的規(guī)則。語言L被相應(yīng)地稱為這個(gè)自動(dòng)機(jī)所識別的語言。,2019/12/16,計(jì)算機(jī)學(xué)院,11/224,冪,設(shè)是一個(gè)半群,由于*滿足結(jié)合律，可定義冪運(yùn)算，即對?x?S，可定義：x=x，x=x*x，x=x*x=x*x=x*x*x，……xn=xn-1*x=x*xn-1=x*x*x*…*x?！绻袉挝辉猠，可以定義：x0=e冪運(yùn)算有如下的公式：（見下頁）,2019/12/16,計(jì)算機(jī)學(xué)院,12/224,,定理15.1設(shè)是半群，a?S，m和n是正整數(shù)，則：①am*an=am+n；②(am)n=amn。當(dāng)是含幺半群時(shí)，上述結(jié)論對任意非負(fù)整數(shù)m和n都成立。證明：設(shè)m是一個(gè)固定的正整數(shù)，對n進(jìn)行歸納。對于①：當(dāng)n=1時(shí)，由冪的定義可知結(jié)論成立；設(shè)結(jié)論對n=k時(shí)成立，則am*ak+1=am*(ak*a)(由冪的定義)=(am*ak)*a(可結(jié)合性）=(am+k)*a（歸納假設(shè)）=am+(k+1)由歸納法可知，結(jié)論成立。,2019/12/16,計(jì)算機(jī)學(xué)院,13/224,,定理15.1設(shè)是半群，a?S，m和n是正整數(shù)，則：①am*an=am+n；②(am)n=amn。當(dāng)是含幺半群時(shí)，上述結(jié)論對任意非負(fù)整數(shù)m和n都成立。證明：設(shè)m是一個(gè)固定的正整數(shù)，對n進(jìn)行歸納。對于①：當(dāng)n=1時(shí)，由冪的定義可知結(jié)論成立；設(shè)結(jié)論對n=k時(shí)成立，則am*ak+1=am*(ak*a)(由冪的定義)=(am*ak)*a(可結(jié)合性）=(am+k)*a（歸納假設(shè)）=am+(k+1)由歸納法可知，結(jié)論成立。,2019/12/16,計(jì)算機(jī)學(xué)院,14/224,,定理15.1設(shè)是半群，a?S，m和n是正整數(shù)，則：①am*an=am+n；②(am)n=amn。當(dāng)是含幺半群時(shí)，上述結(jié)論對任意非負(fù)整數(shù)m和n都成立。證明：設(shè)m是一個(gè)固定的正整數(shù)，對n進(jìn)行歸納。對于①：當(dāng)n=1時(shí)，由冪的定義可知結(jié)論成立；設(shè)結(jié)論對n=k時(shí)成立，則am*ak+1=am*(ak*a)(由冪的定義)=(am*ak)*a(可結(jié)合性）=(am+k)*a（歸納假設(shè)）=am+(k+1)由歸納法可知，結(jié)論成立。,對于②可以類似的進(jìn)行歸納證明。,2019/12/16,計(jì)算機(jī)學(xué)院,15/224,,注意：當(dāng)運(yùn)算為加法“+”時(shí)，上述定理應(yīng)寫成：ma+na=(m+n)an(ma)=(mn)a,2019/12/16,計(jì)算機(jī)學(xué)院,16/224,定理15.2有限半群?S，??必有冪等元，即存在a?S，a2=a。(參見教材p183）,注意此處的a2的正確含義！a*a=a2,不是數(shù)學(xué)中的乘法！,2019/12/16,計(jì)算機(jī)學(xué)院,17/224,定理15.2有限半群?S，??必有冪等元，即存在a?S，a2=a。,證明：如果S中有幺元e，則e就是冪等元。如果S中沒有幺元，任取b?S。由集合S的有限性，必有：bi=bj=bj-i?bi(j>i),所以，對任何t>i都有：bt=bj-i?bt(注:t=i+l,bt=bi+l=bi*b1)=b2(j-i)?bt=...（反復(fù)迭代）=bk(j-i)?bt（此處k(j-i)>i）令t=k(j-i),則得到bt=bt?bt即bt是冪等元。,2019/12/16,計(jì)算機(jī)學(xué)院,18/224,定理15.2有限半群?S，??必有冪等元，即存在a?S，a2=a。,證明：如果S中有幺元e，則e就是冪等元。如果S中沒有幺元，任取b?S。由集合S的有限性，必有：bi=bj=bj-i?bi(j>i),所以，對任何t>i都有：bt=bj-i?bt(例如:t=i+l,bt=bi+l=bi*b1)=b2(j-i)?bt=...（反復(fù)迭代）=bk(j-i)?bt（此處k(j-i)>i）令t=k(j-i),則得到bt=bt?bt即bt是冪等元。,2019/12/16,計(jì)算機(jī)學(xué)院,19/224,定理15.2有限半群?S，??必有冪等元，即存在a?S，a2=a。,證明：如果S中有幺元e，則e就是冪等元。如果S中沒有幺元，任取b?S。由集合S的有限性，必有：bi=bj=bj-i?bi(j>i),所以，對任何t>i都有：bt=bj-i?bt(例如:t=i+l,bt=bi+l=bi*b1)=b2(j-i)?bt=...（反復(fù)迭代）=bk(j-i)?bt（此處k(j-i)>i）令t=k(j-i),則得到bt=bt?bt即bt是冪等元。,2019/12/16,計(jì)算機(jī)學(xué)院,20/224,定理15.2有限半群?S，??必有冪等元，即存在a?S，a2=a。,證明：如果S中有幺元e，則e就是冪等元。如果S中沒有幺元，任取b?S。由集合S的有限性，必有：bi=bj=bj-i?bi(j>i),所以，對任何t>i都有：bt=bj-i?bt(例如:t=i+l,bt=bi+l=bi*b1)=b2(j-i)?bt=...（反復(fù)迭代）=bk(j-i)?bt（此處k(j-i)>i）令t=k(j-i),則得到bt=bt?bt即bt是冪等元。,注意，若S不是有限集，則不一定有冪等元。例如，正整數(shù)集關(guān)于加法運(yùn)算是一個(gè)半群，但是不存在冪等元。含幺半群至少含有一個(gè)冪等元，那就是幺元。一個(gè)半群甚至含幺半群也可以含有多個(gè)冪等元。不難驗(yàn)證是以S為幺元的含幺半群。由于集合交運(yùn)算是冪等的，所以中每個(gè)元都是冪等元。,2019/12/16,計(jì)算機(jī)學(xué)院,21/224,子半群,定義15.1如果是半群，T是S的非空子集，且T對運(yùn)算*是封閉的，則稱是半群的子半群；如果是含幺半群，T∈S，e∈T，且T對運(yùn)算*是封閉的，則稱是含幺半群的子含幺半群。例：半群的子代數(shù)，，都是的子半群。,2019/12/16,計(jì)算機(jī)學(xué)院,22/224,子半群,定義15.1如果是半群，T是S的非空子集，且T對運(yùn)算*是封閉的，則稱是半群的子半群；如果是含幺半群，T∈S，e∈T，且T對運(yùn)算*是封閉的，則稱是含幺半群的子含幺半群。例：半群的子代數(shù)，，都是的子半群。,2019/12/16,計(jì)算機(jī)學(xué)院,23/224,子半群,定義15.1如果是半群，T是S的非空子集，且T對運(yùn)算*是封閉的，則稱是半群的子半群；如果是含幺半群，T∈S，e∈T，且T對運(yùn)算*是封閉的，則稱是含幺半群的子含幺半群。例：半群的子代數(shù)，，都是的子半群。,2019/12/16,計(jì)算機(jī)學(xué)院,24/224,例設(shè)是一個(gè)可換的含幺半群，M是它的所有的等冪元構(gòu)成的集合，則是的一個(gè)子含幺半群。證明：(1)顯然，M?S；(2)是含幺半群，所以幺元e存在，又e*e＝e，則e是一個(gè)等冪元，即有e∈M，所以M是非空的；(3)e∈M；(4)對任意a，b∈M，有(a*b)*(a*b)＝a*(b*a)*b＝a*(a*b)*b＝(a*a)*(b*b)＝a*b，即運(yùn)算“*”關(guān)于集合M是封閉的運(yùn)算。由(1)、(2)、(3)、(4)知：是的一個(gè)子含幺半群。,2019/12/16,計(jì)算機(jī)學(xué)院,25/224,例設(shè)是一個(gè)可換的含幺半群，M是它的所有的等冪元構(gòu)成的集合，則是的一個(gè)子含幺半群。證明：(1)顯然，M?S；(2)是含幺半群，所以幺元e存在，又e*e＝e，則e是一個(gè)等冪元，即有e∈M，所以M是非空的；(3)e∈M；(4)對任意a，b∈M，有(a*b)*(a*b)＝a*(b*a)*b＝a*(a*b)*b＝(a*a)*(b*b)＝a*b，即運(yùn)算“*”關(guān)于集合M是封閉的運(yùn)算。由(1)、(2)、(3)、(4)知：是的一個(gè)子含幺半群。,2019/12/16,計(jì)算機(jī)學(xué)院,26/224,例設(shè)是一個(gè)可換的含幺半群，M是它的所有的等冪元構(gòu)成的集合，則是的一個(gè)子含幺半群。證明：(1)顯然，M?S；(2)是含幺半群，所以幺元e存在，又e*e＝e，則e是一個(gè)等冪元，即有e∈M，所以M是非空的；(3)e∈M；(4)對任意a，b∈M，有(a*b)*(a*b)＝a*(b*a)*b＝a*(a*b)*b＝(a*a)*(b*b)＝a*b，即運(yùn)算“*”關(guān)于集合M是封閉的運(yùn)算。由(1)、(2)、(3)、(4)知：是的一個(gè)子含幺半群。,2019/12/16,計(jì)算機(jī)學(xué)院,27/224,例設(shè)是一個(gè)可換的含幺半群，M是它的所有的等冪元構(gòu)成的集合，則是的一個(gè)子含幺半群。證明：(1)顯然，M?S；(2)是含幺半群，所以幺元e存在，又e*e＝e，則e是一個(gè)等冪元，即有e∈M，所以M是非空的；(3)e∈M；(4)對任意a，b∈M，有(a*b)*(a*b)＝a*(b*a)*b＝a*(a*b)*b＝(a*a)*(b*b)＝a*b，即運(yùn)算“*”關(guān)于集合M是封閉的運(yùn)算。由(1)、(2)、(3)、(4)知：是的一個(gè)子含幺半群。,2019/12/16,計(jì)算機(jī)學(xué)院,28/224,例設(shè)是一個(gè)可換的含幺半群，M是它的所有的等冪元構(gòu)成的集合，則是的一個(gè)子含幺半群。證明：(1)顯然，M?S；(2)是含幺半群，所以幺元e存在，又e*e＝e，則e是一個(gè)等冪元，即有e∈M，所以M是非空的；(3)e∈M；(4)對任意a，b∈M，有(a*b)*(a*b)＝a*(b*a)*b＝a*(a*b)*b＝(a*a)*(b*b)＝a*b，即運(yùn)算“*”關(guān)于集合M是封閉的運(yùn)算。由(1)、(2)、(3)、(4)知：是的一個(gè)子含幺半群。,2019/12/16,計(jì)算機(jī)學(xué)院,29/224,習(xí)題,P1932、4、6,2019/12/16,計(jì)算機(jī)學(xué)院,30/224,,15.2群和子群,2019/12/16,計(jì)算機(jī)學(xué)院,31/224,主要內(nèi)容,一個(gè)非常重要的代數(shù)系統(tǒng)——群。主要從以下幾個(gè)方面來介紹：群的概念和基本性質(zhì)。群的子群和性質(zhì)。群中元素的周期和性質(zhì)。特殊群及其性質(zhì)，如交換群（Abel群）、循環(huán)群。陪集和拉格郎日定理。,2019/12/16,計(jì)算機(jī)學(xué)院,32/224,,在14.2中已經(jīng)為群下了定義，把群看成是在含幺半群的基礎(chǔ)上加上每元有逆元的條件，其核心內(nèi)容可用“閉、結(jié)、幺、逆”四個(gè)字予以概括。下面是一些典型的群的例子。,2019/12/16,計(jì)算機(jī)學(xué)院,33/224,,例：我們已經(jīng)知道是含幺半群，由于每個(gè)整數(shù)a都有加法逆元-a，所以是群，一般叫做整數(shù)加群。同理，是實(shí)數(shù)加群，是有理數(shù)加群。對于數(shù)的乘法，是含幺半群而不是群，因?yàn)檎麛?shù)一般無Z中的乘法逆元。是實(shí)數(shù)乘群，它的幺元是1，每元的乘法逆元為1/a。,2019/12/16,計(jì)算機(jī)學(xué)院,34/224,,例：設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即:Zk={[0],[1],[2],…,[k-1]}。在Zk上定義運(yùn)算和如下：那么，是群。這是因?yàn)榉忾]性和可結(jié)合性是明顯成立的，[0]是幺元，每元[i]的逆元是[k-i]。群習(xí)慣上又稱為剩余類加群。,2019/12/16,計(jì)算機(jī)學(xué)院,35/224,,例設(shè)n個(gè)元素的集合A上的全體置換構(gòu)成集合Sn。由第6章中關(guān)于置換的討論，Sn中兩個(gè)置換的復(fù)合仍然是A上的一個(gè)置換，因而運(yùn)算是封閉的；其次，由于函數(shù)的復(fù)合是可結(jié)合的，因而置換的復(fù)合也是可結(jié)合的；在Sn中存在幺置換=(1)，使對任何Sn中的置換均有，因而=(1)是幺元；把每個(gè)元素的x變成y的置換，其逆置換則把元素y變成x，因而每個(gè)置換都有逆。由此可知，構(gòu)成群，這個(gè)群一般稱為n次對稱群，是一類重要的群。群盡管是用“閉、結(jié)、幺、逆”四個(gè)條件來定義的，但是它還可以用別的形式等價(jià)地定義。,2019/12/16,計(jì)算機(jī)學(xué)院,36/224,,例設(shè)n個(gè)元素的集合A上的全體置換構(gòu)成集合Sn。由第6章中關(guān)于置換的討論，Sn中兩個(gè)置換的復(fù)合仍然是A上的一個(gè)置換，因而運(yùn)算是封閉的；其次，由于函數(shù)的復(fù)合是可結(jié)合的，因而置換的復(fù)合也是可結(jié)合的；在Sn中存在幺置換=(1)，使對任何Sn中的置換均有，因而=(1)是幺元；把每個(gè)元素的x變成y的置換，其逆置換則把元素y變成x，因而每個(gè)置換都有逆。由此可知，構(gòu)成群，這個(gè)群一般稱為n次對稱群，是一類重要的群。群盡管是用“閉、結(jié)、幺、逆”四個(gè)條件來定義的，但是它還可以用別的形式等價(jià)地定義。,2019/12/16,計(jì)算機(jī)學(xué)院,37/224,群,定理15-2.1如果是半群，并且對?a，b?G，都存在x，y?G使x*a=b，a*y=b，則是群。群中元素的數(shù)目稱為群的階。證明：設(shè)a?G，方程x*a=a的解為e1，∵對?t?G，方程a*y=t有解y0，∴e1*t=e1*（a*y0）=（e1*a）*y0=a*y0=t即對?t?G，必有e1*t=t，e1是G中的左幺元。同樣可以證明G中有右幺元e2，所以G中有幺元e。同理，對?b?G，方程x*b=e有解x0，這個(gè)x0是b的左逆元，方程b*y=e的解是b的右逆元，從而b有逆元。所以，是群。,2019/12/16,計(jì)算機(jī)學(xué)院,38/224,群,定理15.3如果是半群，并且對?a，b?G，都存在x，y?G使x*a=b，a*y=b，則是群。群中元素的數(shù)目稱為群的階。證明：設(shè)a?G，方程x*a=a的解為e1，∵對?t?G，方程a*y=t有解y0，∴e1*t=e1*（a*y0）=（e1*a）*y0=a*y0=t即對?t?G，必有e1*t=t，e1是G中的左幺元。同樣可以證明G中有右幺元e2，所以G中有幺元e。同理，對?b?G，方程x*b=e有解x0，這個(gè)x0是b的左逆元，方程b*y=e的解是b的右逆元，從而b有逆元。所以，是群。,2019/12/16,計(jì)算機(jī)學(xué)院,39/224,群,定理15.3如果是半群，并且對?a，b?G，都存在x，y?G使x*a=b，a*y=b，則是群。群中元素的數(shù)目稱為群的階。證明：設(shè)a?G，方程x*a=a的解為e1，∵對?t?G，方程a*y=t有解y0，∴e1*t=e1*（a*y0）=（e1*a）*y0=a*y0=t即對?t?G，必有e1*t=t，e1是G中的左幺元。同樣可以證明G中有右幺元e2，所以G中有幺元e。同理，對?b?G，方程x*b=e有解x0，這個(gè)x0是b的左逆元，方程b*y=e的解是b的右逆元，從而b有逆元。所以，是群。,2019/12/16,計(jì)算機(jī)學(xué)院,40/224,群,定理15.3如果是半群，并且對?a，b?G，都存在x，y?G使x*a=b，a*y=b，則是群。群中元素的數(shù)目稱為群的階。證明：設(shè)a?G，方程x*a=a的解為e1，∵對?t?G，方程a*y=t有解y0，∴e1*t=e1*（a*y0）=（e1*a）*y0=a*y0=t即對?t?G，必有e1*t=t，e1是G中的左幺元。同樣可以證明G中有右幺元e2，所以G中有幺元e。同理，對?b?G，方程x*b=e有解x0，這個(gè)x0是b的左逆元，方程b*y=e的解是b的右逆元，從而b有逆元。所以，是群。,2019/12/16,計(jì)算機(jī)學(xué)院,41/224,群,定理15.3如果是半群，并且對?a，b?G，都存在x，y?G使x*a=b，a*y=b，則是群。群中元素的數(shù)目稱為群的階。證明：設(shè)a?G，方程x*a=a的解為e1，∵對?t?G，方程a*y=t有解y0，∴e1*t=e1*（a*y0）=（e1*a）*y0=a*y0=t即對?t?G，必有e1*t=t，e1是G中的左幺元。同樣可以證明G中有右幺元e2，所以G中有幺元e。同理，對?b?G，方程x*b=e有解x0，這個(gè)x0是b的左逆元，方程b*y=e的解是b的右逆元，從而b有逆元。所以，是群。,這個(gè)定理說明，在群的定義中幺元及逆元的條件可用方程有解來代替。另外，群定義中的幺元條件可以用存在左幺元(或右幺元)的條件代替，逆元的條件可以用左逆元(或右逆元)代替。,2019/12/16,計(jì)算機(jī)學(xué)院,42/224,,定理15.4群G中每個(gè)元素都是可消去的，即運(yùn)算滿足消去律；（即如果a*b=a*c，則必有b=c）群G中除幺元e外無其它冪等元；群G的運(yùn)算表中任意一行(列)都沒有兩個(gè)相同的元素（重復(fù)元素）；,2019/12/16,計(jì)算機(jī)學(xué)院,43/224,,定理15.4群G中每個(gè)元素都是可消去的，即運(yùn)算滿足消去律；（即如果a*b=a*c，則必有b=c）群G中除幺元e外無其它冪等元；群G的運(yùn)算表中任意一行(列)都沒有兩個(gè)相同的元素（重復(fù)元素）；,證明：由于群G中每個(gè)元素都有逆元a-1，由a*b=a*c?a-1*a*b=a-1*a*c，即b=c,2019/12/16,計(jì)算機(jī)學(xué)院,44/224,,定理15.4群G中每個(gè)元素都是可消去的，即運(yùn)算滿足消去律；（即如果a*b=a*c，則必有b=c）群G中除幺元e外無其它冪等元；群G的運(yùn)算表中任意一行(列)都沒有兩個(gè)相同的元素（重復(fù)元素）；,2019/12/16,計(jì)算機(jī)學(xué)院,45/224,,定理15.4群G中每個(gè)元素都是可消去的，即運(yùn)算滿足消去律；（即如果a*b=a*c，則必有b=c）群G中除幺元e外無其它冪等元；群G的運(yùn)算表中任意一行(列)都沒有兩個(gè)相同的元素（重復(fù)元素）；,證明：（反證法）假設(shè)a是群G中非幺元的冪等元，即a*a＝a，且a≠e。因此a*a＝a*e，由（1）知a＝e，矛盾。,2019/12/16,計(jì)算機(jī)學(xué)院,46/224,,定理15.4群G中每個(gè)元素都是可消去的，即運(yùn)算滿足消去律；（即如果a*b=a*c，則必有b=c）群G中除幺元e外無其它冪等元；群G的運(yùn)算表中任意一行(列)都沒有兩個(gè)相同的元素（重復(fù)元素）；,2019/12/16,計(jì)算機(jī)學(xué)院,47/224,,定理15.4群G中每個(gè)元素都是可消去的，即運(yùn)算滿足消去律；（即如果a*b=a*c，則必有b=c）群G中除幺元e外無其它冪等元；群G的運(yùn)算表中任意一行(列)都沒有兩個(gè)相同的元素（重復(fù)元素）；,證明：（反證法）假設(shè)群G的運(yùn)算表中某一行(列)有兩個(gè)相同的元素，設(shè)為a，并設(shè)它們所在的行表頭元素為b，列表頭元素分別為c1,c2，這時(shí)顯然有c1≠c2。而a＝bc1＝bc2，由(1)得c1＝c2，矛盾。,2019/12/16,計(jì)算機(jī)學(xué)院,48/224,補(bǔ)充,例：構(gòu)造一個(gè)3階群。解：設(shè)e是幺元，G={e,a,b}則可構(gòu)造的3階群如下：,2019/12/16,計(jì)算機(jī)學(xué)院,49/224,,定理15.5設(shè)是群，a∈G。構(gòu)造映射，使得對任意x∈G，，令，則對于函數(shù)的復(fù)合運(yùn)算“”，是群。（P185）定理的證明留與讀者練習(xí),這個(gè)定理說明：可以由一個(gè)已知的群來構(gòu)造出一個(gè)新的群。,2019/12/16,計(jì)算機(jī)學(xué)院,50/224,,例：設(shè)X是任意集合，S={f:X→X|f是雙射函數(shù)}，即S是X上的所有雙射函數(shù)的集合，運(yùn)算“?！笔呛瘮?shù)的復(fù)合運(yùn)算，證明是群。證明：（1）封閉性：?f,g∈S，f、g是雙射，則f。g也是雙射，因此f。g∈S，故封閉性成立。（2）結(jié)合律：由函數(shù)的運(yùn)算“?！睗M足結(jié)合律，因此在S中也滿足結(jié)合律。,2019/12/16,計(jì)算機(jī)學(xué)院,51/224,,例：設(shè)X是任意集合，S={f:X→X|f是雙射函數(shù)}，即S是X上的所有雙射函數(shù)的集合，運(yùn)算“?！笔呛瘮?shù)的復(fù)合運(yùn)算，證明是群。證明：（1）封閉性：?f,g∈S，f、g是雙射，則f。g也是雙射，因此f。g∈S，故封閉性成立。（2）結(jié)合律：由函數(shù)的運(yùn)算“?！睗M足結(jié)合律，因此在S中也滿足結(jié)合律。,2019/12/16,計(jì)算機(jī)學(xué)院,52/224,,例：設(shè)X是任意集合，S={f:X→X|f是雙射函數(shù)}，即S是X上的所有雙射函數(shù)的集合，運(yùn)算“?！笔呛瘮?shù)的復(fù)合運(yùn)算，證明是群。證明：（1）封閉性：?f,g∈S，f、g是雙射，則f。g也是雙射，因此f。g∈S，故封閉性成立。（2）結(jié)合律：由函數(shù)的運(yùn)算“?！睗M足結(jié)合律，因此在S中也滿足結(jié)合律。,2019/12/16,計(jì)算機(jī)學(xué)院,53/224,,例：設(shè)X是任意集合，S={f:X→X|f是雙射函數(shù)}，即S是X上的所有雙射函數(shù)的集合，運(yùn)算“。”是函數(shù)的復(fù)合運(yùn)算，證明是群。證明：（續(xù)）（3）幺元：恒等映射IX∈S,且?f∈S，有：IX。f=f。IX=f，因此IX是的幺元。（4）?f,g∈S是雙射，則f的逆函數(shù)f-1存在，f-1也是雙射，即f-1∈S，且有：f-1。f=f。f-1=IX，因此，f的逆函數(shù)f-1就是f關(guān)于“?！钡哪嬖?，即S的任意元素都有逆元。綜合（1）（2）（3）（4）知是群。,2019/12/16,計(jì)算機(jī)學(xué)院,54/224,,例：設(shè)X是任意集合，S={f:X→X|f是雙射函數(shù)}，即S是X上的所有雙射函數(shù)的集合，運(yùn)算“。”是函數(shù)的復(fù)合運(yùn)算，證明是群。證明：（續(xù)）（3）幺元：恒等映射IX∈S,且?f∈S，有：IX。f=f。IX=f，因此IX是的幺元。（4）?f,g∈S是雙射，則f的逆函數(shù)f-1存在，f-1也是雙射，即f-1∈S，且有：f-1。f=f。f-1=IX，因此，f的逆函數(shù)f-1就是f關(guān)于“?！钡哪嬖?，即S的任意元素都有逆元。綜合（1）（2）（3）（4）知是群。,2019/12/16,計(jì)算機(jī)學(xué)院,55/224,,課外練習(xí)：設(shè)A=R-{0，1}，在A上定義6個(gè)映射如下：對于任意x∈A有：令G={f1,f2,f3,f4,f5,f6}。試證明G關(guān)于函數(shù)的復(fù)合運(yùn)算“?！睒?gòu)成群。,2019/12/16,計(jì)算機(jī)學(xué)院,56/224,子群,定義15.2設(shè)是一個(gè)群，S是G的一個(gè)非空子集，若S也是群，則稱是的一個(gè)子群。一般來說，對任意的群，都有兩個(gè)子群，，我們稱此兩個(gè)子群為該群的平凡子群,而若有子群,且S?{e}和S?G，則稱為的真子群。另外，由群中的一個(gè)元素也可生成一個(gè)子群。定義為：a-k=（ak）-1。,2019/12/16,計(jì)算機(jī)學(xué)院,57/224,子群,定義15.2設(shè)是一個(gè)群，S是G的一個(gè)非空子集，若S也是群，則稱是的一個(gè)子群。一般來說，對任意的群，都有兩個(gè)子群，，我們稱此兩個(gè)子群為該群的平凡子群,而若有子群,且S?{e}和S?G，則稱為的真子群。另外，由群中的一個(gè)元素也可生成一個(gè)子群。為此，需要將群中元素的冪擴(kuò)充到負(fù)指數(shù)的形式，即定義為：a-k=（ak）-1。,2019/12/16,計(jì)算機(jī)學(xué)院,58/224,子群,定義15.2設(shè)是一個(gè)群，S是G的一個(gè)非空子集，若S也是群，則稱是的一個(gè)子群。一般來說，對任意的群，都有兩個(gè)子群，，我們稱此兩個(gè)子群為該群的平凡子群,而若有子群,且S?{e}和S?G，則稱為的真子群。另外，由群中的一個(gè)元素也可生成一個(gè)子群。為此，需要將群中元素的冪擴(kuò)充到負(fù)指數(shù)的形式，即定義為：a-k=（ak）-1。,2019/12/16,計(jì)算機(jī)學(xué)院,59/224,,定理15.6設(shè)是一個(gè)群，對任意的a∈G，令S＝{an|n∈Z，Z是整數(shù)}，則是的子群。證明：因?yàn)閍∈S，所以顯然S是G的非空子集。對任意的an，am∈S，則an*am＝an+m，由n,m∈Z，有n+m∈Z，所以an+m∈S，即運(yùn)算是封閉的；由S是G的子集可得結(jié)合律也成立；由于e=a0?S，所以S中有幺元；又∵an?S有逆元a-n使an*a-n=e∴綜上所述，是的子群。,2019/12/16,計(jì)算機(jī)學(xué)院,60/224,,定理15.6設(shè)是一個(gè)群，對任意的a∈G，令S＝{an|n∈Z，Z是整數(shù)}，則是的子群。證明：因?yàn)閍∈S，所以顯然S是G的非空子集。對任意的an，am∈S，則an*am＝an+m，由n,m∈Z，有n+m∈Z，所以an+m∈S，即運(yùn)算是封閉的；由S是G的子集可得結(jié)合律也成立；由于e=a0?S，所以S中有幺元；又∵an?S有逆元a-n使an*a-n=e∴綜上所述，是的子群。,2019/12/16,計(jì)算機(jī)學(xué)院,61/224,,定理15.6設(shè)是一個(gè)群，對任意的a∈G，令S＝{an|n∈Z，Z是整數(shù)}，則是的子群。證明：因?yàn)閍∈S，所以顯然S是G的非空子集。對任意的an，am∈S，則an*am＝an+m，由n,m∈Z，有n+m∈Z，所以an+m∈S，即運(yùn)算是封閉的；由S是G的子集可得結(jié)合律也成立；由于e=a0?S，所以S中有幺元；又∵an?S有逆元a-n使an*a-n=e∴綜上所述，是的子群。,2019/12/16,計(jì)算機(jī)學(xué)院,62/224,,定理15.6設(shè)是一個(gè)群，對任意的a∈G，令S＝{an|n∈Z，Z是整數(shù)}，則是的子群。證明：因?yàn)閍∈S，所以顯然S是G的非空子集。對任意的an，am∈S，則an*am＝an+m，由n,m∈Z，有n+m∈Z，所以an+m∈S，即運(yùn)算是封閉的；由S是G的子集可得結(jié)合律也成立；由于e=a0?S，所以S中有幺元；又∵an?S有逆元a-n使an*a-n=e∴綜上所述，是的子群。,2019/12/16,計(jì)算機(jī)學(xué)院,63/224,,定理15-2.4設(shè)是一個(gè)群，對任意的a∈G，令S＝{an|n∈Z，Z是整數(shù)}，則是的子群。證明：因?yàn)閍∈S，所以顯然S是G的非空子集。對任意的an，am∈S，則an*am＝an+m，由n,m∈Z，有n+m∈Z，所以an+m∈S，即運(yùn)算是封閉的；由S是G的子集可得結(jié)合律也成立；由于e=a0?S，所以S中有幺元；又∵an?S有逆元a-n使an*a-n=e∴綜上所述，是的子群。,2019/12/16,計(jì)算機(jī)學(xué)院,64/224,,特別把由群的一個(gè)元素a生成的子群記為(a)。例如在中，由元素2生成的子群(2)是由全體偶數(shù)關(guān)于加法構(gòu)成的群，而由元素1生成的子群正好是Z本身。,2019/12/16,計(jì)算機(jī)學(xué)院,65/224,,定理15.7設(shè)是一個(gè)群,是的子群,則:1）子群的幺元eS也是群的幺元eG；2）對?a?S，a在S中的逆元aS-1就是a在G中的逆元aG-1。證明：1)對?a?S，由于eS是S的幺元，所以有：eS*a＝a*eS＝a①又S?G,所以a?G,由eG是G的幺元，所以有：eG*a＝a*eG＝a②由①、②有：eS*a＝a*eS＝a＝eG*a＝a*eG，由于G滿足消去律，所以有：eS＝eG。2)對?a?S，由于S?G，所以a?G，即a在S中的逆元就是a在G中的逆元。,2019/12/16,計(jì)算機(jī)學(xué)院,66/224,,定理15.7設(shè)是一個(gè)群,是的子群,則:1）子群的幺元eS也是群的幺元eG；2）對?a?S，a在S中的逆元aS-1就是a在G中的逆元aG-1。證明：1)對?a?S，由于eS是S的幺元，所以有：eS*a＝a*eS＝a①又S?G,所以a?G,由eG是G的幺元，所以有：eG*a＝a*eG＝a②由①、②有：eS*a＝a*eS＝a＝eG*a＝a*eG，由于G滿足消去律，所以有：eS＝eG。2)對?a?S，由于S?G，所以a?G，即a在S中的逆元就是a在G中的逆元。,2019/12/16,計(jì)算機(jī)學(xué)院,67/224,,定理15.7設(shè)是一個(gè)群,是的子群,則:1）子群的幺元eS也是群的幺元eG；2）對?a?S，a在S中的逆元aS-1就是a在G中的逆元aG-1。證明：1)對?a?S，由于eS是S的幺元，所以有：eS*a＝a*eS＝a①又S?G,所以a?G,由eG是G的幺元，所以有：eG*a＝a*eG＝a②由①、②有：eS*a＝a*eS＝a＝eG*a＝a*eG，由于G滿足消去律，所以有：eS＝eG。2)對?a?S，由于S?G，所以a?G，即a在S中的逆元就是a在G中的逆元。,2019/12/16,計(jì)算機(jī)學(xué)院,68/224,,定理15.7設(shè)是一個(gè)群,是的子群,則:1）子群的幺元eS也是群的幺元eG；2）對?a?S，a在S中的逆元aS-1就是a在G中的逆元aG-1。證明：1)對?a?S，由于eS是S的幺元，所以有：eS*a＝a*eS＝a①又S?G,所以a?G,由eG是G的幺元，所以有：eG*a＝a*eG＝a②由①、②有：eS*a＝a*eS＝a＝eG*a＝a*eG，由于G滿足消去律，所以有：eS＝eG。2)對?a?S，由于S?G，所以a?G，即a在S中的逆元就是a在G中的逆元。,2019/12/16,計(jì)算機(jī)學(xué)院,69/224,,定理15.7設(shè)是一個(gè)群,是的子群,則:1）子群的幺元eS也是群的幺元eG；2）對?a?S，a在S中的逆元aS-1就是a在G中的逆元aG-1。證明：1)對?a?S，由于eS是S的幺元，所以有：eS*a＝a*eS＝a①又S?G,所以a?G,由eG是G的幺元，所以有：eG*a＝a*eG＝a②由①、②有：eS*a＝a*eS＝a＝eG*a＝a*eG，由于G滿足消去律，所以有：eS＝eG。2)對?a?S，由于S?G，所以a?G，即a在S中的逆元就是a在G中的逆元。,2019/12/16,計(jì)算機(jī)學(xué)院,70/224,,定理15.8設(shè)是一個(gè)群，S是G的一個(gè)非空子集，則是的子群的充要條件是：對?a，b?S，有a*b-1?S。證明：“?”設(shè)S是G的子群，對?a?S，由群的定義知，b-1?S，即有a*b-1?S。所以必要性成立；,“?”由子群的定義知，需證明如下四點(diǎn)：1)S是非空的子集；,2019/12/16,計(jì)算機(jī)學(xué)院,71/224,,定理15.8設(shè)是一個(gè)群，S是G的一個(gè)非空子集，則是的子群的充要條件是：對?a，b?S，有a*b-1?S。證明：“?”設(shè)S是G的子群，對?a?S，由群的定義知，b-1?S，即有a*b-1?S。所以必要性成立；,“?”由子群的定義知，需證明如下四點(diǎn)：1)S是非空的子集；,2019/12/16,計(jì)算機(jī)學(xué)院,72/224,,定理15.8設(shè)是一個(gè)群，S是G的一個(gè)非空子集，則是的子群的充要條件是：對?a，b?S，有a*b-1?S。證明：“?”設(shè)S是G的子群，對?a?S，由群的定義知，b-1?S，即有a*b-1?S。所以必要性成立；,“?”由子群的定義知，需證明如下四點(diǎn)：1)S是非空的子集；,2019/12/16,計(jì)算機(jī)學(xué)院,73/224,2)幺元存在：由于S?Φ，所以有a?S，由對?a,b?S,有a*b-?S,取a＝b,有eG＝a*a-?S;3)逆元存在：對?a,b?S，有a*b-1?S，對?b?S，由eG?S，有b-＝eG*b-?S；4)封閉性：對?a,b?S，由3)知：b-?S，由條件知：a*(b-)-?S，即a*b?S.由1)、2)、3)、4)知:是的子群。,2019/12/16,計(jì)算機(jī)學(xué)院,74/224,2)幺元存在：由于S?Φ，所以有a?S，由對?a,b?S,有a*b-?S,取a＝b,有eG＝a*a-?S;3)逆元存在：對?a,b?S，有a*b-1?S，對?b?S，由eG?S，有b-＝eG*b-?S；4)封閉性：對?a,b?S，由3)知：b-?S，由條件知：a*(b-)-?S，即a*b?S.由1)、2)、3)、4)知:是的子群。,2019/12/16,計(jì)算機(jī)學(xué)院,75/224,2)幺元存在：由于S?Φ，所以有a?S，由對?a,b?S,有a*b-?S,取a＝b,有eG＝a*a-?S;3)逆元存在：對?a,b?S，有a*b-1?S，對?b?S，由eG?S，有b-＝eG*b-?S；4)封閉性：對?a,b?S，由3)知：b-?S，由條件知：a*(b-)-?S，即a*b?S.由1)、2)、3)、4)知:是的子群。,2019/12/16,計(jì)算機(jī)學(xué)院,76/224,例:,設(shè)是一個(gè)群，令：C＝{a|a?G且對?x?G，有：a*x＝x*a}證明是的一個(gè)子群。證明:1)非空性：對?x?G，由于幺元e?G存在，所以有:e*x＝x*e＝x，即e?C，所以C是非空的；2)封閉性：對?a，b?C，則有：對?x?Ga*x＝x*a，b*x＝x*b，∴(a*b)*x＝a*(b*x)＝a*(x*b)＝(a*x)*b＝(x*a)*b＝x*(a*b)，即：a*b?C；,2019/12/16,計(jì)算機(jī)學(xué)院,77/224,例:,設(shè)是一個(gè)群，令：C＝{a|a?G且對?x?G，有：a*x＝x*a}證明是的一個(gè)子群。證明:1)非空性：對?x?G，由于幺元e?G存在，所以有:e*x＝x*e＝x，即e?C，所以C是非空的；2)封閉性：對?a，b?C，則有：對?x?Ga*x＝x*a，b*x＝x*b，∴(a*b)*x＝a*(b*x)＝a*(x*b)＝(a*x)*b＝(x*a)*b＝x*(a*b)，即：a*b?C；,2019/12/16,計(jì)算機(jī)學(xué)院,78/224,例:,設(shè)是一個(gè)群，令：C＝{a|a?G且對?x?G，有：a*x＝x*a}證明是的一個(gè)子群。證明:1)非空性：對?x?G，由于幺元e?G存在，所以有:e*x＝x*e＝x，即e?C，所以C是非空的；2)封閉性：對?a，b?C，則有：對?x?Ga*x＝x*a，b*x＝x*b，∴(a*b)*x＝a*(b*x)＝a*(x*b)＝(a*x)*b＝(x*a)*b＝x*(a*b)，即：a*b?C；,2019/12/16,計(jì)算機(jī)學(xué)院,79/224,,3)、逆元存在：對?a?C，有：對?x?G，a*x＝x*a∵C?G，∴a?G，即有：a-1?G，有：a-1*(a*x)*a-1＝a-1*(x*a)*a-1，即有：x*a-1＝a-1*x，所以a-1?C。由1)、2)、3)知:是的一個(gè)子群。,2019/12/16,計(jì)算機(jī)學(xué)院,80/224,,3)、逆元存在：對?a?C，有：對?x?G，a*x＝x*a∵C?G，∴a?G，即有：a-1?G，有：a-1*(a*x)*a-1＝a-1*(x*a)*a-1，即有：x*a-1＝a-1*x，所以a-1?C。由1)、2)、3)知:是的一個(gè)子群。,2019/12/16,計(jì)算機(jī)學(xué)院,81/224,,3)、逆元存在：對?a?C，有：對?x?G，a*x＝x*a∵C?G，∴a?G，即有：a-1?G，有：a-1*(a*x)*a-1＝a-1*(x*a)*a-1，即有：x*a-1＝a-1*x，所以a-1?C。由1)、2)、3)知:是的一個(gè)子群。,2019/12/16,計(jì)算機(jī)學(xué)院,82/224,例:,設(shè)是一個(gè)整數(shù)加群，令：H＝{nk|k?Z且n是一個(gè)取定的自然數(shù)}，證明是的一個(gè)子群。證明:1)非空性：顯然；2)封閉性：對?a，b?H，有a＝nk1，b＝nk2(k1，k2?Z)，a+b＝nk1+nk2＝n(k1+k2)?H(k1+k2?Z)；3)逆元存在：對?a?H，有a＝nk1(k1?Z)，則a-＝-a＝-nk1＝n(-k1)?H(-k1?Z)。由1),2),3)知是的一個(gè)子群。,2019/12/16,計(jì)算機(jī)學(xué)院,83/224,例:,設(shè)是一個(gè)整數(shù)加群，令：H＝{nk|k?Z且n是一個(gè)取定的自然數(shù)}，證明是的一個(gè)子群。證明:1)非空性：顯然；2)封閉性：對?a，b?H，有a＝nk1，b＝nk2(k1，k2?Z)，a+b＝nk1+nk2＝n(k1+k2)?H(k1+k2?Z)；3)逆元存在：對?a?H，有a＝nk1(k1?Z)，則a-＝-a＝-nk1＝n(-k1)?H(-k1?Z)。由1),2),3)知是的一個(gè)子群。,2019/12/16,計(jì)算機(jī)學(xué)院,84/224,例:,設(shè)是一個(gè)整數(shù)加群，令：H＝{nk|k?Z且n是一個(gè)取定的自然數(shù)}，證明是的一個(gè)子群。證明:1)非空性：顯然；2)封閉性：對?a，b?H，有a＝nk1，b＝nk2(k1，k2?Z)，a+b＝nk1+nk2＝n(k1+k2)?H(k1+k2?Z)；3)逆元存在：對?a?H，有a＝nk1(k1?Z)，則a-＝-a＝-nk1＝n(-k1)?H(-k1?Z)。由1),2),3)知是的一個(gè)子群。,2019/12/16,計(jì)算機(jī)學(xué)院,85/224,,例：設(shè)是一個(gè)群，H1，H2是G的兩個(gè)子群。證明H＝H1∩H2是G的子群。證明1)、非空性：由于H1，H2是G的兩個(gè)子群，所以有：e?H1，e?H2，即有e?H1∩H2；2)、封閉性：對?a，b?H，有a，b?H1∩H2，即a，b?H1，a，b?H2，由于H1，H2都是G的子群，所以有：a*b?H1，a*b?H2，即有：a*b?H1∩H23)、逆元存在：對?a?H，有a?H1∩H2，即a?H1，a?H2，由于H1，H2都是G的子群，所以有：a-1?H1，a-1?H2，即有：a-1?H1∩H2。由1)、2)、3)知：是的一個(gè)子群。,2019/12/16,計(jì)算機(jī)學(xué)院,86/224,,例：設(shè)是一個(gè)群，H1，H2是G的兩個(gè)子群。證明H＝H1∩H2是G的子群。證明1)、非空性：由于H1，H2是G的兩個(gè)子群，所以有：e?H1，e?H2，即有e?H1∩H2；2)、封閉性：對?a，b?H，有a，b?H1∩H2，即a，b?H1，a，b?H2，由于H1，H2都是G的子群，所以有：a*b?H1，a*b?H2，即有：a*b?H1∩H23)、逆元存在：對?a?H，有a?H1∩H2，即a?H1，a?H2，由于H1，H2都是G的子群，所以有：a-1?H1，a-1?H2，即有：a-1?H1∩H2。由1)、2)、3)知：是的一個(gè)子群。,2019/12/16,計(jì)算機(jī)學(xué)院,87/224,,例：設(shè)是一個(gè)群，H1，H2是G的兩個(gè)子群。證明H＝H1∩H2是G的子群。證明1)、非空性：由于H1，H2是G的兩個(gè)子群，所以有：e?H1，e?H2，即有e?H1∩H2；2)、封閉性：對?a，b?H，有a，b?H1∩H2，即a，b?H1，a，b?H2，由于H1，H2都是G的子群，所以有：a*b?H1，a*b?H2，即有：a*b?H1∩H23)、逆元存在：對?a?H，有a?H1∩H2，即a?H1，a?H2，由于H1，H2都是G的子群，所以有：a-1?H1，a-1?H2，即有：a-1?H1∩H2。由1)、2)、3)知：是的一個(gè)子群。,2019/12/16,計(jì)算機(jī)學(xué)院,88/224,,例：設(shè)是一個(gè)群，H1，H2是G的兩個(gè)子群。證明H＝H1∩H2是G的子群。證明1)、非空性：由于H1，H2是G的兩個(gè)子群，所以有：e?H1，e?H2，即有e?H1∩H2；2)、封閉性：對?a，b?H，有a，b?H1∩H2，即a，b?H1，a，b?H2，由于H1，H2都是G的子群，所以有：a*b?H1，a*b?H2，即有：a*b?H1∩H23)、逆元存在：對?a?H，有a?H1∩H2，即a?H1，a?H2，由于H1，H2都是G的子群，所以有：a-1?H1，a-1?H2，即有：a-1?H1∩H2。由1)、2)、3)知：是的一個(gè)子群。,2019/12/16,計(jì)算機(jī)學(xué)院,89/224,推廣,設(shè)是一個(gè)群，H1，H2，…，Hn是G的n個(gè)子群，則有H＝H1∩H2∩…∩Hn是G的子群。,2019/12/16,計(jì)算機(jī)學(xué)院,90/224,☆復(fù)習(xí),若整數(shù)m和n關(guān)于模d的余數(shù)相同，稱m和n（關(guān)于模d）是同余的，記為：n≡m(mod)d同余是整數(shù)之間的一種重要關(guān)系。模d同余的數(shù)的全體構(gòu)成的集合稱為一個(gè)同余類。這個(gè)集合可以表示成：[n]d={x|n≡x(mod)d},n=m+kdk為整數(shù),2019/12/16,計(jì)算機(jī)學(xué)院,91/224,☆復(fù)習(xí),Zk表示整數(shù)集Z上的模k剩余類集合，即Zk={[0]，[1]，[2]，…，[k-1]}例：n=6，則：Zn={[0]，[1]，[2]，[3]，[4]，[5]}[0]={…，-12，-6，0，6，12，18，…}[1]={…，-11，-5，1，7，13，19，…}[2]={…，-10，-4，2，8，14，20，…}…,2019/12/16,計(jì)算機(jī)學(xué)院,92/224,☆例:,設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即Zk={[0]，[1]，[2]，…，[k-1]}在Zk上定義運(yùn)算?和?如下：[i]?[j]=[t]?（i+j）?t（modk）[i]?[j]=[t]?ij?t（modk）是群（剩余類加群）。[0]是?的幺元，每元[i]的?逆元是[k-i]。不是群，因?yàn)殡m然它滿足封閉性和可結(jié)合性，且[1]是它的幺元，但是[0]無?逆元，所以它僅僅是一個(gè)含幺半群。,2019/12/16,計(jì)算機(jī)學(xué)院,93/224,☆例:,設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即Zk={[0]，[1]，[2]，…，[k-1]}在Zk上定義運(yùn)算?和?如下：[i]?[j]=[t]?（i+j）?t（modk）[i]?[j]=[t]?ij?t（modk）是群（剩余類加群）。[0]是?的幺元，每元[i]的?逆元是[k-i]。不是群，因?yàn)殡m然它滿足封閉性和可結(jié)合性，且[1]是它的幺元，但是[0]無?逆元，所以它僅僅是一個(gè)含幺半群。,2019/12/16,計(jì)算機(jī)學(xué)院,94/224,☆例:,設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即Zk={[0]，[1]，[2]，…，[k-1]}在Zk上定義運(yùn)算?和?如下：[i]?[j]=[t]?（i+j）?t（modk）[i]?[j]=[t]?ij?t（modk）是群（剩余類加群）。[0]是?的幺元，每元[i]的?逆元是[k-i]。不是群，因?yàn)殡m然它滿足封閉性和可結(jié)合性，且[1]是它的幺元，但是[0]無?逆元，所以它僅僅是一個(gè)含幺半群。,2019/12/16,計(jì)算機(jī)學(xué)院,95/224,,是不是群呢？不一定！Z4-{[0]}={[1]，[2]，[3]}，而[2]?[2]=[0]?Z4-{[0]}∴不是群。而Z5-{[0]}={[1]，[2]，[3]，[4]}其運(yùn)算表如右圖，運(yùn)算是封閉的，可結(jié)合的；[1]是幺元，[1]、[4]的逆元是自身，[2]、[3]互為逆元；因此是群。,2019/12/16,計(jì)算機(jī)學(xué)院,96/224,,是不是群呢？不一定！Z4-{[0]}={[1]，[2]，[3]}，而[2]?[2]=[0]?Z4-{[0]}∴不是群。而Z5-{[0]}={[1]，[2]，[3]，[4]}其運(yùn)算表如右圖，運(yùn)算是封閉的，可結(jié)合的；[1]是幺元，[1]、[4]的逆元是自身，[2]、[3]互為逆元；因此是群。,2019/12/16,計(jì)算機(jī)學(xué)院,97/224,,是不是群呢？不一定！Z4-{[0]}={[1]，[2]，[3]}，而[2]?[2]=[0]?Z4-{[0]}∴不是群。而Z5-{[0]}={[1]，[2]，[3]，[4]}其運(yùn)算表如右圖，運(yùn)算是封閉的，可結(jié)合的；[1]是幺元，[1]、[4]的逆元是自身，[2]、[3]互為逆元；因此是群。,2019/12/16,計(jì)算機(jī)學(xué)院,98/224,例:,設(shè)n個(gè)元素的集合A上的全體置換構(gòu)成集合Sn，證明構(gòu)成群。（n次對稱群）證明：1）Sn中兩個(gè)置換的復(fù)合仍然是A上的一個(gè)置換，所以運(yùn)算是封閉的；2）由于函數(shù)的復(fù)合是可結(jié)合的，所以置換的復(fù)合也是可結(jié)合的；3）Sn中存在幺置換(單位置換）?=（1），使對???Sn，???=???=?所以?=（1）是幺元；4）每個(gè)置換將x變成y，而逆置換是將y變成x，所以，每個(gè)置換都有逆。,2019/12/16,計(jì)算機(jī)學(xué)院,99/224,例:,設(shè)n個(gè)元素的集合A上的全體置換構(gòu)成集合Sn，證明構(gòu)成群。（n次對稱群）證明：1）Sn中兩個(gè)置換的復(fù)合仍然是A上的一個(gè)置換，所以運(yùn)算是封閉的；2）由于函數(shù)的復(fù)合是可結(jié)合的，所以置換的復(fù)合也是可結(jié)合的；3）Sn中存在幺置換(單位置換）?=（1），使對???Sn，???=???=?所以?=（1）是幺元；4）每個(gè)置換將x變成y，而逆置換是將y變成x，所以，每個(gè)置換都有逆。,2019/12/16,計(jì)算機(jī)學(xué)院,100/224,例:,設(shè)n個(gè)元素的集合A上的全體置換構(gòu)成集合Sn，證明構(gòu)成群。（n次對稱群）證明：1）Sn中兩個(gè)置換的復(fù)合仍然是A上的一個(gè)置換，所以運(yùn)算是封閉的；2）由于函數(shù)的復(fù)合是可結(jié)合的，所以置換的復(fù)合也是可結(jié)合的；3）Sn中存在幺置換(單位置換）?=（1），使對???Sn，???=???=?所以?=（1）是幺元；4）每個(gè)置換將x變成y，而逆置換是將y變成x，所以，每個(gè)置換都有逆。,2019/12/16,計(jì)算機(jī)學(xué)院,101/224,例:,設(shè)n個(gè)元素的集合A上的全體置換構(gòu)成集合Sn，證明構(gòu)成群。（n次對稱群）證明：1）Sn中兩個(gè)置換的復(fù)合仍然是A上的一個(gè)置換，所以運(yùn)算是封閉的；2）由于函數(shù)的復(fù)合是可結(jié)合的，所以置換的復(fù)合也是可結(jié)合的；3）Sn中存在幺置換(單位置換）?=（1），使對???Sn，???=???=?所以?=（1）是幺元；4）每個(gè)置換將x變成y，而逆置換是將y變成x，所以，每個(gè)置換都有逆。,2019/12/16,計(jì)算機(jī)學(xué)院,102/224,例:,設(shè)n個(gè)元素的集合A上的全體置換構(gòu)成集合Sn，證明構(gòu)成群。（n次對稱群）證明：1）Sn中兩個(gè)置換的復(fù)合仍然是A上的一個(gè)置換，所以運(yùn)算是封閉的；2）由于函數(shù)的復(fù)合是可結(jié)合的，所以置換的復(fù)合也是可結(jié)合的；3）Sn中存在幺置換(單位置換）?=（1），使對???Sn，???=???=?所以?=（1）是幺元；4）每個(gè)置換將x變成y，而逆置換是將y變成x，所以，每個(gè)置換都有逆。,2019/12/16,計(jì)算機(jī)學(xué)院,103/224,習(xí)題,P19310,2019/12/16,計(jì)算機(jī)學(xué)院,104/224,,15.3交換群和循環(huán)群,2019/12/16,計(jì)算機(jī)學(xué)院,105/224,交換群,,定義15.3若群中的運(yùn)算“*”滿足交換律，則稱該群是一個(gè)交換群（或阿貝爾(Abel)群）。例整數(shù)加群，實(shí)數(shù)加群，有理數(shù)加群，剩余類乘群、實(shí)數(shù)乘群都是交換群。而n階非奇異矩陣乘群、n階置換群等不是交換群?！翱蓳Q性”是代數(shù)運(yùn)算的一個(gè)重要性質(zhì)。習(xí)慣上都把數(shù)的加法運(yùn)算作為可換性的代表，因而交換群又常被稱為加群。,2019/12/16,計(jì)算機(jī)學(xué)院,106/224,交換群,,定義15.3若群中的運(yùn)算“*”滿足交換律，則稱該群是一個(gè)交換群（或阿貝爾(Abel)群）。例整數(shù)加群，實(shí)數(shù)加群，有理數(shù)加群，剩余類乘群、實(shí)數(shù)乘群都是交換群。而n階非奇異矩陣乘群、n階置換群等不是交換群?！翱蓳Q性”是代數(shù)運(yùn)算的一個(gè)重要性質(zhì)。習(xí)慣上都把數(shù)的加法運(yùn)算作為可換性的代表，因而交換群又常被稱為加群。,2019/12/16,計(jì)算機(jī)學(xué)院,107/224,交換群,,定義15.3若群中的運(yùn)算“*”滿