离散数学第六章

章几个典型的代数系统

6.1半群与群6.1.1半群与独异点6.1.2群的定义与性质6.1.3子群6.1.4陪集与拉格朗日定理6.1.5正规子群与商群6.1.6循环群和置换群6.2环与域6.2.1环的定义与性质6.2.2整环与域6.3格与布尔代数2021/5/916.1半群与群半群、可交换半群和独异点定义6.1①设V=<S,˚>是代数系统,˚为二元运算,如果˚是可结合的,则称V为半群．②

如果半群V=<S,˚>中的二元运算含有幺元,则称V为含幺半群,也可叫做独异点.定义6.2

如果半群V=<S,˚>中的二元运算˚是可交换的,则称V为可交换半群.注:为了强调幺元的存在,有时将独异点记为<S,˚,e>6.1.1半群与独异点2021/5/92例6.1①<Z+,+>是半群②

<N,+>,<Z,+>,<Q,+>,<R,+>都是半群和独异点，其中+表示普通加法,幺元是0,<N,+,0>,…,<R,+,0>③<Mn(R),·>是半群和独异点,其中·表示矩阵乘法,矩阵乘法的幺元是n阶单位矩阵E.记作<Mn(R),·,E>④

<P(B),>是半群和独异点,其中表示集合的对称差运算,其幺元是,记作<P(B),,>⑤<Zn,>是半群和独异点,其中Zn={0,1,…,n-1},表示模n加法,模n加法的幺元是0.<Zn,,0>其中:①②④⑤为可交换半群.6.1.1半群与独异点2021/5/936.1.1半群与独异点例6.2判断下述论断正确与否,在相应的括号中键入“Y”或“N”.(1)在实数集R上定义二元运算*为：对于任意的a,b∈R,a*b=a+b+ab(a)<R,*>是一个代数系统；()(b)<R,*>是一个半群；()(c)<R,*>是一个独异点。()(2)在实数集R上定义二元运算◦为,对任意a,b∈R,

a◦b=|a|·b(其中·表示数学的乘法运算)(a)<R,◦>是一个代数系统；()(b)<R,◦>是一个半群；()(c)<R,◦>是一个独异点。()NYYYYY2021/5/94子半群和子独异点定义:半群的子代数叫做子半群,即:如果V=<S,˚>是半群,<T,˚>就是V的子半群,需要满足如下两个条件:①T是S的非空子集;②T对V中的运算˚是封闭的.定义:独异点的子代数叫做子独异点,对独异点V=<S,˚,e>,<T,˚,e>构成V的子独异点,需要满足如下条件:①T是S的非空子集;②T要对V中的运算˚封闭;③

e∈T.6.1.1半群与独异点2021/5/95群的定义定义6.3设<G,◦>是代数系统,◦为二元运算.如果◦是可结合的,存在幺元e∈G,并且G中的任意元素x,都有x-1∈G,则称G是群.例6.3①<Z,+>,<Q,+>,<R,+>都是群;②<P(B),,>是群,其中表示集合的对称差运算,任意元素的逆元是其自身;③<Zn,,0>是群,其中Zn={0,1,…,n-1},表示模n加法,0的逆元是0,非0元素的逆元是n-x.6.1.2群的定义与性质2021/5/966.1.2群的定义与性质e为G中的幺元,◦是可交换的.任何G中的元素与自己运算的结果都等于e.在a,b,c三个元素中,任何两个元素运算的结果都等于另一个元素.一般称这个群为Klein四元群.例6.4设G＝{e,a,b,c},◦为G上的二元运算,它由以下运算表给出,不难证明G是一个群.2021/5/976.1.2群的定义与性质群的术语(1)若群G中的二元运算是可交换的,则称群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群的定义与性质群的术语(3)群的阶:对于有限群G,G中的元素个数也叫做G的阶,记作|G|.例如:<Zn,>是有限群,其阶是n;Klein四元群也是有限群,其阶是4.(4)xn定义:x0=e,xn+1=xn◦x,x-n=(x-1)n(5)元素x的阶:设G是群,x∈G,使得xk＝e成立的最小的正整数k叫做x的阶(或周期).如果不存在正整数k,使xk＝e,则称x是无限阶元.注:对有限阶的元素x,通常将它的阶记为|x|.在任何群G中幺元e的阶都是1．2021/5/996.1.2群的定义与性质群的术语例.在Klein四元群中,|a|=?,|b|=?,|c|=?,|e|=?返回6.1.2群的定义与性质群的性质定理6.1设G为群,则G中的幂运算满足(群中元素的幂)(1)x∈G,(x-1)-1＝x(2)x,y∈G,(xy)-1＝y-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的逆元。） 根据逆元的唯一性，(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的逆元。 根据逆元的唯一性等式得证。

2021/5/9126.1.2群的定义与性质群的性质定理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

设群<G,*>,H是G的非空子集.如果H关于G中的运算*构成群,则称H为G的子群,记作H≤G.若H是G的子群,且HG,则称H是G的真子群.例如:在群<Z,＋>中,取2Z＝{2x|x∈Z},

则2Z关于加法构成<Z,＋>的子群.

同样,{0}也是<Z,＋>的子群.注意:类似于子代数,任何群G都存在子群,G和{e}是G的平凡子群.2021/5/9146.1.3子群子群的判断方法判定定理1设G为群,H是G的非空子集,H是G的子群当且仅当:

(1)a,bH都有abH;(2)aH有a-1H.判定定理2设G为群,H是G的非空子集,则H是G的子群当且仅当a,bH都有ab-1H.判定定理3

设G为群,H是G的非空子集.若H是有穷集,则H是G的子群当且仅当a,bH都有abH.2021/5/9156.1.3子群子群的判断方法例6.5

设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根据判定定理二可知<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子群群的中心设G为群,令C是与G中所有的元素都可交换的元素构成的集合,即

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

设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

设A={1,2,3},f1,f2,…,f6是A上的双射函数,其中: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关于复合(本题为右复合)运算构成了群,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陪集与拉格朗日定理陪集的性质定理6.3(定理10.7-10.9):设H是G的子群,则He=HaG有aHaa,bG,aHbab-1HHa=Hb在G上定义关系R:a,bG,<a,b>Rab-1H,则R是G上的等价关系,且[a]R=Ha.aG,H≈Ha(≈指势相等)注意:左陪集的性质与此类似.6.1.4陪集与拉格朗日定理Lagrange定理对G的子群H来说,H的左陪集和右陪集一般是不相等的,但左右陪集的个数是相等的.因此将左右陪集数统称为H在G中的陪集数,也叫做H在G中的指数,记为[G:H].定理6.4(定理10.10):设G是有限群,H是G的子群,则|G|=|H|[G:H].推论1

设G是n阶群,则aG,|a|是n的因子,且an=e.推论2

对阶为素数的群G,必存在aG使得G=<a>.6.1.5正规子群和商群正规子群定义6.5

设H是G的子群,如果aG都有Ha=aH,则称H是G的正规子群,记作HG.定义6.6

设G是群,N是G的正规子群,令G/N是N在G中的全体左陪集(或右陪集)构成的集合,即G/N={Ng|gG}

在G/N上定义二元运算◦如下:

Na,NbG/N,Na◦Nb=NabG/N关于◦构成了群,称为G的商群.6.1.6循环群和置换群循环群定义6.7

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

G={ak|kZ}则称G为循环群,记作G=<a>,称a为G的生成元.☆

循环群必定是阿贝尔群,但阿贝尔群不一定是循环群.证明:

设<G,*>是一个循环群,它的生成元是a,那么,对于任意x,yG,必有r,sZ,使得

x=as,y=at,而且x*y=as*at=as+t=at*as=y*x由此可见<G,*>是一个阿贝尔群.例如,<Z,+>是一个循环群,其生成元是1或-1.2021/5/9246.1.6循环群和置换群循环群在循环群G=<a>中,生成元a的阶与群G的阶是一样的.如果a是有限阶元,|a|＝n,则称G为n阶循环群.如果a是无限阶元,则称G为无限阶循环群.例如:<Z,+>是无限阶循环群;<Z6,>是n阶循环群.注意:(1)对无限阶循环群G=<a>,G的生成元是a和a-1;(2)

对n阶循环群G=<a>=<e,a,…,an-1>,G的生成元是at当且仅当t与n互素,如12阶循环群中,与12互素的数有1、5、7、11.那么G的生成元有a1=a、a5、a7、a11.(3)N阶循环群G=<a>,对于n的每个正因子d,G恰好有一个d阶子群H=<an/d>.6.1.6循环群和置换群n元置换定义6.7

设S＝{1,2,,n},S上的任何双射函数:S→S构成了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循环群和置换群2021/5/927n元置换对于n元置换也可以用不交的轮换之积来表示.=(a1a2…am),mn那么的映射关系是a1a2,a2a3,…am-1am,ama1,而其他的元素都有aa.称为m次轮换.这样,任何n元置换都可表成不交的轮换之积.6.1.6循环群和置换群2021/5/928n元置换例如,是{1,2,…6}上的置换,且=那么的映射关系是16,25,33,44,52,61.去掉3和4这两个保持不变的元素,可得

16,61,25,52

所以=(16)(25)(3)(4)6.1.6循环群和置换群2021/5/929n元置换又如,也是{1,2,…6}上的置换,且=则有=(14325)(6)为使表达式简洁,可以去掉1次轮换，则有=(16)(25)=(14325)6.1.6循环群和置换群2021/5/930n元置换用轮换法表示{1,2,3}上的置换可记为：1=(1),2=(12),3=(13),4=(23),5=(123),6=(132)轮换可以进一步表示成对换之积,如6=(13)(12)奇置换:

能表示成奇数个对换之积的置换;偶置换:

能表示成偶数个对换之积的置换.6.1.6循环群和置换群2021/5/931n元对称群、n元置换群设S={1,2,…n},S上的n!个置换构成集合Sn,其中恒等置换Is=(1)∈Sn.在Sn上规定二元运算,对于任意n元置换,∈Sn,表示与的复合(乘法).显然也是S上的n元置换,

所以,Sn对运算是封闭的,且是可结合的.任取Sn中的置换,有

Is=Is=

所以,恒等置换Is=(1)是Sn中的幺元.6.1.6循环群和置换群2021/5/932n元对称群、n元置换群与的逆置换的复合为Is,因此:

-1=就是的逆元.即:Sn关于置换的复合构成一个群,称之为S上的n元对称群.Sn的任何子群称为S上的n元置换群.6.1.6循环群和置换群n元对称群、n元置换群例如S3={(1),(12),(13),(23),(123),(132)},S3的运算表如表6.1所示.(注意它与例6.6中G的联系)6.1.6循环群和置换群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的真子群.设An是Sn上所有偶置换组成的集合,An是Sn子群,叫做n元交错群.6.1.6循环群和置换群2021/5/9356.2环与域6.2.1环定义6.8设<R,+,·>是代数系统,R为集合,+和·为二元运算,如果(1)<R,+>为阿贝尔群,(2)<R,·>为半群,(3)乘法·对加法+适合分配律,则称<R,+,·>是环.例如:<Z,+,·>,<Q,+,·>,<R,+,·>,<C,+,·>都是环,+和·表示普通加法和乘法,分别叫整数环Z、有理数环Q、实数环R和复数环C.<Mn(R),+,·>是环,,+,·分别是矩阵加法和乘法.注:环中关于加法的逆元称为负元,记为-x;关于乘法的逆元称为逆元,记为x-12021/5/9366.2环与域6.2.2交换环和含幺环在环<R,+,·>中,如果乘法·适合交换律,则称R是交换环.

如果对于乘法有幺元,则称R是含幺环.

为了区别含幺环中加法幺元和乘法幺元,通常把加法幺元记作0,乘法幺元记作1.可以证明加法幺元0恰好是乘法的零元.例如:<Z,+,·>,<Q,+,·>,<R,+,·>,<Mn(R),+,·>都是交换环吗?它们是含幺环吗?2021/5/9376.2环与域6.2.3左零因子、右零因子、无零因子环在环<R,+,·>中,如果存在a,b∈R,a≠0,b≠0,但ab＝0,则称a为R中的左零因子,b为R中的右零因子.如果环R中既不含左零因子,也不含右零因子,即a,b∈R,ab＝0a＝0∨b＝0

则称R为无零因子环.2021/5/9386.2环与域6.2.3整环和域整环:若环<R,+,·>是交换、含幺和无零因子的,称R为整环.域:设环<R,+,·>整环,且R至少含有2个元素,若

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

有理数集Q、实数集R和复数集C关于普通的加法和乘法都构成了域,整数集Z只能构成整数环,而不是域,因为并不是任意非零整数的倒数都属于Z.2021/5/939例6.6

设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和+,·能否构成整环？能否构成域？为什么？6.2环与域解:(1)不是整环也不是域,因为乘法幺元是1,1S.(2)不是整环也不是域,因为S不是环,普通加法的幺元是0,0S,(3)S不是环,因为除0以外任何正整数x的加法逆元是-x,而-xS当然也不是整环和域.2021/5/9406.2.4环的性质定理6.6

设<R,+,·>是环,则(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环与域2021/5/9416.3格和布尔代数6.3.1格定义6.10

设<S,≤>是偏序集,如果

x,y∈S,{x,y}都有最小上界和最大下界,则称S关于≤构成一个格.x∨y表示x和y的最小上界

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

设n为正整数,Sn为n的正因子的集合,D为整除关系,则<Sn,D>构成格.x,y∈Sn,x∨y是x,y的最小公倍数[x,y],x∧y是x,y的最大公约数(x,y)2021/5/9426.3格和布尔代数格<S8,D>,<S6,D>和<S30,D>x∨y是x,y的最小公倍数[x,y],x∧y是x,y的最大公约数(x,y)155例6.8

判断图中偏序集是否构成格,说明为什么.6.3格和布尔代数2021/5/9446.3格和布尔代数6.3.2对偶原理对偶命题:设f是含有格中的元素以及符号=,≤,≥,∨,∧的命题,令f*是将f中的≤改写成≥,将≥改写成≤,∨改写成∧,∧改写成∨所得到的命题,称为f的对偶命题.根据格的对偶原理,若f对一切格为真,则f*也对一切格为真.例如,若在格中有

(a∨b)∧c≤c

成立,

则有(a∧b)∨c≥c

成立.2021/5/945定理6.7

设<L,≤>为格,则运算∨和∧适合交换律、结合律、幂等律和吸收律,即(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格和布尔代数2021/5/9466.3格和布尔代数格的另一个等价的定义设<S,*,>是具有两个二元运算的代数系统,且对于*和运算适合交换律、结合律、吸收律,则可以适当定义S中的偏序≤使得<S,≤>构成一个格,且

a,b∈Sa∧b=a*b,a∨b=ab.2021/5/9476.3格和布尔代数6.3.3分配格定义6.11

设<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格和布尔代数