第八章几个典型的代数结构
本章我们将介绍具有一个二元运算的代数结构半群与群，以及具有两个运算的代数结构环和域。半群与群在形式语言、快速加法器设计、纠错码制定和自动机理论中都有卓有成效的应用。
§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 如果是从到的半群同态，是从到的半群同态，则是从到的半群同态。证明：对任意的，有
可见，是所求的半群同态。
给定集合S，从S到S的函数集合在合成运算下构成一个半群。任意半群和这个半群有以下关系：
定理8.1.4 设是给定半群，是从S到S的函数集合在合成运算下构成的半群，则存在半群同态：。
证明：对任意的，定义函数，则。作映射：，
，
由于，其中。所以，
故：是从到的半群同态。
例6 给定半群，其中，运算*由下表给定，则：，是一半群同态。这里，，，并且
，，
，，
，，
。
注意，映射：是满射的，但不能保证是单射的，因为当S的运算表有两行相同时，不能得出。只有是独异点时，由于有么元，运算表没有两行或两列完全相同，因为对任意的且时，总有
和
在这种情况下，：才是双射的，即：是一同构。于是有以下定理：
定理8.1.5 设是独异点，则存在一子集，使得同构于。这里是S上的恒等函数。
本定理通常叫独异点表示定理。
商代数和积代数的概念也可引入到半群和独异点中。由此得出商半群、商独异点、半群的积代数、独异点的积代数等概念和性质。但它们只不过是前面相应定义的简单重复而已，所以就不具体罗列了。
§ 8.2 群
群比半群要复杂一些，群论是抽象代数中得到充分发展的一个分支，并已广泛地应用于数学、物理、通信和计算机科学。
一. 群的定义及性质
定义1 给定代数结构，若是含么半群，且G中的每个元素都有逆元，则称为群。
从定义1中可以看到，群比含么半群多了“每个元素都有逆元”的条件，故凡含么半群所具有的性质，群也具有。以后要证明一个代数结构是否是群，根据定义需要证明以下3点：
（1）*在G上满足结合律；
（2）关于*存在么元；
（3）G中的每个元素关于*存在逆元。
由于结合律成立，有定理7.1.3知，每个元素的逆元是唯一的，所以可看成是一种一元运算，故一个群的构成成分可看成是，这里－1是求逆运算。但通常为了简便仍记为。
定义2 给定群，若G是有限集合，则称是有限群，并把G的基数|G|称为有限群的阶数；若G是无限集合，则称是无限群。
群中的运算*一般称为乘法。如果*是可交换的，则称群是可交换群，或称阿贝尔群。在可交换群中，若运算*改用＋，则称为加法群，此时逆元写成。
例1（1）代数是一个阿贝尔群，这里“－”表示一元减法。
（2）代数是一个阿贝尔群，这里－1表示一个有理数的倒数运算。
（3）代数是群，这里。但代数不是群，因为0元素没有逆元。
定理8.2.1 若是群且|G|>1，则无零元。
证明：设群的么元是，若存在零元设为，先证。
若，则，，可见G中的所有元素都是相同的，这于|G|>1矛盾。
对，均有，所以0无逆元，这于是群矛盾。
故：群无零元。
定理8.2.2 如果是一个群，则对任意的，
（1）存在唯一的元素，使得。
（2）存在唯一的元素，使得。
证明：先证存在性。因为是群，应有么元，并且*是可结合的。于是
故，。
再证唯一性。若是G中满足的任意元素，则
同理可证（2）。
定理8.2.3 如果是群，则对任意的，有
（1）。
（2）。
即群满足可约律。
证明：因为群的每一元素都有逆元，由定理7.1.4（可结合的代数结构中，若运算是可结合的，则可逆的元素是可约的），本定理显然成立。
定理8.2.4 设是群，则中唯一的幂等元是么元。
证明：如果是幂等元，则
定理8.2.5 设是一个群，则对任意的，
证明：因为是群，令为其么元，则
又由*是可结合的，有
而逆元是唯一的，所以。
定理8.2.6 群的运算表中的每一行或每一列都是G中元素的一个置换。
证明：首先，证明运算表中的任一行所含G中的每个元素不可能多于一次。若不然，如果对
应于元素的那一行中有两个元素都是，即假定，而，但根据群的可约律，有。得出矛盾。其次，证明G中的每一元素都在运算表中的每一行中出现。考察对应于元素的那一行，，由于，所以必定出现在对应于的那一行中。
最后，因为中含么元，所以没有两行是完全相同的。
综合以上结果便得出：运算表中的每一行都是G中元素的一个置换，且各行都是不同的置换。类似可证，同样的结论对于列也成立。
现在，应用该定理来考察一、二、三、和四阶群。
一阶群仅有么元，即。其运算如表8.2.1
二阶群除么元外，还有一个元素，设为，则有，其运算表如表8.2.2。由定理8.2.6可知，不可能再有其它运算表。因而所有的二阶群都与该群同构。
三阶群仅有一个，可设为，其运算表入表8.2.3，任何三阶群都与它同构。
表8.2.1 表8.2.2 表8.2.3
教学大纲 一．课程的教学目的和要求 通过这门课的学习，使学生掌握高等代数的基本知识，基本方法，基本思路，为进一步学习专业课打下良好的基础，适当地了解代数的一些历史，一些背景。 要突出传授数学思想和数学方法，让学生尽早地更多地掌握数学的思想和方法。突出高等代数中等价分类的思想，分解结构的思想，同构对应的思想，揭示课程内部的本质的有机联系。 二．课程的主要内容： 代数学是研究代数对象的结构理论与表示方法的一门学科。代数对象是在一个集合上定义若干运算，且满足若干公理所构成的代数系统，线性空间则是数学类专业本科生所接触和学习的第一个代数对象。本课程力求突出代数学的思想和方法。 《高等代数》分为两个部分主要内容。一部分是基本工具性质的，包括多项式，行列式，矩阵初步，二次型。既然是工具性质的，因而除了多项式内容外，也是数学专业以外的理科、工科、经管类《线性代数》的内容，以初等变换为灵魂的矩阵理论是这部分内容的核心。另外一部分是研究线性空间的结构，这是研究代数结构的起点和模型，也是《高等代数》有别于《线性代数》之所在。《高等代数》从三个角度进行研究。从元素的角度看，研究向量间的线性表示，线性相关性，基向量；从子集角度看，研究子空间的运算和直和分解；从线性空间之间的关系来研究线性空间结构，就是线性映射，线性变换，线性映射的像与核，Jordan 标准形对应的空间分解。而欧氏空间则是具体的研究空间的例子。在研究线性空间中，始终贯穿着几何直观和矩阵方法的有机结合，矩阵的相似标准形和对应的线性空间分解则是这种有机结合的生动体现和提升，因而是本课程的精华内容。 本课程力求突出几何直观和矩阵方法的对应和互动。我们强调矩阵理论，把握简洁和直观的代数方法，同时重视线性空间和线性映射（变换）的主导地位和分量，从几何观点理解和把握课程内容。 三．课程教材和参考书： 教材：林亚南编著，高等代数，高等教育出版社，第一版 参考书：1. 姚慕生编著，高等代数（指导丛书），复旦大学出版社，第二版 2. 北京大学数学系编，高等代数，高等教育出版社，北京（1987） 3. 张禾瑞、郝炳新，高等代数，高等教育出版社，北京（1999）
第四章代数结构（作业） 作业：P86：4、7、9 4、 （1）若a和b是整数，则a+b+ab也是整数，故a*b也是整数，所以运算*是封闭的。（2）任选整数集合中的三个元素x,y和z。则有： (x*y)*z = (x+y+xy)*z = (x+y+xy)+z+(x+y+xy)×z = x+y+z+xy+xz+yz+xyz x*(y*z) = x*(y+z+yz) = x+(y+z+yz)+x×(y+z+yz) = x+y+z+yz+xy+xz+xyz = (x*y)*z 因此，*运算满足结合律。 （3）假设e为（Z,*）的幺元，则有： 任选整数集中的一个元素x，都有 0*x = 0+x+0×x=x且 x*0 = x+0+x×0=x 故0是(Z,*)的幺元。 7、N+上的所有元素都是（N+ ,*）等幂元； （N+ ,*）无幺元； （N+ ,*）的零元为1。 9、（A,*）中的等幂元：a、b、c、d； （A,*）中的幺元：b； （A,*）中的零元：c； a-1 = d，b-1 = b，c-1 不存在，d-1 = a， 作业：P87：12、13、18 12、（A，*）到（N4,⊕4）的同构映射f为： f(a)=0, f(b)=1, f(c)=2, f(d)=3; 或者： f(a)=0, f(b)=3, f(c)=2, f(d)=1; 13、同构映射f为： f(0)=?, f(1)={a}, f(2)={b}, f(3)={a,b};
或者： f(0)=?, f(1)={b}, f(2)={a}, f(3)={a,b}; 18、任选a ∈N +,b ∈N +, 只需证明f(a+b)=f(a)+f(b) 由f 的定义可知：f(a+b)=2a+2b=f(a)+f(b)，故f 是（N +,+）到(E +,+)的同态映射。 作业：P96：3，P97：7 3、(1)显然，*运算对Z 是封闭的。 (2) (a*b)*c = (3(a+b+2)+ab)*c = 3((3(a+b+2)+ab)+c+2)+(3(a+b+2)+ab)×c = 3(3a+3b+c+ab+8+ac+bc+2c)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc a*(b*c) = a*(3(b+c+2)+bc) = 3(a+(3(b+c+2)+bc)+2)+a(3(b+c+2)+bc) = 3(a+3b+3c+bc+8+ab+ac+2a)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc = (a*b)*c 故*运算满足结合律。 （3）任选a ∈Z ，(-2)*a=a 且a*(-2)=a ，所以-2是(Z,*)的幺元。 所以（Z,*）是独异点。 7、因为1为(A,*)运算的幺元，而且对任意A 的子集A ’,*在A ’上都是封闭和可结合的运算，因此，（A,*）的所有子独异点为(A ’,*)，其中A ’必须包含1。即：(A,*)的所有子独异点为： ({1},*),({1,2},*),({1,3},*),({1,4},*),({1,2,3},*),({1,2,4},*),({1,3,4},*),({1,2,3,4},*) P105：3、4、13 3、??????1100b a ×??????220 0b a ＝??? ?? ?212100b b a a ,a 1,a 2∈{1,-1}, 所以a 1×a 2∈{1,-1}，b 1×b 2∈{1,-1}。 故（G,×）是封闭的。 而 (??????1100b a ×??????2200b a )×??????3300b a =??????212 100b b a a ×????? ?3300b a =??????3213 2100b b b a a a ??????1100b a ×(????? ?22 00b a ×??????3300b a )=??????1100b a ×??????323 200b b a a =??????3213210 0b b b a a a 故（G,×）是可结合的。（也可以说因为矩阵乘法是可结合的。）
目录 摘要................................................................................ I Abstract........................................................................... I 1 引言 (1) 2 知识方面的联系 (1) 2．1多项式理论的应用 (1) 2．2行列式的应用 (2) 2．3柯西不等式的应用 (3) 2．4二次型的应用 (4) 3 思想方面的联系 (4) 3．1符号化思想 (4) 3．2分类思想 (5) 3．3化归与转化思想 (5) 3．4结构思想 (6) 3．5公理化方法 (6) 3．6坐标方法 (6) 3．7构造性方法 (7) 4 观念方面的联系 (7) 结束语 (8) 参考文献 (8)
致谢 (10)
摘要：运用高等代数的理论、方法、思想与观点剖析和阐述中学数学相关内容的若干问题，通过若干典型试题的解析，从知识方面、思想方面以及观念方面研究了高等代数与中学数学的联系，探索高等数学观点对中学数学一些教学内容的理论依据，深化与发展高等代数在中学数学的相关内容，促进高等代数在中学数学领域的应用，探求二者的内在的联系，以便高等代数能与中学数学完美的结合． 关键词：高等代数；中学数学；数学思想方法；应用 Abstract: The problems related to elementary mathematics are analyzed and explained by using the theory，method，thoughts and views of higher algebra．Through analyzing some typical test questions，the relation between higher algebras and elementary mathematics are investigated from the aspects of knowledge、thought and idea. Exploring the higher mathematics view to middle school mathematics some teaching content theory and model，deepening and development in higher algebra in middle school mathematics related content，and promote higher algebra in the middle school mathematics field of application，and to explore the inner link，so that higher algebra can be combined with the middle school closely．Keywords: higher Algebra；middle school mathematics；mathematical thinking；application
组合数学论文 现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好像是有思维的。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。 广义的组合数学就是离散数学，离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。 狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。 组合数学中有几个著名的问题： 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。 船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？ 这是线性规划的问题。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。 货郎问题：一个货郎要去若干城镇卖货，然后会到出发地，给定各个城镇之间的旅行时间，应怎么样计划他的路线，使他可以去每个城镇而且所用的时间最短。这个问题至今都没有有效的算法。 这几个问题将组合数学研究的问题具体表现出来，同时也可以看出他在我们生活中有着很重要的地位。 组合数学中主要可以分成以下几个部分：排列组合与容斥原理、二项式定理、递推关系与生成函数、polya定理。下面我将以这四个部分分别介绍组合数学的各方面问题。 1、排列组合与容斥原理： 排列组合里面的4个重要的基本原理：加法原理、乘法原理、减法原理、除法原理 前面两个最为基本，后面两个是根据前两个派生出来的。乘法原理有的时候的应用很巧妙，可以作为一种打开思路的办法。
第三部分：代数系统 1.在代数系统,S *中，若一个元素的逆元是唯一的，其运算*必定可结合。( ) 2.每一个有限整环一定是域，反之也对。( ) 3.任何循环群必定是阿贝尔群，反之亦真。( ) 4.设(),A ∧∨是布尔代数，则(),A ∧∨一定为有补分配格。( ) 5.设Q 为有理数集，Q 上运算*定义为max(,)a b a b *=，则 ,Q * 是半群。( ) 6.阶数为偶数的有限群中，周期为2的元素的个数一定为偶数。( ) 7.群中可以有零元（对阶数大于一的群）。( ) 8.循环群一定是阿贝尔群。( ) 9.每一个链都是分配格。( ) 1. 对自然数集合N ，哪种运算不是可结合的，运算定义为任,a b N ∈ ( ) A. min(,)a b a b *= B. 2a b a b *=+ C. 3a b a b *=+- D. a b a b *=+ (mod 3) 2. 任意具有多个等幂元的半群，它 ( ) A. 不能构成群 B. 不一定能构成群 C. 不能构成交换群 D. 能构成交换群 3. 循环群33,Z +的生成元为[][]1,2，它们的周期为 ( ) A. 5 B. 6 C. 3 D. 9 4. 设
《离散数学》代数结构部分练习题参考答案 2018年6月 一、填空题 1.在代数系统（N ，+）中，其单位元是0，仅有单位元0有逆元. 2.设A 是非空集合，集合代数),),(( A P 中，)(A P 对运算 的单位元是?，零元是 A.)(A P 对运算 的单位元是A . 3.设Z 为整数集，若1,,-+=∈?b a b a Z b a ，则Z a ∈?，a 的逆元=-1a 2－a . 4.设}3,2,1,0{4=Z ，?为模4乘法，即4mod )(xy y x =?，4,Z y x ∈?.则4Z 上运算?的运算表为.（略） 二、选择题 1.设集合{}10,...,3,2,1=A ,在集合A 上定义运算,不是封闭的为(A ) (A){}b a lcm b a A b a ,,,=?∈?(最小公倍数)(B){}b a ged b a A b a ,,,=?∈?(最大公约数) (C){}b a b a A b a ,max ,,=?∈?(D){} b a b a A b a ,min ,,=?∈?2.在自然数集N 上定义的二元运算?,满足结合律的是 (C )(A)b a b a -=?(B)b a b a 2+=?(C){}b a b a ,max =?(D)b a b a -=?三、解答题 1.通常数的乘法运算是否可以看成是下列集合上的二元运算，说明理由. （1）{}2,1=A （2）{}是质数x x B =（3）{}是偶数x x C =（4）{}N n D n ∈=2解：（1）数的乘法运算不是集合A 上的二元运算.因为A ?=?422（2）数的乘法运算不是集合B 上的二元运算.因为质数与质数的乘积不是质数. （3）数的乘法运算是集合C 上的二元运算.因为偶数乘偶数是偶数. （4）数的乘法运算是集合D 上的二元运算.因为D n m m n ∈=?+222. 2.实数集R 上的下列二元运算是否满足结合律与交换律？
组
合
数
学
Combinatorics
马昱春 MA Yuchun myc@https://www.doczj.com/doc/bc2939548.html,
1
组
合
数
学
Combinatorics
组合数学:有人认为广义的组合数学就是离散数学，也有人认 为离散数学是狭义的组合数学和图论、代数结构、数理逻辑 等的总称。但这只是不同学者在叫法上的区别。总之，组合 数学是一门研究离散对象的科学。
https://www.doczj.com/doc/bc2939548.html,/zh-cn/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6
Combinatorics: Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics.
https://www.doczj.com/doc/bc2939548.html,/wiki/Combinatorics 2
组合数学与离散数学
? 狭义的组合数学主要研究满足一定条件的组态（ 也称组合模型）的存在、计数以及构造等方面的 问题。
– 组合数学的主要内容有组合计数、组合设计、组合矩 阵、组合优化等。
? 离散数学(Discrete mathematics)是数学的几个分 支的总称，以研究离散量的结构和相互间的关系 为主要目标，其研究对象一般地是有限个或可数 无穷个元素；因此它充分描述了计算机科学离散 性的特点。
– 离散数学通常研究的领域包括：数理逻辑、集合论、 关系论、函数论、组合学、代数系统与图论。 。
3
一、填空 1.下列集合中， 对普通加法和普通乘法都封闭。 （ ） （A ）{}1,0 （B ）{}2,1 （C ）{}N n n ∈2 （D ）{} N n n ∈2 2、在自然数集N 上，下面哪种运算是可结合的？ （ ） （A ）b a - （B ）),max(b a （C ）b a 2+ （D ）b a - 3、有理数集Q 关于下列哪个运算能构成代数系统？ （ ） （A ）b a b a =* （B ）()1ln 22++=*b a b a （C ）()b a b a +=*sin （D ）ab b a b a -+=* 4、下列运算中，哪种运算关于整数集I 不能构成半群？ （ ） （A ）()b a b a ,max =* （B ）b b a =* （C ）ab b a 2=* （D ）b a b a -=* 5．设代数系统?A ，·?，则（ ）成立. A ．如果?A ，·?是群，则?A ，·?是阿贝尔群 B ．如果?A ，·?是阿贝尔群，则?A ，·?是循环群 C ．如果?A ，·?是循环群，则?A ，·?是阿贝尔群 D ．如果?A ，·?是阿贝尔群，则?A ，·?必不是循环群 6．设?L ,∧∨,?是格，?L ，≤?是由这个格诱导的偏序集，则（ ）不成立. A ．对任意a L b a ,,∈≤b b a b =∨? B ．∧∨对是可分配 C ．∧∨,都满足幂等律 D ．?L,≤?的每对元素都有最小上界与最大下界 7．在下列四个哈斯图表示的偏序集中（ ）是格.
8. 已知偏序集的哈斯图，如图所示，是格的为( ) 9. 6阶有限群的任何子群一定不是（）。 (A) 2阶(B) 3 阶(C) 4 阶(D) 6 阶 10. 下列哪个偏序集构成有界格（） (1) （N,≤）(2) （Z,≥） (3) （{2,3,4,6,12},|（整除关系））(4) (P(A),?) 11. 下面代数系统中（G、＊）中（）不是群 A、G为整数集合＊为加法 B、G为偶数集合＊为加法 C、G为有理数集合＊为加法 D、G为有理数集合＊为乘法 12. 设
组合数学作业 第一章引言 Page 13, ex3,4,7,30 ex3. 想象一座有64个囚室组成的监狱，这些囚室被排列成8 8棋盘。所有相邻的囚室间都有门。某角落处意见囚室例的囚犯被告知，如果他能够经过其它每一个囚室正好一次之后，达到对角线上相对的另一间囚室，那么他就可以获释。他能获得自由吗？ 解：不能获得自由。 方法一：对64个囚室用黑白两种颜色染色，使得横和竖方向相邻的囚室颜色不同。则对角线上两个囚室颜色为同黑或同白。总共偶数个囚室，若能遍历且不重复，则必然是黑出发白结束，矛盾。 方法二：64个囚室，若要经过每个囚室正好一次，需要走63步，即奇数步。 不妨假设该囚犯在第1行第1列，那么到第8行第8列，横着的方向需要走奇数步，竖着的方向需要走奇数步，即总共需要偶数步。 所以不能恰好经过每个囚室一次到达对角线上的囚室。 ex4. (a) 设f(n)是用多米诺牌(2-牌)对2×n棋盘作完美覆盖的个数。估计一下f(1),f(2),f(3),f(4)和f(5). 试寻找(或证明)这个计数函数f满足的简单关系。利用这个关系计算f(12)。 (b) 设g(n)是用多米诺牌(2-牌)对3×n棋盘作完美覆盖的个数。估计g(1),g(2),…,g(6). 解：(a) f(1)=1, f(2)=2, f(3)=3, f(n+2)=f(n+1)+f(n) f(4)=f(3)+f(2)=5, f(5)=f(4)+f(3)=8 f(6)=f(5)+f(4)=13 f(7)=f(6)+f(5)=21 f(8)=f(7)+f(6)=34 f(9)=f(8)+f(7)=55 f(10)=f(9)+f(8)=89 f(11)=f(10)+f(9)=144 f(12)=f(11)+f(10)=233 (b) g(1)=0, g(2)=3, g(3)=0, g(4)=9+2=11, g(n+4)=4g(n+2)-g(n), g(5)=0, g(6)=41. ex7. 设a和b是正整数，且a是b的因子。证明m×n棋盘有a×b的完美覆盖当且仅当a 既是m又是n的因子，而b是m或n的因子。(提示: 把a×b牌分割成a个1×b牌。) 解：充分性。当a既是m又是n的因子，而b是m或n的因子，则m×n棋盘有a×b的平凡完美覆盖。 必要性。假设m×n棋盘有a×b牌的完美覆盖。则m×n棋盘必有b牌的完美覆盖。根据书中的定理，b是m的因子或n的因子。 下面证明a既是m的因子又是n的因子。 方法一: 因为a是b的因子，所以a×b牌可以分割成b/a个a×a牌。m×n棋盘有a×a的完美覆盖，则必然有a×a牌的完美覆盖。而a×a牌是正方形的，所以只有唯一的一种平凡覆盖方式。从而m是a的倍数，n也是a的倍数。 方法二: 因为a是b的因子，不妨设b=ka。由m×n棋盘有a×b牌的完美覆盖，可任取一个完美覆盖。设第一行的n个方格由p个a×b牌和q个b×a牌盖住，则有n=pb+qa=(pk+q)a，所以n是a的倍数。同理，m也是a的倍数。
如何学好《高等代数》 ——范崇金（哈尔滨工程大学陈赓班高等代数教师） 笔者现承担哈尔滨工程大学陈赓实验班的《高代》课程的教学工作，很早就有很多同学追问笔者，如何才能学好《高代》，虽然笔者在课堂上也简略地谈过此问题，但笔者一直不敢以文字的形式讨论此问题。因为对此没有正确的答案，就如同谈学习方法，一个人认为正确的方法不一定适合他人，对他人甚至是错误或有害的，但鉴于目前同学们的学习状况，也为了应付许多同学给笔者布置的作业，故写点东西，完全从个人角度谈谈如何学习《高代》，未必正确，仅供同学们参考！ 一、认识《高代》课程 学习一门课程，兴趣无疑是极为重要的，但大学中不可能针对每个学生的兴趣安排 课程，许多学生往往要‘被迫’学习许多课程。当然课程也是专家针对专业需要所 安排的，特别是一二年级的重要基础课。对于一门课程，如果对其有一个全面的认 识，对学习也是大有好处的： （1） 从理科角度，如对数学专业、理论物理专业等，《高代》是新生的基础课，是学习许多后续课程的基础。 （2） 从工科角度，《线性代数》（英文是Linear Algebra）是工科学生的重要基础课，《高代》（英文是Advanced Linear Algebra）实际上就是偏理的《线性代 数》。对于线性代数要求较高或偏理的工科，一般以《高代》替代《线代》。 （3） 从应试角度，《高代》是理科硕士研究生的入学必考课程；《线代》也是工科硕士研究生入学考试课程必考的；对于我们大家，《高代》是高学分的必 修课，总不及格. . . ? 二、大学数学课程与中学数学课程的差异 就宏观角度，大学数学与中学数学没有本质差别，但从微观上，大学数学课程与 中学的数学有很大的不同。首先，中学数学很大程度上是数的计算，恒等式的推 演以及少量而简单的不等式推演；从教学角度，中学数学是知识积累型教育，虽 然也渗透数学思想的教育，但不是主线。大学数学课程不仅在内容上比中学数学 要难的多，而且除了特别的计算类数学课程，数的计算在大学数学中虽然也是重 要的，但已经不是主要的，大学数学，特别是偏理的数学课程，更关注于理论、 数学方法和数学思想；在学习一门数学课程时，在积累知识时，更要求学生能从 整体和宏观上认识这门课程中的数学内容和思想方法。 三、高等代数的特点 《高代》是大学数学, 但《高代》与数学分析比又有自身的特点： （1） 《高代》的概念更抽象。在数学分析中, 在引入导数和定积分时, 我们有很直观的几何背景, 初学者容易接受，而《高代》中为什么要引入什么概 念（如向量组的秩、矩阵的秩）往往是后验式的，也就是当我们学习了后 面的内容后才明白为什么要引入此概念，这一点与中学数学大不相同。当 我们将行列式、线性方程组理论、矩阵的矩阵、向量组理论学习完后，再 来整体认识这个理论体系，我们才会明白矩阵的秩是它们的灵魂。 （2） 《高代》中的推理多数是逻辑运算。在任何数学理论中，逻辑运算都是不
信息科学技术学院2003-2004学年第二学期 本科生期末考试试卷 一、（每小题3分,共18分）判断以下命题的真假.如果为真在后面括弧内打 √，否则打?. 1．A ={x |x ∈N 且(x ,5)=1}，则构成代数系统，+为普通加法 （ ） 2．?x , y ∈R ，x o y =|x -y |，则0为
一、离散数学介绍 离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 离散数学常常被分成三门课程进行教学，即集合论与图论、代数结构与组合数学、数理逻辑。 其中各部分内容在本书中又有如下涉及： 1．集合论部分：集合及其运算(3.1)、二元关系(3.2)与函数(3.5)、自然数及自然数集、集合的基数注：集合这个概念比较了解，在数学上，基数(cardinal number)也叫势(cardinality)，指集合论中刻画任意集合所含元素数量多少的一个概念。这是康托尔在1874年～1884年引入最原始的集合论（现称朴素集合论）时, 给出的基数概念。他最先考虑的是集合{1,2,3} 和 {2,3,4}，它们并非相同，但有相同的基数。 那何谓两个集合有相同数目的元素？ 康托尔的答案，是所谓一一对应，即把两个集合的元素一对一的排起来，若能做到，两个集合的基数自然相同。 这个答案虽然简单，却起到了革命性的作用，因为用相同的方法即可比较任意集合，包括无穷集合的大小。 2．图论部分(第5章)：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配
集、覆盖集、独立集与匹配、带权图及其应用3．代数结构部分（第6、7章）：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数4．组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理 组合数学在本书中没有介绍，而关于组合数学的问题却是十分有趣的，可以供大家思考一下。 组合数学中的著名问题 ?计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆的。 ?地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是 否总共只需四种颜色？这是图论的问题。 ?船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、 狼就会吃羊。船夫的船每次只能运送一种东西。 怎样把所有东西都运过河？这是线性规划的问 题。 ?中国邮差问题：由中国组合数学家 ?管梅谷教授① ?提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全 问题，存在多项式复杂度算法：先求出度为奇数 的点，用匹配算法算出这些点间的连接方式，然 后再用欧拉路径算法求解。这也是图论的问题。 ?任务分配问题（也称婚配问题）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时 间都不同。每个员工只分配一项任务。每项任务 只被分配给一个员工。怎样分配员工与任务以使 所花费的时间最少？这是线性规划的问题。 ?如何构作幻方。
《离散数学》代数系统 1.以下集合和运算是否构成代数系统？如果构成，说明该系统是否满足结合律、交换律？求出该运算的幺元、零元和所有 可逆元素的逆元. 1)P(B)关于对称差运算⊕，其中P(B)为幂集. 构成代数系统；满足结合律、交换律；幺元φ；无零元；逆元为自身。 2)A={a,b,c}，*运算如下表所示：构成代数系统；满足结合律、交换律；无幺元；无逆元；零元b. 2.设集合A={a,b}，那么（1）在A上可以定义多少不同的二元运算？（2）在A上可以定义多少不同的具有交换律的二元 运算？24个不同的二元运算；23个不同的具有交换律的二元运算 3.设A={1,2},B是A上的等价关系的集合. 1)列出B的元素. 2元集合上只有2种划分，因此只有2个等价关系，即B={I A，E A} 2)给出代数系统V=
从高等代数看中学数学 高等代数是大学数学专业的主干专业基础课,是初等代数的继续和提高。高中新课改形势下的师范院校数学系的学生,经常面临着怎样运用所学的大学数学知识指导中学数学这个老大难的问题。因此,在教学中应该注意联系中学教学实际,引导学生在中学知识和大学知识之间架起一座桥梁,从而顺利实现思维方式和学习方法的过渡和转变,指导学生、也是未来的中学数学教师能利用课程的理论、方法与观点去剖析中学数学的方法问题,有利于帮助他们融会贯通中学数学的相关内容,提高解决中学数学问题的能力,高屋建瓴地深刻理解中学数学有关内容的来龙去脉,知其然且知所以然,培养较高层次的数学素质,为今后的教学实践打下专业基础。同时,反过来也有利于激发学习兴趣,促进知识深化。下面将从数学知识、数学思想方法、数学观念等方面发掘高等代数与中学数学的联系。 一线性方程组理论的应用 1.关于消元法与解的结构。线性方程组的理论是线性代数的重要理论结果,它是中学数学方程组求解方法的理论化与规范化。线性方程组是否有解、有解时解的数量、通解的公式表示、解的几何意义等一系列问题都得到了圆满的解决,体现了高等代数相对于初等代数的新观点、新思想、新方法的优越性,对中学数学教学具有高屋建瓴的指导作用。消元法是中学数学求解二(三)元一次方程组的基本方法,在高等代数中可以得到理论上的完美解释,即由于线性方程组的初等变换保持同解性,所以消元法可行,而且消元法的实质是反复对方程组作初等变换,或者说消元法是对线性方程组的增广矩阵作行的初等变换的过程。并且,根据线性方程组解的理论容易知道解的只有三种情况(唯一解、无解、无穷多解)以及具体判定方法和解的结构特征。特别地,在一定条件下,方程组的唯一解可以用公式形式给出,即Cramer法则。Cramer法则的意义主要在于:明确了解的存在性与唯一性,为判断这类方程组的有解性提供了比较直接的方法;将求解问题,转化为行列式的计算,避免了消元法的繁琐计算;以公式的形式给出了解与系数的明显关系,为一般线性方程组公式解的表达式提供了理论依据。 2.几个平面共点、共线、平行与重合的问题。利用线性方程组的理论容易解决平面共点、共线、平行与重合的问题。 实际上,平面族交于一点的条件是对应的方程组有唯一解,相当于系数矩阵与增广矩阵的秩都等于3;平面族共线的条件是系数矩阵与增广矩阵的秩都等于2;平面族过同一平面(重合)的条件是系数矩阵与增广矩阵的秩都等于1;平面族互相平行的条件是对应的方程组无解,相当于系数矩阵与增广矩阵的秩不相等。此外线性方程组理论还可解决直角坐标平面上四点共圆或者过不共线的三点的圆的方程等问题。 二向量线性关系的几何意义 向量思想体现了数学的抽象性与严谨性,反过来又展示了应用广泛性的特点,向量之间的线性相关性有着明显的几何意义。 一维情况:非零向量a与向量e共线(平行)的充要条件是a可由e线性表示。更一般的,两个向量共线(平行)的充要条件是它们线性相关。 二维情况:向量a与不共线的两个向量e1,e2共面的充要条件是a可由e1,e2线性表示。更一般的,三个向量共面的充要条件是它们线性相关。
第12卷第3期 数 学 教 育 学 报 Vol.12, No.3 2003年8月 JOURNAL OF MA THEMA TICS EDUCA TION Aug., 2003 收稿日期：2003–06–15 从数学方法论看高等代数与中学数学的多种联系 侯维民 （天水师范学院 数学系，甘肃 天水 741001） 摘要：高等数学类课程在知识上是中学数学的继续和提高，在思想方法上是中学数学的因袭和扩张，在观念上是中学数学的深化和发展．高等代数与中学数学在思想方法方面的联系主要体现在抽象化思想、分类思想、结构思想、类比推理思想、公理化方法等方面．注意与中学数学的联系对比不但可以降低高等代数课的学习难度，而且增强了高等代数课对培养中学数学教师的指导作用． 关键词：高等代数；中学数学；数学知识；数学思想方法；数学观念 中图分类号：G421 文献标识码：A 文章编号：1004–9894（2003）03–0084–04 数学教育的双专业性不但要求数学教师精通较多的数学知识，具备多种数学能力；还要求他们懂得系统的教育理论，练就娴熟的教育技能．为使未来的中学数学教师精通较多的数学知识，具备多种数学能力，高师数学系除开设“中学数学复习与研究”，“中学数学教材教法”等直接指导中学数学教学的课程外，还开设了“数学分析”、“高等代数”等高等数学类的课程．然而，在长期开设高等数学类课程的实践中，一直存在着2方面的问题．一方面由于中学数学知识难以与高等数学知识直接衔接，使不少大一学生一接触到“数学分析”、“高等代数”等课程，就对数学专业课产生了畏难情绪；另一方面，由于高等数学理论与中学教学需要严重脱节，许多高师毕业生对如何用高等数学理论指导中学数学教学感到茫然．为了解决上述长期存在的问题，笔者认为，用数学方法论[1]的望远镜和显微镜来剖析各门高等数学类课程与中学数学的联系是一项有效的措施．不但要挖掘知识体系方面的联系，更要挖掘数学思想方法、数学观念方面的联系．通过这些工作，使师生都清楚地看到：高等数学类课程在知识上是中学数学的继续和提高，在思想方法上是中学数学的因袭和扩张，在观念上是中学数学的深化和发展．这样，学生学习高等数学类课程的难度就会大大降低，高等数学类课程对培养中学数学教师的指导作用也会显著增强． 下面以高等代数课为例[2]，从数学知识、数学思想方法、数学观念3个方面发掘一下高等数学类课程与中学数学的联系． 1 知识方面的联系 这个问题至少可由以下6点说明． （1）中学代数讲多项式的加、减、乘、除运算法则．高等代数在拓宽多项式的含义，严格定义多项式的次数及加法、乘法运算的基础上，接着讲多项式的整除理论及最大公因式理论． （2）中学代数给出了多项式因式分解的常用方法．高等代数首先用不可约多项式的严格定义解释了“不可再分”的含义，接着给出了不可约多项式的性质、唯一因式分解定理及不可约多项式在3种常见数域上的判定． （3）中学代数讲一元一次方程、一元二次方程的求解方法及一元二次方程根与系数的关系．高等代数接着讲一元n 次方程根的定义，复数域上一元n 次方程根与系数的关系及根的个数，实系数一元n 次方程根的特点，有理系数一元n 次方程有理根的性质及求法，一元n 次方程根的近似解法及公式解简介． （4）中学代数讲二元一次、三元一次方程组的消元解法．高等代数讲线性方程组的行列式解法和矩阵消元解法、讲线性方程组解的判定及解与解之间的关系． （5）中学代数学习的整数、有理数、实数、复数为高等代数的数环、数域提供例子．中学代数学习的有理数、实数、复数、平面向量为高等代数的向量空间提供例子．中学代数中的坐标旋转公式成为高等代数中坐标变换公式的例子． （6）中学几何学习的向量的长度和夹角为欧氏
第八章 代数系统 习题8.1 1．解 ⑴是，⑵不是，⑶是，⑷不是。 2．解 若﹡对 是可分配的，则有任意a,b,c ∈* I ,均有 a ﹡( b c)=(a ﹡b) (a ﹡c)= a b a c =( a b ? a c )= a b+c 而a ﹡(b c)=a ﹡(b ?c)= a b ?c ≠a b+c 故﹡对 是不可分配的。 3．解 ⑴对于任意A ∈P(S), 因为A ?S ，所以，A ?S =S ，因此，S 是关于?运算的零元； ⑵对于任意A ∈P(S), 因为A ?S ，所以，A ?S = A ，因此，S 是关于?运算的零元单。 4．解 ⑴①因为x*y=xy-2x-2y+6，则y*x=yx-2y-2x+6= x*y ，满足交换律； ②任意x,y,z ∈R 有 x*(y*z)=x*(yz-2y-2 z +6)=x(yz-2y-2 z +6)-2x-2(yz-2y-2z+6)+6 =xyz-2xy-2xz+6x-2x -2yz+4y+4z-12+6= xyz-2xy-2xz-2yz+4x+4y+4z-6. (x*y)*z=(xy-2x-2y+6) *z =(xy-2x-2y+6)z-2(xy-2x-2y+6)-2z+6 =xyz-2xz-2yz+6z-2xy+4x+4y-2z-6=x*(y*z). 故满足结合律。 (2) ①设任意a ∈R,存在e ∈R,要e*a= ea-2e-2a+6=a ，由于a 的任意性则e=3。 因此e=3是其单位元; ②设任意b ∈R, z ∈R ，要有z*b= zb-2 z-2b+6= z ，由于b 的任意性则z=2，因此 z=2是其零元。 （3）因为*是满足交换律，对于x ∈R ，要存在1 -x ∈R ，须有x*1 -x = x 1 -x -2x-21 -x +6= e=3, 当x ≠2 时，2 321 --= -x x x 。即对于任意的x ，当x ≠2时x 都是可逆的，且2 321 --= -x x x 。 5．解 f 1,f 2,f 3都满足交换律，f 4满足等幂率，f 2有单位元a ，f 1有零元a ，f 3有零元b 。 习题8.2 1．解 构成代数系统的运算有（2），（3），（4）。 2．解 >⊕<>⊕<>⊕<444},3,2,1,0{,},2,0{,},0{ 1f b a a a a a b a 2f b a b a a b b a 3f b a a b a a b a 4f b a b a b a b a 表8-2