第3篇代数系统.ppt

1、第3篇 代数系统篇,非负整数集与普通加法 +构成的代数系统中，没有 单位元。 ( ),设N为自然数集合，在xy=x+y-2*x*y运算下构成代数系统。,设G=0,1,2,3,4,5,为模6加法，则中的6阶元是（ ）A. 5,0 B. 5,1 C. 4,3 D. 2,1,在中有3-5= 。,引 言 代数系统也叫做抽象代数，主要研究抽象的代数结构。抽象的代数系统也是一种数学模型，可以用它表示实际世界中的离散结构。,抽象代数在计算机中有着广泛的应用，例如自动机理论、编码理论、形式语义学、代数规范、密码学等等都要用到抽象代数的知识。代数系统的主要研究对象就是各种典型的抽象代数结构。,例如在形式语言中常

2、将有穷字符表记为，由上的有限个字符（包括0个字符）可以构成一个字符串，称为上的字。上的全体字符串构成集合*。设,是*上的两个字，将连接在后面得到*上的字。如果将这种连接看作*上的一种运算，那么这种运算不可交换，但是可结合。集合*关于连接运算就构成了一个代数系统，它恰好是抽象代数系统-半群的一个实例。,第3-1章 代数结构,3-1-1 代数系统的概念 3-1-2 代数系统的运算及其性质 3-1-3 半群与含幺半群 3-1-4 群与子群,二元运算的定义与实例 设S为集合,函数f：SSS称为S上的二元运算,简称为二元运算。,验证一个运算是否为集合S上的二元运算主要考虑两点：,(1) S中任何两个元素

3、都可以进行这种运算,且运算的结果是唯一的。 (2) S中任何两个元素的运算结果都属于S,即S对该运算是封闭的。,3-1-1 代数系统的概念,加法运算是自然数集合N上的二元运算,例如： f：NNN,f()=x+y,减法运算不是自然数集合N上的二元运算。,也称N对减法运算不封闭。,除法运算不是实数集合R上的二元运算,因为0R,而0不能做除数。,但在R*=R0上就可以定义除法运算了,因为 x,yR*,都有x/yR*。,n阶(n=2)实矩阵的集合Mn(R)上的乘法和加法。,设S为任意集合，则， 是()上的二元运算。,设S为集合,函数f：SS称为S上的一元运算,简称为一元运算。,求一个数的相反数是整数集

4、合Z，有理数集合Q， 和实数集合R上的一元运算。,(2)求一个数的倒数1/x是非零有理数集合Q*，非零 实数集合R*上的一元运算。,(3)幂集合P(s)上，如果规定全集为S，则求集合的绝对补运算是P(s)上的一元运算。,(4) n阶(n=2)实矩阵的集合Mn(R)上求转置矩阵。,二二元与一元运算的表示,2表示二元或一元运算的方法 -解析公式和运算表,表示二元或一元运算的方法有两种：解析公式和运算表。,1算符用 、* 、 、 等符号表示二元或一元运算,称为算符。,解析公式就是函数表达式。,若f：SSS为S上的二元运算, 如果任意x，y S , x与y运算结果是z,即 f(x,y)=z；,用符号

5、表示二元运算, 可记做x y=z。,例 设S1, 2, 3 ,4，定义S上的二元运算 如下：x y=(xy)mod 5 ， x,yS,解析公式,运算表,其中a1,a2,an是S中的元素, 为算符。,有穷集S上的二元和一元运算运算表表示：,设是代数系统，*是实数集合R上的二元运算， 使得对于R中任意元素x,y,都有x*y=x+y+xy, （1） 求4*6，7*3.（2） 求*运算的单位元。,解 ：4*6=34，7*3=31.,其中a1,a2,an是S中的元素, 为算符。,有穷集S上的二元和一元运算运算表表示：,列头元素,行头元素,例： 设S1, 2，给出P(S)上的运算和 的运算表，其中全集为S

6、。,解：,1,ai,1,2,2,P(S)= ， 1， 2， 1,2,1,2,2,1,2,1,2,1,例 设S1, 2, 3 ,4，定义S上的二元运算 如下：x y=(xy)mod 5， x,yS 求运算 的运算表。,解： (xy)mod 5 表示xy除以5的余数，运算表如下,1 2 3 4,代数系统的定义与实例,定义3-1-1.2 非空集合A和A上k个一元或二元运算f1 , f2 , , fk组成的系统称为一个代数系统,简称代数,记做。,例如:,都是代数系统,其中+和分别表示普通加法和乘法。,也是代数系统,其中含有两个二元运算和以及一个一元运算。,设N为自然数集合，在xy=x+y-2*x*y运

7、算下构成代数系统吗？,是代数系统,其中Zn0,1,n-1, 和 分别表示模n的加法和乘法,对于 x,yZn,x y=(xy)modn,x y=(xy)modn,在某些代数系统中存在着一些特定的元素,它们对于系统的一元或二元运算起着重要的作用,例如二元运算的单位元和零元。,在定义代数系统的时候,如果把含有这样的特定元素也作为系统的性质,比如规定系统的二元运算必须含有单位元，这时称这些元素为该代数系统的特异元素或代数常数。,有时为了强调某个代数系统是含有代数常数的系统,也可以把这些代数常数列到系统的表达式中,例如中的+运算有单位元0,为了强调0的存在,可以将记做。,不发生混淆的情况下为了叙述的简便

8、也常用集合的名字来标记代数系统,例如上述代数系统可以简记为Z和P(S)。,又如中的和运算存在单位元 和S,当规定 和S是该系统的代数常数时,也可将它记为。,定义3-1-2.1、2、5 设*为S上的二元运算, (1)如果对于任意的x,yS,有 x*y=y*x,则称 运算*在S上满足交换律。（可交换） (2)如果对于任意的x,y,zS有(x*y)*z=x*(y*z), 则称运算*在S上满足结合律。(可结合、可群) (3)如果对于任意的xS有x*x=x,则称运算*在S 上满足幂等律。（*运算是等幂的）,3-1-2 代数系统的运算及其性质,例3-1-2.1 设Z是整数集，、分别是Z上的 二元运算，其定

9、义为，对 a,bZ , a b=ab-a-b , a b=ab-a+b , 问运算 、是否可交换？,解： a,bZ , a b=ab-a-b ， b a=ba-b-a, a b= b a，所以运算 可交换,a,bZ , a b=ab-a+b ， b a=ba-b+a, 运算 不可交换。,例3-1-2.2 设Q是有理数集合，、*分别是Q上的 二元运算，其定义为，对 a,bZ , a b=a , a * b=a-2b , 问运算 、*是否可结合？,解：对 a,b,cZ , (a b) c=a c=a,a (b c)=a b=a,(a b) c= a (b c)，,所以运算可结合,对 a,b,cZ

10、, (a * b) * c=(a-2b)*c=a-2b-2c,a *(b * c)=a * (b-2c)=a-2(b-2c)=a-2b+4c,所以运算*不可结合,若是代数系统，其中是S上的二元运算， 且满足结合律，n是正整数，aS,则定义幂运算,aaa a是S中的元素，称其为a的n次幂,n个a做运算,记作 an,aman= am+n,（am)n= amn,其中，m,n是正整数,幂运算的性质,定义3-1-2.3 设 和*为S上两个不同的二元运算,如果对于任意的x,y,zS有x(y* z)=(xz)*(yz) 和 (y*z)x =(yx)*(zx),则称 运算对*运算满足分配律。,实数集R上的乘法

11、对加法是可分配的,N(n=2)阶实矩阵集合Mn(R)上矩阵乘法对加法是可分配的,幂集P(S)上和是互相可以分配的。,例3-1-2.2 设集合A=0，1,在A上定义两个二元 运算和*，运算表如下，分析两个运算是否相互 满足分配律。,1*(0 1),(1*0)(1*1),=1*1=1,=01=1,解：*对,1(0 * 1),(10)*(11),=10=1,=1*0=0,对*,满足分配律,不满足分配律,如果和*都可交换,并且对于任意的x,yS有 x(x*y)=x 和 x*(xy)=x, 则称和*运算满足 吸收律。,幂集P(S)上和运算满足吸收律。,A（AB）A,A（AB）A, A，B P(S),定义

12、3-1-2.4 设 和*为S上两个不同的二元运算,二元运算的特异元素,1.单位元(幺元),定义3-1-2.6 设为S上的二元运算，如果存在 el(或er) S，使得对任何x S都有 el x = x （或 x er = er ） 则称el(或er)是S中关于c 的一个左幺元 (或右幺元),若eS关于 运算既是左幺元又是右幺元，则称e为S上关于 运算的幺元。也称 单位元。,在自然数集N上， 是加法的单位元， 是乘法的单位元。,n(n=2)阶实矩阵集合Mn(R)上 是矩阵加法的单位元， 是矩阵乘法的单位元。,幂集P(S)上, 运算的单位元是 ，运算的单位元是 ，对称差 运算的单位元是,0,1,全0

13、的n阶矩阵,n阶单位矩阵,相对补运算的单位元,没有,S,非负整数集与普通加法 +构成的代数系统中，没有 单位元。 ( ),定理3-1-2.1 设 为S上的二元运算，el，er S分别是 左单位元和右单位元，则有 elere 且e为S上关于 运算的唯一单位元。,证明： el el er （er 为右单位元）,er el er （el 为左单位元）,所以eler,设是代数系统，*是实数集合R上的二元运算， 使得对于R中任意元素x,y,都有x*y=x+y+xy, （1） 求4*6，7*3.（2） 求*运算的单位元。,2.零元,定义3-1-2.7 设为S上的二元运算，如果存在 l(或r) S，使得对任

14、何x S都有 称l(或r)是S中关于 的一个左零元(或右零元),l x = l,x r = r,若S关于 运算既是左零元又是右零元，则称为S上关于 运算的零元。,在自然数集N上，乘法的零元是,0,n(n=2)阶实矩阵集合Mn(R)上乘法的零元是,全0的n阶矩阵,幂集P(S)上,运算的零元是 ,运算的零元是,S,设 为S上的二元运算， l,r S分别是 运算的左零元和右零元，则有 lr 且为S上关于 运算的惟一零元。,定理3-1-2.2,定理3-1-2.3 设 是一个代数系统，其中*是S上的一个二元运算， 且集合S中的元素个数大于1，若这个代数系统中存在幺元e和零元 ，则 e 。,证：(反证法)

15、,假设 e，则任意xS有,x=x e=x =,与S中至少有两个元素相矛盾,3.逆元,yl x = e,(或x yr = e),定义3-1-2.8 设 为S上的二元运算，如果存在 e S为 运算的单位元，对 x S，如果存在 ylS 或yrS有使得 则称yl(或yr)是x的左逆元(或右逆元),若yS既是x的左逆元又是x的右逆元，则称 y是x的逆元。,如果x的逆元存在，则称x是可逆的。,记作x-1,自然数集合N上的加法运算,只有0有加法逆元，就是0本身。,整数集合Z上的加法运算,任何整数x都有加法逆元，为x,n(n2)阶实矩阵集合Mn(R)上矩阵加法和矩阵乘法：,对任何n阶实矩阵M，M的加法逆元是

16、M,n阶实可逆矩阵M，M的乘法逆元是M-1,幂集P(S)上, 运算、运算和 运算：,对运算只有 有逆元，为自身，其他元素没有逆元,对运算只有 S 有逆元，为自身S，其他元素没有逆元,对 运算, P(S)中任何元素都有逆元，就是自身。,例3-1-2.6 设集合A=a1 ，a2 ，a3 ，a4 ，a5 ，a6, 定义在A上一个二元运算*的运算表如下，指出 代数系统中各元素的左、右逆元的情况。,* a1 a2 a3 a4 a5,a1 a1 a2 a3 a4 a5,a2 a2 a4 a1 a1 a4,a3 a3 a1 a2 a3 a1,a4 a4 a3 a1 a4 a3,a5 a5 a4 a2 a3

17、a5,解： a1 是幺元,一个元素的左右逆元可能不止一个，但若有逆元则必唯一,a2 、a3互为逆元,定理3-1-2.4 设 是一个代数系统，其中*是 S上的一个可结合的二元运算，e S为该运算的 单位元，对 x S，如果存在左逆元yl和右逆元yr 则有,yl = yry,且y是x惟一的逆元。,对于可结合的二元运算而言，可逆的元素x 只有惟一的逆元，通常记作x-1,yl = yry,定理10.4 设 为S上可结合的二元运算，如果存在 e S为运算的单位元，对 x S，如果 存在左逆元yl和右逆元yr S ，则有,且y是x惟一的逆元。,yl = yl e yl (x yr ) =(yl x ) y

18、r= e yr = yr,所以yl = yr,令yl = yry，则y是x的逆元。假设y S也是x的逆元,y是x惟一的逆元,例3-1-2.6 对于代数系统,其中k是正整数， Nk=0,1,2,k-1,+k是定义在Nk上的加法运算， 定义如下：x,y Nk,x +k y =,x + y , 若x+yk,x + y - k , 若x+yk,问是否每个元素都有逆元？,解： +k是一个可结合的二元运算， Nk中关于+k运算的幺元是0,每个元素都有逆元，0-1=0，x-1=k-x (x0),K=6时，计算每个元素的逆元,若是代数系统， 是定义在非空有限集 合S上的二元运算，则运算的部分性质可由运算表 看

19、出：,(1) 运算的封闭性,当且仅当运算表中每个元素都属于S,(2) 运算的可交换性,当且仅当运算表关于主对角线对称,(3) 运算的幂等性,当且仅当运算表中主对角线元素与它所在的行(列)的表头相同,(4) S关于运算有幺元e,当且仅当运算表中表头e所在的行与表头一行相同； e所在的列与表头一列相同。,(5) S关于运算有零元,当且仅当运算表中表头所在的行与列元素都是,(6) S关于运算有逆元,当且仅当运算表中行头a所在的行与列头b所在列 交叉点元素是幺元e；反之，行头b所在的行与 列头a所在列交叉点元素也是幺元e；,a-1=b,例 设Aa,b,c,A 上的二元运算 , 如 表所示 （1）说明

20、,*运算是否满足交换律和幂等律。 （2）求出 , *运算的单位元、零元和所有可 逆元素的逆元。,满足交换律，幂等律,单位元为a,零元为b,只有a有逆元，a-1=a,满足交换律,不满足幂等律,单位元为a,无零元,b,c互为逆元，b-1=c , c-1=b,a-1=a,不满足交换律,满足幂等律,无单位元，无零元，无逆元,注意：被消去的x不能是零元,例如：整数集合Z上的加法和乘法都满足消去律。,幂集P(S)上的并和交运算一般不满足消去律,运算满足消去律，对任意A，B，CP(S),3-1-3 半群与含幺半群,定义3-1-3.1 设是一个代数系统,*是S上的一个二元运算，如果*是可结合的，即对任意x,y

21、,zS,都有(x*y)*z=x*(y*z),则称代数系统为半群。,半群中的二元运算有时也称“乘法”，运算结果 称“积”。,，,， ,验证满足结合律,例3-1-3.1 设Sa,b,c, S 上的二元运算 如表所示，验证是半群。,a,b,c是左幺元,(a b) c= b c=c,a (b c)= a c=c,例3-1-3.2 设k是非负整数，集合定义为 Skx|x是整数且xk, 验证是半群,其中+就是普通加法运算。,解：运算+在Sk,是封闭的，且满足结合。,问: 是半群吗？,定理3-1-3.1 设是半群,B是S的非空子集，并且*在B上是封闭的，即对任意a,bB,都有a*bB,那么也是半群。,通常称

22、是的子半群。,例3-1-3.3 设是表示普通乘法运算，则 ， ， 是 的子半群。,如果是加法运算呢？,半群中的幂运算,设是半群，设a是S中任一个元素，定义 a的n次幂，记做 an,am an = am+n,(am)n = amn,设m,n是正整数,定理3-1-3.2 设是半群,若S是一个有限集合，则S中有幂等元。,有限半群中一定有幂等元,证明：是半群，取aS，由于运算* 的封闭型有 a*a=a2S，a2*a=a3S，,因为S是有限集合，所以必存在正整数i,j，使得 ji且ai=aj，,记m=j-i (m1) ，则ai=aj =am *ai,取任意正整数ni, an=ai*an-i=am*ai*

23、an-i=am*an,m1，必存在k1,使得kmi，则akm必是幂等元,因为 akm=am*akm=am*(am*akm)=a2m*akm,=a2m*(am*akm)=a3m*akm,=akm*akm,=,定义3-1-3.3 若半群的运算满足交换律， 则称是一个可交换半群。,定义3-1-3.4 含有幺元的半群称为含幺半群或 独异点。,设A=1，2，3，则是否半群？ 是否独异点？,是否半群？是否独异点？,定理3-1-3.3 设S是至少有两个元素的有限集合，且是一个含幺半群,则关于*运算的运算表中任何两行或两列都是不同的。,xi*e= xj*e,e是幺元,xi= xj,xi xj,定理3-1-3.

24、4 设是一个含幺半群,对于任意的x,yS，当x,y都有逆元时，则有 (1) (x-1)-1=x (2) 当x*y有逆元时，有(x*y)-1=y-1*x-1,3-1-4 群与子群,定义3-1-4.1 设是一个代数系统，其中G 是非空集合，是G上一个二元运算，如果 运算是可结合的。 中有幺元e 对每个元素aG，G中都有a的逆元a-1 则称是一个群。,(1) ,群,和,不是群,群,不是群,因为并非所有的n阶实矩阵都有逆矩阵。,(3) ,对任何B的子集A,A的逆元就是A自身。,群,下列代数系统中能够成群的是（ ） A. ,N是自然数集合，+是普通加法。 B. ,Mn(R)是n阶实矩阵的集合(n2) ，

25、表示矩阵乘法。 C. ，P(B)表示集合B的幂集，, 表示集合对称差运算。 D , AA表示所有从A到A的函数的集合， 表示函数的复合运算。,群的术语,定义3-1-4.1 (1)若群G是有穷集,则称G是有限群,否则称为无限群。,群G的基数称为群G的阶,有限群G的阶记作|G|,(2)只含单位元的群称为平凡群。,(3)若群G中的二元运算是可交换的,则称G为交换群 或阿贝尔(Abel)群。,是无限群,是有限群,也是n阶群。,是平凡群。,设G是群,aG,nZ,则a的n次幂,幂运算可以推广到半群和独异点。 但不同的是： 半群中幂指数n只能取正整数； 独异点中幂指数n只能取自然数， 群中幂指数n可以负整数

26、。,例如: 在模3加群 中,整数加群中， 23 =？ ,2-3 =？,2-3 = (2-1)3=13=1 1 1=0,2-3 =？,23 =？,23 = 2 2 2=0,2-3=(2-1)5=(-2)5=(-2)+(-2)+(-2)+(-2)+(-2) =-10,23 = 2 + 2 + 2 =6,3-5=？,二群的性质,1群的幂运算规则 设G为群,则G中的幂运算满足： (1) aG,(a-1)-1=a. (2) a,bG,(ab)-1=b-1a-1. (3) aG,anam=an+m,n,mZ. (4) aG,(an)m=anm,n,mZ. (5) 若G为交换群,则(ab)n=anbn.,元

27、素的阶,例如中,Z6=0,1,2,3,4,5中元素分别是几阶元？,2和4是3阶元；,3是2阶元；,1和5是6阶元；,0是1阶元；,中,0是1阶元,其它的整数都是无限阶元。,设G是群,aG,使得等式 ak=e成立的最小正整数k 称为a的阶,记作|a|=k,这时也称a为k阶元。 若不存在这样的正整数k,则称a为无限阶元。,例10.6 对于下面给定的集合和该集合上的二元运算， 指出该运算的性质，并求出它的单位元，零元 和所有可逆元素的逆元。,Z+， x,y Z+,x*y=lcm(x,y)，即求x和y的最小 公倍数。,解：*运算可交换，可结合，是幂等的。,x Z+, x*1= x ， 1*x= x，所

28、以1为单位元。,不存在零元,只有1有逆元，是它自身，其他整数无逆元。,问：满足消去律吗？,不满足,2*32*66，但23,（2） x,yQ, x*y=x+y-xy,一般方法是把单位元、零元或逆元分别代入公式解 出相应的值。,设*运算的单位元为e，零元为， xQ，x的逆元为y。,根据交换性，e 只需对一 切有理数x满足x*e=x， 即 x+e-xe=x e(1-x)=0,求它的单位元、零元和逆元,解：*运算可交换，可结合,满足消去律；不满足幂等律。,由x的任意性得e=0。所以单位元为0,类似地有 x+-x= x(1-)=0。,由x的任意性得=1。所以零元为1,x+y-xy=0,xQ,设其逆元为y

29、,则有,y=x/(x-1) (x1),所以当x1时，x-1=x/(x-1)。,例10.7设Aa,b,c,A 上的二元运算 *, , 如 表所示 （1）说明*, , 运算是否满足交换律，结合律，消去 律和幂等律。 （2）求出*, , 运算的单位元、零元和所有可逆元素 的逆元。,*运算的单位元为a，无零元。,a-1=a,b-1=c,c-1=b,满足交换律，结合律，消去律,不满足幂等律,满足交换律，结合律，幂等律,不满足消去律,单位元为a,零元为b,只有a有逆元，a-1=a,不满足交换律，消去律,满足结合律，幂等律,无单位元，无零元，无逆元,交换律：运算表中结果矩阵关于主对角线对称。,幂等律：运算表

30、中结果矩阵的主对角线上任一元素等于 所在行的行头元素或所在列的列头元素。,消去律：运算表中结果矩阵中任意一行中无相等 元素，并且任意一列中也无相等元素。,单位元：单位元元素所在行与列分别与对应的行头和 列头元素一致,零元：零元素所在行与与所在列中结果完全一致，就是 该元素本身。,10.2 代数系统,一、代数系统的定义与实例,1代数系统的定义与实例,定义10.6 非空集合S和S上k个一元或二元运算f1,f2,fk组成的系统称为一个代数系统,简称代数,记做。,例如:,都是代数系统,其中+和分别表示普通加法和乘法。,是代数系统,其中和分别表示n阶(n2)实矩阵的加法和乘法。,是代数系统,其中Zn0,1,n-1, 和 分别表示模n的加法和乘法,对于 x,yZn,x y=(xy)modn,x y=(xy)modn,也是代数系统,其中含有两个二元运算和以及一个一元运算。,在某些代数系统中存在着一些特定的元素,它们对于系统的一元或二元运算起着重要的作用,例如二元运算的单位元和零元。,在定义代数系统的时候,如果把含有这样的特定元素也作为系统的性质,比如规定系统的二元运算必须含有单位元，这时称这些元素为该代数系