离散数学第十二章代数结构基本概念及性质.ppt

1、第十二章 代数结构概念及性质,12.1 代数结构的定义与例 12.2 代数结构的基本性质 12.3 同态与同构 12.4 同余关系 12.5 商代数 12.6 积代数,12.1 代数结构的定义与例,在正式给出代数结构的定义之前，先来说明什么是在一个集合上的运算，因为运算这个概念是代数结构中不可缺少的基本概念。 定义12.1.1 设S是个非空集合且函数 或 f : Sn S，则称 f 为一个n元运算。其中n是自然数，称为运算的元数或阶。当n=1时，称f为一元运算，当n=2时，称f为二元运算，等等。,注意，n元运算首先是一个函数，其次是个闭运算(所谓闭运算是指：集合上的运算，其运算结果都在原来的集

2、合中，我们把具有这种特征的运算称作封闭的，简称闭运算)。封闭性表明了n元运算与一般函数的区别之处。此外，有些运算存在幺元或零元，它在运算中起着特殊的作用，称它为S中的特异元或常数。,运算的例子很多，例如，在数理逻辑中，否定是谓词集合上的一元运算，合取和析取是谓词集合上的二元运算；在集合论中，并与交是集合上的二元运算；在整数算术中，加、减、乘运算是二元运算，而除运算便不是二元运算，因为它不满足封闭性。,在下面讨论的代数结构中，主要限于一元和二元运算，将用、或等符号表示一元运算符；用、等表示二元运算符，一元运算符常常习惯于前置、顶置或肩置，如x、 、x；而二元运算符习惯于前置、中置或后置，如：+x

3、y，x+y，xy+。 有了集合上运算的概念后，便可定义代数结构了。,定义12.1.2 设S是个非空集合且fi是S上的ni元运算，其中i=1，2，m。由S及f1，f2，fm组成的结构，称为代数结构，记作。 例：设Z是整数集， “”是Z上的普通加法运算，则是一个代数结构。 例：设R是实数集 ，“”与“”是实数集R上的普通加法和乘法运算，则是一个代数结构。,例：我们可以构造下述的一个代数结构： 设有一个由有限个字母组成的集合 ，叫字母表，在上任意长的字母串，叫做上句子或字符串，串中字母的个数m叫这个串的长度，我们假定当一个字的长度m=0时用符号表示，它叫做空串。这样我们可以构造一个在上的所有串的集合

4、*。 其次，我们定义一个在*上的运算“/”并置运算或者连接运算，设， *，则 /。通过并置运算将两个串联成一个新的串，而此联成的新串也在*内，这样构造的 是一个代数结构,如果令+ *，则也是一个代数结构。 这两种代数结构都是计算机科学 中经常要用到的代数结构。,例：设有一计算机它的字长是32位，它以定点加、减、乘、除及逻辑加、逻辑乘为运算指令，并分别用01，02，06表示之。则在该计算机中由232有限个不同的数字所组成的集合S以及计算机的运算型机器指令就构成了一个代数结构。,因此，一个代数结构需要满足二个条件：(1)有一个非空集合S(2) 在集合S上定义的运算一定是封闭的,此外，我们把集合S的

5、基数即|S|，定义为代数结构的基数。如果S是有限集合，则说代数结构是有限代数结构；否则便说是无穷代数结构. 有时，要考察两个或多个代数结构，这里就有个是否同类型之说，请看下面定义：,定义12.1.3 设两个代数结构和，如果fi和gi(1im)具有相同的元数，则称这两个代数结构是同类型的。 可见，判定两个代数结构是否同类型，主要是对其运算进行考察： 两个代数结构是否有相同个数的运算符； 每个相对应的运算符是否有相同的元数。,例：代数结构与代数结构是相同类型的，因为它们都有一个二元运算符。 例：代数结构与的类型是不相同的，因为它们的运算符的个数不同。,例：设S是非空集合，P(S)是它的幂集。对任意

6、集合A，BP(S)上的运算和如下: AB =(AB)(BA) AB = AB 则是一代数结构。因为，显然和是闭运算。 与是同类型代数结构的。 有时还需要在代数结构中集合的某个子集上讨论其性质，这就引出子代数结构的概念.,定义12.1.4 设是一代数结构，且非空集TS在运算f1，f2，fm作用下是封闭的，且T含有与S中相同的特异元，则称为代数结构的子代数。记为。 例：设 E是所有偶数所组成的集合，则代数结构是的一个子代数结构 例： 显然， .,12.2 代数结构的基本性质,所谓代数结构的性质即是结构中任何运算所具有的性质。以下我们均假设运算为二元运算。 1.结合律 给定，则运算“”满足结合律或“

7、”是可结合的，即 (x)(y)(z)(x,y,zS(xy)z=x(yz),例12.2.1 给定且对任意a，bA有ab=b。证明运算“”是可结合的。 证明：因为对任意a，b，cA(ab)c=bc=ca(bc)=ac=c故 (ab)c=a(bc) 注意，不是任何代数结构上的运算都满足结合律，如整数集上“”运算就不满足结合律。如：5(21)4,但是(52)12.,2.交换律 给定，则运算“”满足交换律或“”是可交换的，即 (x)(y)(x,ySxy=yx)。 例12.2.2 给定，其中Q为有理数集合，并且对任意a，bQ有ab = a + b - ab，问运算是否可交换? 证： ab = a + b

8、- ab= b + a - ba b a ，故运算是可交换的。,同样，并不是所有代数结构上运算均满足交换律，如矩阵的乘法就不满足交换律。 易见，如果一代数结构中的运算是可结合和可交换的，那么，在计算a1a2am时可按任意次序计算其值。 特别当a1a2ama时，则a1a2amam。称am为a的m次幂，m称a的指数。 下面给出am的归纳定义：,设有且aS，对于mZ+，其中Z+表示正整数集合，可有： (1) a1=a (2)am+1=ama 由此利用归纳法不难证明指数定律： (1)aman=am+n (2)(am)n=amn 这里，m,nZ+。 类似地定义某代数结构中的负幂和给出负指数定律。,3.分

9、配律 一个代数结构若具有两个运算时，则分配律可建立这两个运算之间的某种联系。 给定，称运算对于满足左分配律，或者对于是可左分配的，如果有(x)(y)(z)(x,y,zSx(yz)=(xy)(xz) 同理，称运算对于满足右分配律或对于是可右分配的，如果有(x)(y)(z)(x,y,zS(yz)x=(yx)(zx),类似地可定义对于是满足左或右分配律. 若对于既满足左分配律又满足右分配律，则称对于满足分配律或是可分配的。同样可定义对于满足分配律。 由定义不难证明下面定理： 定理12.2.1 给定且是可交换的。如果对于满足左或右分配律，则对于满足分配律。,例12.2.3 给定，其中B=0,1。表12

10、.2.1分别定义了运算和，问运算对于是可分配的吗？对于呢？,形如表12.2.1的表常常被称为运算表或复合表，它由运算符、行表头元素、列表头元素及复合元素四部分组成。当集合S的基数很小，特别限于几个时，代数结构中运算常常用这种表给出。其优点简明直观，一目了然。 解 可以验证对于是可分配的，但对于并非如此。因为 1(01)(10)(11) 1 0 1 0 0,4.吸收律 给定，则 对于满足左吸收律:=(x)(y)(x,ySx(xy)=x) 对于满足右吸收律:=(x)(y)(x,yS(xy)x=x),若对于既满足左吸收律又满足右吸收律，则称对于满足吸收律或可吸收的。 对于 和吸收律类似地定义。 若对

11、于是可吸收的且对于也是可吸收的，则和是互为吸收的或和同时满足吸收律。,例12.2.4 给定，其中N是自然数集合，和定义如下： 对任意a，bN有ab = maxa，b，a b = mina，b，试证，和互为吸收的。 证明：不妨假设ab a(ab) = maxa， mina，b= a (ab)a = maxmina，b ，a= a 故对于满足吸收律。 同理可证， 对于满足吸收律。故和互为吸收的。,5.等幂律与等幂元 给定，则 “”是等幂的或“”满足等幂律:=( x)(xSxx=x) 给定且xS，则 x是关于“”的等幂元:=xx=x 于是，不难证明下面定理： 定理12.2.2 若x是中关于的等幂元，

12、对于任意正整数n，则xn=x。,例12.2.5 给定，其中P(S)是集合S的幂集，和分别为集合的并和交运算。验证：和是等幂的。 证：对任意A P(S)，有AA=A和AA=A，故和是等幂的。,6. 幺元或单位元 给定且el，er，eS，则 el为关于的左幺元:=( x)(xSelx=x) er为关于的右幺元:=( x)(xSxer=x) 若e既为的左幺元又为的右幺元，称e为关于的幺元。亦可定义如下： e为关于的幺元 :=( x)(xSex=xe=x)。,定理12.2.3 给定且el和er分别是关于的左、右幺元，则el=er=e且幺元e唯一。 例：实数集R上的代数结构的“”运算的幺元为1，因为对任

13、意xR有x11xx。而“”运算的幺元为0，因为对任意xR有x00 xx。 例：前面例子中关于串的并置运算，它的单位元素是空串，因为对任一串A，均有 / A = A / = A。,7.零元 给定及l，r，S，则 l为关于的左零元 :=( x)(xSlx=l) r为关于的右零元 :=( x)(xSxr=r) 为关于的零元 :=( x)(xSx=x=),定理12.2.4 给定且l和r分别为关于的左零元和右零元，则l=r=且零元是唯一的。 定理12.2.5 给定且|S|1。如果，eS，其中和e分别为关于的零元和幺元，则e。,例：代数结构上的零元是“0”，因为对于任何整数x，均有x00 x0。 例：正整

14、数集Z+上的运算“min”，叫“取最小”运算。min(a,b)为取a,b的最小者。代数结构中对应于运算“min”的零元为1。,8逆元 给定且幺元e，xS，则 x为关于的左逆元:=(y)(ySxy=e) x为关于的右逆元:=(y)(ySyx=e) x为关于可逆的 :=(y)(ySyx=xy=e),给定及幺元e；x，yS，则 y为x的左逆元:=yx=e y为x的右逆元:=xy=e y为x的逆元:=yx=xy=e,显然，若y是x的逆元，则x也是y的逆元，因此称x与y互为逆元。通常x的逆元表示为x-1。 一般地说来，一个元素的左逆元不一定等于该元素的右逆元。而且，一个元素可以有左逆元而没有右逆元，反之

15、亦然。甚至一个元素的左或右逆元还可以不是唯一的。,定理12.2.6 给定及幺元eS。如果是可结合的并且一个元素x的左逆元xl-1和右逆元xr-1存在，则xl-1=xr-1。 定理12.2.7 给定及幺元eS。如果是可结合的并且x的逆元x-1存在，则x-1是唯一的。,例：代数结构上的幺元是“0”，对于任何整数x，它的逆元是x，因为 x(x)0。 例：代数结构中0和1分别为和的幺元。对于“”，对每个元素rR都有逆元r；对于“”，对每个元素 rR都有逆元1/r(r 0) 。,9.可约律与可约元 给定且零元S，则 满足左可约律或是左可约的:=( x)( y)( z)(x,y,zSxxy=xz)y=z)

16、，并称x是关于的左可约元。 满足右可约律或是右可约的:=( x)( y)( z)(x,y,zSxyx=zx)y=z)，并称x是关于的右可约元。,若既满足左可约律又满足右可约律或既是左可约又是右可约的，则称满足可约律或是可约的。 若x既是关于的左可约元又是关于的右可约元，则称x是关于的可约元。可约律与可约元也可形式地定义如下：,满足可约律 :=( x)( y)( z)(x,y,zSx(xy=xzyx=zx)y=z) x是关于的可约元 :=( y)( z)(y,zSx(xy)=xzyx=zx)y=z),例：给定，其Z是整数集合，是一般乘法运算。显然，每个非零整数都是可约元，而且运算满足可约律。,定

17、理12.2.8 给定且是可结合的，如果x是关于可逆的且x，则x也是关于的可约元。 证明 设任意y,zS且有xy=xz或yx=zx。因为是可结合的及x是关于可逆的，则有 x-1(xy)=(x-1x)y=ey=y x-1(xz)=(x-1x)z=ez=z,故得xy=xzy=z，故x是关于的左可约元。同样可证得yx=zxy=z，故x是关于的右可约元。故x是关于的可约元。 最后，作一补充说明，用运算表定义一代数结构的运算，从表上很能反映出关于运算的各种性质。为确定起见，假定及x，y，eS。,(1)运算具有封闭性，当且仅当表中的每个元素都属于S。 (2)运算满足交换律，当且仅当表关于主对角线是对称的。,

18、(3)运算是等幂的，当且仅当表的主对角线上的每个元素与所在行或列表头元素相同。,(4)元素x是关于的左零元，当且仅当x所对应的行中的每个元素都与x相同；元素y是关于的右零元，当且仅当y所对应的列中的每个元素都与y相同；元素是关于的零元，当且仅当所对应的行和列中的每个元素都与相同。,(5)元素x为关于的左幺元，当且仅当x所对应的行中元素依次与行表头元素相同；元素y为关于的右幺元，当且仅当y所对应的列中元素依次与列表头元素相同；元素e是关于的幺元，当且仅当e所对应的行和列中元素分别依次与行表头元素和列表头元素相同。,(6)x为关于的左逆元，当且仅当位于x所在行的元素中至少存在一个幺元，y为关于的右

19、逆元，当且仅当位于y所在列的元素中至少存在一个幺元；x与y互为逆元，当且仅当位于x所在行和y所在列的元素以及y所在行和x所在列的元素都是幺元。,例12.2.8 给定，其中S=，且的定义如表12.2.5所示。试指出该代数结构中各元素的左、右逆元情况。 表12.2.5 解：是幺元；的左逆元和右逆元都是，即与互为逆元；的左逆元是而右逆元是；有两个左逆元和；的右逆元是，但没有左逆元。,12.3 同态与同构,本节将阐明两个重要概念同态与同构。在以后各节中，它们会经常被使用到。,定义12.3.1 设与是同类型的。称同态于或为的同态象，记为 ，其定义如下： :=(f)(fYX(x1)(x2)(x1,x2Xf

20、(x1x2)=f(x1)f(x2) 同时，称f为从到的同态映射. 可以看出，同态映射f不必是惟一的。,X x1 x2 x3 x1x3,f(X) y1=f(x1) f(x1)=f(x2) y3=f(x3) y1y3,Y,同态示意图,f,例12.3.1 给定和，其中R是实数集合，和分别是加法和乘法运算，试证 。 证：关键是找一个同态映射。今构造函数fRR如下： f(x)=ax , 其中a0, xR 则f为所求的同态映射，这是因为对任意y,zR，有 f(yz)= ayz ay az f(y)f(z) 因此， ,两个同类型的代数结构间的同态定义不仅适用于具有一个二元运算的代数结构，也可以推广到具有多个

21、二元运算的任何两个同类型代数结构。例如，对于具有两个二元运算的两个同类型代数结构和的同态定义如下： :=(f)(fYX(x1) (x2)(x1,x2X(f(x1x2)=f(x1)f(x2)f(x1x2)=f(x1)f(x2),定理12.3.1 如果 且f为其同态映射，则 。 由于函数fYX的不同性质，将给出不同种类的同态定义。,定义12.3.2 设 且f为其同态映射。 (i)如果 f 为满射，则称 f 是从到的满同态映射。 (ii)如果f为单射(或一对一映射)，则称f为从到的单一同态映射。,(iii)如果f为双射(或一一对应)，则称f为从到的同构映射。记为 。 显然，若 f 是从到的同构映射，

22、则 f 为从到的满同态映射及单一同态映射，反之亦然。,例12.3.3 设与是同类型的，其中*为有限字母表上的字母串集合，为并置运算，N为自然数集合，+为普通加法。若定义 f：*N为 f(x)= | x | 其中x*，| x |表示字母串的长度。 因为对任意 x，y*，有f(xy )= | xy | = | x | + | y | = f(x)+ f(y)，故 。 显然，f是满射，因此，f为从到的满同态映射。,例12.3.4 给定，其中Z为整数集合，+为一般加法。作函数fZZ：f(x)=kx，(此处乘法是一般乘法)其中x,kZ 则当k0时，由于 f(y+z)=k(y+z)=ky+kz=f(y)+

23、f(z)，故f为到的同态映射。又易知f为单射，故f为到的单一同态映射。 当k=-1或k=1时，f为从到的同构映射(我们稍后再来证明)。,综上可以看出，同态映射具有一个特性，即“保持运算”。对于满同态映射来说，它能够保持运算的更多性质，为此，给出如下定理： 定理12.3.2 给定 且 f 为其满同态映射，则 (a)如果和满足结合律，则和也满足结合律。 (b)如果和满足交换律，则和也满足交换律。,(c)如果对于或对于满足分配律，则对于或对于也相应满足分配律。 (d)如果对于或对于满足吸收律，则对于或对于也满足吸收律。 (e)如果和满足等幂律，则和也满足等幂律。 (f)如果e1和e2分别是关于和的幺

24、元，则f(e1)和f(e2)分别为关于和的幺元。,(g)如果1和2分别是关于和的零元，则f(1)和f(2)分别为关于和的零元。 (h)如果对每个xX均存在关于的逆元x-1，则对每个f(x)Y也均存在关于的逆元f(x-1)；如果对每个zX均存在关于的逆元z-1，则对每个f(z)Y也均存在关于的逆元f(z-1)。,定理12.3.2告诉我们，对于满同态映射来说，代数结构的许多性质都能保持，如结合律、交换律、分配律、等幂律、幺元、零元、逆元等，但这种保持性质是单向的，即如果满同态于，则所具有的性质，均具有。但反之不然，即所具有的某些性质，不一定具有。不尽要问，在怎样条件下，所具有的性质都完全具有呢?为

25、了回答这个问题，需要引出两个代数结构同构的概念。,定义12.3.3 设与是同类型的。称同构于，记为 ，其定义如下： :=(f)(f为从到的同构映射) 或更详细地定义为： :=(f)(fYXf为双射f为从到的同态映射), x1 x2 x1x2, f(x1) f(x2) f(x1)f(x2),同构示意图,f,例 代数结构与是同构的。其中R为实数，R+为正实数。 证：关键是找一个双射。对 与，有一个函数h：R+R，h(x)=lnx 此函数是双射的。因为对每个x0,均存在一个y=lnxR，同时，对每个yR，均存在一个x=ey R+.又因为 h(yz)=ln(yz)=lnylnz=h(y)h(z) 故与

26、是同构的。 注：当然，我们也可以取函数h(x)=lgx，,续例12.3.4 给定，其中Z为整数集合，+为一般加法。作函数fZZ：f(x)=kx，(此处乘法是一般乘法)其中x,kZ，则当k=-1或k=1时，f为从到的同构映射。 证：先证明当k=-1或k=1时f为双射。因为对每个xZ,均存在一个y=kx(即y=x或y=-x)Z，同时，对每个yZ，均存在一个x=y/k (即x=y或x=-y) Z。(显然，若k取1以外的值，y/k不一定是整数，或者y/k无意义，此时f 就不是双射了.) 又由于f(y+z)=k(y+z)=ky+kz=f(y)+f(z)， 故f为到的同构映射。,例 代数结构与是同构的。其

27、中M, H分别表示低电平、高电平，“”表示或门，它们的运算表如下。 证：这两个代数结构间存在一个函数f:0,1M,H，且f(0)=M, f(1)=H，显然这是一个双射，而且有f(xy)=f(x)+f(y)。故它们是同构的。,例 设S=4,5,6,在S上的二元运算“”其定义如下表所示。又有P=1,2,3及在P上的二元运算“”，其运算表如下表所示。这样所构成的两个代数结构与是同构的。 证：这两个代数结构间存在一个函数f:4,5,61,2,3，f(x)=x-3，其中xS。显然这是一个双射，而且有f(xy)=f(x)f(y)。故它们是同构的。,由定义可知，同构的条件比同态强，关键是同构映射是双射，即一

28、一对应。而同态映射不一定要求是双射。正因为如此，同构不再仅仅象满同态那样对保持运算是单向的了，而对保持运算成为双向的。两个同构的代数，表面上似乎很不相同，但在结构上实际是没有什么差别，只不过是集合中的元素名称和运算的标识不同而已，而它们的所有发生“彼此相通”。,这样，当探索新的代数结构的性质时，如果发现或者能够证明该结构同构于另外一个性质已知的代数结构，便能直接地知道新的代数结构的各种性质了。对于同构的两个代数结构来说，在它们的运算表中除了元素和运算的标记不同外，其它一切都是相同的。因此，可以根据这些特征来识别同构的代数结构。,下面给出两个二元运算的代数结构的同构定义 定义 设两个代数结构与，

29、如果它们之间存在一个双射f：XY，使得任意x1,x2X，有 f(x1 x2)=f(x1) f(x2) f(x1 x2)=f(x1) f(x2) 则说此两个代数结构是同构的。,例12.3.6 给定，其中S=，A，B，C，和是一般的集合运算；又有，这里T = 1，2，5，10，且对于a，bT有a b = lcma，b(最小公倍数)，a b = gcda，b(最大公约数) ，表12.3.3至表12.3.6给出四个运算表。试说明.,表12.3.3表12.3.4 表12.3.5表12.3.6,解：令fTS：f()=1，f(A)=2，f(B)=5，f(C)=10。显然，f是从S到T的双射。经验证，对任意x

30、1, x2S，又有 f(x1x2)=f(x1) f(x2) f(x1x2)=f(x1) f(x2) 故与是同构的。,同构是一个关系，而且可以证明它是个等价关系，对此有如下定理： 定理12.3.3 代数结构间的同构关系是等价关系。,证明 显然，因为恒等映射是同构映射。又若且f为其同构映射，则f-1为从到的同构映射。因此，。再令及，则。这里因为若f为到的同构映射，g为到的同构映射，则gf为从到的同构映射。可见同构关系满足自反性、对称性和传递性。因此，同构关系是等价关系。,由于同构关系是等价关系，故令所有的代数结构构成一个集合S，于是可按同构关系将其分类，得到商集S/ 。因为同构的代数结构具有相同的

31、性质，故实际上代数结构所需要研究的总体并不是S而是S/ 。 在同态与同构中有一个特例，即具有相同集合的任两个代数结构的同态与同构，这便是自同态与自同构。,定义12.3.4 给定及fSS。 f为自同态映射:=f为从到的同态映射。 f为自同构映射:=f为从到的同构映射。 例12.3.7 在例12.3.4中，当k 0时，f = kx是从到的自同态映射；当k = 1或k = -1时，f = kx是从到的自同构映射。,12.4 同余关系,本节主要阐明同态与同余关系之间的联系。主要内容如下： 定义12.4.1 给定，且E为S中的等价关系。 E有代换性质 :=(x1)(x2)(y1)(y2)(x1,x2,y

32、1,y2Sx1Ex2y1Ey2)(x1y1)E(x2y2)。 E为中的同余关系:=E有代换性质。,与此同时，称同余关系E的等价类为同余类。 由定义可知，同余关系是代数结构的集合中的一类特殊的等价关系，并且在运算的作用下，能够保持关系的等价类。即在x1y1中，如果用集合S中的与x1等价的任何其它元素x2代换x1，并且用与y1等价的任何其它元素y2代换y1，则所求的结果x2y2与x1y1位于同一等价类之中。,亦即若x1E=x2E并且y1E=y2E，则x1y1E=x2y2E。 此外，同余关系与运算密切相关。如果一个代数结构中有多个运算，则需要考察等价关系对于所有这些运算是否都有代换性质。如果有，则说

33、该代数结构存在同余关系；否则，同余关系不存在。,同余关系示意图,例12.4.1 给定，其中Z是整数集合，+和是一般加、乘法。假设Z中的关系R定义如下： i1Ri2:=|i1|=|i2|，其中i1、i2Z 试问，R为该结构的同余关系吗？,解 显然，R为Z中的等价关系。接着先考察R对于+运算的代换性质： 若取i1,-i1,i2Z ，则有|i1|=|-i1|和|i2|=|i2|，于是，下式 (i1R(-i1)(i2Ri2)(i1+i2)R(-i1+i2) 不真。这是因为前件为真，后件为假。故R对于+运算不具有代换性质。,至此可以说，R不是该结构的同余关系。但为了熟悉验证一个关系是否为同余关系，还是来考察R对于的代换性质。 令i1,i2,j1,j2Z且i1Ri2和j1Rj2。于是，对任意i1,i2,j1,j2都有： (i1Ri2)和(j1Rj2)(i1j1)R(i2j2) 因此，E对于具有代换性质。,可见，考察一个等价关系E对于有多个运算的代数结构是否为同余关系，这里有个次序先后问题，选择得好，马上就考察到了E对某个运算是不具有代换性质，那么便可立刻断定E不是该结构的同余关系，否则验证应继续下去，直至遇到不具有代换性质的运算为止。如果对于所有运算都有代换性质，则E为该结