第五章代数系统

1、第三编 代数系统 本篇用代数方法来研究数学结构, ,故又叫代数结构, ,它将用抽象的方法来研究集合上的关系和运算。 代数的概念和方法已经渗透到计算机科学的许多分支中, ,它对程序理论, ,数据结构, ,编码理论的研究和逻辑电路的设计已具有理论和实践的指导意义。 本篇讨论一些典型的代数系统及其性质。 第五章 代数结构5.1代数系统概述代数系统概述5.2运算及其性质运算及其性质5.3半群半群5.4群与子群群与子群第五章 代数结构 教学目的及要求：教学目的及要求： 深刻理解和掌握代数系统的基本概念和运算。 教学内容：教学内容： 代数系统的引入、运算及性质、半群、群与子群。 教学重点：教学重点： 群的

2、概念及运算。5.1 代数系统概述1、代数运算的定义定义1：设A是个非空集合，AA到A的一个映射f，f： AAA称为A上的一个二元代数运算，简称二元运算； A到A的一个映射f，f： AA称为A上的一个一元代数运算，简称一元运算。类似可定义n元运算。 通常用 , , ，+ +，等符号来表示二元或一元运算符。5.1 代数系统概述1、代数运算的定义例如：f是A上的二元运算，即AAA的映射。 x, yA, f()=zA，用公式表示为：x y = z注：映射有存在性和唯一性的要求，运算当然也要满足该要求。5.1 代数系统概述1、代数运算的定义例1：（1）在实数集合R上定义二元运算 ， x， yR， x y

3、=y则2 3=3，0.5 (-1/4)=-1/4， 50 0=0，0*50=505.1 代数系统概述1、代数运算的定义例1：（2）在正整数集合Z+上的二元运算 ，+ x， yZ+， x y=x，y的最大公约数， x + y=x，y的最小公倍数 6 8=2， 6 + 8=245.1 代数系统概述1、代数运算的定义例1：（3）在实数集合R上定义除法运算，这不是一个代数运算，因0不能作为除数，运算的存在性不满足 。例1：（4）在实数集合R上求平方根运算，不是一个代数运算。-9不存在平方根，存在性不满足。9有两个平方根：3和-3，唯一性不满足。 但在R+上求平方根运算，是一个一元运算。5.1 代数系统

4、概述1、代数运算的定义例2：（1）自然数集合N上的乘法是N上的二元运算。（2）整数集合Z上的加法、减法、乘法是Z上的二元运算，但除法不是Z上的运算。（3）设Mn(R)表示所有n 阶(n2)实矩阵的集合，矩阵加法和乘法都是Mn(R)上的二元运算。（4）在集合Z的幂集 (z)中， ， ， 均为二元运算，而“”是一元运算；5.1 代数系统概述1、代数运算的定义例2： （5 5） 命题公式 中,均为二元运算, ,而“ ”为一元运算（6 6） 双射函数 中, ,函数的复合运算是二元运算；5.1 代数系统概述2、表示二元或一元运算的方法（1 1）公式法（2 2）运算表：在有限集上可以将结果一一列出来定义运

5、算，简便明了的方法就是画出运算表。 二元运算的运算表 一元运算的运算表5.1 代数系统概述2、表示二元或一元运算的方法（2 2）运算表：例例3 A=P(a,b), , 分别为对称差和绝对补分别为对称差和绝对补运算，（运算，（a,b为全集）为全集） 的运算表的运算表 的运算表的运算表5.1 代数系统概述3、运算的封闭性定义5-1.1若对给定集合中的元素进行运算, ,而产生的象点仍在该集合中, ,则称此集合在该运算的作用下是封闭的。例4 4：（1 1）在正整偶数的集合E E中, ,对,+,+运算是封闭的；在正整奇数的集合中, ,对运算是封闭的, ,而对+ +运算不是封闭的。 （2 2）在集合R,I

6、R,I中+,-,+,-,运算； 在 (Z)(Z)的元素中,运算等均为封闭的。5.1 代数系统的引入4、代数系统定义5-1.2一个非空集合A A连同若干个定义在该集合上的运算f f1 1,f,f2 2,.,f,.,fk k所组成的系统就称为一个代数系统，记作A, f 。实例：（1 1）,是代数系统， +和分别表示普通加法和乘法. （2）是代数系统， +和 分别表示 n 阶(n2)实矩阵的加法和乘法. 5.1 代数系统的引入定义5-1.2一个非空集合A A连同若干个定义在该集合上的运算f f1 1,f,f2 2,.,f,.,fk k所组成的系统就称为一个代数系统，记作A, f 。实例：（3）是代数

7、系统，Zn 0, 1, , n 1 ， 和 分别表示模 n 的加法和乘法， 对于x, yZn， x y=(xy)modn，x y=(xy)modn （4）也是代数系统， 和为并和交，为绝对补5.2 运算及其性质定义5-2.1设*是集合A上的二元运算，对任一x,y A有x yAA，则称 运算在A上是封闭的。例1 ： A=xx=2n，nN， 问运算封闭否，呢？解： 2r，2sA， 2r * * 2s=2r+sA （） 运算封闭 2，4A，2+4 A，运算不封闭 2，4A，2/4 A， 运算不封闭5.2 运算及其性质定义5-2.2设* *是集合A A上的二元运算，对任一x,yx,y A A有x x

8、y=y y=y x x，则称 运算在A A上是可交换的（或者说 在A A上满足交换律) )。定义5-2.3设*是集合A上的二元运算,对任一x,y,z A都有（x y） z=x （y z）,则称 运算在A上是可结合的（或者说*在A上满足结合律）。 5.2 运算及其性质定义5-2.4设 和 是集合A上的两个二元运算, 对任一x,y,z A有 x （y z）=（x y） （x z）； （y z） x=（y x） （z x），则称运算 对 是可分配的（或称 对 满足分配律）。定义5-2.5设 ， 是定义在集合A上的两个可交换二元运算，如果对于任意的x,y A，都有：x (x y)=x；x (x y)=

9、x则称运算 和运算 满足吸收律。5.2 运算及其性质定义5-2.6设*是A上的二元运算,若对任一x A有x x=x,则称 满足等幂律。讨论定义：1)A上每一个元素均满足x x=x,称 在A上满足幂等律；2)若在A上存在元素x A有x x=x,称x为A上的幂等元；3)由此定义,若x是幂等元素,则有x x=x和xn=x成立。5.2 运算及其性质例例 Z, Q, R分别为整数、有理数、实数集；分别为整数、有理数、实数集；Mn(R)为为n阶实矩阵集合阶实矩阵集合, n 2；P(B)为幂集；为幂集；AA为为A到到A，|A| 2。5.2 运算及其性质例例 Z, Q, R分别为整数、有理数、实数集；分别为整

10、数、有理数、实数集；Mn(R)为为n阶实阶实矩阵集合矩阵集合, n 2；P(B)为幂集；为幂集；AA为为A到到A，|A| 2.5.2 运算及其性质下面定义特异元素：幺元,零元和逆元。定义5-2.7设*是集合A中的二元运算,(1)若有一元素el A,对任一x A有el*x=x；则称el为A中对于*的左幺元(左单位元素)； (2)若有一元素er A,对任一x A有x* er=x；则称er为A中对于*的右幺元（右单元元素）。5.2 运算及其性质定理5-2.1若el和er分别是A中对于*的左幺元和右幺元,则对于每一个x A，可有el= er = e和e*x=x* e=x，则称e为A中关于运算* 的幺元

11、，且e A是唯一的。证明： el和er分别是对*的左,右幺元， 则有el * er = er = el 有el = er = e成立。 （2）幺元e是唯一的。用反证法：假设有两个不同的幺元e1和e2,则有e1* e2= e2= e1,这和假设相矛盾。若存在幺元的话一定是唯一的。5.2 运算及其性质例：（1）在实数集合R中，对+而言， e+=0；对而言， e*=1 ；（2）在 (E)中， 而言， e =E（全集合）； 对 而言， e = （空集）；（3）双射函数中,对“ ”而言， e =Ix（恒等函数）；（4）命题逻辑中，对而言，e =F（永假式）；对而言， e =T（永真式）。5.2 运算及其

12、性质定义5-2.8设*是对集合A中的二元运算， （1）若有一元素l A，且对每一个x A有 l *x= l ，则称l 为A中对于*的左零元；（2）若有一元素r A，且对每一个x A有 x* r= r ，则称r为A中对于*的右零元。5.2 运算及其性质运算及其性质定理若l和r分别是A中对于*的左零元和右零元，于是对所有的x A，可有l = r =，能使*x=x*=。在此情况下， A是唯一的，并称是A中对*的零元。证明：方法同幺元。例：（1）在实数集合R中，对而言，l = r =0 （2）在 (E)中，对 而言， = ； 对 而言， = E ； （3）命题逻辑中，对而言， =T ； 对而言， =

13、F。5.2 运算及其性质运算及其性质定义5-2.9设*是A中的二元运算，且A中含幺元e，令x A，（1）若存在一xl A，能使xl *x= e，则称xl是x的左逆元,并且称x是左可逆的；（2）若存在一xr A，能使x* xr = e，则称xr是x的右逆元，并且称x是右可逆的；（3）若元素x既是左可逆的，又是右可逆的，则称x是可逆的，且x的逆元用x-1表示。5.2 运算及其性质运算及其性质定理5-2.4设A是集合，并含有幺元e 。*是定义在A上的一个二元运算，并且是可结合的。若x A是可逆的，则它的左逆元等于右逆元，且逆元是唯一的。证明：（1）先证左逆元=右逆元： 设xl和xr分别是x A的左逆

14、元和右逆元，x是可逆的和*是可结合的（条件给出） xl *x=x* xr = e xl *x* xr =（ xl*x）* xr = e * xr= xr ； xl *x* xr = xl*(x* xr) = xl* e = xl xr = xl5.2 运算及其性质运算及其性质（2 2）证明逆元是唯一的（若有的话）： 假设x1-1和x2-1均是x的二个不同的逆元，则 x1-1= x1-1*e = x1-1 *（x* x2-1 ） =（ x1-1 *x）* x2-1 = e * x2-1 = x2-1， 这和假设相矛盾。x若存在逆元的话一定是唯一的。5.2 运算及其性质运算及其性质推论(x-1)-

15、1 =x , e-1= e证明： x-1 *x= (x-1)-1 *（ x-1 ）=x* x-1 = e 有(x-1)-1 =x e-1 * e= e= e* e 有e-1= e 实例分析 和和 E 分别分别表示表示n 阶全阶全0 矩阵矩阵 和和 单位实数矩阵单位实数矩阵5.2 运算及其性质运算及其性质定义设 为集合S S上二元运算，如果对于任意元素 x x, , y y, , z z S S, , x x ，都有 x x y y = = x x z z y y = = z z, , y y x x = = z z x x y y = = z z成立，则称 运算满足消去律。例如，普通加法和乘法

16、满足消去律，矩阵加法满足消去律，矩阵乘法不满足消去律. . 集合的并和交运算也不满足消去律，例如11 1,2=21,2=2 1,21,2，但是11 2. 2. 例题分析例例 设设 运算为运算为 Q 上的二元运算，上的二元运算， x, y Q, x y = x+y+2xy, (1) 判断判断 运算是否满足交换律和结合律，并说明理由运算是否满足交换律和结合律，并说明理由. (2) 求出求出 运算的单位元、零元和所有可逆元素的逆元运算的单位元、零元和所有可逆元素的逆元.解解 (1) 运算可交换运算可交换. 任取任取x, y Q, x y = x+y+2xy = y+x+2yx = y x, 运算可结

17、合，任取运算可结合，任取x, y, z Q, (x y) z = (x+y+2xy) + z + 2(x+y+2xy) z = x+y+z+2xy+2xz+2yz+4xyz x (y z) = x + (y+z+2yz) + 2x(y+z+2yz = x+y+z+2xy+2xz+2yz+4xyz(2) 设设 运算的单位元和零元分别为运算的单位元和零元分别为 e 和和 ，则对于任意，则对于任意 x 有有 x e = x 成立，即成立，即 x+e+2xe = x e = 0 由于由于 运算可交换，所以运算可交换，所以 0 是幺元是幺元.给定给定 x，设，设 x 的逆元为的逆元为 y, 则有则有 x

18、 y = 0 成立，即成立，即 x+y+2xy = 0 (x = 1/2) 是是 x 的逆元的逆元, x 1/2. xxy21 xxy21 例题分析(续)对于任意对于任意 x 有有 x = 成立，即成立，即 x+ +2x = x+2x =0 = 1/2 1/2为零元为零元. 例题分析(续)下面是三个运算表下面是三个运算表 (1) 说明哪些运算是可交换的、可结合的、幂等的说明哪些运算是可交换的、可结合的、幂等的. (2) 求出每个运算的单位元、零元、所有可逆元素的逆元求出每个运算的单位元、零元、所有可逆元素的逆元.解解 (1) 满足交换律、结合律；满足交换律、结合律； 满足结合律、幂等律；满足结

19、合律、幂等律； 满足交换律、结合律满足交换律、结合律. (2) 的单位元为的单位元为 b, 没有零元，没有零元， a 1=c, b 1=b, c 1=a 的单位元和零元都不存在，没有可逆元素的单位元和零元都不存在，没有可逆元素. 的单位元为的单位元为 a，零元为，零元为c, a 1=a. b, c不是可逆元素不是可逆元素 5.5.3 半群定义5-3.1一个代数系统，S为非空集合， *是S上的二元运算，如果运算*是封闭的，则称代数系统为广群。定义5-3.2设是一代数系统，S为非空集合， *是S上的二元运算，若(1)*运算是封闭的。(2)*运算满足结合律，则称为半群。例： , , ,均为半群5.5

20、.3 半群定义5-3.3对于*运算，拥有幺元的半群称为含幺半群。（幺半群，独异点）。例： , 均为含幺半群， 而就不为幺半群。例：设A A为非空集合， (A) (A)是A A的幂集，则 , , ,A均为含幺半群。而，其中max(xmax(x1 1,x,x2 2) )取二者之大值；，其中min(xmin(x1 1,x,x2 2) )取二者之小值，均不为幺半群（不存在幺元）。则为含幺半群，其中 e =0e =0 5.5.3 半群定理5-3.1设是一半群，B S，且*在B上是封闭的，那么也是半群，称是 的子半群。讨论定义：（1）因为*在S上是可结合的，而B S且*在B上是封闭的，所以*在B上也是可结

21、合的。 （2）由定义可知， S S ， 也是的子半群（子含幺半群）。为了和其它子半群相互区别，称是的“平凡子半群”;5.5.3 半群定义设是一个含幺半群，B S，且*在B上是封闭的，则也是一个含幺半群，称是的子含幺半群。讨论定义：（1）在幺半群中，由于幺元e的存在， 保证在运算表中一定没有相同的行和列。设任一x1,x2 Z，且x1 x2 ， 则e * x1 = x1 e * x2 = x2 ；（2）在中若存在零元的话，上述性质继续存在。5.5.3 半群例：半群是的子半群，而不是子含幺半群。*运算由运算表定义： 10100010*1011000010 10 *由运算表可见：由运算表可见：中幺元为

22、中幺元为1，而在，而在中幺元为中幺元为 。5.5.3 半群 定理定理5-3.2如果半群如果半群的载体的载体S为有限集，则为有限集，则必有必有a S，使，使a*a=a。（。（有限半群一定含幂等元有限半群一定含幂等元）证明：因证明：因 S, 是半群，对任意的是半群，对任意的b b S S，由由* *的封闭性，的封闭性，b b* *b b S S，b b3 3 S S，b b4 4 S S，由于由于S S是有限集，必有是有限集，必有ijij，使，使b bi i=b=bj j设：设：p=jp=j i i，则，则b bj j=b=bp p* *b bi i，即：，即： b bi i=b=bp p* *b

23、 bi i当当qiqi时，时，b bq q=b=bp p* *b bq q，又因又因p1p1，总可以找到，总可以找到k1k1，使，使kpikpi，对，对S S中的中的b bkpkp有有b bkpkp=b=bp p* *b bkpkp=b=bp p* *(b(bp p* *b bkpkp)=b)=b2p2p* *b bkpkp =b =b2p2p* *(b(bp p* *b bkpkp)=b)=b3p3p* *b bkpkp=.=b=.=bkpkp* *b bkpkp令令a=ba=bkpkp，则，则a a* *a=aa=a。5.5.3 半群定理5-3.3设是独异点，则在关于运算*的运算表中任何两

24、行或两列都是不相同的。 证明：设独异点的幺元是e， 对任意的a a，b b S S且a ab a*e b*e， 运算表中a a，b b两行不同。 由a a，b b的任意性，运算表中任两行不同。 e*a e*b， 运算表中a a，b b两列不同。 由a a，b b的任意性，运算表中任两列不同。5.5.3 半群定理5-3.4设是独异点，对于任意a，b S，且a， b均有逆元，则 a)(a-1)-1=a b)a*b有逆元，且(a*b)-1=b-1*a-1 证明：a)因为a-1是a的逆元，即a* a-1= a-1*a=e 所以 (a-1)-1=a b)因为(a*b)*(b-1*a-1)= a*(b*b

25、-1)*a-1=a*e*a-1=e 同理可证：(b-1*a-1) * (a*b)=e 所以 (a*b)-1=b-1*a-15.5.4 群与子群1.群的定义定义5-4.1设是一代数系统，S是非空集合，*为S上的二元运算，它满足以下四个条件时，则称为群（1）*运算是封闭的；（2） *运算是可结合的；（3）存在幺元e； （4）S中每一个元素均有逆元。 例：, ,等均为群 （其中Z2 =0,1, Z3 =0,1,2 ），而,只是含幺半群而不是群。5.5.4 群与子群例：设M= 0,60,120, 180,240,300表示平面上几何图形顺时针旋转的六种位置，定义一个二元运算*，对M中任一元素a,b有a

26、*b=图形旋转(a+b)的角度，并规定当旋转到360时即为0，试验证是一个群。240180120600300300180120600300240240120600300240180180600300240180120120030024018012060603002401801206000300240180120600*5.5.4 群与子群（1）运算是封闭的）运算是封闭的（2）*是可结合的是可结合的（3）幺元为）幺元为0 ；（4）每一个元素均有逆元：）每一个元素均有逆元： (0 )-1= 0 , (60 )-1=300 , (120 )-1=240 , (180 )-1= 180 , (240

27、)-1=12 0 , (300 )-1= 60 是一个群。是一个群。 5.5.4 群与子群定义5-4.2设是一个群，如果G是有限集合，则称为有限群，并把|G|称为群的阶数，如果G为无限集合，则称为无限群。例：为无限群，上例中为有限群，群的阶为|M| =6。至此，可以概括地说：广群仅仅是具有一个封闭的二元运算的非空集合；半群是一个具有结合运算的广群；独异点是具有幺元的半群；群是每个元素都有逆元的独异点。5.5.4 群与子群2.群的性质 由群的定义可知:（1）群具有半群和含幺半群所具有的所有性质；（2）由于群中存在幺元，在群的运算表中一定没有相同的行（和列）（3）在群中，每一个元素均存在逆元，所以

28、群相对半群和含幺半群来说有一些特殊的性质。下面以定理形式介绍群的性质5.5.4 群与子群 定理5-4.15-4.1一个群 G , 中一定不存在零元。 零元不存在逆元。5.5.4 群与子群定理5-4.2 若是一个群，则对任一a,b G有：（1）存在唯一的元素x G ，使a * x= b； （2）存在唯一的元素y G ，使y * a= b。证明：（1）（a）在G中存在x，使a * x= b成立。a * (a-1 * b) = (a * a-1 ) *b =e* b=b， 至少有一x = (a-1 * b)满足a * x= b成立。（b）下面证明这样的x是唯一的。 若x是G中任一元素，且能使a* x

29、= b成立， 则有x =e *x = (a-1 * a) * x = a-1 * (a * x) = a-1 * b， x = (a-1 * b)是满足a * x= b的唯一元素，即x是唯一的。（2）的证明同上。5.5.4 群与子群 定理5-4.35-4.3若G , 是一个群，则对任一a,b,ca,b,c G G有：（1 1）a a * * b = a b = a * * c c b = c b = c（a a是左可消去的）; ;（2 2）b b * * a = c a = c * * a a b = c b = c（a a是右可消去的）。结论：在代数系统中，二元运算是可结合的，且a a是可逆

30、的，则a a是可约的。此定理说明群满足消去律。5.5.4 群与子群定义5-4.3设S是一个非空集合，从集合S到S的一个双射称为S的一个置换。定理5-4.4：群的运算表中的每一行或每一列都是G的元素的一个置换。5.5.4 群与子群证明： 首先，证明运算表中的任一行或任一列所含G中的一个元素不可能多于一次。 （反证法）如果对应于元素a G的那一行中有两个元素都是c，即有a*b1=a*b2=c，且b1 b2 由可约性，得： b1b2，这与b1 b2矛盾。其次，证明G中的每一个元素都在运算表的每一行和每一列中出现。5.5.4 群与子群 考察对应于元素a G的那一行，设b是G中的任一元素，由于b=a*(

31、a-1*b)，所以b必定出现在对应于a的那一行。再由运算表中没有两行（或两列）是相同的，所以， 的运算表中的每一行都是G的元素的一个置换，且每一行都是不相同的。同样，对于每一列结论同样成立。5.5.4 群与子群 定义5-4.45-4.4代数系统 G , 中，如果存在a a G,G,有a a* *a=aa=a，则称a a为等幂元。定理5-4.5一个群中，除了幺元e之外，不存在其它等幂元素。证明：若任一a G ，有a * a = a的话， 则a = e 。 e = a * a-1 = (a * a ）* a-1 =a * (a * a-1 ) =a * e = a5.5.4 群与子群3.子群定义5

32、-4.5设是一个群，且S G是一个非空集合。若满足下列三个条件，则称是的子群： （1）e是的幺元，且e S；（保持幺元） （2）对任一 a S一定有a-1 S ； （保持逆元） （3）对任一a,b S一定有a*b S （运算的封闭性）讨论定义： （1）任一群至少可找到二个子群，即和 ，称此二子群为平凡子群； （2）除了平凡子群以外的子群称为的真子群。5.5.4 群与子群定义设是群的真子群，若不再有一个真子群 （其中S T），则称 是的极大子群。例：是一个群，设S=x|x是6的倍数，T =y|y是3的倍数，则,是的真子群。 S T， 不是的极大子群。5.5.4 群与子群定理5-4.7设是一个群，B是G的非空子集，如果B是一个有限集，那么，只要运算*在B上是封闭的，则必定是的子群。5.5.4 群与子群证明：设b B，已知*在B上封闭，则b*b B，即b2 B， b