几个典型的代数系统离散数学

几个典型的代数系统离散数学3/14/20231第一页，共六十一页，2022年，8月28日§1半群与群DEFINITION1.

设V=<S,◦>是代数系统，◦为二元运算，如果◦是可结合的，则称V为半群。如：

(1)<Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>都是半群，其中+表示普通加法。(2)<Mn(R),·>是半群，其中·表示矩阵乘法。3/14/20232第二页，共六十一页，2022年，8月28日可交换半群：半群V中的二元运算可交换。含幺半群（独异点）：半群V中的二元运算含有幺元。子半群：半群的子代数。子独异点：独异点的子代数。积半群：若V1,V2是半群，则V1V2是积半群。积独异点：若V1,V2是独异点，则V1V2是积独异点。3/14/20233第三页，共六十一页，2022年，8月28日(1)<Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>都是可交换半群。(2)<Mn(R),·>不是可交换半群，因为矩阵乘法不适合交换律。(1)中除了<Z+,+>外都是独异点，其中普通加法的幺元是0。(2)<Mn(R),·>是独异点，矩阵乘法的幺元是n阶单位矩阵E。<Z+,+>,<N,+>都是<Z,+>的子半群，且<N,+>也是<Z,+>的子独异点，但<Z+,+>不是<Z,+>的子独异点，因为幺元0Z，但0Z+。3/14/20234第四页，共六十一页，2022年，8月28日DEFINITION2.设V1=<S1,◦>,V2=<S2,*>为半群，:S1→S2，且x,yS1，有：(x◦y)=(x)*(y)，则称为半群V1到V2的同态。设V1=<S1,◦,e1>,V2=<S2,*,e2>为独异点，:S1→S2，且x,yS1，有：(x◦y)=(x)*(y)，(e1)=e2，则称为独异点V1到V2的同态。3/14/20235第五页，共六十一页，2022年，8月28日EXAMPLE1设半群V1=<S,·>，独异点V2=<S,·,>，其中，·为矩阵乘法。令：

，则TS，且T对矩阵乘法·是封闭的。∴<T,·>是V1=<S,·>的子半群。3/14/20236第六页，共六十一页，2022年，8月28日在<T,·>中存在自己的幺元，因为∴<T,·,>也构成一个独异点，但它不是V2=<S,·,>的子独异点。∵V2中的幺元3/14/20237第七页，共六十一页，2022年，8月28日令有：∴是半群V1的自同态，但不是满自同态，且同态象为3/14/20238第八页，共六十一页，2022年，8月28日对于独异点V2=<S,·,>，还是同一个映射，根据前面的证明，对x,yS都有：(x·y)=(x)·(y)，但是而不是独异点V2的幺元，∴不是独异点V2的自同态。3/14/20239第九页，共六十一页，2022年，8月28日DEFINITION3.设<G,◦>是代数系统，◦为二元运算。如果◦是可结合的，存在幺元eG，并且对G中的任意元素x都有x-1G，则称G为群。如，(1)<Z,+>,<Q,+>,<R,+>都是群，而<Z+,+>,<N,+>不是群，因为<Z+,+>中的元素都没有逆元，而在<N,+>中只有0有逆元0。(2)<Mn(R),·>不是群，因为不是所有的实矩阵都有逆矩阵。3/14/202310第十页，共六十一页，2022年，8月28日EXAMPLE2设G={a,b,c,e}，·为G上的二元运算，由下表给出，不难证明G是一个群。·eabceabceabcaecbbceacbae该运算的特点：e为G中的幺元；·是可交换的；G中的任何元素的逆元就是它自己；在a,b,c三个元素中，任何两个元素运算的结果都等于另一个元素。称这个群为Klein四元群。3/14/202311第十一页，共六十一页，2022年，8月28日一些特殊的群：交换群：群G中的二元运算可交换。也叫阿贝尔(Abel)群。无限群：群G中有无限多个元素。有限群：群G中有有限个元素。有限群G中的元素个数叫做G的阶，记作|G|。3/14/202312第十二页，共六十一页，2022年，8月28日如，(1)<Z,+>,<Q,+>,<R,+>都是阿贝尔群，Klein四元群也是阿贝尔群。(2)<Z,+>,<R,+>都是无限群，<Zn,>是有限群，其阶是n，Klein四元群也是有限群，其阶是4。3/14/202313第十三页，共六十一页，2022年，8月28日定理1：设G为群，则G中的幂运算满足(1)对xG，(x-1)-1=x.(2)对x,yG，(xy)-1=y-1x-1.(3)对xG，xnxm=xn+m.(4)对xG，(xn)m=xnm.m,n是整数。3/14/202314第十四页，共六十一页，2022年，8月28日定理2：设G为群，对a,bG，方程ax=b和ya=b在G中有解，且有唯一解。易证方程ax=b的唯一解是x=a-1b，而方程ya=b的唯一解是y=ba-1。3/14/202315第十五页，共六十一页，2022年，8月28日如，S={1,2,3}，在群<P(S),>中有方程{1,2}x={1,3}，由定理2有x=a-1b={1,2}-1

{1,3}={1,2}{1,3}={2,3}。即为原方程的解。⊕

Ø{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}Ø{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}

Ø{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}{1}Ø{1,2}{1,3}{2}{3}{1,2,3}{2,3}{2}{1,2}Ø{2,3}{1}{1,2,3}{3}{1,3}{3}{1,3}{2,3}Ø{1,2,3}{1}{2}{1,2}{1,2}{2}{1}{1,2,3}Ø{2,3}{1,3}{3}{1,3}{3}{1,2,3}{1}{2,3}Ø{1,2}{2}{2,3}{1,2,3}{3}{2}{1,3}{1,2}Ø{1}{1,2,3}{2,3}{1,3}{1,2}{3}{2}{1}Ø同理可知，方程y{1}={2,3}的解是y={1,2,3}。abab3/14/202316第十六页，共六十一页，2022年，8月28日定理3：设G为群，则G中适合消去律，即对a,b,cG，有：(1)若ab=ac，则b=c.(2)若ba=ca，则b=c.3/14/202317第十七页，共六十一页，2022年，8月28日定理4：设G为有限群，则G的运算表中的每一行（每一列）都是G中元素的一个置换，且不同的行（或列）的置换都不相同。

这就是说，在G的运算表的每一行里。G的每个元素都出现且仅出现一次，行不同，元素的排列顺序也不同。使用这个定理可以通过运算表很快地判断出哪些代数系统G=<S,◦>不是群。3/14/202318第十八页，共六十一页，2022年，8月28日DEFINITION4.设群<G,*>，H是G的非空子集。如果H关于G中的运算*构成群，则称H为G的子群，记作H≤G。如，在群<Z,+>中，取2Z={2z|zZ}，则2Z关于加法运算构成<Z,+>的子群。同样，{0}也是<Z,+>的子群。3/14/202319第十九页，共六十一页，2022年，8月28日定理5：设G为群，H是G的非空子集，如果对x,yH，都有xy-1H，则H是G的子群。子群判定定理如，对xG，G为群，令H={xk|kZ}，即x的所有次幂的集合。则H是G的子群。∵xm,xlH，有：xm(xl)-1=xmx-l=xm-lH。称这个子群是由元素x生成的子群，记作<x>。3/14/202320第二十页，共六十一页，2022年，8月28日EXAMPLE3群<Z6,>（其中表示模6加法）中由2生成的子群包含2的各次幂，21=2，22=22=4，23=222=0…∴<2>={0,2,4}。同理有：<0>={0}，<1>=<5>={0,1,2,3,4,5}，<3>={0,3}，<4>=<2>={0,2,4}。3/14/202321第二十一页，共六十一页，2022年，8月28日又如，设G为群，令C是与G中所有的元素都可交换的元素构成的集合，即C={a|aG∧xG(ax=xa)}，则C是G的子群。∵a,bC，要证明ab-1C，只要证明ab-1与G中所有的元素都可交换就行了。xG，有：(ab-1)x

=ab-1x

=ab-1((x-1)-1)=a(x-1b)-1=a(bx-1)-1

=a(xb-1)=(ax)b-1=(xa)b-1=x(ab-1)

。∴C是G的子群。称C为群G的中心3/14/202322第二十二页，共六十一页，2022年，8月28日DEFINITION5.在群G中如果存在aG使得G={ak|kZ}，则称G为循环群，记作G=<a>，称a为G的生成元。如，<Z,+>是循环群，其生成元是1或-1，因为任何整数都可以由若干个1或若干个-1相加而得到。

<Z6,>也是循环群，其生成元是1或5，因为0,1,…,5中的每个数都可以由1或5作若干次模6加法而得到。循环群都是阿贝尔群，但阿贝尔群不一定都是循环群。3/14/202323第二十三页，共六十一页，2022年，8月28日循环群生成元的判定方法：对无限阶循环群G=<a>，G的生成元是a和a-1。对n阶循环群G=<a>={e,a,a2,…,an-1}，G的生成元是at当且仅当t与n是互质的。

<Z,+>是无限阶循环群，生成元是1和-1，-1是1的加法逆元。

<Z6,>是6阶循环群，1和5都与6互质，所以1和5是生成元。

12阶循环群G={e,a,…,a11}中，与12互质的数有1,5,7,11，则G的生成元就是a,a5,a7,a11。3/14/202324第二十四页，共六十一页，2022年，8月28日循环群G=<a>的子群仍是循环群。若G是无限阶循环群，则G的子群除了{e}外都是无限阶；N阶循环群G=<a>的子群的阶都是n的正因子。对于n的每个正因子d，G中只有一个d阶子群，就是由an/d生成的子群。3/14/202325第二十五页，共六十一页，2022年，8月28日DEFINITION6.设S={1,2,…,n}，S上的任何双射函数:SS构成了S上n个元素的置换，称为n元置换。如，S={1,2,3}，令:SS，且有(1)=2,(2)=3,(3)=1,则将1,2,3分别置换成2,3,1。此置换常被记为：3/14/202326第二十六页，共六十一页，2022年，8月28日一般的n元置换可记为：n个不同元素有n!种排列方法。所以S上有n!个置换。如，{1,2,3}上有3!=6种不同的置换，即3/14/202327第二十七页，共六十一页，2022年，8月28日简记法：设n元置换=(a1a2…am),m≤n，则的映射关系是：(a1)=a2,(a2)=a3,…,(am-1)=am,(am)=a1，而其它的元素a都有(a)=a，称为m次轮换。任何n元置换都可表成不交的轮换之积。如，是{1,2,…,6}上的置换，且除了3和4这两个保持不变的元素外，其它元素的映射关系为：(1)=6,(6)=1,(2)=5,(5)=2。∴=(16)(25)3/14/202328第二十八页，共六十一页，2022年，8月28日又如，也是{1,2,…,6}上的置换，且则有=(14325)。根据这种表法，{1,2,3}上的置换可记为：1=(1),2=(12),3=(13),4=(23),5=(123),6=(132)3/14/202329第二十九页，共六十一页，2022年，8月28日设S={1,2,…,n}，S上的n!个置换构成集合Sn，其中恒等置换IS=(1)Sn，在Sn上规定二元运算◦，对任意n元置换,Sn，◦表示与的复合。证明Sn关于置换的复合构成一个群。证明：(1)设,Sn，与的复合◦显然也是S上的n元置换，即◦Sn，∴Sn对◦运算是封闭的。(2),,Sn，显然(◦)◦=◦(◦)，∴Sn对◦运算是可结合的。(3),Sn，有◦IS=IS◦=，则恒等置换IS

是Sn中的幺元，且的逆置换就是的逆元。∴Sn关于置换的复合◦构成一个群。S上的n元对称群3/14/202330第三十页，共六十一页，2022年，8月28日

n元对称群的任何子代数称为n元置换群。如：S3={(1),(12),(13),(23),(123),(132)}就是3元对称群。因为S3关于置换的复合运算◦不能交换，所以S3不是阿贝尔群。

S3有6个子群，即有6个3元置换群。见P135。3/14/202331第三十一页，共六十一页，2022年，8月28日§2环与域DEFINITION7.设<R,+,·>是代数系统，R为集合，+,·为二元运算，如果(1)<R,+>为阿贝尔群；(2)<R,·>为半群；(3)乘法·对加法+适合分配律。则称<R,+,·>是环。+可结合、可交换，存在幺元，且任何元素都有逆元。·可结合3/14/202332第三十二页，共六十一页，2022年，8月28日如：(1)<Z,+,·>,<Q,+,·>,<R,+,·>都是环。(2)<Mn(R),+,·>是环。(3)<Zn,,⊙>是模n的整数环。其中Zn={0,1,…,n-1}，和⊙分别表示模n的加法和乘法，即x,yZn，有：xy=(x+y)modnx⊙y=(xy)modn3/14/202333第三十三页，共六十一页，2022年，8月28日交换环：在环<R,+,·>中，·适合交换律。含幺环：在环<R,+,·>中，·有幺元。此时，通常把+幺元记作0，·幺元记作1。可以证明+的幺元恰好是·的零元。左（右）零因子：在环<R,+,·>中，若a,bR,a0,b0，但ab=0，则a为R中的左零因子。b为R中的右零因子。无零因子环：环R中既不含左零因子，也不含右零因子，即a,bR,ab=0a=0b=0.0为·的零元3/14/202334第三十四页，共六十一页，2022年，8月28日如：(1)<Z,+,·>,<Q,+,·>,<R,+,·>,<Zn,,⊙>都是交换环。<Mn(R),+,·>不是交换环，因为矩阵乘法运算不可交换。(2)它们都是含幺环。因为1是·的幺元，也是⊙的幺元。n阶单位矩阵E是环Mn(R)的乘法幺元。(3)<Z,+,·>,<Q,+,·>,<R,+,·>都是无零因子环。而<Zn,,⊙>不一定是无零因子环。如<Z6,,⊙>中有2⊙3=0，但2和3都不是0，所以<Z6,,⊙>不是无零因子环，而<Z5,,⊙>是无零因子环。3/14/202335第三十五页，共六十一页，2022年，8月28日DEFINITION8.若环<R,+,·>是交换、含幺、和无零因子的，则称R为整环。若环<R,+,·>至少含有2个元素且是含幺和无零因子的，并且aR(a0)有a-1R，则称R为除环。若环<R,+,·>既是整环，又是除环，则称R是域。（至少含有2个元素、交换、含幺、无零因子、除0外都有逆元）3/14/202336第三十六页，共六十一页，2022年，8月28日如：(1)<Z,+,·>是整环但不是域。因为乘法可交换，1是幺元，且不含零因子，所以是整环。但除了1之外，任何整数都没有乘法的逆元，所以不是域。(2)<R,+,·>是域，即实数域。因为xR，x0，有：x-1=1/xR.3/14/202337第三十七页，共六十一页，2022年，8月28日EXAMPLE4设S为下列集合，+和·为普通加法和乘法。(1)S={x|x=2n∧nZ}.(2)S={x|x=2n+1∧nZ}.(3)S={x|xZ∧x≥0}=N.(4)问S和+,·能否构成整环？能否构成域？为什么？3/14/202338第三十八页，共六十一页，2022年，8月28日解：(1)不是整环，也不是域。因为乘法幺元是1，而1S.(2)不是整环，也不是域。因为<S,+>不是群，S当然就不是环，+的幺元是0，而0S.(3)<S,+>不是群，因为除0以外任何正整数x的加法逆元是-x，而-xS.S当然就不是环，更不是整环和域。3/14/202339第三十九页，共六十一页，2022年，8月28日(4)S是域。∵x1,x2S，有：∴S对+和·是封闭的。又∵乘法幺元1S，易证<S,+,·>是整环。∴<S,+,·>是域。3/14/202340第四十页，共六十一页，2022年，8月28日定理6：设<R,+,·>是环，则：(1)aR，a·0=0·a=0.(2)a,bR，(-a)b=a(-b)=-(ab).(3)a,bR，(-a)(-b)=ab.(4)a,b,cR，a(b-c)=ab-ac.(b-c)a=ba-ca.在环中做加法和乘法只能遵从加法的交换律和结合律、乘法的结合律、乘法对加法的分配律，以及此定理中所给出的算律。3/14/202341第四十一页，共六十一页，2022年，8月28日EXAMPLE5设<R,+,·>是环，a,bR，计算(a-b)2和(a+b)3.解：(a-b)2=(a-b)(a-b)=a2-ba-ab-b(-b)=a2-ba-ab+b2.(a+b)3=(a+b)(a+b)(a+b)=(a2+ba+ab+b2)(a+b)=a3+ba2+aba+b2a+a2b+bab+ab2+b3.幂运算分配律及定理6(2)定理6(3)及幂运算幂运算分配律及幂运算分配律及幂运算注：乘法没有交换律注：乘法没有交换律3/14/202342第四十二页，共六十一页，2022年，8月28日§3格与布尔代数格有两种等价的定义：一种是从偏序集的角度给出格的定义，这种定义可以借助哈斯(Hasse)图来表示，因而比较直观、易于理解，这样定义的格称为偏序格；另一种是从代数系统的角度来给出格的定义，这种定义方法我们在上几节的群、环的定义中已有所体会，用代数系统的方法定义的格称为代数格。3/14/202343第四十三页，共六十一页，2022年，8月28日布尔代数是计算机科学最重要的基础理论之一，它在开关网络及数字电路的设计上有广泛深入的应用。布尔代数是计算机科学工作者必备的基础知识，应掌握格与布尔代数的一般理论和方法。3/14/202344第四十四页，共六十一页，2022年，8月28日DEFINITION7.设<S,≤>是偏序集，如果x,yS，{x,y}都有最小上界和最大下界，则称S关于≤构成一个格。可将求{x,y}的最小上界和最大下界看成x与y的二元运算∨和∧，即x∨y和x∧y。偏序格3/14/202345第四十五页，共六十一页，2022年，8月28日EXAMPLE6设n为正整数，Sn为n的正因子的集合，D为整除关系，则<Sn,D>构成格。x,ySn，x∨y是x与y的最小公倍数，x∧y是x与y的最大公约数。<S8,D><S6,D><S30,D>8421123612356101530如：3/14/202346第四十六页，共六十一页，2022年，8月28日EXAMPLE7判断下图中偏序集是否构成格，为什么？abcdefabdeceabdfc解：都不是格。(1)中的{a,b}没有下界。(2)中的{b,d}有上界c和e，但没有最小上界。(3)中的{b,c}有上界d,e,f，但没有最小上界。(1)(2)(3)3/14/202347第四十七页，共六十一页，2022年，8月28日格的对偶原理：设f是含有格中的元素以及符号=,≤,≥,∨,∧的命题，令f*是将f中的≤改写成≥，≥改写成≤，∨改写成∧，∧改写成∨所得到的命题，称为f的对偶命题。若f对一切格为真，则f*也对一切格为真。3/14/202348第四十八页，共六十一页，2022年，8月28日定理7：设<L,≤>为格，则运算∨和∧适合交换律、结合律、幂等律和吸收律，即：(1)a,bL，有a∨b=b∨a,a∧b=b∧a.(2)a,b,cL，有(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c).(3)aL，有a∨a=a,a∧a=a.(4)a,bL，有a∨(a∧b)=a,a∧(a∨b)=a.3/14/202349第四十九页，共六十一页，2022年，8月28日证明：(1)a∨b和b∨a分别是{a,b}和{b,a}的最小上界，由于{a,b}={b,a}，所以a∨b=b∨a。同理可证a∧b=b∧a.(2)由最小上界的定义有：

a≤a∨(b∨c),①b≤b∨c≤a∨(b∨c),②c≤b∨c≤a∨(b∨c).③由式①和②有：a∨b≤a∨(b∨c).④再由式③和④有：(a∨b)∨c≤a∨(b∨c).同理可证：(a∨b)∨c≥a∨(b∨c).根据偏序关系的反对称性有：(a∨b)∨c=a∨(b∨c).类似地可以证明：(a∧b)∧c=a∧(b∧c).3/14/202350第五十页，共六十一页，2022年，8月28日(3)显然a≤a∨a，又由a≤a可得a∨a≤a。根据偏序关系的反对称性有：a∨a=a.同理可证：a∧a=a.(4)显然a∨(a∧b)≥a。⑤又由a≤a,a∧b≤a，可得：

a∨(a∧b)≤a.⑥由式⑤和⑥可得：a∨(a∧b)=a.同理可证：a∧(a∨b)=a.3/14/202351第五十一页，共六十一页，2022年，8月28日DEFINITION8.设<S,*,◦>是具有两个二元运算的代数系统，且对于*和◦适合交换律、结合律、吸收律，则可以适当定义S中的偏序≤，使得<S,≤>构成一个格，且a,bS，有a∧b=a*b,a∨b=a◦b.代数格只要吸收律成立，则幂等律就一定成立。证：aS，有a◦a=a◦(a*(a◦a))=a.

同理可证a*a=a.3/14/202352第五十二页，共六十一页，2022年，8月28日DEFINITION9.设<L,∧,∨>是格，若a,b,cL，有a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)成立，则称L为分配格。3/14/202353第五十三页，共六十一页，2022年，8月28日DEFINITION10.在格<L,∧,∨>中存在一个元素a，bL,a≤b(或b≤a)，则称a为格L的全下界（或全上界），记为0（或1）。具有全上界和全下界的格称为有界格。记作<L,∧,∨,0,1>.3/14/202354第五十四页，共六十一页，2022年，8月28日DEFINITION11.设<L,∧,∨,0,1>是有界格，aL，若存在bL，使得a∧b=0,a∨b=1，则称b为a的补元。若格中每个元素都至少有一个补元，则称这个格为有补格。对分配格L来说，若aL有补元，则一定是唯一的补元。3/14/202355第五十五页，共六十一页，2022年，8月28日EXAMPLE8判断下图中的格是不是分配格、有补格？abceabdfcghaedbc••abc•••01cab