离散数学：6-1 代数系统

1、离散数学II 近世代数部分计算机科学与技术专业核心基础课程国家级精品课程Galois(18111832)近世代数的创始人 Born: 25 Oct 1811 in Bourg La Reine (near Paris), FranceDied: 31 May 1832 in Paris, France1789年 -1857年第一个认识到无穷级数论并非多项式理论的平凡推广而应当以极限为基础建立其完整理论的数学家。写了大约800篇论文 傅立叶（1768 1830 ）1817年当选为科学院院士，1822年任该院终身秘书 傅立叶级数 、傅立叶变换热的解析理论 泊松（1781年 -1840年）数学家、几

2、何学家和物理学家泊松定理、泊松公式、泊松方程、泊松分布 第六章 群 与 环123代数系统群的定义子群及其陪集群的同构及同态567环域的特征 素域多项式4有限域86.1 代数系统运算设S是一个非空集合，称SS到S的一个映射f为S的一个二元代数运算，即：对于S中任意两个元素a,b，通过f，唯一确定S中一个元素c：f (a, b)= c，常记为a * b = c。6.1 代数系统运算表*abcaabcbbaccccc代数系统 设S是一个非空集合，f1，fm是S 上的若干代数运算，把S及其运算f1, fm 看成一个整体来看, 叫做一个代数系统，记为（S， f1, , fm）6.1 代数系统交换律定义6

3、.1.2 设*是集合S上的二元代数运算，如果对于S中任意两个元素a，b，等式a * b = b * a都成立，则称运算 * 满足交换律。结合律定义6.1.3 设 * 是集合S上的二元代数运算，如果对于S中任意三个元素a，b，c，等式 (a * b) * c = a * (b * c)都成立，则称运算 * 满足结合律。等幂律定义6.1.4 设 * 是集合S上的二元代数运算，a是S中的元素，如果a * a = a，则称a是关于运算 * 的幂等元。如果S中每个元素都是关于*的幂等元，则称运算*满足等幂律。分配律定义6.1.5 设 * 和 + 是集合S上的两个二元代数运算，如果对于S中任意三个元素a，

4、b，c，等式 a *(b + c)= (a * b)+ (a * c)， (b + c)* a =(b * a)+(c * a）都成立，则称运算 * 对 + 满足分配律。 吸收律定义6.1.6 设 * 和 + 是集合S上的两个二元代数运算，如果对于S中任意两个元素a，b，等式 a * (a + b) = a ， a + (a * b) = a，都成立，则称运算 * 和 + 满足吸收律。消去律定义6.1.7 设 * 是集合S上的二元代数运算,如果对于S中任意三个元素a,b,c,（1）若 a * b = a * c，则b = c，（2）若 b * a = c * a，则b = c，就称 * 满足消

5、去律。第六章 群 与 环123子群及其陪集群的同构及同态567环域的特征 素域多项式4有限域8群的定义代数系统6.2.1 半群定义6.2.1 设G是一个非空集合，若为G上的二元代数运算，且满足结合律，则称该代数系统（G， ）为半群。 6.2.2 群 定义6.2.2 设（G, ）为半群，如果满足下面条件： (1) G中有一个元素1，适合对于G中任意元素a，都 有1a = a1 = a; (2) 对于G中任意a，都可找到G中一个元素a-1，满足aa-1 = a-1a = 1， 则称（G, ）为群。 元素1称为G的单位元素，a-1称为a的逆元素。6.2.3 群 的 性 质定理6.2.1 设(G, )

6、是一个群，则G中恰有一个元素1适合1a=a1=a, 而且对于任意a恰有一个元素a-1适合aa-1=a-1a=1。证明：(反证法）若1和1都是单位元素，则 1=11=1，故1=1。若b和c都是a的逆元素,则 b=b1=b(ac)=(ba)c = 1c = c故b = c. 群的单位元素是唯一的。任意元素的逆也是唯一的。有(a-1)-1=a。定理6.2.2群定义中的条件（1）和（2）可以减弱如下：(1) G中有一个元素左壹适合1a=a;(2) 对于任意a，有一个元素左逆a-1适合a-1a=1。 证明：先证aa-1=1。 因为a-1=1a-1 = (a-1a)a-1，故a-1= (a-1a)a-1。

7、 由(2)， a-1也应该有一个左逆适合ba-1=1。 于是： ba-1=b(a-1a)a-1) =(ba-1)(aa-1) =1(aa-1) = aa-1因此，aa-1=1。再证a1=a。 a1 = a(a-1a) =(aa-1)a = 1a = a证毕。定理6.2.3群定义中的条件（1）和（2）等于下列可除条件：对于任意a，b，有x使x a=b，又有 y使 ay=b。定理6.2.3证明：首先证明在任一群中可除条件成立。取x =ba-1，y=a-1b，即得x a=b，ay=b，故由(1)和(2)可以推出可除条件成立。再证明由可除条件也可以推出(1)、(2)，因而可以推出(1),(2)。任取c

8、 G，令1为适合x c=c的x ，则1c=c。对于任意aG，有y使cy=a，故1a=1(cy)=(1c)y=cy=a，即(1)成立。关于(2)，令a-1为适合x a=1的x ，则a-1a=1。即(2)成立。 定理6.2.4设G是一个群，在一个乘积a1an中可以任意加括号而求其值。证明： 只要证明任意加括号而得的积等于按次序由左而右加括号所得的积(a1a2)a3)an-1)an （1）(1)式对于n=1，2不成问题；对于n=3,由结合律也不成问题。现在对n用归纳法,假定对少于n个因子的乘积（1）式成立.试证对n个因子的乘积（1）式也成立。a1an任意加括号而得到的乘积A，求证A等于(1)式。设在

9、A中最后一次计算是前后两部分B与C相乘： A = （B）（C）定理6.2.4今C的因子个数小于n，故由归纳假设,C等于按次序自左而右加括号所得的乘积（D）an。由结合律，A=(B)(C)=(B)(D)an)=(B)(D)an。但（B）（D）的因子个数小于n，故由归纳假设，（B）（D）等于按次序由左而右加括号所得的乘积 (B)(D)=(a1a2)a3)an-2)an-1因而A =(B)(D)an=(a1a2)a3)an-2)an-1）an即A等于（1）式。注意：当给出二元运算后，若无结合律，则三个以上元素的运算不一定有意义，本定理对有结合律的一切代数系统成立。现在a1an有意义，当它们都相同时，

10、称n个a连乘积为a的n次方，记为an。我们规定a0=1，a-n=(an)-1= (a-1)n对于任意整数m、n，第一指数律 aman=am+n第二指数律 (am)n=amn。定义6.2.3若群(G, )的运算适合交换律，则称(G, )为Abel群或交换群。阿贝尔(18021829)挪威数学家，以证明五次方程的根式解的不可能性和对椭圆函数论的研究而闻名。 1823年当阿贝尔的第一篇论文发表.1824年他发表了他的一元五次方程没有代数一般解的论文 .在一个Abel群(G，)中，一个乘积可以任意颠倒因子的次序而求其值。证明：考虑一个乘积a1an。设是1，n上的一个一对一变换，欲证a(1) a(n)=

11、a1an对n用归纳法，n=1时只有一个a1,显然成立，n=2时a1a2 =a2a1定理显然成立，假定n-1时定理成立，试证n时定理亦成立。设将a1an中各因子任意颠倒次序而得一式 P = a(1) a(n) 因子an必在P中某处出现，因而P可以写成 P =（P）an（P）定理6.2.5 P =（P）an（P） P 或P中可能没有元素，但照样适用以下的论证，由交换律， P=P (anP)=P (Pan)=(P P)an， 现在P P中只有n-1个元素a1,an-1,只不过次序有颠倒，故由归纳法假定， P P= a1an-1。 因此,P =（P P）an = a1an-1an，从而归纳法完成，定理

12、得证。 定理6.2.5在Abel群中，有第三指数律：(ab)m=ambm，m为任意整数。加法群如果群G的运算不写作乘而写作加+，则G叫做一个加法群，我们永远假定一个加法群是一个Abel群： a+b=b+a在乘法群中写做1的现在写做0： a+0=a在乘法群中写做a-1而称为a的逆的，现在写做-a而称为a的负： a+(-a)= 0n为任意整数时，在乘法群中写作an而称为a的n次方的，现在写做na而称为a的n倍。三个指数律现在成为下面的形式： ma+na= (m+n)a m(na)=(mn)a m(a+b)= ma+mb， 群的其它结论：(ab)-1= b-1a-1消去律成立其运算表中每一行或每一列

13、中的元素互不相同。存在唯一的幂等元1。一元群、二元群、三元群是唯一的，且都是交换群有限半群中必存在幂等元。含有单位元的半群称为独异点。习题6.21. 设（G,）是代数系统,则（GG,*）是代数系统，这里GG的运算“*”规定如下：（a，b）*（c，d）=（ac，bd），其中:a,b,c,d为G中任意元素。证明：当（G,）是半群时,（GG,*）是半群；当（G,）有单位元素时,（GG,*）有单位元素；当（G,）是群时,（GG，*）是群； 证明：设（G,）是半群,a,b,c,d,e,f为G中任意元素,若有(a,b),(c,d),(e,f)属于GG，则有(a,b)*(c,d)*(e,f)=(a,b)*(

14、ce,df)=(a(ce),b(df)=(ac)e,(bd)f)=(ac),(bd)*(e,f)=(a,b)*(c,d)*(e,f)这就证明了当（G,）是半群时,（GG,*）是半群.设（G,）有单位元素1，(a,b)是（GG,*）中任意元素,则有(a,b)=(a1,b1)=(a,b)*(1,1)且(a,b)=(1a,1b)=(1,1)*(a,b),故(1,1)就是（GG，*）的单位元素。设（G,）是群，1是群（G,）的单位元素，则由前面的证明知(1，1)就是（GG，*）的1且（GG，*）是半群。 我们来证明（GG，*）中的任意元素(a，b)有逆元素。(1，1)=(aa，bb )=(a，b)*(a，b )，其中a和b分别是a和b在群（G， ）中的逆元素。同样有(1，1)=(aa，bb ) =(a，b )*(a，b )，这就证明了(a，b )是(a，b)的逆元素，从而说明（GG，*）是群。 2. 举例说明不要求可除条件而要求消去条件，即要求由ax=ay可推出x=y，由xa=ya可推出x=y，则G不见得是一个群，若G有限怎么样？解：例如，全体自然数在普通乘法下，适合消去律，但不是群。若G=a1，a2，an，用a右乘G中各元