大连理工Chapter5代数结构

1、（代数结构）Discrete Mathematics（Algbra Structures）2022/8/161离散数学是现代数学的一个重要分支, 是计算机 科学与技术的理论基础, 所以又称为计算机数学人们已公认, 高技术本质上是数学技术。 因此, 计算机科学与技术说到底根本是数学技术 事实上，从计算机产生到以后它的每一步发展都 离不开数学内容简介2022/8/1621936年, 英国数学家图灵(A.M.Turing)发表了著名 论文 “理想计算机”，从而给出了计算机的理论模型1946年在著名数学家冯诺依曼(J.Von Neumann) 的领导下, 制造了世界上第一台计算机 ENIAC (Ele

2、ctronic Numerical Integrator and Calculator). 尔后，计算机各代的发展也都无不证实了这一点内容简介2022/8/163离散数学是计算机科学与技术专业的核心、骨干 课程一方面，它给后继课，如数据结构、编译系统、 操作系统、数据库原理和人工智能等, 提供必要 的数学基础；内容简介2022/8/164另一方面, 通过学习离散数学, 培养和提高了学生 的抽象思维和逻辑推理能力，为学生今后继续学 习和工作，参加科学研究，处理离散信息，从事 计算机软件的开发和设计以及计算机的其他应用 打好数学基础。内容简介2022/8/165第一篇 数理逻辑 第一章 命题逻辑

3、第二章 谓词逻辑第二篇 集合论 第三章 集合与关系 第四章 函数 第三篇 代数系统 第五章 代数结构 第六章 格与布尔代数 第四篇 图论 第七章 图论主要内容2022/8/166第三篇 代数系统代数结构是近世代数或抽象代数学研究的中心 问题, 是数学中最重要的、基础的分支之一, 是在初等代数学的基础上产生和发展起来的. 它起始于19世纪初, 形成于20世纪30年代. 2022/8/167第三篇 代数系统挪威数学家阿贝尔(N H Abel)法国数学家伽罗瓦(E Galois)英国数学家德 摩根(A De Morgan) 和 布尔(G Boole)等人都做出了杰出贡献，荷兰数学家范德瓦尔登(B L

4、 Van DerWaerden) 根据德国 数学家诺特 (A E Noether) 和奥地利数学家阿廷(E Artin) 的讲稿, 于 1930年和1931年分别出版了 近世代数学 一卷和二卷，标志着抽象代数的 成熟. 2022/8/168代数结构是以研究数字、文字和更一般元素的运算的规律和由这些运算适合的公理而定义的各种数学结构的性质为中心问题. 它对现代数学如拓扑学、泛函分析等, 以及一些其他科学领域, 如计算机科学、编码理论等, 都有重要影响和广泛地应用.第三篇 代数系统2022/8/169第五章 代数结构本章给出代数结构的一般定义与实例, 讨论 代数结构的基本性质.在正式给出代数结构的

5、定义之前, 先来说明 什么是在一个集合上的运算, 因为运算这个 概念是代数结构中不可缺少的概念.2022/8/1610定义5.1.1 设 S 是个非空集合且函数 f : Sn S, 则称 f 为一个n元运算, 其中 n是自然数, 称为运算的元数或阶. 当 n=1时, 称f为一元运算, 当 n=2时, 称f为2元运算, 等等.5.1 运算、代数系统与特异元素2022/8/1611注意, n元运算是个闭运算, 因为经运算后产生 的象仍在同一个集合中. 封闭性表明了n元运算与一般函数的区别之处. 此外, 有些运算存在幺元或零元, 它在运算中 起着特殊的作用, 称它为S中的特异元或常数5.1 运算、代

6、数系统与特异元素2022/8/1612运算的例子很多. 例如, 在数理逻辑中, 否定是谓词集合上的一元运算； 合取和析取是谓词集合上的二元运算; 在集合论中, 并与交是集合上的二元运算; 在整数算术中, 加、减、乘运算是二元运算, 除运算便不是二元运算, 因为它不满足封闭性.5.1 运算、代数系统与特异元素2022/8/1613讨论代数结构时, 主要限于一元和二元运算. 将用 , , , , , !, 等符号表示一元运算符;用,等符 号表示二元运算符.一元运算符常常习惯于前置、顶置或肩置, 如: x、x、x”, 二元运算符习惯于前置、中置或后置, 如：+xy, x+y, xy+. 有了集合上运

7、算的概念后, 可定义代数结构.5.1 运算、代数系统与特异元素2022/8/1614定义5.1.2 设 S 是个非空集合且 fi 是 S 上的 ni 元运算，其中 i=1, 2, , m. 由 S 及 f1, f2, , fm组成的结构, 称为代数结构, 记作 .5.1 运算、代数系统与特异元素2022/8/1615此外, 集合S的基数即|S|定义为代数结构的基数. 如果S是有限集合, 则代数结构是有限代数结构; 否则便说是无穷代数结构.有时, 要考察两个或多个代数结构, 这里就有个 是否同类型之说, 请看下面定义:5.1 运算、代数系统与特异元素2022/8/1616定义5.1.3 设两个代

8、数结构 和 ，如果 fi 和 gi (1im)具有相同的元数,则称这两个代数结构是同类型的.5.1 运算、代数系统与特异元素2022/8/1617判定两个代数结构是否同类型, 主要是对其运算进行考察.有时还需要在代数结构中集合的某个子集上讨论其性质, 引出子代数结构的概念.5.1 运算、代数系统与特异元素2022/8/1618定义 5.1.4 是一代数结构, 且非空集 T S在运算 f1, f2, , fm下是封闭的, 且T含有与S中相同的特异元, 则称为代数结构 的子代数, 记为 .5.1 运算、代数系统与特异元素2022/8/1619例5.1.1 设R是实数集合, 且+和是R上的普通加法和

9、乘法运算, 则是一代数结构. 因为运算+ 和在R中是封闭的.显然, 是无穷代数结构. 5.1 运算、代数系统与特异元素2022/8/1620例5.1.2 设 S是非空集合, PS是它的幂集. 对任意集合 A, B PS, PS上的运算和定义如下： AB=(A B)(B A) AB=AB则是一代数结构. 因为, 显然和 是闭运算.可以看到, 例5.1.l和例5.1.2中给出的两个代数结构是同类型的, 即与是同类型的.5.1 运算、代数系统与特异元素2022/8/1621例5.1.3 设是由有限个字母组成的集合, 称为字母表. 由中的字母组成的有序集合, 称为上的串. 串中的字母个数m称为该串的长

10、度. m0时, 叫做空串, 用表示. 用*表示上的串集合. 在*上定义一个连接运算, 用 表示. 例如 , *, 则 = , 那么是一个代数结构. 如果令 + =*- , 则 也是一个代数结构.5.1 运算、代数系统与特异元素2022/8/1622例5.1.4 设有一台字长为8位的计算机, 它以定点加、减、乘、除以及逻辑加和逻辑乘为运算指令, 并分别用 01, 02, , 06 表示. 则在计算机中由 28 个不同数字所组成集合S同该机器中运算指令构成一代数结构.5.1 运算、代数系统与特异元素2022/8/1623声明记号 即为一代数结构, 除 特别指明外, 运算符 f1, f2, , fm

11、 均为二元运算. 根据需要对S 及 f1, f2, , fm可置不同的集合符 和运算符.5.1 运算、代数系统与特异元素2022/8/1624下面讨论一般代数结构的基本性质, 也即是结构中任何运算所具有的性质.对于代数结构性质的考察方法不是一个一个研究各个结构,而是列举一组性质, 把那些被选出的性质看成是公理并且从这些公理推导出有效结论. 这些结论对于满足这些公理的任何代数结构也都必定成立. 5.1 运算、代数系统与特异元素2022/8/16251. 结合律给定, 运算 “” 满足结合律或者 “”是可结合的, 即(z)(x,y,zS(xy)z=x(yz).例5.1.5. 给定, 且对任意a,

12、bA有ab=b. 证明运算“”是可结合的.证明 因为对任意a, b, c A, 有 (ab)c=bc=c, a(bc)=acc 故(ab)c=a(bc)5.1 运算、代数系统与特异元素2022/8/16262.交换律 给定, 运算“”满足交换律或者“”是可交换的, 即(x)(y)(x,ySxy=yx)例5.1.6. 给定, 其中Q为有理数集合, 并且对任意a, bR有ab=a+b-ab = b+a-ba, 问运算是否可交换？解 因为ab=a+b-ab=b+a-ba=ba, 所以, 运算是可交换的. 5.1 运算、代数系统与特异元素2022/8/1627如果一代数结构中的运算是可结合和可交换的,

13、 那么, 在计算a1a2am时可按任意次序计算其值. 特别当a1=a2=am=a时, 则a1a2am=am. 称am为a的m次幂, m称a的指数. 5.1 运算、代数系统与特异元素2022/8/1628下面给出am的归纳定义:设有且aS. 对于mI+, 其中I+表示正整数集合, 可有: (1)a1=a (2)am+1=ama 由此利用归纳法不难证明指数定律: (1) aman=am+n (2) (am)n=amn 这里, m, n I+. 类似地定义某代数结构中的负幂和给出负指数定律5.1 运算、代数系统与特异元素2022/8/16293. 分配律一个代数结构若具有两个运算时, 则分配律可建立

14、这两个运算之间的某种联系. 给定, 运算对于满足左分配律, 或者对于是可左分配的, 即: (x)(y)(x)(x,y,zS x(yz)=(xy) (xz)运算对于满足右分配律或者对于是可右分配的, 即: (x)(y)(x)(x,y,zS (yz)x =(yx) (zx)5.1 运算、代数系统与特异元素2022/8/1630类似地可定义 对于满足左或右分配律.若对于既满足左分配律又满足右分配律, 则称对于满足分配律或是可分配的. 同样可定义对于满足分配律.由定义不难证明下面定理:定理5.1.1 给定且是可交换的. 如果对于 满足左分配律或者右分配律, 则 对于满足分配律.5.1 运算、代数系统与

15、特异元素2022/8/1631例5.1.7 给定, 其中B=0,1. 表5.1.1分别定义了运算和, 问运算对于是可分配的吗？ 对于呢？(表5.1.1)解 可以验证对于是可分配的, 但对于并非如此. 因为: 1(01)(10)(11) 0 1 0 1 0 0 0 1 0 1 0 1 0 1 1 0 5.1 运算、代数系统与特异元素2022/8/1632形如表 5.1.1 的表常常被称为运算表或复合表。 由运算符、 行表头元素、 列表头元素及复合 元素四部分组成. 当集合 S 的基数很小, 特别限于几个元素时, 代数结构中运算常常用这种表给出. 其优点是 简明直观, 一目了然.5.1 运算、代数

16、系统与特异元素2022/8/16334. 吸收律 给定, 则 对于满足左吸收律: (x)(y)(x,ySx(xy)=x) 对于满足右吸收律: (x)(y)(x,yS(xy)x=x) 若对于既满足左吸收律又满足右吸收律, 则称对于满足吸收律或者可吸收的.5.1 运算、代数系统与特异元素2022/8/1634可类似地定义，对于满足左、右吸收律和吸收律.若对于是可吸收的且对于也是可吸收的, 则称和是互为吸收的 或和同时满足吸收律.5.1 运算、代数系统与特异元素2022/8/1635例5.1.8 给定, 其中N是自然数集合, 和 定义如下: 对任意 a, bN有: ab=maxa,b, ab=min

17、a,b 试证和互为吸收的.证明 因为 a(ab)=maxa,mina,b=(ab)a a(ab)=maxa,mina,b=(ab)a 故, 和是互为吸收的.5.1 运算、代数系统与特异元素2022/8/16365. 等幂律与等幂元 给定, 则 “”是等幂的或“”满足等幂律 := (x)(xSxx=x)给定, 且xS, 则 x是关于“”的等幂元:= xx=x不难证明下面定理:定理5.1.2 若 x 是中关于的等幂元, 对于任意正整数n, 则xn=x.5.1 运算、代数系统与特异元素2022/8/1637例5.1.9 给定, 其中PS是集合S的幂集,和分别为集合的并和交运算. 验证和是等幂的.证明

18、 对任意APS, 有 AA=A和AA=A, 故和都是等幂的.5.1 运算、代数系统与特异元素2022/8/16386. 幺元或单位元给定且, el, er, eS, 则 el: 为关于的左幺元:=(x)(xS elx=x) er: 为关于的右幺元:=(x)(xS xer=x)若 e 既为的左幺元又为的右幺元, 称e为 关于的幺元. 亦可定义如下: e为关于的幺元:= (x)(xSex=xe=x)5.1 运算、代数系统与特异元素2022/8/1639例5.1.10 给定, 表5.1.2, 表5.1.3和表5.1.4分别给出的不同定义的运算表, 试指出左幺元、右幺元及幺元. (表5.1.2, 5.

19、1.3, 5.1.4)解 如表5.1.2所定义, 是的幺元; 如表5.1.3所定义, 和是的右幺元; 如表5.1.4所定义, 是的左幺元. 5.1 运算、代数系统与特异元素2022/8/1640定理 5.1.3 给定且el和er分别关于的左、右幺元, 则 el = er = e, 且幺元e唯一.证明 由题设可得el = el er = er =e. 下面再证幺元e是唯一的. 若还有一幺元 e1 S, 则 e1 = e1 e = e, 即只有一个幺元.5.1 运算、代数系统与特异元素2022/8/16415.1 运算、代数系统与特异元素7. 零元 给定及 l, r, S l为关于的左零元:=(x

20、)(xSlx = l). r为关于的右零元:=(x)(xSxr = r). 为关于的零元:=(x)(xSx = x=).2022/8/16425.1 运算、代数系统与特异元素例5.1.11 在例5.1.10中,试指出左、右零元及零元. 解 如表5.1.2所定义, 是的零元; 如表5.1.3所定义, 和都是的左零元; 如表5.1.4所定义, 是的右零元.2022/8/16435.1 运算、代数系统与特异元素定理5.1.4 给定且l和r 分别为关于的左零元和右零元, 则l = r = 且零元是唯一的.证明 可仿定理5.1.3证明.2022/8/16445.1 运算、代数系统与特异元素定理5.1.5

21、 给定且|S|1.如果, eS, 其中 和e分别为关于的零元和幺元, 则e.证明 用反证法. 假设 = e, 则对任意 xS, 有 x= ex = x = = e, 可见S中的所有元素都是相同的, 这与 |S|1矛盾.2022/8/16455.1 运算、代数系统与特异元素8. 逆元给定且么元eS, 则: x为关于的左逆元:=(y)(ySxy=e) x为关于的右逆元:=(y)(ySyx=e) x关于的可逆:=(y)(ySyx=xy=e)给定及么元e; x, yS, 则: y为x的左逆元:=yx=e： y为x的右逆元:=xy=e y为e的逆元:= yx=xy=e2022/8/16465.1 运算、

22、代数系统与特异元素显然，若y是x的逆元, 则x也是y的逆元, 因此 称x与y互为逆元. 通常x的逆元表示为x-1.一般地说来，一个元素的左逆元不一定等于 该元素的右逆元. 而且, 一个元素可以有左逆 元而没有右逆元, 同样可以有右逆元而没有 左逆元. 一个元素的左或者右逆元还可以不唯一2022/8/16475.1 运算、代数系统与特异元素例5.1.8 给定 , 其中S=,且的定义如表5.2.5所示. 试指出该代数结构中各元素的左、右逆元情况 2022/8/16485.1 运算、代数系统与特异元素解: 是么元, 的左逆元和右逆元都是, 即与互为逆元; 的左逆元是, 而右逆元是, 有两个左逆元和;

23、 的右逆元是, 但没有左逆元. 2022/8/16495.2 半群、独异点与群在本节中将讨论具有一个二元运算的抽象代数： 半群、独异点与群半群与群在形式语言、快速加法器设计、纠错 码制定和自动机理论中都有卓有成效的应用2022/8/16505.2 半群、独异点与群定义5.2.1 给定代数结构, 若满足结合律，则称为半群即半群就是由集合及其定义的一个可结合的二元运算组成的代数结构2022/8/16515.2 半群、独异点与群定义5.2.2 给定，若是半群且有么元，或者满足结合律且拥有么元，则称为独异点可以看出，独异点是含有么元的半群因此又将独异点叫做含么半群有时为了强调么元e，独异点表为2022

24、/8/16525.2 半群、独异点与群例1. 给定和,其中N为自然数集合， 和为普通加法和乘法易知和 都是半群，而且还是独异点因为0 是的么元, 1 是的么元如果半群中的集合S是有限的，则称半群 为有限半群对于有限半群可以给出下面有趣定理：2022/8/16535.2 半群、独异点与群定理5.2.1 为有限半群(x)(xSxx=x)（本定理告诉我们，有限半群存在等幂元。）证明 因为为半群, 则是可结合的, 故对 任意yS有: yy = y2S, y2y = y3S, 又因为S是限集合，所以必存在ji，使得 yiyj 令 pj-i, 则yiypyi 所以，对于qi有: yqypyi (1) 20

25、22/8/16545.2 半群、独异点与群因为p1, 故总有k1, 使得: kpi对于ykpS, 则由(1)有: ykp=ypykp=yp(ypykp)=y2pykp = = ykpykp 因此,存在x=ykpS, 使得: xx=x2022/8/16555.2 半群、独异点与群定义5.2.3 给定半群,若是可交换的, 则称 是可交换半群类似地可定义可交换独异点.2022/8/16565.2 半群、独异点与群例: 给定和,其中PS是集合S的幂集,和为集合上的交运算和并运算可知和是可交换半群. 不仅如此，它们还都是可交换独异点，因为与S分别是它们的么元2022/8/16575.2 半群、独异点与群

26、定义5.2.4 给定半群和gS,以及自然数集合N, 则g为的生成元:= ( x)(xS(n)(nNx=gn)此时也说, 元素g生成半群, 而且称该半群为循环半群类似地，定义独异点 的生成元 g 和循环独异点, 并且规定g0e2022/8/16585.2 半群、独异点与群定理5.2.2 每个循环独异点都是可交换的证明 令为循环独异点且 g为其生成元. 则对任意 a,bM，存在m,nN, 使得 agm , b=gn . 于是 ab= gmgn=gm+n=gn+m= gmngm =ba 可见是可交换的, 故是可交换 的显然，每个循环半群也是可交换的2022/8/16595.2 半群、独异点与群例.

27、给定, 其中N是自然数集合, +为普通 加法, 则是无穷循环独异点, 0是么元 , 1是生成元2022/8/16605.2 半群、独异点与群定义5.2.7 给定半群, 及非空集合TS, 若 T对封闭, 则称为的子半群.类似地, 定义独异点 的子独异点, 应注意的是eP2022/8/16615.2 半群、独异点与群定理 5.2.2 给定半群 及任意 aS, 是循环子半群证明 因为是半群, 故对任意aS, aiS, 其中iI+ . 则 a, a2, a3,.S. 显然, a是的生成元. 故是循环子半群2022/8/16625.2 半群、独异点与群定理 5.2.3 给定可交换独异点, 若P为其等幂元

28、集合，则为子独异点.证明 显然, eP. 令a,bP, 于是 aa=a, bb=b, 又因为是可交换的，故: (ab)(ab) = (ab)(ba) = a(bb)a = aba = aab = ab 可见，abP, 即P对于是封闭的, 因而, 是的子独异点.2022/8/16635.2 半群、独异点与群定理 5.2.4 设为独异点, 则关于的运算表中任两列或任两行均不相同.证明 因为对任意的a, bM且ab时, 总有 ea = ab = eb 和 ae = ab = be 因此，在的运算表中不可能有两列或两行 是相同的2022/8/16645.2 半群、独异点与群定理5.2.5 给定独异点

29、, 对任意a,bM且a,b均有逆元，则: (1) (a-1)-1=a; (2) ab有逆元, 且(ab)-1=b-1a-1 .证明 (1) 因为a-1是a的逆元, 且aa-1=a-1a=e, 故, (a-1)-1=a. (2) 因为 (ab)(b -1a -1)= a(bb -1)a -1 = aea -1 = aa 1 = e. 同理 (b-1a-1)(ab)=e, 故: (ab)-1=b-1a-12022/8/16655.2 半群、独异点与群下面介绍群的概念及性质.定义5.2.9 给定独异点, 若中每个元素均可逆, 称该独异点为群. 2022/8/16665.2 半群、独异点与群群是独异点

30、的特例. 群对运算满足: (1) 封闭性； (2)具有结合律; (3)含有幺元; (4)每个元素均可逆.群、独异点、半群和代数系统之间的关系是：2022/8/16675.2 半群、独异点与群例. 给定和, 其中,I和Q分别是整数集合和有理数, +和是一般的加法和乘法. 可知, (1) 是群,0是幺元,每个元素的逆元是-i； (2) 不是群, 1是幺元, 0无逆元； (3) 是群.2022/8/16685.2 半群、独异点与群例: 设G=a,b,c, 在G上定义运算“ ”如下表: 则是群. a是幺元, b 和 c互为逆元. a b cabc a b c b c a c a b2022/8/166

31、95.2 半群、独异点与群定义5.2.10 给定群 , 若G是有限集,则称是有限群. 并且把G的基数称为该有限群的阶数. 若集合G是无穷的,则称为无穷群.例. 和都是无穷群.由群的定义,群具有半群和独异点的性质,除外 还有自己独特的性质,下面讨论如下.2022/8/16705.2 半群、独异点与群定理5.2.6 若是群,并且其元素个数大于1,那么中无零元.证明: 若 为 的零元, 又知道|G|1, 则由 代数系统中的知识, e. 对任意xG, 均有: e=e, 故无逆元, 这与假设矛盾.2022/8/16715.2 半群、独异点与群定理 5.2.7 群中一元一次方程 ax=b 和 ya=b总有

32、解.证明: 事实上, 其解可以构造为: x=a-1b, y=ba-12022/8/16725.2 半群、独异点与群定理 5.2.8 群中具有消去律. 即若ab=ac, 或ba=ca, 则b=c.证明: b=ea=(a-1a)b=a-1(ab) = a-1(a c)=(a-1a)c=ec=cb=be=b(aa-1)=(ba)a-1 =(ca) a-1=c(aa-1)=ce=c 则b=c.2022/8/16735.2 半群、独异点与群然而, 具有消去律的半群、独异点未必就是群.例如，是半群也是独异点并且具有 消去律, 然而它不是群(幺元1外的元素无逆元).2022/8/16745.2 半群、独异点

33、与群定理 5.2.9 群中幺元以外的元素均不等幂.证明: 假设存在幺元以外一个元素a, 满足a=aa, 则a=ea=(a-1a)a=a-1(aa) =a-1a=e. 与假设矛盾.2022/8/16755.2 半群、独异点与群定理 5.2.10 有限群的运算表中的每行、每列都是群中元素的一个置换.证明: 显然该定理是定理5.2.8的一个推论.2022/8/16765.2 半群、独异点与群下面介绍子群.定义5.2.11 设是群, 若G的非空子集S关于运算 也构成群, 则称 为 的子群, 记为.任何一个群至少有两个子群, 和自身, 称为的平凡子群.关于子群, 有以下定理.2022/8/16775.2

34、 半群、独异点与群定理5.2.11 子群保持群的幺元.证明: 因为 是群, 故有幺元e1, 是群, 有幺元e. 所以 gS, 有e1g=g. 但, 故e1g=g在中也成立. 从而有e1g=g= eg. 由消去律得, e1=e.2022/8/16785.2 半群、独异点与群定理5.2.12 设是群, S是G的有限非空子集合,如果S关于运算封闭, 那么是的子群.证明: bS, 由S对运算的封闭性, 知b1,b2,b3,bj,都是S中的元素. 又因为S是非空子集, 所以b的幂次序列中一定 有相同元素,不妨设bi=bj, 并有bj=bibj-i, 但bi e=bi=bibj-i, 由消去律, 得bj-

35、i =e. 即除了封闭性而保持结合性外, 还具有幺元. 考虑bj-i=e, 若j-i=1, 则b=e, b-1=e; 若j-i1则bj-i+1b=e, 对bS都满足. 故是群, 因而是的子群.2022/8/16795.2 半群、独异点与群如果S是G的无限子群,则结论不能成立. 例如, 是群, N对+封闭, 但不是子群, 因为自然数在加法下没有逆元(相反数不属于N). 因为任一自然数形成的加法幂序列中没有相同元.2022/8/16805.2 半群、独异点与群定理 5.2.13 设是群, S是G的非空子集,则 是的子群的充分必要条件是满足下列条件:(1) 对运算封闭;(2) xS, 有x-1S.2022/8/16815.2 半群、独异点与群证明:如果是群,则它显然满足上面两个条件. 反之,设满足条件(1),(2),则有eS (e=x, x-1S), 而运算的结合律既然在 中成立,当然在中也成立, 故是群。2022/8/16825.2 半群、独异点与群定理 5.2.14(子群的判定)设是群, S 是G的非空子集