《離散數(shù)學(xué)》第五章3-4節(jié)

定義5-3.1：一個(gè)代數(shù)系統(tǒng)<S,*>，其中S是非空集合，*是S上的一個(gè)二元運(yùn)算，如果運(yùn)算*是封閉的，則稱代數(shù)系統(tǒng)<S,*>為廣群。

例如：？？

5-3半群1、廣群、半群及其性質(zhì)1整理ppt定義5-3.2：一個(gè)代數(shù)系統(tǒng)<S,*>，其中S是非空集合，*是S上的一個(gè)二元運(yùn)算。如果：(1)運(yùn)算*是封閉的。(2)運(yùn)算*是可結(jié)合的，即對(duì)任意的x,y,z∈S，滿足(x*y)*z=x*(y*z)則稱代數(shù)系統(tǒng)<S,*>為半群。思考：（a）例如：？？(b)與廣群的關(guān)系(1)<N,+>,

<Z,+>,

<Q,+>,

<R,+>。(2)<Mn(R),+>,<Mn(R),.>,其中Mn(R)為n階實(shí)矩陣。2整理ppt例1：證明代數(shù)系統(tǒng)<R*,?>是一個(gè)半群，其中R*是非零實(shí)數(shù)集合，?運(yùn)算定義為：x?y=y。解：x,y∈R*，x?y=y∈R*，封閉性；x,y,z∈R*，有(x?y)?z=y?z=zx?(y?z)=x?z=z，即(x?y)?z=x?(y?z)，結(jié)合律；所以代數(shù)系統(tǒng)<R*,?>是一個(gè)半群。3整理ppt

例2設(shè)S={a,b,c}，在S上的一個(gè)二元運(yùn)算△的運(yùn)算表如下，驗(yàn)證<S,△>是一個(gè)半群。△abcabcabcabcabc觀察特點(diǎn)？要驗(yàn)證3！個(gè)式子嗎4整理ppt定理5-3.1：設(shè)<S,*>是一個(gè)半群，B

S且*在B上是封閉的，那么<B,*>也是一個(gè)半群。稱<B,*>是半群<S,*>的子半群。問(wèn)題：設(shè)<S,*>是一個(gè)半群，B

S，則<B,*>？？5整理ppt例3：設(shè)?表示普通的乘法運(yùn)算，那么<[0,1],?>、<[0,1),?>和<I,?>都是<R,?>的子半群。驗(yàn)證<B,*>是半群<S,*>的子半群，滿足：*在B上封閉；B是S的子集。6整理ppt定理5-3.2：設(shè)<S,*>是一個(gè)半群，如果S是一個(gè)有限集，則必有a∈S，使得a*a=a。證明：因?yàn)?lt;S,*>是半群。對(duì)于

b∈S，由*的封閉性，有b∈S，b2=b*b∈S，…，bi∈S，…，bn∈S，因S是有限集，j>i，使得bi=bj，令p=j-i，所以有bi=bp*bi，顯然對(duì)于q≥i，有bq=bp*bq，7整理ppt∵p≥1，∴總可以找到k≥1，使得kp≥i，對(duì)于S中的元素bkp，就有bkp=bp*bkp

=bp*(bp*bkp)=b2p*bkp=b2p*(bp*bkp)=…=bkp*bkp

證明了在S中存在元素a=bkp,使得a*a=a8整理ppt定義5-3.3：含有幺元的半群稱為獨(dú)異點(diǎn)。思考：舉例？？與半群的關(guān)系例如，下列代數(shù)系統(tǒng)是不是獨(dú)異點(diǎn)<R,+>，<I,?>、<I+,?>、<R,?>，2、獨(dú)異點(diǎn)及其性質(zhì)0是R中運(yùn)算+的幺元；具有幺元1。9整理ppt定理5-3.3設(shè)<S,*>是一個(gè)獨(dú)異點(diǎn)，則在關(guān)于運(yùn)算*的運(yùn)算表中任何兩行或兩列都是不相同的。證明：設(shè)S中關(guān)于運(yùn)算*的幺元為e，

a,b∈S且a≠b時(shí)，總有e*a=a，e*b=b；a≠b,∴任何兩列都是不相同的。a*e=a，b*e=b；a≠b,∴任何兩行都是不相同的。所以*的運(yùn)算表中不可能有兩行或兩列是相同的。10整理ppt例4：設(shè)I是整數(shù)集合，m是任意正整數(shù)，Zm是由模m的同余類組成的同余類集，在Zm上定義兩個(gè)二元運(yùn)算+m和×m分別如下：對(duì)于任意的[i],[j]∈Zm[i]+m[j]=[(i+j)(modm)][i]×m[j]=[(i×j)(modm)]試證明在這兩個(gè)二元運(yùn)算的運(yùn)算表中任何兩行或兩列都不相同。咋證呢？11整理ppt證明：1)由運(yùn)算+m和×m的定義，可知它們?cè)赯m上都封閉的。2)對(duì)于任意[i],[j],[k]∈Zm

([i]+m[j])+m[k]=[(i+j+k)(modm)]=[i]+m([j]+m[k])

([i]×m[j])×m[k]=[(i×j×k)(modm)]=[i]×m([j]×m[k])12整理ppt

3)∵[0]+m[i]=[i]+m[0]=[i]，∴[0]是<Zm,+m>中的幺元。∵[1]×m[i]=[i]×m[1]=[i]，∴[1]是<Zm,×m>中的幺元。因此，代數(shù)系統(tǒng)<Zm,＋m>，<Zm,×m>都是獨(dú)異點(diǎn)。由定理5-3.3可知這兩個(gè)運(yùn)算表中任何兩行或兩列都不相同。13整理ppt定理5-3.4：設(shè)<S,*>是獨(dú)異點(diǎn)，對(duì)于任意a,b∈S，且a,b均有逆元，則1）(a-1)-1=a；2）a*b有逆元，且(a*b)-1=b-1*a-1。證明：a)因?yàn)閍-1是a的逆元，即a*a-1=a-1*a=e(a-1)-1=ab)

因?yàn)?a*b)*(b-1*a-1)=a*(b*b-1)*a-1

=a*e*a-1

=a*a-1=e同理可證(b-1*a-1)*(a*b)=e所以(a*b)-1=b-1*a-114整理ppt1、群及其性質(zhì)1)基本概念(群、有限群、無(wú)限群)定義5-4.1：設(shè)<G,*>是代數(shù)系統(tǒng)，其中G是非空集合，*是G上的二元運(yùn)算，如果(1)運(yùn)算*是封閉的；(2)運(yùn)算*是可結(jié)合的；(3)存在幺元；(4)對(duì)于每一個(gè)元素x∈G，存在著它的逆元x-1∈G；則稱<G,*>是一個(gè)群。5-4群與子群廣群半群獨(dú)異點(diǎn)15整理ppt廣群，半群，獨(dú)異點(diǎn)，群的關(guān)系（封閉）半群（結(jié)合律）獨(dú)異點(diǎn)（有幺元）群（有逆元）廣群16整理ppt例1：判斷下列代數(shù)系統(tǒng)是否為群<R-{0},+>，<P(S),⊕>，<R-{0},×>群的分類：定義5-4.2設(shè)<G,*>是一個(gè)群。如果G是有限集，那么稱<G,*>為有限群，G中元素的個(gè)數(shù)通常稱為該有限群的階數(shù)，記為|G|；如果G是無(wú)限集，則稱<G,*>為無(wú)限群。約定無(wú)限群的階數(shù)為∞17整理ppt例2：試驗(yàn)證代數(shù)系統(tǒng)<I,+>是一個(gè)群，I是整數(shù)集合，+是普通加法運(yùn)算。解：二元運(yùn)算+在I上是封閉的且是可結(jié)合的。幺元是0，任一元素a∈A，它的逆元是-a，所以<I,+>是一個(gè)群，且是一個(gè)無(wú)限群。又如：<I+,+>是嗎？18整理ppt2）群的性質(zhì)復(fù)習(xí)：定理5-2.3：設(shè)A是一個(gè)代數(shù)系統(tǒng)，且集合A中元素的個(gè)數(shù)大于1，如果該系統(tǒng)中存在幺元e和零元θ，則e≠θ。定理5-3.2：設(shè)<S,*>是一個(gè)半群，如果S是一個(gè)有限集，則必有a∈S，使得a*a=a（等冪元）。定理5-3.3設(shè)<S,*>是一個(gè)獨(dú)異點(diǎn)，則在關(guān)于運(yùn)算*的運(yùn)算表中任何兩行或兩列都是不相同的。定理5-3.4：設(shè)<S,*>是獨(dú)異點(diǎn)，對(duì)于任意a,b∈S，且a,b均有逆元，則1）(a-1)-1=a；2）a*b有逆元，且(a*b)-1=b-1*a-1。19整理ppt定理5-4.1：群中不可能有零元。證明：當(dāng)群的階為1時(shí)，它的唯一元素視為幺元。設(shè)|G|>1且群<G,*>有零元θ，任意x∈G，有x*θ=θ*x=θ≠e，定理5-2.3所以，零元θ就不存在逆元，與<G,*>是群相矛盾。20整理ppt定理5-4.2：設(shè)<G,*>是群，對(duì)于a,b∈G，必存在唯一的x∈G，使得a*x=b。證明：設(shè)a的逆元是a-1，令x=a-1*b（常用方法）則a*x=a*(a-1*b)=(a*a-1)*b=e*b=b若另有一解x1，滿足a*x1=b，則a-1*(a*x1)=a-1*b即x1=a-1*b21整理ppt定理5-4.3：設(shè)<G,*>是群，對(duì)于a,b,c∈G，如果有a*b=a*c或b*a=c*a，則必有b=c（消去律）。證明：設(shè)a*b=a*c，且a的逆元是a-1，則有a-1*(a*b)=a-1*(a*c)(a-1*a)*b=(a-1*a)*ce*b=e*cb=c當(dāng)b*a=c*a時(shí)，同理可證b=c。22整理ppt定義5-4.3：設(shè)S是一個(gè)非空集合，從集合S到S的一個(gè)雙射稱為S的一個(gè)置換。例如：S={a,b,c,d},一個(gè)置換為3）置換、等冪元23整理ppt定理5-4.4：群<G,*>的運(yùn)算表中的每一行或每一列都是G的元素的一個(gè)置換。2)對(duì)每一行，G中每個(gè)元素出現(xiàn)最多一次：入射設(shè)對(duì)應(yīng)于元素a∈G的那一行中若有兩個(gè)元素都是c，即有a*b1=a*b2=c，且b1≠b2，由消去律可得b1=b2，矛盾所以<G,*>的運(yùn)算表中每一行都是G的一個(gè)置換。同理<G,*>的運(yùn)算表中每一列都是G的一個(gè)置換。證明：1)G中每個(gè)元素都在每一行中出現(xiàn)：滿射設(shè)

b∈G的元素，考察對(duì)應(yīng)于a∈G的那一行由于b=a*(a-1*b)，所以b必定出現(xiàn)在對(duì)應(yīng)a的那一行中。24整理ppt定理5-4.5：在群<A,*>中，除幺元e外，不可能有任何別的等冪元。證明:(1)證幺元e是等冪元

(2)假設(shè)a

∈A，且a≠e，滿足a*a=a，則a=e*a=(a-1*a)*a=a-1*(a*a)=a-1*a=e矛盾25整理ppt1）基本概念(子群、平凡子群)定義5-4.5：設(shè)<G,*>是一個(gè)群，S是G的一個(gè)非空子集，如果<S,*>也構(gòu)成群，則稱<S,*>是<G,*>的一個(gè)子群。2、子群及其性質(zhì)定義5-4.6：設(shè)<G,*>是一個(gè)群，<S,*>是<G,*>的一個(gè)子群，如果S={e}或S=G，則稱<S,*>為<G,*>的平凡子群。平凡子集26整理ppt例1：判斷下列說(shuō)法是否正確<Z,+>為<Q,+>的子群<R+,×>是<R-{0},×>的子群，也是<R,+>的子群27整理ppt例2：<I,+>是一個(gè)群，設(shè)IE={x|x=2n,n∈I}，證明<IE,+>是<I,+>的一個(gè)子群。證明：1）封閉性。

2）運(yùn)算+在IE上保持可結(jié)合性。

3）<I,+>中的幺元0在IE中。

4）對(duì)于任意的x∈IE，-x=-2n，-n∈I，∴-x∈IE，x+(-x)=0。因此<IE，+>是一個(gè)群，又IE是I的子集，所以<IE，+>是<I,+>的一個(gè)子群。28整理ppt證明：設(shè)<S,*>中的幺元為e1，對(duì)于任一x∈S

G，必有e1*x=x=e*x，故e1=e（根據(jù)？？）。定理5-4.6：設(shè)<G,*>是一個(gè)群，<S,*>是<G,*>的一個(gè)子群，那么<G,*>中的幺元e必定也是<S,*>中的幺元。29整理ppt補(bǔ)充：定義：設(shè)<S,*>為一半群，a∈S，n為正整數(shù)，符號(hào)an表示n個(gè)a的計(jì)算結(jié)果，即an=a*a*……*a。在半群<S,*>中指數(shù)律成立，即對(duì)任意整數(shù)m，n和S中的元素a，有aman=am+n，(am)n=amn定義的擴(kuò)充如果<S,*>是獨(dú)異點(diǎn)，e是幺元，a∈S，令a0=e，如果<S,*>是群，a∈S，n為正整數(shù)，則令a-n=(a-1)n30整理ppt定理5-4.7：設(shè)<G,*>是一個(gè)群，B是G的非空子集，如果B是一個(gè)有限集，那么只要運(yùn)算*在B上封閉，<B,*>必定是<G,*>的子群。證明：要證滿足已知條件的<B,*>是一個(gè)子群，

1)封閉。2)結(jié)合。

3)存在幺元。b∈B，b2=b*b∈