第5章代数结构

《第5章代数结构》由会员分享，可在线阅读，更多相关《第5章代数结构（68页珍藏版）》请在金锄头文库上搜索。

1、离散数学Discrete Mathematics,主 讲 教 师 : 王 涛Email:,第5章 代数结构,关于代数结构 “时至今日，数学家们还在忙于发展简单的计算方法，也就是在一切数学领域中的所谓算法。一旦我们有了算法，所有的其他事都留给了计算机。计算机所作的不再是数学了，但为了使用计算机，需要数学和数学家。” H.Freudenthal“模型化是数学中的一个基本概念，它处于所有的数学应用之心脏，也处于某些最抽象的纯数学核心之中。” R.C.Buck数学之所以重要，其中心原因就在于它提供的数学系统丰富多彩；此外的原因是，数学给出了一个系统，以便于使用这些模型对物理现实和技术领域提出问题、回答

2、问题，并且也就探索了模型的行为。 R.C.Buck &.E.F.Buck,初等代数、高等代数、线性代数都称为经典代数.它的研究对象主要是代数方程和线性方程组.而现代代数学也即近世代数(又称为抽象代数),其主要内容是研究各种代数系统(代数结构),而对于代数结构,其基本成分则是集合和集合上的映射.,而近世代数就像古典代数那样,是关于运算的学说,是计算规则的学说,但它不把自己局限在研究数的运算的性质上,而是企图研究更具一般性的元素上运算的性质,这种趋向是现实中的要求所提示的.,由于近世代数在数学的其他分支、近代物理、近代化学、计算机科学、数字通信、系统工程等许多领域都有重要应用，因而它是现代科学技术

3、的数学基础之一，是许多科技人员需要掌握的基本内容和方法，因此近世代数也是数学专业的专业基础课之一。,一 关于代数的观念,从人们的观念上来看,人们关于代数的观念大致有三种：1 用字母的代数2 解方程 3 各种代数结构的理论,二 数学史的发展阶段,1 萌芽阶段2 初等数学阶段3 高等数学阶段4 近代数学阶段5 现代数学阶段,四 代数学发展的四个阶段,代数学经历了漫长的发展过程,抽象代数(近世代数)是19世纪最后20年直到20世纪前30年才发展起来的现代数学分支. 1 最初的文字叙述阶段 2 代数的简化文字阶段 3 符号代数阶段 4 结构代数阶段,1 最初的文字叙述阶段,古希腊之前直到丢番图(Dio

4、phantine,公元250年)时代,代数学处于最初的文字叙述阶段,这一阶段除古希腊数学之外还包括古巴比伦、古埃及与古代中国的数学.此时算术或代数尚未形成任何简化的符号表达法,代数运算则都采用通常的语言叙述方式表达,因而代数推理也都采用直观的方法.在中国古代则有著名的筹算法,而在古希腊则借助于几何图形的变换方法.最典型的代表是毕达哥拉斯(Pythagoras,公元前585-497)几何数论方法.例如通过图形的组合可以得到 不要认为简单的几何变换只能产生简单的代数结论,恰当地利用几何图形的变换有时也会产生重要的代数结论(如勾股定理与勾股数.,2 简化文字阶段,缺乏符号运算的代数当然是相当原始的代

5、数学.直到古希腊数学后期,数学家丢番图才开始把通常的语言叙述作简化,利用简化的文字符号代替一些相对固定的代数表达式.这一时期称为代数的简化文字阶段,这一时期大致延续到欧洲文艺复兴时代.丢番图对代数学的发展做出了突出的贡献,算术一书是丢番图留下来的著作,该著作研究了一系列不定方程的求解问题.例如把一个平方数表为两个平方数之和的问题.后来欧拉发现了正整数能够表为两个整数平方和的充分必要条件.把一个给定的整数表为四个数的和再加上这四个数的平方和.求两个有理数使它们的和等于它们的立方和,例如七分之五与七分之八等等.正是在丢番图关于整数诸如此类表法研究的基础上,17世纪伟大的法国数学家费马(Pierre

6、 de Fermat,1601-1665)提出了不定方程xn+yn=zn在n3时不可解问题.19世纪费马问题的研究也是导致近世代数理想论产生的重要契机.,3 符号代数阶段,这一阶段是经过欧洲文艺复兴之后的好几位数学家的努力而达到(它大致在17世纪完成).它的标志是用字母表示数,这一过程使代数学达到了现在我们看到的这种符号演算形式.较早的代表著作是德国数学家M.Stiefel(1486-1567)1553年的著述综合算术.其利用10进制小数表示实数.对代数学的符号体系做出了重要贡献的另一位代表人物是法国数学家韦达(F.Viete,1540-1603).韦达是第一个系统使用字母表示数的人,在代数、

7、三角学等许多方面都做出了杰出的贡献.,4 结构代数阶段,这一阶段代数学的研究对象不再是个别的数字运算,而是抽象的运算系统(如群、环、域等)的代数结构.它起因于年轻的法国数学家Evariste Galois(1811-1832)对代数方程式解的研究. Galois引入了群与扩域的工具,解决了高次方程的求根问题.这个问题是在16世纪中叶,两位意大利数学家G.Cardano(1506)与L.Ferrari(1545)发现了三、四次方程的求根公式之后一直困扰数学家达三百年之久的代数学难题. Galois摆脱了前人关于根的计算方法的研究途径,发现根的对称性群的结构能够决定根的可解性. Galois的研究

8、不但确立了群论在数学中的地位,同时也开创了结构代数这个新型的代数学研究方向. 在数学家们致力于解决高次方程的求根问题的同时,Carl Gauss(1777-1855)为了解决Fermat问题,开始一般性的研究代数数域.他的学生E.Kummer(1810-1893)在Gauss方法的基础上引入理想数,使Fermat问题的研究推进了一步.直到19世纪末已建立了群、环、域的系统理论.,1834年爱尔兰数学家William R.Hamiton(1805-1865)在Gauss把复数解释为二元数这一思想的启发下创建了一种奇特的不交换的数系,后来称之为Hamiton四元数. 三大进展奠定了近世代数学的重要

9、基础.1931年荷兰数学家B.L.van.der.Waerden出版了两卷本,1955年该书第四版更名为.这一著作标志着群、环、域等抽象结构理论已经成为现代代数学的主要研究对象,该著作同时也成为现代结构主义数学的起点.1951年美国数学家N.Jacobson又出版了新的代数学著作,书名为(共三卷).因此近世代数也被称为抽象代数.,五 几类与近世代数的应用有关的实际问题,1 项链问题2 分子结构的计数问题3 正多面体的着色问题4 图的构造与计数问题5 开关线路的构造与计数问题6 数字通信的可靠性问题7 几何作图问题8 代数方程根式的求解问题,1)基本问题: 用黑白两种颜色的珠子做成有五颗珠子的项

10、链,问可以做成多少种不同的项链？ 2)问题解决思路:枚举法 3)问题推广:用n种颜色的珠子做成m颗珠子的项链,问可做成多少种不同类型的项链？,1 项链问题,数学表述,把m颗珠子做成一个项链用一个正m边形来代替,其中每个顶点代表一颗珠子.从任意正m边形一个顶点开始,沿逆时针方向,依次给每个顶点标以码:1,2,3, ,m.这样的一个项链称之为有标号的项链.由于每一颗珠子的颜色有n种选择,因此由乘法原理,这些有标号的项链共有 种.但是其中有一些项链可通过旋转一个角度或反转180度使它们完全重合.对于这些项链称它们为本质上是相同的.对那些无论怎样旋转或反转都不能使它们重合的项链,称之为本质上不相同的项

11、链,即为问题所提的不同类型的项链.当n与m较小时,不难用枚举法求得问题的解答.但随着n与m的增加,用枚举法越来越难,因而必须寻找更为有效的可解决一般正整数n与m的方法.采用群论可解决此问题,且至今尚未发现其它更为简单和有效的方法.,2 分子结构的计数问题,1)背景:在化学中研究有某几种元素可合成多少种不同物质的问题,可以知道人们在大自然中寻找或人工合成这些物质.,2)问题:在一个苯环上结合 原子或 原子团,问可以形成多少种不同的化合物？ 3)转化:如果假定苯环上相邻 原子之间的键都是互相等价的,则此问题就是两种颜色六颗珠子的项链问题.,其中:下图中外圈球右边两个每个代表一个 ,其余四个每个代表

12、一个 ;内圈每个代表一个 .,3 正多面体的着色问题,1) 问题:用n种颜色对正六面体的面着色,问有多少种不同的着色方法？2) 数学模型:为了将问题中的概念量化:设n种颜色的集合为 ,正六面体的面集合为 ,则每一种着色法对应一个映射: ,反之,每一个映射 对应一种着色法. 由于每一面的颜色有n种选择,所以全部着色法的总数为 ,但这样的着色与面的编号有关,其中有些着色可适当旋转正六面体使它们完全重合,对这些着色法,称它们为本质上是相同的.因而我们的问题转化为求本质上不同的着色法的数目. 当n很小时,不难用枚举法求得结果,如当n取2时,本质上不同的着色数为10,对于一般的情况则必须用群论方法才能解

13、决.,4 图的构造与计数问题,1) 图的概念： 设 称为顶点集合,是由 的一些二元子集构成的集合,称为边集,则有序对 称为一个图. 2) 图的画法: 每一个顶点用圆圈表示,对边集 中的每一对元素 用一条直线或曲线连接顶点 与 .顶点的位置及边的长短、形状均无关紧要.,一个图可以代表一个电路、水网络、通讯网络、交通网络、地图等有形的结构,也可以代表一些抽象关系.例如:可用一个图代表一群人之间的关系,其中点代表单个人,凡有边相连的的两个点表示他们之间互相认识,否则表示不认识,则这个图就表示出这群人之间的关系. 图论中自然会涉及到某类图有多少个的问题.,3)问题:画出所有点数为3的图.解决办法:首先

14、画出3个顶点:1,2,3,在每两个点之间有“无边”和“有边”两种情况,因而全部有8种情况,每种情况对应一个图.,4)推广:当点数为 时,共可形成 个二元子集,每个二元子集可以对应图中的边或不对应边两种情况,故可形成 个图.我们观察上图中的8个图,可以发现有些图是完全相同的,如不考虑它们的顶点号,这些图可完全重合,这样的图称它们是同构的,可以看出:上图中有4个互不同构的图.那么,对于一般的情况,也即顶点数为 的图中互不同构的图有多少个呢?这个问题也不能用初等方法解决.,1)问题:一个有两种状态的电子元 件称为一个开关,例如普通的电灯开关、二极管等.由一些开关组成的二端网络称为开关线路.一个开关线

15、路的两端也只有两种状态:通与不通.我们的问题是:用n个开关可以构造多少种不同的开关线路？,5 开关线路的构造与计数问题,2)模型： 我们用 个变量 代表 个开关,每个变量的取值为0或1且代表开关的两种状态.开关线路的状态也用一个变量 来表示,它的取值也是 0或1代表开关线路的两种状态.是 的函数,称为开关函数,记为 ,其中每一个函数 对应一个开关线路. 3)数学计算： 由于每一个函数 对应一个开关线路,因而开关线路的数目就是开关函数的数目.又由于 的定义域的点数目为 ,在定义域的每一个点上的取值有两种可能.所以全部开关函数的数目为 ,这就是 个开关的开关线路的数目. 4)总结 上面考虑的开关线路中的开关是有标号的,有一些开关线路结构完全相同,只是标号不同,我们称这些开关线路本质上是相同的.要进一步解决本质上的开关线路的数目问题,必须用群论方法.,