离散数学第六章群论.ppt

第六章群论 6 1半群与单元半群6 2群 群在代码的查错 改错的研究 自动机理论等方面都有应用 6 1半群与单元半群 半群与群都是具有一个二元运算的代数系统 群是半群的特殊例子 事实上 群是历史上最早研究的代数系统 它比半群复杂一些 而半群概念是在群的理论发展之后才引进的 逻辑关系见图6 1 1 图6 1 1 群 半群 一 半群1 半群的有关定义定义6 1设 S 是代数系统 是二元运算 如果 运算满足结合律 则称它为半群 换言之 a b c S 若 是S上的封闭运算且满足 a b c a b c 则 S 是半群 许多代数系统都是半群 例如 I I E E N4 4 N4 4 均是半群 再如 设X是有限字母表 X 是X中的字母串 X X 其中 是不含字母的空串 运算 是字母串的 并置 运算 则 X 是半群 如Com X puter X 经 运算后 得Computer仍是字母串 定理6 1一个半群 S 如果它有一个子代数 M 则此子代数也是一个半群 定义6 2一个半群 S 的子代数 M 也是半群 称为 S 的子半群 一个半群 S 中的元素a 可定义它的幂 a1 a a2 a a an 1 an a即半群中的元素有时可用某些元素的幂表示出来 因为半群满足结合律 所以可得到am an am n an m amn 如果有a2 a 则称a为半群中的等幂元素 2 一些特殊半群 1 可交换半群 如果半群 S 中二元运算 是可交换的 则称 S 是可交换半群 例如 I I E E N4 4 N4 4 均是可交换半群 但 X 不是可交换半群 2 循环半群 一个半群 S 如果它的每个元素均为S内某一固定元素a的某一方幂 则此半群称为由a所生成的循环半群 元素a称为此半群的生成元素 3 单元半群 或单位半群 有单位元素e的半群 S 常记为 S e 定理6 2 一个循环半群一定是可交换半群 定理6 3 一个半群内的任一元素a和它所有的幂组成一个由a所生成的循环子半群 例 下面半群都是单位半群 I 单位元素是0 可记为 I 0 I 单位元素是1 可记为 I 1 X 单位元素是 空串 可记为 X E 单位元素是 可记为 E E 单位元素是E 可记为 E E N4 4 单位元素是 0 可记为 N4 4 0 N4 4 单位元素是 1 可记为 N4 4 1 定理6 5一个单位半群 S 如果存在一个子代数 M 且其单位元e M 则 M 也是一个单位半群 定义6 5一个单位半群 S 如果存在一个子代数 M 且其单位元e M 则 M 也是一个单位半群 称为 S 的子单位半群 定义6 5 一个单位半群 S 如果由它的一个元素a所生成 则称为由a所生成的循环单位半群 元素a称为此单位半群的生成元素 定理6 6 一个循环单位半群是一个可换单位半群 6 2群 一 群与群的同构1 群的有关定义定义6 7如果代数系统 G 满足 1 G 为一半群 2 G 中有单位元e 3 G 中每一元素a G都有逆元a 1 则称代数系统 G 为群 例如 I 是群 因a I都有逆元 a N4 4 是群 0 的逆元是 0 1 的逆元是 3 2 的逆元是 2 I X E E N4 4 均不是群 定义6 8一个群 G 如果满足交换律 则称为可交换群或称阿贝尔群 例如 群 I N4 4 都是阿贝尔群 定义6 9一个群 G 如果它的一个子代数 H 也是一个群 则称 H 是 G 的一个群 定义6 10一个群 G 如果它的元素个数是有限的 则称为有限群 如果它的元素个数是无限的 则称为无限群 定义6 11一个群 G 的阶记为 G 如果一个群是有限群 则阶为元素个数 如果一个群为无限群 则阶为无穷大 2 群的一些性质 1 群满足消去律 2 一个阶大于1的群一定没有零元 3 除了单位元外 一个群一定没有等幂元素 4 一个群 G 的方程 a x b与y a b 其中a b G在群内有唯一解 3 群的第二个定义 定义6 12一个代数系统 G 若满足下列条件 则称为群 1 满足结合律 2 方程 a x b与y a b 其中a b G在G内有唯一解 4 群的同构 定义6 13设 G 与 H 是两个群 若存在一个函数g G H 使得对每个a b G 有g a b g a g b 则称g是从 G 到 H 的群同态 若g G H是一一对应的 则称g是从 G 到 H 的群同构 定理6 9 设 G 与 H 是两个群 有一个函数g G H使其群同态 则有g eG eHg a 1 g a 1 定理6 9 设 G 是一个群 若 G 与 H 满同态或同构 则 H 也构成群 二 变换群 定义6 14集合S上的若干个变换与复合运算若构成群 则此种群叫变换群 定理6 9 任一个群均与一个变换群同构 三 有限群 群表 对有限群 可用一张组合表将其运算表示出来 称为群表 设有限群 G 其中G 1 2 3 这个群可用表6 3所示的群表定义 表6 3 群表的特性 1 总存在一行 或一列 其元素与横线上 或竖线左边 的元素一样 2 每一行 列 内元素各不相同 且任两行 列 对应元素间也均不相同 故群表每一行 列 是G中元素的一个全排列 3 若群是可换群 则群表是对称的 由群表可知 一个阶为n的有限群 G 它的每个元素对应G的一个置换 就是说 设有有限群 G 其中G a1 a2 an 则存在一个函数 由这些置换组成一个集合 则集合P与其复合运算构成一个群 即一个置换群 如表6 3中G的每个元素对应的置换所组成的集合为 存在一个函数 集合P与其复合运算构成一个置换群 定理6 15 每个有限群均与一个置换群同构 因此 当有限群 G 分别为1 2 3阶群时 运算都只有一个定义方式 即不计元素记号的不同 只有一张定义 运算的运算表 分别如表6 4 6 5和6 3所示 于是可以说 1 2 3阶的群都只有一个 表6 4 表6 5 4阶群的群表不只一个 四 循环群 定义6 16 设 G 是一个群 a G 则令 a0 e aj 1 aj a j 0 a j a 1 j j 0 由定义可得到am an am n an m amn 群中元素方幂的定义 定义6 17 若一个群 G 的每一个元素均是它的某一个固定元素a的某次方幂 则称 G 是由a生成的循环群 而a称为 G 的生成元素 记为 定义6 18 一个由a生成的循环群 G 若存在m 使得am e的最小正整数m称为a的周期 若不存在这样的一个m 则称a的周期为无限 例1 整数加群 I 是一个生成周期为无限的循环群 1或 l 为其生成元 例2 剩余类加群 Nm m 是一个生成周期为m的循环群 1 为其生成元 定理6 16 设有一个由a生成的循环群 G 则有若a的周期无限 则 G 与 I 同构 2 若a的周期为m 则 G 与 Nm m 同构 四 子群 定理6 17 一个群 G 及由它的一个子集H组成一个代数 H 该代数构成一个 G 的子群的充要条件是 a b H 则a b Ha H 则a 1 H 定理6 18 设 G 是一个群 而 H 是 G 的子群 则 H 的单位元素