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

章幾個典型的代數(shù)系統(tǒng)

6.1半群與群6.1.1半群與獨(dú)異點(diǎn)6.1.2群的定義與性質(zhì)6.1.3子群6.1.4陪集與拉格朗日定理6.1.5正規(guī)子群與商群6.1.6循環(huán)群和置換群6.2環(huán)與域6.2.1環(huán)的定義與性質(zhì)6.2.2整環(huán)與域6.3格與布爾代數(shù)2021/5/916.1半群與群半群、可交換半群和獨(dú)異點(diǎn)定義6.1①設(shè)V=<S,?>是代數(shù)系統(tǒng),?為二元運(yùn)算,如果?是可結(jié)合的,則稱V為半群．②

如果半群V=<S,?>中的二元運(yùn)算含有幺元,則稱V為含幺半群,也可叫做獨(dú)異點(diǎn).定義6.2

如果半群V=<S,?>中的二元運(yùn)算?是可交換的,則稱V為可交換半群.注:為了強(qiáng)調(diào)幺元的存在,有時將獨(dú)異點(diǎn)記為<S,?,e>6.1.1半群與獨(dú)異點(diǎn)2021/5/92例6.1①<Z+,+>是半群②

<N,+>,<Z,+>,<Q,+>,<R,+>都是半群和獨(dú)異點(diǎn)，其中+表示普通加法,幺元是0,<N,+,0>,…,<R,+,0>③<Mn(R),·>是半群和獨(dú)異點(diǎn),其中·表示矩陣乘法,矩陣乘法的幺元是n階單位矩陣E.記作<Mn(R),·,E>④

<P(B),>是半群和獨(dú)異點(diǎn),其中表示集合的對稱差運(yùn)算,其幺元是,記作<P(B),,>⑤<Zn,>是半群和獨(dú)異點(diǎn),其中Zn={0,1,…,n-1},表示模n加法,模n加法的幺元是0.<Zn,,0>其中:①②④⑤為可交換半群.6.1.1半群與獨(dú)異點(diǎn)2021/5/936.1.1半群與獨(dú)異點(diǎn)例6.2判斷下述論斷正確與否,在相應(yīng)的括號中鍵入“Y”或“N”.(1)在實(shí)數(shù)集R上定義二元運(yùn)算*為：對于任意的a,b∈R,a*b=a+b+ab(a)<R,*>是一個代數(shù)系統(tǒng)；()(b)<R,*>是一個半群；()(c)<R,*>是一個獨(dú)異點(diǎn)。()(2)在實(shí)數(shù)集R上定義二元運(yùn)算?為,對任意a,b∈R,

a?b=|a|·b(其中·表示數(shù)學(xué)的乘法運(yùn)算)(a)<R,?>是一個代數(shù)系統(tǒng)；()(b)<R,?>是一個半群；()(c)<R,?>是一個獨(dú)異點(diǎn)。()NYYYYY2021/5/94子半群和子獨(dú)異點(diǎn)定義:半群的子代數(shù)叫做子半群,即:如果V=<S,?>是半群,<T,?>就是V的子半群,需要滿足如下兩個條件:①T是S的非空子集;②T對V中的運(yùn)算?是封閉的.定義:獨(dú)異點(diǎn)的子代數(shù)叫做子獨(dú)異點(diǎn),對獨(dú)異點(diǎn)V=<S,?,e>,<T,?,e>構(gòu)成V的子獨(dú)異點(diǎn),需要滿足如下條件:①T是S的非空子集;②T要對V中的運(yùn)算?封閉;③

e∈T.6.1.1半群與獨(dú)異點(diǎn)2021/5/95群的定義定義6.3設(shè)<G,?>是代數(shù)系統(tǒng),?為二元運(yùn)算.如果?是可結(jié)合的,存在幺元e∈G,并且G中的任意元素x,都有x-1∈G,則稱G是群.例6.3①<Z,+>,<Q,+>,<R,+>都是群;②<P(B),,>是群,其中表示集合的對稱差運(yùn)算,任意元素的逆元是其自身;③<Zn,,0>是群,其中Zn={0,1,…,n-1},表示模n加法,0的逆元是0,非0元素的逆元是n-x.6.1.2群的定義與性質(zhì)2021/5/966.1.2群的定義與性質(zhì)e為G中的幺元,?是可交換的.任何G中的元素與自己運(yùn)算的結(jié)果都等于e.在a,b,c三個元素中,任何兩個元素運(yùn)算的結(jié)果都等于另一個元素.一般稱這個群為Klein四元群.例6.4設(shè)G＝{e,a,b,c},?為G上的二元運(yùn)算,它由以下運(yùn)算表給出,不難證明G是一個群.2021/5/976.1.2群的定義與性質(zhì)群的術(shù)語(1)若群G中的二元運(yùn)算是可交換的,則稱群G為交換群,也叫做阿貝爾(Abel)群．例①

<Z,+>,<Q,+>,<R,+>都是群,也是阿貝爾(Abel)群;②<P(B),,>是群,也是阿貝爾(Abel)群;

③<Zn,,0>是群,也是阿貝爾(Abel)群.④Klein四元群也是阿貝爾群．(2)若群G中有無限多個元素,則稱G為無限群,否則稱為有限群,只含幺元的群為平凡群.例如,<Z,＋>,<R,＋>都是無限群.<Zn,>是有限群.Klein四元群也是有限群.2021/5/986.1.2群的定義與性質(zhì)群的術(shù)語(3)群的階:對于有限群G,G中的元素個數(shù)也叫做G的階,記作|G|.例如:<Zn,>是有限群,其階是n;Klein四元群也是有限群,其階是4.(4)xn定義:x0=e,xn+1=xn?x,x-n=(x-1)n(5)元素x的階:設(shè)G是群,x∈G,使得xk＝e成立的最小的正整數(shù)k叫做x的階(或周期).如果不存在正整數(shù)k,使xk＝e,則稱x是無限階元.注:對有限階的元素x,通常將它的階記為|x|.在任何群G中幺元e的階都是1．2021/5/996.1.2群的定義與性質(zhì)群的術(shù)語例.在Klein四元群中,|a|=?,|b|=?,|c|=?,|e|=?返回6.1.2群的定義與性質(zhì)群的性質(zhì)定理6.1設(shè)G為群,則G中的冪運(yùn)算滿足(群中元素的冪)(1)x∈G,(x-1)-1＝x(2)x,y∈G,(xy)-1＝y(tǒng)-1x-1(3)x∈G,xnxm＝xn+m(4)

x∈G,(xn)m＝xnm(5)若G為交換群,則(ab)n=anbn2021/5/911定理6.1的證明(1)a∈G,(a-1)-1＝a (a-1)-1是a-1的逆元，a也是a-1的逆元。 （或者：a-1是a的逆元，a也是a-1的逆元。） 根據(jù)逆元的唯一性，(a-1)-1＝a。(2)a,b∈G，(ab)-1＝b-1a-1 (b-1a-1)(ab)＝b-1(a-1a)b＝b-1b＝e (ab)(b-1a-1)＝a(bb-1)a-1＝aa-1＝e

故b-1a-1是ab的逆元。 根據(jù)逆元的唯一性等式得證。

2021/5/9126.1.2群的定義與性質(zhì)群的性質(zhì)定理6.2G為群,a,b∈G,則(1)G有唯一的單位元,G中每個元素恰有一個逆元;(2)G適合消去律,即對任意a,b,c∈G有若ab＝ac,則b＝c;若ba＝ca,則b＝c;(3)單位元是G的唯一的冪等元素;6.1.3子群子群的定義定義6.4

設(shè)群<G,*>,H是G的非空子集.如果H關(guān)于G中的運(yùn)算*構(gòu)成群,則稱H為G的子群,記作H≤G.若H是G的子群,且HG,則稱H是G的真子群.例如:在群<Z,＋>中,取2Z＝{2x|x∈Z},

則2Z關(guān)于加法構(gòu)成<Z,＋>的子群.

同樣,{0}也是<Z,＋>的子群.注意:類似于子代數(shù),任何群G都存在子群,G和{e}是G的平凡子群.2021/5/9146.1.3子群子群的判斷方法判定定理1設(shè)G為群,H是G的非空子集,H是G的子群當(dāng)且僅當(dāng):

(1)a,bH都有abH;(2)aH有a-1H.判定定理2設(shè)G為群,H是G的非空子集,則H是G的子群當(dāng)且僅當(dāng)a,bH都有ab-1H.判定定理3

設(shè)G為群,H是G的非空子集.若H是有窮集,則H是G的子群當(dāng)且僅當(dāng)a,bH都有abH.2021/5/9156.1.3子群子群的判斷方法例6.5

設(shè)G為群,對任何xG,令H＝{xk|kZ},即x的所有冪的集合,則H是G的子群,稱為由元素x生成的子群,記作<x>.證明:<x>≤G由x<x>可知<x>不為空.任取H中的元素xm,xl,都有

xm(xl)-1＝xmx-l＝xm-lH根據(jù)判定定理二可知<x>≤G.2021/5/9166.1.3子群例如,群<Z6,>中由2生成的子群包含2的各次冪,20=0,21=2,22=22=4,23=222=0,所以

<2>={0,2,4}.對于Klein四元群G={e,a,b,c}來說,由它的每個元素生成的子群是

<e>={e},<a>={e,a},<b>={e,b},<c>={e,c}2021/5/9176.1.3子群群的中心設(shè)G為群,令C是與G中所有的元素都可交換的元素構(gòu)成的集合,即

C＝{a|aG∧xG(ax=xa)},

稱C為群G的中心.2021/5/9186.1.4陪集與拉格朗日定理陪集的定義定義6.4H是G的子群,aG,令Ha={ha|hH}稱Ha是子群H在G中的右陪集,稱a為Ha的代表元素.例6.6

設(shè)G={e,a,b,c}是Klein四元群,H={e,a}是G的子群,那么H的所有右陪集是:He={e,a}=HHa={e,a}=HHb={b,c}Hc={c,b}注:

類似地可以定義左陪集.?eabceeabcaaecbbbceaccbae6.1.4陪集與拉格朗日定理陪集的定義例6.6

設(shè)A={1,2,3},f1,f2,…,f6是A上的雙射函數(shù),其中:f1={<1,1>,<2,2>,<3,3>},f2={<1,2>,<2,1>,<3,3>}f3={<1,3>,<2,2>,<3,1>}f4={<1,1>,<2,3>,<3,2>}f5={<1,2>,<2,3>,<3,1>}f6={<1,3>,<2,1>,<3,2>}令G={f1,f2,f3,f4,f5,f6},則G關(guān)于復(fù)合(本題為右復(fù)合)運(yùn)算構(gòu)成了群,G的子群H={f1,f2},求H的全部右陪集.Hf1={f1?f1,

f2?f1}={f1,f2}=HHf2={f1?f2,

f2?f2}={f1,f2}=HHf3={f1?f3,

f2?f3}={f3,f5}Hf4={f1?f4,

f2?f4}={f4,f6}Hf5={f1?f5,

f2?f5}={f5,f3}Hf6={f1?f6,

f2?f6}={f6,f4}6.1.4陪集與拉格朗日定理陪集的性質(zhì)定理6.3(定理10.7-10.9):設(shè)H是G的子群,則He=HaG有aHaa,bG,aHbab-1HHa=Hb在G上定義關(guān)系R:a,bG,<a,b>Rab-1H,則R是G上的等價關(guān)系,且[a]R=Ha.aG,H≈Ha(≈指勢相等)注意:左陪集的性質(zhì)與此類似.6.1.4陪集與拉格朗日定理Lagrange定理對G的子群H來說,H的左陪集和右陪集一般是不相等的,但左右陪集的個數(shù)是相等的.因此將左右陪集數(shù)統(tǒng)稱為H在G中的陪集數(shù),也叫做H在G中的指數(shù),記為[G:H].定理6.4(定理10.10):設(shè)G是有限群,H是G的子群,則|G|=|H|[G:H].推論1

設(shè)G是n階群,則aG,|a|是n的因子,且an=e.推論2

對階為素數(shù)的群G,必存在aG使得G=<a>.6.1.5正規(guī)子群和商群正規(guī)子群定義6.5

設(shè)H是G的子群,如果aG都有Ha=aH,則稱H是G的正規(guī)子群,記作HG.定義6.6

設(shè)G是群,N是G的正規(guī)子群,令G/N是N在G中的全體左陪集(或右陪集)構(gòu)成的集合,即G/N={Ng|gG}

在G/N上定義二元運(yùn)算?如下:

Na,NbG/N,Na?Nb=NabG/N關(guān)于?構(gòu)成了群,稱為G的商群.6.1.6循環(huán)群和置換群循環(huán)群定義6.7

在群G中,如果存在aG使得

G={ak|kZ}則稱G為循環(huán)群,記作G=<a>,稱a為G的生成元.☆

循環(huán)群必定是阿貝爾群,但阿貝爾群不一定是循環(huán)群.證明:

設(shè)<G,*>是一個循環(huán)群,它的生成元是a,那么,對于任意x,yG,必有r,sZ,使得

x=as,y=at,而且x*y=as*at=as+t=at*as=y*x由此可見<G,*>是一個阿貝爾群.例如,<Z,+>是一個循環(huán)群,其生成元是1或-1.2021/5/9246.1.6循環(huán)群和置換群循環(huán)群在循環(huán)群G=<a>中,生成元a的階與群G的階是一樣的.如果a是有限階元,|a|＝n,則稱G為n階循環(huán)群.如果a是無限階元,則稱G為無限階循環(huán)群.例如:<Z,+>是無限階循環(huán)群;<Z6,>是n階循環(huán)群.注意:(1)對無限階循環(huán)群G=<a>,G的生成元是a和a-1;(2)

對n階循環(huán)群G=<a>=<e,a,…,an-1>,G的生成元是at當(dāng)且僅當(dāng)t與n互素,如12階循環(huán)群中,與12互素的數(shù)有1、5、7、11.那么G的生成元有a1=a、a5、a7、a11.(3)N階循環(huán)群G=<a>,對于n的每個正因子d,G恰好有一個d階子群H=<an/d>.6.1.6循環(huán)群和置換群n元置換定義6.7

設(shè)S＝{1,2,,n},S上的任何雙射函數(shù):S→S構(gòu)成了S上n個元素的置換,稱為n元置換.例如,S={1,2,3},令:S→S,且有:

(1)=2,(2)=3,(3)=1則將1,2,3分別置換成2,3,1,此置換常被記為=采用這種記法,一般的n元置換可記為n元置換n個不同元素有n!種排列的方法,所以,S上有n!個置換.例如,<1,2,3>上有3!=6種不同的置換,即

6.1.6循環(huán)群和置換群2021/5/927n元置換對于n元置換也可以用不交的輪換之積來表示.=(a1a2…am),mn那么的映射關(guān)系是a1a2,a2a3,…am-1am,ama1,而其他的元素都有aa.稱為m次輪換.這樣,任何n元置換都可表成不交的輪換之積.6.1.6循環(huán)群和置換群2021/5/928n元置換例如,是{1,2,…6}上的置換,且=那么的映射關(guān)系是16,25,33,44,52,61.去掉3和4這兩個保持不變的元素,可得

16,61,25,52

所以=(16)(25)(3)(4)6.1.6循環(huán)群和置換群2021/5/929n元置換又如,也是{1,2,…6}上的置換,且=則有=(14325)(6)為使表達(dá)式簡潔,可以去掉1次輪換，則有=(16)(25)=(14325)6.1.6循環(huán)群和置換群2021/5/930n元置換用輪換法表示{1,2,3}上的置換可記為：1=(1),2=(12),3=(13),4=(23),5=(123),6=(132)輪換可以進(jìn)一步表示成對換之積,如6=(13)(12)奇置換:

能表示成奇數(shù)個對換之積的置換;偶置換:

能表示成偶數(shù)個對換之積的置換.6.1.6循環(huán)群和置換群2021/5/931n元對稱群、n元置換群設(shè)S={1,2,…n},S上的n!個置換構(gòu)成集合Sn,其中恒等置換Is=(1)∈Sn.在Sn上規(guī)定二元運(yùn)算,對于任意n元置換,∈Sn,表示與的復(fù)合(乘法).顯然也是S上的n元置換,

所以,Sn對運(yùn)算是封閉的,且是可結(jié)合的.任取Sn中的置換,有

Is=Is=

所以,恒等置換Is=(1)是Sn中的幺元.6.1.6循環(huán)群和置換群2021/5/932n元對稱群、n元置換群與的逆置換的復(fù)合為Is,因此:

-1=就是的逆元.即:Sn關(guān)于置換的復(fù)合構(gòu)成一個群,稱之為S上的n元對稱群.Sn的任何子群稱為S上的n元置換群.6.1.6循環(huán)群和置換群n元對稱群、n元置換群例如S3={(1),(12),(13),(23),(123),(132)},S3的運(yùn)算表如表6.1所示.(注意它與例6.6中G的聯(lián)系)6.1.6循環(huán)群和置換群2021/5/934從上表6.1可以看到:(13)?(12)≠(12)?(13)所以,S3不是阿貝爾群,在S3中,(12),(13)和(23)都是2階元,而(123)和(132)是3階元.S3有6個子群,即

<(1)>={(1)},<(12)>={(1),(12)},<(13)>={(1),(13)},<(23)>={(1),(23)},<(123)>=<(132)>={(1),(123),(132)},其中{(1)}和S3是平凡的,除S3自己以外,都是S3的真子群.設(shè)An是Sn上所有偶置換組成的集合,An是Sn子群,叫做n元交錯群.6.1.6循環(huán)群和置換群2021/5/9356.2環(huán)與域6.2.1環(huán)定義6.8設(shè)<R,+,·>是代數(shù)系統(tǒng),R為集合,+和·為二元運(yùn)算,如果(1)<R,+>為阿貝爾群,(2)<R,·>為半群,(3)乘法·對加法+適合分配律,則稱<R,+,·>是環(huán).例如:<Z,+,·>,<Q,+,·>,<R,+,·>,<C,+,·>都是環(huán),+和·表示普通加法和乘法,分別叫整數(shù)環(huán)Z、有理數(shù)環(huán)Q、實(shí)數(shù)環(huán)R和復(fù)數(shù)環(huán)C.<Mn(R),+,·>是環(huán),,+,·分別是矩陣加法和乘法.注:環(huán)中關(guān)于加法的逆元稱為負(fù)元,記為-x;關(guān)于乘法的逆元稱為逆元,記為x-12021/5/9366.2環(huán)與域6.2.2交換環(huán)和含幺環(huán)在環(huán)<R,+,·>中,如果乘法·適合交換律,則稱R是交換環(huán).

如果對于乘法有幺元,則稱R是含幺環(huán).

為了區(qū)別含幺環(huán)中加法幺元和乘法幺元,通常把加法幺元記作0,乘法幺元記作1.可以證明加法幺元0恰好是乘法的零元.例如:<Z,+,·>,<Q,+,·>,<R,+,·>,<Mn(R),+,·>都是交換環(huán)嗎?它們是含幺環(huán)嗎?2021/5/9376.2環(huán)與域6.2.3左零因子、右零因子、無零因子環(huán)在環(huán)<R,+,·>中,如果存在a,b∈R,a≠0,b≠0,但ab＝0,則稱a為R中的左零因子,b為R中的右零因子.如果環(huán)R中既不含左零因子,也不含右零因子,即a,b∈R,ab＝0a＝0∨b＝0

則稱R為無零因子環(huán).2021/5/9386.2環(huán)與域6.2.3整環(huán)和域整環(huán):若環(huán)<R,+,·>是交換、含幺和無零因子的,稱R為整環(huán).域:設(shè)環(huán)<R,+,·>整環(huán),且R至少含有2個元素,若

aR(a≠0)有a-1R,則稱R是域.例如:

有理數(shù)集Q、實(shí)數(shù)集R和復(fù)數(shù)集C關(guān)于普通的加法和乘法都構(gòu)成了域,整數(shù)集Z只能構(gòu)成整數(shù)環(huán),而不是域,因?yàn)椴⒉皇侨我夥橇阏麛?shù)的倒數(shù)都屬于Z.2021/5/939例6.6

設(shè)S為下列集合,+和.為普通加法和乘法.(1)S＝{x｜x＝2n∧n∈Z}.(2)S＝{x｜x＝2n+1∧n∈Z}.(3)S＝{x｜x∈Z∧x≥0}＝N,問S和+,·能否構(gòu)成整環(huán)？能否構(gòu)成域？為什么？6.2環(huán)與域解:(1)不是整環(huán)也不是域,因?yàn)槌朔ㄧ墼?,1S.(2)不是整環(huán)也不是域,因?yàn)镾不是環(huán),普通加法的幺元是0,0S,(3)S不是環(huán),因?yàn)槌?以外任何正整數(shù)x的加法逆元是-x,而-xS當(dāng)然也不是整環(huán)和域.2021/5/9406.2.4環(huán)的性質(zhì)定理6.6

設(shè)<R,+,·>是環(huán),則(1)a∈R,a·0＝0·a＝0.(2)a,b∈R,(-a)b＝a(-b)＝-(ab).(3)a,b∈R,(-a)(-b)＝ab.(4)a,b,c∈R,a(b-c)=ab-ac,(b-c)a＝ba-ca.6.2環(huán)與域2021/5/9416.3格和布爾代數(shù)6.3.1格定義6.10

設(shè)<S,≤>是偏序集,如果

x,y∈S,{x,y}都有最小上界和最大下界,則稱S關(guān)于≤構(gòu)成一個格.x∨y表示x和y的最小上界

x∧y表示x和y的最大下界.例6.7

設(shè)n為正整數(shù),Sn為n的正因子的集合,D為整除關(guān)系,則<Sn,D>構(gòu)成格.x,y∈Sn,x∨y是x,y的最小公倍數(shù)[x,y],x∧y是x,y的最大公約數(shù)(x,y)2021/5/9426.3格和布爾代數(shù)格<S8,D>,<S6,D>和<S30,D>x∨y是x,y的最小公倍數(shù)[x,y],x∧y是x,y的最大公約數(shù)(x,y)155例6.8

判斷圖中偏序集是否構(gòu)成格,說明為什么.6.3格和布爾代數(shù)2021/5/9446.3格和布爾代數(shù)6.3.2對偶原理對偶命題:設(shè)f是含有格中的元素以及符號=,≤,≥,∨,∧的命題,令f*是將f中的≤改寫成≥,將≥改寫成≤,∨改寫成∧,∧改寫成∨所得到的命題,稱為f的對偶命題.根據(jù)格的對偶原理,若f對一切格為真,則f*也對一切格為真.例如,若在格中有

(a∨b)∧c≤c

成立,

則有(a∧b)∨c≥c

成立.2021/5/945定理6.7

設(shè)<L,≤>為格,則運(yùn)算∨和∧適合交換律、結(jié)合律、冪等律和吸收律,即(1)a,b∈L,有a∨b＝b∨a,a∧b＝b∧a(2)a,b,c∈L,有(a∨b)∨c＝a∨(b∨c),(a∧b)∧c＝a∧(b∧c).(3)a∈L,有a∨a＝a,a∧a＝a.(4)a,b∈L,有a∨(a∧b)＝a,a∧(a∨b)＝a.6.3格和布爾代數(shù)2021/5/9466.3格和布爾代數(shù)格的另一個等價的定義設(shè)<S,*,>是具有兩個二元運(yùn)算的代數(shù)系統(tǒng),且對于*和運(yùn)算適合交換律、結(jié)合律、吸收律,則可以適當(dāng)定義S中的偏序≤使得<S,≤>構(gòu)成一個格,且

a,b∈Sa∧b=a*b,a∨b=ab.2021/5/9476.3格和布爾代數(shù)6.3.3分配格定義6.11

設(shè)<L,∧,∨>是格,若a,b,c∈L有

a∧(b∨c)＝(a∧b)∨(a∧c)a∨(b∧c)＝(a∨b)∧(a∨c)

成立,則稱L為分配格.2021/5/948圖中(1)、(2)、(3)、(4)是分配格嗎？(3)a∧(b∨c)＝a∧e＝a(a∧b)∨(a∧c)＝d∨d＝d(4)b∧(a∨c)＝b∧e＝b(b∧a)∨(b∧c)＝d∨c=c.2021/5/9496.3格和布爾代數(shù)