离散数学群与半群

离散数学群与半群第1页，课件共25页，创作于2023年2月本章内容11.1半群与独异点11.2群的定义与性质11.3子群11.4陪集与拉格朗日定理11.5正规子群与商群11.6群的同态与同构11.7循环群与置换群本章总结例题选讲作业第2页，课件共25页，创作于2023年2月11.1半群与独异点半群与独异点都是具有一个二元运算的代数系统。半群与独异点的定义，及其子代数的说明。半群与独异点的幂运算。半群与独异点的同态映射。第3页，课件共25页，创作于2023年2月半群与独异点定义11.1

(1)设V＝<S,>是代数系统，为二元运算，如果运算是可结合的，则称V为半群（semigroup）。(2)设V＝<S,>是半群,若e∈S是关于运算的单位元,则称V是含幺半群，也叫做独异点（monoid）。有时也将独异点V记作V＝<S，，e>。第4页，课件共25页，创作于2023年2月半群与独异点的实例<Z+,+>，<N,+>，<Z,+>，<Q,+>，<R,+>都是半群,+是普通加法。这些半群中除<Z+,+>外都是独异点。设n是大于1的正整数,<Mn(R),+>和<Mn(R),·>都是半群,也都是独异点,其中+和·分别表示矩阵加法和矩阵乘法。<P(B),>为半群,也是独异点,其中为集合的对称差运算。<Zn,>为半群,也是独异点,其中Zn＝{0,1,…,n-1},为模n加法。第5页，课件共25页，创作于2023年2月半群中元素的幂由于半群V＝<S,>中的运算是可结合的,可以定义元素的幂,对任意x∈S,规定： x1＝x

xn+1＝xnx,n∈Z+

用数学归纳法不难证明x的幂遵从以下运算规则： xn

xm＝xn+m (xn)m＝xnmm,n∈Z+普通乘法的幂、关系的幂、矩阵乘法的幂等都遵从这个幂运算规则。第6页，课件共25页，创作于2023年2月独异点中的幂 独异点是特殊的半群，可以把半群的幂运算推广到独异点中去。 由于独异点V中含有单位元e，对于任意的x∈S,可以定义x的零次幂,即x0＝exn+1＝xnxn∈N第7页，课件共25页，创作于2023年2月半群与独异点的直积定义11.2

设V1＝<S1,>，V2＝<S2,*>是半群(或独异点),

令S＝S1×S2,定义S上的·运算如下： <a,b>,<c,d>∈S,

<a,b><c,d>＝<ac,b*d>

称<S,>为V1和V2的直积，记作V1×V2。可以证明V1×V2是半群。若V1和V2是独异点，其单位元分别为e1和e2，则<e1,e2>是V1×V2中的单位元，因此V1×V2也是独异点。第8页，课件共25页，创作于2023年2月半群与独异点的同态映射定义11.3

(1)设V1＝<S1,>,V2＝<S2,>是半群,:S1→S2。 若对任意的x,y∈S1有

(xy)＝(x)(y)

则称为半群V1到V2的同态映射,简称同态(homomorphism)。(2)设V1＝<S1,,e1>,V2＝<S2,,e2>是独异点,:S1→S2.

若对任意的x,y∈S1有

(xy)＝(x)(y)且(e1)＝e2,

则称为独异点V1到V2的同态映射,简称同态。第9页，课件共25页，创作于2023年2月两点说明：为了书写的简便，有时经常省略上述表达式中的算符和，而简记为

(xy)＝(x)(y)应该记住，该表达式中左边的xy是在V1中的运算，而右边的(x)(y)是在V2中的运算。第10页，课件共25页，创作于2023年2月本节的主要内容集合S和运算构成半群的条件（封闭性、结合律）。集合S和运算构成独异点的条件（封闭性、结合律、单位元）。半群与独异点的两条幂运算规则：xnxm＝xn+m，(xn)m＝xnm

。通过笛卡尔积构造直积

。同态映射的判别：(xy)＝(x)(y)

对于独异点要加上(e)＝e。第11页，课件共25页，创作于2023年2月定义11.2说明任取<a,b>,<c,d>,<u,v>S(<a,b><c,d>)<u,v>=<ac,b*d><u,v>=<(ac)u,(b*d)*v>=<acu,b*d*v>

<a,b>(<c,d><u,v>)=<a,b>(<cu,d*v>)=<a(cu),b*(d*v)>=<acu,b*d*v>第12页，课件共25页，创作于2023年2月11.2群的定义与性质群是特殊的半群和独异点。群论中常用的概念或术语： 有限群、无限群、平凡群、交换群、元素的幂和阶。群的运算规则。第13页，课件共25页，创作于2023年2月群的定义定义11.4

设<G,>是代数系统，为二元运算。如果运算是可结合的，存在单位元e∈G，并且对G中的任何元素x都有x-1∈G,则称G为群（group）。举例

(1)<Z,+>,<Q,+>,<R,+>都是群,而<Z+,+>和<N,+>不是群。(2)<Mn(R),+>是群,而<Mn(R),·>不是群。因为并非所有的n阶实矩阵都有逆阵。第14页，课件共25页，创作于2023年2月Klein四元群设G＝{a,b,c,d}，为G上的二元运算，见下表。eabceeabcaaecbbbceaccbaeG是一个群：e为G中的单位元；运算是可结合的；运算是可交换的；G中任何元素的逆元就是它自己；在a,b,c三个元素中,任何两个元素运算的结果都等于另一个元素。称这个群为Klein四元群,简称四元群。第15页，课件共25页，创作于2023年2月群的直积设<G1,>,<G2,*>是群，在G1G2上定义二元运算如下：<a,b>,<c,d>∈G1×G2,<a,b><c,d>＝<ac,b*d>称<G1×G2,>是G1与G2的直积。上一节已经证明：<G1G2,>是独异点，可以证明对任意的<a,b>∈G1G2,<a-1,b-1>是<a,b>的逆元，因此G1×G2关于运算构成一个群。第16页，课件共25页，创作于2023年2月群论中常用的概念或术语定义11.5(1)若群G是有穷集,则称G是有限群，否则称为无限群。

群G的基数称为群G的阶，有限群G的阶记作|G|。(2)只含单位元的群称为平凡群。(3)若群G中的二元运算是可交换的，则称G为交换群或阿贝尔(Abel)群。

第17页，课件共25页，创作于2023年2月例<Z,+>,<R,+>是无限群、交换群。<Zn,>是有限群，也是n阶群、交换群。Klein四元群是4阶群、交换群。<{0},+>是平凡群、交换群。第18页，课件共25页，创作于2023年2月群中元素的n次幂定义11.6

设G是群，a∈G，n∈Z，则a的n次幂与半群和独异点不同的是：群中元素可以定义负整数次幂。第19页，课件共25页，创作于2023年2月群中元素的阶定义11.7

设G是群，a∈G，使得等式

ak＝e

成立的最小正整数k称为a的阶，记作|a|＝k，这时也称a为k阶元。若不存在这样的正整数k,则称a为无限阶元。举例在<Z6,>中，2和4是3阶元，3是2阶元，而1和5是6阶元，0是1阶元。在<Z,+>中，0是1阶元，其它的整数都是无限阶元。在Klein四元群中，e为1阶元，其它元素都是2阶元。第20页，课件共25页，创作于2023年2月群的性质—群的幂运算规则

定理11.1

设G为群,则G中的幂运算满足：(1)a∈G,(a-1)-1＝a。(2)a,b∈G，(ab)-1＝b-1a-1。(3)a∈G，anam＝an+m，n,m∈Z。(4)a∈G，(an)m＝anm，n,m∈Z。(5)若G为交换群，则(ab)n＝anbn。分析：(1)和(2)可以根据定义证明。(3)、(4)、(5)中的等式,先利用数学归纳法对于自然数n和m证出相应的结果，然后讨论n或m为负数的情况。第21页，课件共25页，创作于2023年2月定理11.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的逆元。 根据逆元的唯一性等式得证。

第22页，课件共25页，创作于2023年2月定理11.1的证明(3)a∈G，anam＝an+m，n,m∈Z。先考虑n,m都是自然数的情况。任意给定n，对m进行归纳。m＝0，有ana0＝ane＝an＝an+0成立。假设对一切m∈N有anam＝an+m成立，则有anam+1＝an(ama)＝(anam)a＝an+ma＝an+m+1由归纳法等式得证。下面考虑存在负整数次幂的情况。设n<0，m≥0，令n＝-t，t∈Z+，则anam＝a-tam＝(a-1)tam＝a-(t-m)＝am-t＝an+m t≥mam-t＝an+m t<m对于n≥0,m<0以及n<0,m<0的情况同理可证。第23页，课件共25页，创作于2023年2月定理11.1的证明(5)若G为交换群，则(ab)n＝anbn。当n为自然数时，对n进行归纳。(ab)n＝(ba)n＝(ba)-m＝((ba)-1)m＝(a-1b-1)m＝(a-1)m(b-1)m＝a-mb-m＝anbnn＝0，有(ab)0＝e＝ee＝a0b0。假设(a