《代数结构.docVIP

第八章 几个典型的代数结构 本章我们将介绍具有一个二元运算的代数结构 半群与群，以及具有两个运算的代数结构 环和域。半群与群在形式语言、快速加法器设计、纠错码制定和自动机理论中都有卓有成效的应用。 §8.1 半群与独异点 半群是最简单的一类代数结构，其运算个数少，且运算的性质也少。半群在时序机理论、形式语言、语法分析等方面有着广泛的应用。 一. 半群、独异点和它们的子代数 定义1 给定代数 ，其中*是二元运算，若*满足结合律，则称代数 为半群。 定义2 给定代数 ，如果二元运算*满足结合律且有么元 ，则称 为独异点。 可以看出，独异点是含有么元的半群。因此有些人将独异点称为含么半群。 例1（1）代数 和 都是半群，因为运算＋和×都满足结合律；而且还是独异点，因为0是＋的么元，1是×的么元。 （2）代数 和 不是半群，因为减法和除法不满足结合律。 定义3 如果 是半群， 且关于运算*封闭，则 是 的子代数，称为 的子半群。 显然子半群是半群。 定义4 如果 是独异点， 且关于运算*封闭， ，则 是 的子代数，称为 的子独异点。 显然子独异点是独异点。 例2（1）代数 和 分别是独异点 和 的子独异点。 （2）如果∑是非空有限字母表，那么∑＋,连结是半群，∑*,连结,Λ是独异点。如果 ，则 连结是∑＋,连结的子半群， 连结,Λ是∑*,连结,Λ的子独异点。 定义5 在半群（独异点）中，若运算是可交换的。则称此半群（独异点）为可交换半群（可交换独异点）。 定理8.1.1 在任何可交换独异点 中，S的幂等元组成的集合T可构成其子独异点。 证明： ， 是幂等元，所以 。对任意的 ， 。所以 ，故 是子独异点。 本定理对可交换半群也成立。 下面我们定义独异点 中任意元素 的幂。用归纳定义： （1）（基础） 。 （2）（归纳） 。 由于独异点中，运算*是可结合的，容易证明如此定义的 的幂满足以下指数定律： （a） （b） 定义6 设 是独异点，若存在元素 ， ，都 ，使得 。则称元素 为 的生成元，也称元素 生成独异点 ，并称此独异点为循环独异点。 定理8.1.2 每个循环独异点是可交换的。 证明：设 是循环独异点，且其生成元为 。则 ，存在 ，使得， ， 。于是 故： 是可交换的。 类似地，可定义半群 的任意元素的幂、循环半群、生成元等概念，也可得出循环半群是可交换的结论。但注意，如果 不含么元，则不存在 ，与此有关的地方要作相应修改，例如，归纳定义的基础条款需改为 。 例3 给定代数 ，则 是由1生成的无限循环独异点。 对生成元的概念加以推广可得生成集的概念。 定义7 设 是半群， ，集合 定义如下： （1）如果 ，则 ； （2）如果 ，则 ； （3）只有有限次应用条款1和2生成的元素才属于 。 显然 是 的子半群，我们称它为由∑生成的子半群，∑叫生成元集合。 如果 不含么元，我们给 增添一么元 ，则称 是由∑生成的独异点。 当∑是单元素集合时，生成的半群（独异点）就是上述循环半群（循环独异点）。 * 例4（1）令半群 ，其中 ，运算*定义如右表，试证明：半群 由 生成。 证：由右表可知 所以，半群 由 生成。 （2） 是半群，取元素6为生成元，可生成循环半群 。取生成元集为｛3,5｝，可生成半群 。 二. 半群同态和独异点同态 现在我们将代数结构间的同态与同构的概念应用于半群与独异点。有些定义与性质，几乎就是完全平行地搬过来的。 定义8 设 和 是半群，映射 ： ，若 ，有 则称 是从 到 的半群同态。 定义9 设 和 是独异点，映射 ： ，若 ，有 且 ，则称 是从 到 的独异点同态。 由于代数结构间的满同态具有保持运算的各种性质，对于半群满同态当然完全适用，在此不赘述了。 例5 映射 ： ， 是从半群 到 的半群同态。 因为， ， 又 ，所以它也是从独异点 到 的独异点同态。 由于半群同态是函数，因此可对半群同态进行复合运算，从而产生新的半群同态。有如下定理： 定理8.1.3 如果 是从 到 的半群同态， 是从 到 的半群同态，则 是从 到 的半群同态。 证明：对任意的 ，有