离散数学代数结构基本概念及性质

《离散数学代数结构基本概念及性质》由会员分享，可在线阅读，更多相关《离散数学代数结构基本概念及性质（98页珍藏版）》请在金锄头文库上搜索。

1、第十二章 代数结构概念及性质l12.1 代数结构的定义与例l12.2 代数结构的基本性质l12.3 同态与同构l12.4 同余关系l12.5 商代数l12.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；而二元运算符习惯于前置、中置或后置，如：

3、+xy，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上定义的运算一定是封闭的此

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

6、S)是它的幂集。对任意 集合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

8、+ b - 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.2

10、.1分别定义了运算和，问运算对于是可 分配的吗？对于呢？形如表12.2.1的表常常被称为运算表或复合表，它由运算符、行表头元素、列表头元素及复合元素四部分组 成。当集合S的基数很小，特别限于几个时，代数结构中运算常常用这种表给出。其优点简明直观，一目了然。解 可以验证对于是可分配的，但对于并非如此。因为1(01)(10)(11)1 0 1 0 04.吸收律给定，则对于满足左吸收律:=(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，试证，和互为吸收的。证明：不妨假设aba(ab) = maxa， mina，b= a(ab)a = maxmina，b ，a= a故对于满足吸收律。同理可证， 对于满足吸收律。故和互为吸收的。5.等幂律与等幂元 给定，则 “”是等幂的或“”满足等幂律:=( x)(xSxx=x) 给定且xS，则 x是关于“”的等幂元:=xx=x于是，不难证明下面定理： 定理12.2.2 若x是中关于的等幂元， 对于任意正整数n，则xn=x。例12.

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，因为对任意xR有x11x x。而“”运算的幺元为0，因为对任意

13、xR有x 00xx。例：前面例子中关于串的并置运算，它的单 位元素是空串，因为对任一串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，均有x00x0。例：正整数集Z+上的运算“min”，叫“取最小”运算。min(a,b)为取a,b的最小

14、者。代数结构中对应于运算“min”的零元为1。8逆元给定且幺元e，xS，则x为关于的左逆元:=(y)(ySxy=e)x为关于的右逆元:=(y)(ySyx=e)x为关于可逆的:=(y)(ySyx=xy=e)给定及幺元e；x，yS，则y为x的左逆元:=yx=ey为x的右逆元:=xy=ey为x的逆元:=yx=xy=e显然，若y是x的逆元，则x也是y的逆元，因此称x与y互为逆元。通常x的逆元表示为x-1。一般地说来，一个元素的左逆元不一定等于该元素的右逆元。而且，一个元素可以有左逆元而没有右逆元，反之亦然。甚至一个元素的左或右逆元还可以不是唯一的。定理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都