哈尔滨理工大学呻斛生課程 离影数 第11章半群与群 O计算机系
第11章 半群与群 离 散 数 学 哈尔滨理工大学本科生课程 计算机系
本章内容 11.1半群与独异点 11.2群的定义与性质 11.3子群 11.4陪集与拉格朗旦定理 11.5正规子群与商群 11.6群的同态与同构 11.7循环群与置换群 本章总结 例题选进 作业
本章内容 11.1 半群与独异点 11.2 群的定义与性质 11.3 子群 11.4 陪集与拉格朗日定理 11.5 正规子群与商群 11.6 群的同态与同构 11.7 循环群与置换群 本章总结 例题选讲 作业
lL,半群与独异点 口半群与独异点都是具有一个二元运算的代数系统。 口半群与独异点的定义,及其子代数的说明。 口半群与独异点的幂运算。 口半群与独异点的同态映射
11.1 半群与独异点 ❑ 半群与独异点都是具有一个二元运算的代数系统。 ❑ 半群与独异点的定义，及其子代数的说明。 ❑ 半群与独异点的幂运算。 ❑ 半群与独异点的同态映射
半群与独异点 定义11 (1)设V=
半群与独异点 定义11.1 (1)设V＝是代数系统，为二元运算，如果运算是可结 合的，则称V为半群（semigroup）。 (2)设V＝是半群,若e∈S是关于运算的单位元,则称V是 含幺半群，也叫做独异点（monoid）。 有时也将独异点V记作V＝
半群与独异点的奥例 口,州N,+,,,都是半群,+是普通加 法。这些半群中除外都是独异点 口设n是大于1的正整数,和都是半群,也都是 独异点,其中+和分别表示矩阵加法和矩阵乘法。 口4P(B),⊕>为半群,也是独异点,其中为集合的对称差运算 口为半群,也是独异点,其中Zn={0,1,…,.n-1},⊕为模n加 法 口<AA,°为半群,也是独异点,其中为函数的复合运算。 口<R*,°为半群,其中R*为非零实数集合,运算定义如下: vx,y∈R*,xy=y
半群与独异点的实例 ❑ ，，，，都是半群,+是普通加 法。这些半群中除外都是独异点。 ❑ 设n是大于1的正整数,和都是半群,也都是 独异点,其中+和·分别表示矩阵加法和矩阵乘法。 ❑ 为半群,也是独异点,其中为集合的对称差运算。 ❑ 为半群,也是独异点,其中Zn＝{0,1,…,n-1},为模n加 法。 ❑ 为半群,也是独异点,其中为函数的复合运算。 ❑ 为半群,其中R 为非零实数集合, 运算定义如下： x,y∈R, xy＝y
半群中元素的界 口由于半群V=<S,°中的运算是可结合的,可以定义元素的 幂,对任意x∈S,规定: xI=x xn+=xn°x, n∈Z+ 用数学归纳法不难证明x的幂遵从以下运算规则: xn°xm=xnm X m,n∈Z+ 口普通乘法的幂、关系的幂、矩阵乘法的幂等都遵从这个 幂运算规则
半群中元素的幂 ❑ 由于半群V＝中的运算是可结合的,可以定义元素的 幂,对任意x∈S,规定： x 1＝x x n+1＝x n x, n∈Z+ 用数学归纳法不难证明x的幂遵从以下运算规则： x n x m＝x n+m (xn) m＝x nm m,n∈Z+ ❑ 普通乘法的幂、关系的幂、矩阵乘法的幂等都遵从这个 幂运算规则
独异点中的 独异点是特殊的半群,可以把半群的幂运算推广到独异点 中去。 由于独异点V中含有单位元e,对于任意的x∈S,可以定义x 的零次幂,即 xn+1=xn°x n∈N 不难证明,独异点的幂运算也遵从半群的幂运算规则,只不 过m和n不一定限于正整数,只要是自然数就成立
独异点中的幂 独异点是特殊的半群，可以把半群的幂运算推广到独异点 中去。 由于独异点V中含有单位元e，对于任意的x∈S,可以定义x 的零次幂,即 x 0＝e x n+1＝x n x n∈N 不难证明，独异点的幂运算也遵从半群的幂运算规则，只不 过m和n不一定限于正整数，只要是自然数就成立
子半群与子独异点 口半群的子代数叫做子半群。 口独异点的子代数叫做子独异点。 口根据子代数的定义不难看出: 如果V=才构成V的子独异点
子半群与子独异点 ❑ 半群的子代数叫做子半群。 ❑ 独异点的子代数叫做子独异点。 ❑ 根据子代数的定义不难看出： –如果V＝是半群,TS，要T对V中的运算封闭，那 么就是V的子半群。 –对独异点V＝来说，TS，不仅T要对V中的运算 封闭,而且e∈T，这时才构成V的子独异点
°例11。2 例112设半群Vv1=。 其中 a0 a,d∈R ●为矩阵乘法,e为2阶单位矩阵 a∈R 00 则TcS,且T对矩阵乘法·是封闭的, 所以的子半群。 易见在中存在着自己的单位元 00 所以(7·,(10》也构成一个独异点 00 但它不是V2=的子独异点,因为v2中的单位元 e=\0
例11.2 例11.2 设半群V1 ＝，独异点V2 ＝。 其中 = a ,d R 0 d a 0 S 0 1 1 0 = a R 0 0 a 0 T •为矩阵乘法，e为2阶单位矩阵 令 则T S，且T对矩阵乘法•是封闭的， 所以是V1 ＝的子半群。 但它不是V2=的子独异点，因为V2中的单位元 e= T 。 0 1 1 0 0 0 1 0 易见在中存在着自己的单位元 ， 0 0 所以 1 0 也构成一个独异点
半群与独异点的直积 定义1.2设V1=,∈S, a,b>·是 V1×V2中的单位元,因此V1×V2也是独异点
半群与独异点的直积 定义11.2 设V1 ＝，V2 ＝是半群(或独异点), 令S＝S1×S2 ,定义S上的·运算如下： ,∈S, •＝ 称为V1和V2的直积，记作V1×V2。 可以证明V1×V2是半群。 若V1和V2是独异点，其单位元分别为e1和e2，则是 V1×V2中的单位元，因此V1×V2也是独异点