离散数学课件(第5章).ppt

《离散数学课件(第5章).ppt》由会员分享，可在线阅读，更多相关《离散数学课件(第5章).ppt（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学教案教案计算机科学与技术学院计算机科学与技术学院课程学时：课程学时：64主主 讲：宋讲：宋 成成河南理工大学河南理工大学电子教案电子教案 本篇用代数方法来研究数学结构，故本篇用代数方法来研究数学结构，故又叫代数结构，它将用抽象的方法来研究又叫代数结构，它将用抽象的方法来研究集合上的关系和运算。集合上的关系和运算。代数的概念和方法已经渗透到计算代数的概念和方法已经渗透到计算机科学的许多分支中，它对程序理论，数机科学的许多分支中，它对程序理论，数据结构，编码理论的研究和逻辑电路的设据结构，编码理论的研究和逻辑电路的设计已具有理论和实践的指导意义计已具有理论和实践的指导意义 本篇讨论

2、一些典型的代数系统及其性本篇讨论一些典型的代数系统及其性质。质。第三篇：代数系统第三篇：代数系统第五章：代数结构第五章：代数结构5.1 代数系统的引入代数系统的引入5.2 运算及其性质运算及其性质5.3 半群半群5.4 群与子群群与子群5.5 阿贝尔群和循环群阿贝尔群和循环群5.6*陪集与拉格朗日定理陪集与拉格朗日定理 5.7 同态与同构同态与同构5.8 环与域环与域第五章：代数结构第五章：代数结构教学目的及要求：教学目的及要求：深刻理解和掌握代数系统的基本概念和运算深刻理解和掌握代数系统的基本概念和运算教学类容：教学类容：代数系统的引入、运算及性质、半群、群与子群、代数系统的引入、运算及性质

3、、半群、群与子群、阿贝尔群和循环群、陪集与拉格朗日定理阿贝尔群和循环群、陪集与拉格朗日定理、同态、同态与同构、环和域。与同构、环和域。教学重点：教学重点：群、环、域的概念及运算，同态和同构。群、环、域的概念及运算，同态和同构。教学难点：教学难点：同态与同构同态与同构 的概念。的概念。第五章：代数结构第五章：代数结构5.1 代数系统的引入代数系统的引入1、运算、运算【定义定义5.1.1】设设A是非空集合，一个从是非空集合，一个从An到到B的的映射映射,称为集合称为集合A上的上的n元运算。简称为元运算。简称为n元运算。元运算。如果如果B A，则称该则称该n元运算是封闭的。元运算是封闭的。在定义在定

4、义5.1中，当中，当n=1时，时，f称为集合称为集合A上的一上的一元运算；当元运算；当n=2时，时，f称为集合称为集合A上的二元运算。上的二元运算。在讨论抽象运算时，在讨论抽象运算时，“运算运算”常记为常记为“*”、“”等。设等。设*是二元运算，如果是二元运算，如果a与与b运算得到运算得到c，记作，记作a*b=c；若；若*是一元运算，是一元运算，a的运算结果记的运算结果记作作*a或或*(a)。第五章：代数结构第五章：代数结构 设设A=1,a,，其中，其中，a是非零实数。是非零实数。f定义为：定义为：a A，f(a)=。容易看出容易看出f是是A上的一元运算。上的一元运算。又如，又如，f：m,n

5、N，f(m,n)=mn，f是自然数集合是自然数集合N上上的二元运算，它就是普通加法运算。普通减法也是自然数的二元运算，它就是普通加法运算。普通减法也是自然数集合集合N上的二元运算，但是它不是封闭的，因为两个自然数上的二元运算，但是它不是封闭的，因为两个自然数相减可能得到负数，而负数不是自然数。所以普通的减法相减可能得到负数，而负数不是自然数。所以普通的减法不是自然数集合不是自然数集合N上封闭的二元运算。上封闭的二元运算。通过以上讨论可以看出，一个运算是否为集合通过以上讨论可以看出，一个运算是否为集合A上的封上的封闭运算必须满足以下两点：闭运算必须满足以下两点：A中任何元素都可以进行这种运算，且

6、运算的结果是中任何元素都可以进行这种运算，且运算的结果是惟一的。惟一的。A中任何元素的运算结果都属于中任何元素的运算结果都属于A。A中任何元素的运中任何元素的运算结果都属于算结果都属于A通常通常称为运算在称为运算在A是封闭的。是封闭的。【例例5.1】设设N为为自自然然数数集集合合，*和和 是是NN到到N映映射射，规规定为：定为：m,n N，m n=min m,n m n=max m,n 则则 和和 是是N上的二元封闭运算。上的二元封闭运算。【例例5.2】设设Nk=0,1,k-1。Nk上上的的二二元元运运算算+k定定义义为：对于为：对于Nk中的任意两个元素中的任意两个元素i和和j，有有 称二元运

7、算称二元运算+k为模为模k加法。加法。第五章：代数结构第五章：代数结构称二元运算称二元运算k为模为模k的乘法。的乘法。模模k加法加法+k和模和模k乘法乘法k是两种重要的二元运算。是两种重要的二元运算。在在N7=0,1,2,3,4,5,6 中中，有有4+72=6，4+75=2。如如果果把把N7中中的的元元素素：0，1，2，3，4，5，6分分别别看看作作是是：星星期期日日、星星期期一一、星星期期二二、星星期期三三、星星期期四四、星星期期五五、星星期期六六。那那么么4+72=6可可解解释释为为：星星期期四四再再过过两两天天后后是是星星期期六六；4+75=2可可解解释释为为：星星期期四四再再过过五五天

8、天后后是是星星期期二二。这这是是模模7加加法法实实际际意义的一种解释。意义的一种解释。Nk上上的的二二元元运运算算k定定义义为为：对对于于Nk中中的的任任意意两两个个元元素素i和和j，有有 第五章：代数结构第五章：代数结构第五章：代数结构第五章：代数结构2.运算的表示运算的表示 表示运算的方法通常有两种：解析公式和运算表。表示运算的方法通常有两种：解析公式和运算表。解析公式是指用运算符号和运算对象组成的表达式。如解析公式是指用运算符号和运算对象组成的表达式。如 f(a)=，运算表是指运算对象和运算结果构成的二维表。运算表是指运算对象和运算结果构成的二维表。经经常常使使用用运运算算表表来来定定义

9、义有有限限集集合合上上的的二二元元运运算算，特特别别当当有有限限集集合合上上的的二二元元运运算算不不能能用用表表达达式式简简明明地地表表示示时时，借借助助于于运运算算表表来来定定义义二二元元运运算算会会带带来来方方便便。另另外外，运运算算表表还还便便于于对对二二元元运运算算的的某某些性质进行讨论，更形象地了解二元运算的有关特征。些性质进行讨论，更形象地了解二元运算的有关特征。设设N4=0,1,2,3，N4上上的的模模4加加法法4可可以以用用运运算算表表表表示示，它它的的运运算算表表如如表表5.1所所示示。N4上上的的模模4乘乘法法4也也可可以以用用运运算算表表表表示示，它它的运算表如表的运算表

10、如表5.2所示。所示。表5.1+4012300123112302230133012表5.2 4012300000101232020230321第五章：代数结构第五章：代数结构 3 代数系统代数系统 【定定义义5.1.2】一一个个非非空空集集合合A连连同同若若干干个个定定义义在在该该集集合合上上的的运运 算算 1,2,k所所 组组 成成 的的 系系 统统 称称 为为 一一 个个 代代 数数 系系 统统，记记 作作。根据定义根据定义5.1.2，一个代数系统需要满足下面两个条件：，一个代数系统需要满足下面两个条件：有一个非空集合有一个非空集合A。有一些定义在集合有一些定义在集合A上的运算。上的运算。

11、集集合合和和定定义义在在集集合合A上上的的运运算算是是一一个个代代数数系系统统的的两两个个要要素素，缺一不可。缺一不可。【例例5.3】设设B是是一一个个集集合合，A=P P(B)是是A幂幂集集合合。集集合合的的求求补补运运算算是是A上上的的一一元元运运算算，集集合合的的并并和和交交运运算算是是A上上的的是是二二元元运运算算。于是于是构成一个代数系统，该代数系常称为集合代数。构成一个代数系统，该代数系常称为集合代数。【例例5.4】设设R-0 是是全全体体非非零零实实数数集集合合，*是是R-0 上上二二元元运运算，定义为：算，定义为：a,b R-0，a*b=b。则则是代数系统。是代数系统。第五章：

12、代数结构第五章：代数结构5.2二元运算的性质二元运算的性质 5.2.1运算的基本性质运算的基本性质 1.1.交换律交换律 【定定义义5.2.1】设设*是是非非空空集集合合A上上的的二二元元运运算算，如如果果对对于于任任意意的的a,b A，有有a b=b a，则则称称二二元元运运算算 在在A上上是是可可交交换换的的，也也称二元运算称二元运算*在在A上满足交换律。上满足交换律。例如，设例如，设R为实数集合，对于任意的为实数集合，对于任意的a,b R，规定规定 a b=(ab)2 a b=a2+b2 ab=a+bab则运算则运算、和和都是可交换的。都是可交换的。2.结合律结合律 【定定义义5.2.2

13、】设设*是是非非空空集集合合A上上的的二二元元运运算算，如如果果对对于于任任意意的的a,b,c A，有有(a*b)*c=a*(b*c)，则则称称二二元元运运算算*在在A上上是是可可结结合的，也称二元运算合的，也称二元运算 在在A上满足结合律上满足结合律第五章：代数结构第五章：代数结构 实数集合上的普通加法和乘法是二元运算，满足结合律；实数集合上的普通加法和乘法是二元运算，满足结合律；矩阵的加法和乘法也是二元运算，也满足结合律。矩阵的加法和乘法也是二元运算，也满足结合律。【例例5.5】设设*是是非非空空集集合合A上上的的二二元元运运算算，定定义义为为：a,b A，a b=b。证明运算证明运算*是

14、可结合的。是可结合的。证明：证明：对于任意的对于任意的a,b,c A，有有(a b)c=c，而而a(b c)=a c=c，故故有有(a b)c=a(b c)，即运算即运算 是可结合的。是可结合的。当二元运算当二元运算*在在A上适合结合律时，在只有该运算符的上适合结合律时，在只有该运算符的表达式中，表示运算顺序的括号常被省略。所以将表达式中，表示运算顺序的括号常被省略。所以将(x*y)*z=x*(y*z)常写成常写成x*y*z。这样，可以令这样，可以令 第五章：代数结构第五章：代数结构 当运算当运算*满足结合律时，满足结合律时，an的也可以递归定义如下：的也可以递归定义如下：a1=a an+1=

15、an a 由此利用数学归纳法，不难证明下列的公式：由此利用数学归纳法，不难证明下列的公式：am an=am+n (am)n=amn 3.分配律分配律 【定定义义5.2.3】设设*和和 是是非非空空集集合合A上上的的两两个个二二元元运运算算，如如果对于任意果对于任意a,b,c A，有有a*(b c)=(a*b)(a*c)(左分配律左分配律)(b c)*a=(b*a)(c*a)(右分配律右分配律)则称运算则称运算*对运算对运算 是可分配的。也称运算是可分配的。也称运算*对运算对运算 满足分配满足分配律律。第五章：代数结构第五章：代数结构 【例例5.6】设设A=0,1，*和和 都都是是A上上的的二二

16、元元运运算算，定定义为：义为：0 0=1*1=0，0*1=1*0=1 0 0=0 1=1 0=0，1 1=1 则则容容易易验验证证 对对于于运运算算*是是可可分分配配的的，但但*对对于于运运算算 是是不不可可分分配的。如配的。如1*(0 1)=10=(1*0)(1*1)【定定理理5.2.1】设设*和和 是是非非空空集集合合A上上的的两两个个二二元元运运算算，*是是可可交交换换的的。如如果果*对对于于运运算算 满满足足左左分分配配律律或或右右分分配配律律，则运算则运算*对于运算对于运算 是可分配的。是可分配的。证证明明：设设*对对于于运运算算 满满足足左左分分配配律律，且且 是是可可交交换换的的

17、，则对于任意则对于任意a,b,c A，有有 (b c)a=a(b c)=(a b)(a c)=(b a)(c a)即即 (b c)a=(b a)(c a)故故 对于运算对于运算 是可分配的。是可分配的。同理可证另一半。同理可证另一半。第五章：代数结构第五章：代数结构4.4.吸收律吸收律【定定义义5.2.4】设设*和和 是是非非空空集集合合A上上的的两两个个可可交交换换的的二二元元运运算算，如果对于任意如果对于任意a,b A，有，有 a*(a b)=a；a(a*b)=a则称运算则称运算 和和运算运算 满足吸收律。满足吸收律。【例例5.7】设设N为为自自然然数数集集合合，*和和 是是集集合合N上上

18、的的二二元元运运算算，定定义义为：为：a N，b N a*b=max(a,b)，a b=min(a,b)验证运算验证运算*和和 适合吸收律适合吸收律。解解：a N，b N 若若ab，a*(a b)=a*min(a,b)=a*b=max(a,b)=a 若若ab，a*(a b)=a*min(a,b)=a*a=max(a,a)=a 若若ab，a*(a b)=a*min(a,b)=a*a=max(a,a)=a 即即 a*(a b)=a 同理可证同理可证a(a*b)=a 因此运算因此运算*和和 适合吸收律。适合吸收律。第五章：代数结构第五章：代数结构 5.幂等律幂等律 【定定义义5.2.5】设设*是是非

19、非空空集集合合A上上的的二二元元运运算算，如如果果对对于于任任意意的的a A，有有a a=a，则则称称运运算算*是是幂幂等等的的或或运运算算 满满足足幂幂等等律律。如如果果A的的某个元素某个元素a满足满足a a=a，则称则称a为运算为运算*的幂等元。的幂等元。易见，集合的并、交运算满足幂等律，每一个集合都是幂等元。易见，集合的并、交运算满足幂等律，每一个集合都是幂等元。由定义由定义5.2.5不难证明下面定理。不难证明下面定理。【定定理理5.2.2】设设 是是非非空空集集合合A上上的的二二元元运运算算，a为为运运算算 的的幂幂等元，对任意的正整数等元，对任意的正整数n，则，则an=a。5.2.2

20、特殊元素特殊元素 1.幺元幺元【定义定义5.2.6】设设 是定义在集合是定义在集合A上的二元运算，如果有一个上的二元运算，如果有一个el A，对于任意的对于任意的a A，有，有el a=a，则称则称el为为A中关于运算中关于运算 的左单位的左单位元或元或左幺元；如果有一个左幺元；如果有一个er A，对于任意的对于任意的a A，有，有a er=a，则称则称er为为A中关于运算中关于运算 的的右右单位元或右幺元；如果在单位元或右幺元；如果在A中有一个元素，它既中有一个元素，它既是左单位元又是右单位元，则称为是左单位元又是右单位元，则称为A中关于运算中关于运算 的单位元或幺元。的单位元或幺元。第五章

21、：代数结构第五章：代数结构 【定定理理5.2.3】设设 是是定定义义在在集集合合A上上的的二二元元运运算算，el为为A中中关关于于运运算算 的的左左幺幺元元，er为为A中中关关于于运运算算 的的右右幺幺元元，则则el=er=e，且且A中的幺元是惟一的。中的幺元是惟一的。证证明明：因因为为el和和er分分别别是是A中中关关于于运运算算 的的左左幺幺元元和和右右幺幺元元，所以所以el=el er=er=e设另一幺元设另一幺元e1 A，则则e1=e1 e=e 2.零元零元 【定义定义5.2.7】设设 是集合是集合A上的二元运算，如果有一个上的二元运算，如果有一个l A，对于任意的对于任意的a A都有

22、都有l a=l，则称则称l为为A中关于运算中关于运算 的左零元；的左零元；如果有一个如果有一个r A，对于任意的对于任意的a A，都有都有a r=r，则称则称r为为A中关于运算中关于运算 的右零元；如果的右零元；如果A中有一个元素中有一个元素 A，它既是左零它既是左零元又是右零元，则称元又是右零元，则称为为A中关于运算中关于运算 的零元。的零元。第五章：代数结构第五章：代数结构 【定定理理5.2.4】设设 是是集集合合A上上的的二二元元运运算算，l为为A中中关关于于运运算算 的的左左零零元元，r为为A中中关关于于运运算算 的的右右零零元元，则则l=r=，且且A中的零元是惟一的。中的零元是惟一的

23、。证证明明：因因为为l和和r分分别别是是A中中关关于于运运算算 的的左左零零元元和和右右零零元，所以元，所以l=l r=r=设另一零元设另一零元1 A，则，则1=1 =【定定理理5.2.5】设设 是是集集合合A上上的的二二元元运运算算，集集合合A中中元元素素的的个数大于个数大于1。如果。如果A中存在幺元中存在幺元e和零元和零元，则，则e。证明：证明：用反证法。设用反证法。设e=，那么对于任意的那么对于任意的a A，必有必有 a=e a=a=，于是于是A中的所有元素都是零元中的所有元素都是零元，与，与A中至少有两个元素矛盾中至少有两个元素矛盾。第五章：代数结构第五章：代数结构 3.逆元逆元 【定

24、定义义5.2.8】设设 是是集集合合A上上的的二二元元运运算算，e为为A中中关关于于运运算算 的的幺幺元元。如如果果对对于于A中中的的元元素素a存存在在着着A中中的的某某个个元元素素b，使使得得b a=e，那那么么称称b为为a的的左左逆逆元元；如如果果存存在在A中中的的某某个个元元素素b，使使得得a b=e，那那么么称称b为为a的的右右逆逆元元；如如果果存存在在着着A中中的的某某个个元元素素b，它它既既是是a的的左左逆逆元元又又是是a的的右右逆逆元元，那那么么称称b为为a的的逆逆元元。a的的逆元记为逆元记为a1。如果如果a A存在逆元存在逆元a1 A，那么称那么称a为可逆元为可逆元。一一般般地

25、地说说，一一个个元元素素的的左左逆逆元元不不一一定定等等于于该该元元素素的的右右逆逆元元。一一个个元元素素可可以以有有左左逆逆元元而而没没有有右右逆逆元元，同同样样可可以以有有右右逆逆元元而而没没有有左左逆逆元元。甚甚至至一一个个元元素素的的左左逆逆元元或或者者右右逆逆元元还还可可以以不不是是惟惟一一的。的。【定定理理5.2.6】设设 为为A中中的的一一个个二二元元运运算算，A中中存存在在幺幺元元e且且每每个个元元素素都都有有左左逆逆元元。如如果果 是是可可结结合合的的运运算算，则则在在A中中任任何何元元素素的的左左逆逆元元必必定定是是该该元元素素的的右右逆逆元元，且且每每个个元元素素的的逆逆

26、元元是是惟惟一一的的。第五章：代数结构第五章：代数结构 证证明明：设设a,b,c A，b是是a的的左左逆逆元元，c是是b的的左左逆逆元元。于于是是(b a)b=e b=b，所以所以 e=c b=c(b a)b)=(c(b a)b =(c b)a)b=(e a)b=a b因此，因此，b也是也是a的右逆元。的右逆元。设元素设元素a有两个逆元有两个逆元b和和d，那么那么b=b e=b(a d)=(b a)d=e d=d故故a的逆元是惟一的。的逆元是惟一的。4.消去律消去律 【定定义义5.2.9】设设 是是集集合合A上上的的二二元元运运算算，为为A中中关关于于运算运算 的零元，的零元，a,b,c A，

27、a。如果如果 若若a b=a c，便便有有b=c，则则称称运运算算 满满足足左左消消去去律律，称称a为运算为运算 的左可消元。的左可消元。若若b a=c a，便便有有b=c，则则称称运运算算 满满足足右右消消去去律律，称称a为运算为运算 的右可消元。的右可消元。第五章：代数结构第五章：代数结构 若若运运算算 既既满满足足左左消消去去律律又又满满足足右右消消去去律律，则则称称运运算算 满满足消去律，称足消去律，称a为运算为运算 的可消元。的可消元。注意可消元注意可消元a不能是零元不能是零元。【定定理理5.2.7】设设 是是A中中可可结结合合的的二二元元运运算算，如如果果a的的逆逆存存在且在且a，

28、则，则a为关于为关于 的可消元。的可消元。证证明明：设设b,c A，且且有有a b=a c或或b a=c a。由由于于 为为可可结合的二元运算、结合的二元运算、a的逆存在且的逆存在且a，则则a 1 (a b)=(a 1 a)b=e b=ba 1 (a c)=(a 1 a)c=e c=c而而 a 1 (a b)=a 1 (a c)于是于是b=c，同理由同理由b a=c a，得得b=c，故，故a为关于为关于 的可消元。的可消元。第五章：代数结构第五章：代数结构 【例例5.8】实实数数集集R上上的的下下列列二二元元运运算算是是否否满满足足结结合合律律和和交换律？交换律？a b=a+bab a b=(

29、a+b)解：解：因为因为 a,b,c R，有有 (a b)c=(a+b-ab)c=(a+b-ab)+c-(a+b-ab)c =a+b+c-ab-ac-bc+abc又又 a(b c)=a(b+c-bc)=a+b+c-bc-a(b+c-bc)=a+b+c-ab-ac-bc+abc所以所以 (a b)c=a(b c)因此运算因此运算 满足结合律。满足结合律。又又 a b=a+bab=b+aba=b a 所以运算所以运算 满足交换律。满足交换律。因为因为 a,b,c R，有有(a b)c=(a+b)c=(a+b)+c)=(a+b+2c)第五章：代数结构第五章：代数结构a(b c)=a (b+c)=(a

30、+(b+c)=(2a+b+c)在一般情况下在一般情况下(a+b+2c)(2a+b+c)所以运算所以运算 不满足结合律。而不满足结合律。而a b=(a+b)=(b+a)=b a所以运算所以运算 满足交换律。满足交换律。【例例5.9】在在例例5.8中中，运运算算*是是否否有有单单位位元元，零零元元和和幂幂等等元？若有单位元，哪些元素有逆元？元？若有单位元，哪些元素有逆元？解：解：运算运算 的定义为：的定义为：a b=a+bab 若若e是是单单位位元元，则则对对任任意意元元素素a R，有有a e=e a=a，由由于于元元素素 是是可可交交换换的的，仅仅考考虑虑e a=a，即即e a=e+aea=a，

31、于于是是eea=0，即即e(1a)=0。由由于于a是是任任意意的的，要要使使上上式式成成立立，只只有有e=0。因此因此0是运算是运算 的单位元。的单位元。第五章：代数结构第五章：代数结构 若若是是零零元元，则则对对任任意意元元素素a R，有有a=a=。仅仅考考虑虑 a=，即即 a=+aa=，于于是是aa=0，即即a(1)=0。由由于于a是是任任意意的的，要要使使上上式式成成立立，只只有有=1。因因此此1是是运运算算 的的零零元。元。若若a R是幂等元，则应有是幂等元，则应有a a=a，即，即a+aa2=a。于是于是aaa=0，即，即a(1a)=0。要使上式成立，只有要使上式成立，只有a=0或或

32、a=1。因此因此0或或1是运算是运算 的幂等元。的幂等元。设设b是是a的的逆逆元元，则则应应有有a b=a+bab=0(的的单单位位元元)，于于是是b=，因因此此对对于于R中中的的任任何何元元素素a(只只要要a1)均均有有逆逆元元，其其逆元是逆元是 。第五章：代数结构第五章：代数结构5.3 半群半群【定义定义5.3.1】一个代数系统一个代数系统，其中，其中S是非空集合，是非空集合，*是是S上的一个二元运算，如果运算上的一个二元运算，如果运算*是封闭的，则称代数系是封闭的，则称代数系统统为广群。为广群。【定义定义5.3.2】设设是代数系统，是代数系统，*是是S上的二元运算，上的二元运算，如果如果

33、*满足结合律，则称代数系统满足结合律，则称代数系统为半群。为半群。【例如例如】代数系统代数系统、R，、和和都是半群。都是半群。半群是一个非空集合和一个定义在其上的可结合二元运算半群是一个非空集合和一个定义在其上的可结合二元运算组成的代数系统。设组成的代数系统。设是半群，如果运算是半群，如果运算*又满足交又满足交换律，则称半群换律，则称半群为可换半群。若为可换半群。若S为有限集合，则为有限集合，则半群半群称为有限半群。称为有限半群。【定理定理5.3.1】设设是半群，是半群，*是是S上的二元运算，上的二元运算，B S，如果，如果*在在B上是封闭的，则上是封闭的，则 B，*也是半群。也是半群。第五章

34、：代数结构第五章：代数结构 证证明明：因因为为*在在B上上是是封封闭闭的的，所所以以*是是B上上的的二二元元运运算算。B,*是是代代数数系系统统。a,b,c B，由由于于B S，所所以以a,b,c S，又又由于由于 S,*是半群，所以是半群，所以(a*b)*c=a*(b*c)，故故 B,*是半群。是半群。【定定义义5.3.3】定定理理5.3.1中中的的半半群群 B,*叫叫做做半半群群 S,*的的子子半群半群。例例如如，因因为为Q R且且乘乘法法在在有有理理数数集集上上是是封封闭闭的的，由由定定理理5.3.1和和定定义义5.3.3，Q,是是 R,的的子子半半群群，所所以以 Q,是是半半群群。类似

35、的可以证明类似的可以证明 N,、0,1,和和(0,1),是半群。是半群。【定定理理5.3.2】设设 S,*是是半半群群，S是是有有限限集集，则则必必有有a S，使使得得a*a=a 证明：证明：b S，由由*在在S上的封闭性知：上的封闭性知：b2=b*b S b3=b2*b S 第五章：代数结构第五章：代数结构 因为因为S是有限集，所以必有是有限集，所以必有ij使使 bi=bj 令令p=ji，则，则p=ji1，而，而j=p i bi=bj=bp+i=bp*bi 于是下式成立：于是下式成立：bq=bp*bq qi 因为因为p=ji1，总可以找到总可以找到k1，使得使得kpi 对于对于S中的元素中的

36、元素bkp，就有就有 bkp=bp*bkp =bp*(bp*bkp)=b2p*bkp =b2p*(bp*bkp)=bkp*bkp 令令a=bkp，a*a=a第五章：代数结构第五章：代数结构 设设I是是正正整整数数集集合合，是是I上上的的普普通通加加法法，加加法法在在正正整整数数集集合合I上上封封闭闭且且适适合合结结合合律律。所所以以 I,是是半半群群。但但因因I是无限集，所以是无限集，所以I中没有幂等元。中没有幂等元。【例例5.3.1】设设R是实数集，定义是实数集，定义R上的二元运算上的二元运算*为：为：x,y R，x*y=x|y|其其中中x|y|为为实实数数x与与实实数数y的的绝绝对对值值的

37、的乘乘法法运运算算，证证明明是是一个半群。一个半群。证明：证明：显然，显然，x,y R，则，则x|y|R，故运算故运算*在在R上封闭。上封闭。接下来只需验证接下来只需验证*满足结合律。满足结合律。x,y,z R，有有 (x y)z=(x y)|z|=(x|y|)|z|=x|y|z|x(y z)=x|y z|=x|y|z|=x|y|z|所以，所以，(x y)z=x(y z)，故，故是一个半群。是一个半群。【定定义义5.3.4】设设 G,*是是半半群群，如如果果运运算算*的的单单位位元元e G，则则称半群称半群 G,*为含幺半群或独异点。为含幺半群或独异点。第五章：代数结构第五章：代数结构 若若

38、G,*为为独独异异点点，且且*是是可可交交换换的的，则则称称 G,*为为可可换换的的独独异点。异点。例例如如，设设A是是任任一一集集合合，P P(A)是是A的的幂幂集集合合。集集合合并并运运算算在在P P(A)上上是是封封闭闭的的，并并运运算算的的单单位位元元P P(A)，所所以以半半群群是是独独异异点点；交交运运算算在在P P(A)上上也也是是封封闭闭的的，交交运运算算的的单单位位元元A P P(A)，所所以以半半群群也也是是独独异异点点。显显然然，并并运算运算和和交交运算运算满足交换律。所以，它们都是可交换独异点。满足交换律。所以，它们都是可交换独异点。【定定理理5.3.3】设设 G,*是

39、是可可交交换换的的独独异异点点，H为为其其所所有有幂幂等等元元的的集合，则集合，则 H,*为独异点。为独异点。证证明明：a,b H，于于是是a*a=a，b*b=b。由由*是是可可交交换换的的，从从而而(a*b)*(a*b)=(a*b)*(b*a)=a*(b*b)*a =a*(b*a)=(a*a)*b=a*b于于是是a*b H，即即*在在H上上封封闭闭，显显然然H G，根根据据定定理理5.3.1，H,*是半群。是半群。因因e*e=e，故，故e H。所以所以 H,*为独异点。为独异点。第五章：代数结构第五章：代数结构【定定理理5.3.4】设设 G,*是是独独异异点点，则则在在*的的运运算算表表中中

40、任任何何两两行行两两列列都不相同。都不相同。证明：证明：先证明任何两列不相同。先证明任何两列不相同。设运算设运算*的单位元是的单位元是e G，x G，y G，xy 因因为为e*x=x，e*y=y，所所以以e*xe*y，这这说说明明e所所在在行行的的元元素素是是两两两两互互不不相相同同的的且且都都是是G的的元元素素。故故在在*的的运运算算表表中中任任何何两两列列是是不不相同的，至少相同的，至少e所在行互不相同。所在行互不相同。类似地可证任何两行是不相同的。类似地可证任何两行是不相同的。【定理定理5.3.5】设设是独异点，是独异点，a,b G且且a,b均有逆元，则均有逆元，则第五章：代数结构第五章

41、：代数结构 (a1)1=a a*b有逆元，且有逆元，且(a*b)1=b1*a1证明：证明：因因a*a1=a1*a=e，故，故(a1)1=a 因因(a*b)*(b1*a1)=(a*(b*b1)*a1 =a*e*a1=a*a1=e又又 (b1*a1)*(a*b)=(b1*a1)*(a*b)=b1*(a1*a)*b=b1*e*b=b1*b=e故故 (a*b)1=b1*a1【定定义义5.3.5】设设是是半半群群，如如果果它它的的每每个个元元素素均均为为G的的某某元元素素a的的某某一一方方幂幂，则则称称半半群群为为由由a所所生生成成的的循循环环半半群，而群，而a称为半群称为半群的生成元素，并记的生成元素

42、，并记(a)。【定理定理5.3.6】一个循环半群一定是可换半群。一个循环半群一定是可换半群。第五章：代数结构第五章：代数结构 证证明明：设设为为由由a所所生生成成的的循循环环半半群群，x,y G，则则x=am，y=an，于是于是x*y=am*an=am+n=an+m=an*am=y*x即即是可换半群。是可换半群。5.4 群与子群群与子群 1、群、群第五章：代数结构第五章：代数结构【定定义义5.4.1】设设 G,*,*是是代代数数系系统统，其其中中，G是是非非空空集集合合，*是是G上二元运算。如果上二元运算。如果 运算运算*在在G上是可结合的。上是可结合的。运算运算*的单位元的单位元e G。x

43、G，有，有x1 G。则称则称 G,*为群。有时也可将群为群。有时也可将群 G,*简称为群简称为群G。根据定义，广群是一个非空集合和一个定义在非空集合根据定义，广群是一个非空集合和一个定义在非空集合的二元运算组成；半群是一个具有结合运算的广群；独异点的二元运算组成；半群是一个具有结合运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异点。是具有幺元的半群；群是每个元素都有逆元的独异点。普普通通加加法法在在I上上是是封封闭闭的的和和可可结结合合的的，在在I中中有有关关于于加加法法的的单单位位元元0，x I，有有x1x I，所所以以 I,是是群群。该该群叫做整数加法群。群叫做整数加法群。第

44、五章：代数结构第五章：代数结构 乘乘法法 在在Q-0 上上也也是是封封闭闭的的和和可可结结合合的的，在在Q-0 中中有有关关于于乘乘法法的的单单位位元元1，x Q-0，有有x1 Q-0，所所以以 Q-0,是群。是群。用用同同样样的的办办法法可可以以证证明明 R,是是群群，其其中中0是是单单位位元元，x R，x1x R。群群 R,叫叫做做实实数数加加法法群群；但但 R,不不是是群群，因因为为对对普普通通乘乘法法，0的的逆逆元元是是不不存存在在的的；而而 R-0,是群，其中是群，其中1是单位元，是单位元，x R-0 0，有，有x1=R-0。【例例5.4.1】设设G e,a,b,c，表表5.3给给出

45、出了了*的的运运算算表表。证证明明 G,*是群。是群。证明证明：由表由表5.3可以看出，可以看出，*运算是封闭的和运算是封闭的和可结合的，在可结合的，在G中有关于中有关于*的单位元的单位元e。G中中每个元素都是自己的逆元，即每个元素都是自己的逆元，即e1=e，a1=a，b1=b，c1=c。所以所以 G,*是群。是群。表5.3*eabceeabcaaecbbbceaccbae第五章：代数结构第五章：代数结构 例例5.4.1中的群中的群 G,*叫做叫做Klein 四元群，简称四四元群，简称四元群。元群。Klein 四元群有以下四元群有以下4个特点：个特点：e为为G中的单位元。中的单位元。*运算是可

46、交换的。运算是可交换的。G中每个元素的逆元都是自己。中每个元素的逆元都是自己。a,b,c三三个个元元素素中中任任何何两两个个元元素素的的*运运算算结结果果都等于第三个元素。都等于第三个元素。由由于于群群G中中有有幺幺元元且且每每一一个个元元素素都都有有逆逆元元，所所以以可可以以定定义义G中中元元素素的的0次次幂幂和和负负整整数数次次幂幂。定定义义x0=e，x G，n I+，定义定义xn(x1)n【定定义义5.4.2】设设是是群群，如如果果G是是有有限限集集，则则称称为为有有限限群群，如如果果G是是无无限限集集，则则称称为为无无限限群群。基基数数|G|称为群称为群的阶数，简称群的阶数，简称群G的

47、的阶。阶。【定理定理5.4.1】群中不可能有零元。群中不可能有零元。证证明明：当当群群的的阶阶为为1 1时时，惟惟一一元元素素为为幺幺元元。设设|G|1 1且且群群,*有零元有零元。那么对群中任何元素那么对群中任何元素x G，都有都有x=x=e，所以，零元所以，零元就不存在逆元，这与就不存在逆元，这与是群相矛盾。是群相矛盾。【定理定理5.4.2】设设是群，对于是群，对于a,b G，必存在惟一的必存在惟一的x G，使得使得a x=b。证明：证明：设设a的逆元是的逆元是a1 1，令，令x=a 1 b，则则 a x=a(a 1 b)=(a a 1)b=e b=b若另有一解若另有一解x1 1，满足满足

48、a x1=b，则，则a 1(a x1)=a 1 b 即即x1=a 1 b=x。第五章：代数结构第五章：代数结构【定理定理5.4.3】设设是群，对于任意的是群，对于任意的a,b,c G，如果有如果有a b=a c或者或者b a=c a，则必有则必有b=c。证明：证明：设设a b=a c，且，且a的逆元是的逆元是a 1，则有则有 a 1(a b)=a 1(a c)(a 1 a)b=(a 1 a)c即即e b=e c，故，故b=c；当当b a=c a时，同样可证得时，同样可证得b=c。“对对于于任任意意的的a,b,c G，如如果果有有a b=a c或或者者b a=c a，则则必必有有b=c。”即即消

49、消去去律律。所所以以，定定理理5.4.3可可理理解解为为：群群中中满足消去律。满足消去律。第五章：代数结构第五章：代数结构【定定理理5.4.4】在在群群中中，除除幺幺元元e外外，不不可可能能有有别别的的幂幂等元。等元。证证明明：因因为为e e=e，所所以以e是是幂幂等等元元。设设a G且且a a=a，则有则有a=e a=(a 1 a)a=a 1(a a)=a 1 a=e 即即a=e。2、子群、子群【定义定义5.4.3】设设是群，是群，H是是G的非空子集，如果的非空子集，如果也构成群，则称也构成群，则称是是的子群。的子群。由由子子群群的的定定义义可可以以看看出出，如如果果H是是G的的非非空空子子

50、集集，考考察察 H,*,*是否是群是否是群 G,*,*的子群，应当验证：的子群，应当验证：运算运算*在在H H上封闭。上封闭。群群G中的幺元中的幺元e H。x H，有有x1 H【定理定理5.4.5】设设是一个群，是一个群，是是的子群，的子群，则则中的幺元中的幺元e必定也是必定也是中的幺元。中的幺元。证明：证明：设设中的幺元为中的幺元为e1，对于任意对于任意a H G，有有e1*a=a=e*a由消去律得由消去律得e1=e。第五章：代数结构第五章：代数结构 如如果果 G,*,*是是群群，其其中中e单单位位元元。e 和和G都都是是G的的非非空空子子集集，e,*,*和和 G,*,*也也都都构构成成群群