离散数学群与半群.ppt

第11章半群与群 离散数学 江苏科技大学本科生必修课程 计算机教研室周塔 本章内容 11 1半群与独异点11 2群的定义与性质11 3子群11 4陪集与拉格朗日定理11 5正规子群与商群11 6群的同态与同构11 7循环群与置换群本章总结例题选讲作业 11 1半群与独异点 半群与独异点都是具有一个二元运算的代数系统 半群与独异点的定义 及其子代数的说明 半群与独异点的幂运算 半群与独异点的同态映射 半群与独异点 定义11 1 1 设V 是代数系统 为二元运算 如果运算是可结合的 则称V为半群 semigroup 2 设V 是半群 若e S是关于 运算的单位元 则称V是含幺半群 也叫做独异点 monoid 有时也将独异点V记作V 半群与独异点的实例 都是半群 是普通加法 这些半群中除外都是独异点 设n是大于1的正整数 和都是半群 也都是独异点 其中 和 分别表示矩阵加法和矩阵乘法 为半群 也是独异点 其中 为集合的对称差运算 为半群 也是独异点 其中Zn 0 1 n 1 为模n加法 半群中元素的幂 由于半群V 中的运算是可结合的 可以定义元素的幂 对任意x S 规定 x1 xxn 1 xn x n Z 用数学归纳法不难证明x的幂遵从以下运算规则 xn xm xn m xn m xnm m n Z 普通乘法的幂 关系的幂 矩阵乘法的幂等都遵从这个幂运算规则 独异点中的幂 独异点是特殊的半群 可以把半群的幂运算推广到独异点中去 由于独异点V中含有单位元e 对于任意的x S 可以定义x的零次幂 即 x0 e xn 1 xn x n N 半群与独异点的直积 定义11 2设V1 V2 是半群 或独异点 令S S1 S2 定义S上的 运算如下 S 称为V1和V2的直积 记作V1 V2 可以证明V1 V2是半群 若V1和V2是独异点 其单位元分别为e1和e2 则是V1 V2中的单位元 因此V1 V2也是独异点 半群与独异点的同态映射 定义11 3 1 设V1 V2 是半群 S1 S2 若对任意的x y S1有 x y x y 则称 为半群V1到V2的同态映射 简称同态 homomorphism 2 设V1 V2 是独异点 S1 S2 若对任意的x y S1有 x y x y 且 e1 e2 则称 为独异点V1到V2的同态映射 简称同态 两点说明 为了书写的简便 有时经常省略上述表达式中的算符 和 而简记为 xy x y 应该记住 该表达式中左边的xy是在V1中的运算 而右边的 x y 是在V2中的运算 本节的主要内容 集合S和运算构成半群的条件 封闭性 结合律 集合S和运算构成独异点的条件 封闭性 结合律 单位元 半群与独异点的两条幂运算规则 xnxm xn m xn m xnm 通过笛卡尔积构造直积 同态映射的判别 xy x y 对于独异点要加上 e e 定义11 2说明 任取 S 11 2群的定义与性质 群是特殊的半群和独异点 群论中常用的概念或术语 有限群 无限群 平凡群 交换群 元素的幂和阶 群的运算规则 群的定义 定义11 4设是代数系统 为二元运算 如果 运算是可结合的 存在单位元e G 并且对G中的任何元素x都有x 1 G 则称G为群 group 举例 1 都是群 而和不是群 2 是群 而不是群 因为并非所有的n阶实矩阵都有逆阵 Klein四元群 设G a b c d 为G上的二元运算 见下表 G是一个群 e为G中的单位元 运算是可结合的 运算是可交换的 G中任何元素的逆元就是它自己 在a b c三个元素中 任何两个元素运算的结果都等于另一个元素 称这个群为Klein四元群 简称四元群 群的直积 设 是群 在G1 G2上定义二元运算 如下 G1 G2 称是G1与G2的直积 上一节已经证明 是独异点 可以证明对任意的 G1 G2 是的逆元 因此G1 G2关于 运算构成一个群 群论中常用的概念或术语 定义11 5 1 若群G是有穷集 则称G是有限群 否则称为无限群 群G的基数称为群G的阶 有限群G的阶记作 G 2 只含单位元的群称为平凡群 3 若群G中的二元运算是可交换的 则称G为交换群或阿贝尔 Abel 群 例 是无限群 交换群 是有限群 也是n阶群 交换群 Klein四元群是4阶群 交换群 是平凡群 交换群 群中元素的n次幂 定义11 6设G是群 a G n Z 则a的n次幂 与半群和独异点不同的是 群中元素可以定义负整数次幂 群中元素的阶 定义11 7设G是群 a G 使得等式ak e成立的最小正整数k称为a的阶 记作 a k 这时也称a为k阶元 若不存在这样的正整数k 则称a为无限阶元 举例在中 2和4是3阶元 3是2阶元 而1和5是6阶元 0是1阶元 在中 0是1阶元 其它的整数都是无限阶元 在Klein四元群中 e为1阶元 其它元素都是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为负数的情况 定理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的逆元 根据逆元的唯一性等式得证 定理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 mt m am t an mt m 对于n 0 m 0以及n 0 m 0的情况同理可证 定理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 anbn n 0 有 ab 0 e ee a0b0 假设 ab k akbk 则有 ab k 1 ab k ab akbk ab ak bka b ak abk b aka bk b ak 1 bk 1 由归纳法等式得证 设n0 则 定理11 1说明 定理11 1 2 中的结果可以推广到有限多个元素的情况 即 注意上述定理中的最后一个等式只对交换群成立 如果G是非交换群 那么只有