离散数学第三部分.ppt

第三部分 代 数 结 构,第五章 代数系统 5.1 二元运算及其性质 1二元运算的定义与实例 设S为集合,函数f：SSS 称为S上的二元运算,简称为二元运算. 例如 f：NN N, f() = x + y就是自然数集合N上的二元运算,即普通的加法运算.,验证一个运算是否为集合S上的二元运算主要考虑两点： (1)、S中任何两个元素都可以进行这种运算,且运算的结果是唯一的. (2)、S中任何两个元素的运算结果都属于S,即S对该运算是封闭的. ,例 设A=xx=2n,n N,则在集合A上通常的乘法运算是否封闭？加法运算呢？ 解：对任意的x，yA, 设x=2r，y=2s，r,s N xy=2r2s=2r+s A,所以，A对乘法封闭. 但对加法运算不封闭 事实上，取x=2，y=22 A, X+y=2+4=6 A.,2、一元运算的定义与实例 设S为集合,函数f：SS称为S上的一元运算,简称为一元运算. 例如，设R是实数集合，求一个数的相反数就是R上的一个一元运算. 即 f: RR ， f(x)=x 求一个复数的共轭复数是复数集上的一个一元运算. 求集合的补集也是一元运算.,对于一元运算 f：SS ，如果 x 的运算结果是y, 则f(x) = y,利用运算符，如，简记为 x = y 如求A的补集记成A，或 3表示二元或一元运算的方法 (1)、解析公式法 所谓解析公式就是使用算符和表达式给出参与运算的元素和运算结果之间的映射规则. 例如： f：NN N ，f () = 2m+n.,（2）、运算表法 对有穷集合上的一元和二元运算，还可以有运算表给出. 例 S=a,b,c,d,S上的二元运算 如下表定义 a b c d a a d c c b c a b d c a a c b d d d a b,,,4二元运算的性质 设 为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上满足等幂律（幂等律）.,(4)、设 和为S上两个不同的二元运算, 如果对于任意的x,y,zS有 x ( y z ) =(xy) (x z) ( y z) x =(y x) (z x), 则称运算对运算是可分配的，也称对满足分配律. (5)、如果和都可交换,并且对于任意的x,yS ， 有 x (x y) = x x (x y) = x, 则称和运算满足吸收律.,5.2 二元运算中的特殊元素 1、幺元（单位元） 设 为S上的二元运算, el、er、 e S (1)、如果对任何x S都有 el x = x 则称el 是S中关于运算 的一个左幺元. （2）、如果对任何x S都有 x er = x 则称或er是S中关于运算 的一个右幺元. （3）、若e 既是左幺元又是右幺元，则称 e 是S中关于运算 的一个幺元.,例 在自然数集N上，0是加法的单位元， 1是乘法的单位元。

例 幂集P(S)上运算的单位元是 ， 运算的单 位元是S. 例 考虑非零实数全体所成集合R*，如下定义的二元运算 ： 对任意的a,b R*, a b = a 则运算没有左单位元，但S中的每一个元素都是右单位元.,定理5.1 设 为S上的二元运算, 如果S中存在（关于运算的）幺元，则幺元必是唯一的. 定理5.2 设 为S上的二元运算, 如果S中既存在 左幺元el，又存在右幺元er ，则S中必存在幺元e， 并且el=er=e.,2、零元 设为S上的二元运算, l，r， S （1） 如果对任意的xS 都有l x = l 则称l 是S中关于运算 的一个左零元； （2）如果对任意的x S都有 x r = r ，则称r是S中关于运算 的一个右零元； （3） 若既是左零元又是右零元，则称 是S中关于运算 的一个零元.,例如，自然数集合上0是普通乘法的零元，而加法没有零元. 幂集P(S)上运算的零元是S，运算的零元是， 而对称差运算没有零元.（为什么？） 定理 5.3 设 为S上的二元运算, 如果S中存在（关于运算的）零元，则零元必是唯一的. 定理5.4 设 为S上的二元运算, 如果S中既存在左零元l，又存在右零元r ，则S中必存在零元， 并且l= r= ,3、逆元 设为S上的二元运算,eS为S关于运算的单位元，对于xS, （1）若存在ylS使得 ylx=e，则称yl是x的左逆元； （2）若存在yrS使得 xyr=e，则称yr是x的右逆元； （3）若y既是x的左逆元，又是x的右逆元，则称y是x的 逆元. 如果x的逆元存在，则称x是可逆的.,定理5.5 设为S上可结合的二元运算,e为S的单位元，如果S中元素x有逆元,则逆元是唯一的.x的逆元记为x-1,定理 5.6 设为S上可结合的二元运算,e为S的单位元，如果S中元素x有左逆元yl ,又有右逆元yr ,则x有逆元x-1 ，且yl= yr = x-1 .,4、消去律 设 为S上的二元运算，如果对于任意的x,y,z S，满足以下条件： (1)、若x y = x z 且 x ，都有 y = z; (2)、若y x = z x 且x ，都有y = z; 则称 运算满足消去律. 其中(1)称为左消去律， (2)称为右消去律. 例: 设A=1,2, ,10, A上二元运算 定义如下: 对任意的a,bA, a b = maxa,b. 求A的单位元和零元.,例 有理数集Q上二元运算定义为: x,yQ,x y = x + y - xy . 指出该运算的性质，并求出它的单位元、零元、 所有可逆元的逆元. 解： x,y Q, x y = x + y - xy = y+x yx=y x, 所以满足交换律. x,y,z Q, (x y ) z =(x + y xy) z,= (x + y xy) +z (x + y xy) z = x+y +z xy xz yz + xyz x ( y z ) = x (y +z yz) = x + (y+z yz) x(y +z yz) = x + y + z xy xz yz + xyz 即 (x y ) z = ( (x y ) z 所以， 满足结合律. （ 不满足幂等律） x Q,x 0 = x+0 x0 = x = 0 x, 所以,0为单位元.,x Q,x 1 = x+1 x1 = 1 = 1 x 所以,1为零元. x,y,z Q,x1,若x y= x z, 即x+y xy =x+z xz y(1 x ) = z(1 x) y = z . 由于运算可交换,所以,运算满足消去律. x Q,(x1),欲使x y =y x = 0 即x+y xy = 0 ,从运算表检验运算的性质和特殊元素. 交换律、消去律、结合律、单位元、零元、逆元等 P.93例 5.7 、 P.95 例 5.9 关于结合律有如下结论：,,,a b c d,a a b c d b b a d c c c d a b d d c b a,,,单位元为结合元.为检验x是否结合元,作表L(x),R(x), 其中L(x)表头行元素为运算表中元素x所在的行,表内元素按所给运算规则算出;R(x)表头列元素为运算表中元素x所在的列, 表内元素按所给运算规则算出.x是结合元 L(x)表与R(x)表中对应元素相同.,解:上例中 a 是单位元,只要检验 b, c, d L(b) b a d c a b a d c b a b c d c d c b a d c d a b,,,,b b a d c a a b c d d d c b a c c d a b,所以,b是结合元.同理,检验得 c,d均为结合元, 所以运算满足结合律. 每个元素的逆元就是自身。

R(b) a b c d,5.3 代数系统 一、代数系统的定义与实例 定义5.10 设S是非空集合，S和S上k个运算f1,f2,fk 组成的系统称为一个代数系统,简称代数,记做. 例如：,,都是代数系统,其中+和分别表示普通加法和乘法. 是代数系统,其中和分别表示n阶(n2)实矩阵的加法和乘法.,也是代数系统,其中含有两个二元运算和以及一个一元运算. 在不发生混淆的情况下为了叙述的简便也常用集合的名字来标记代数系统,例如上述代数系统可以简记为Z和P(S).,二子代数系统 (不做要求) 定义5.11 设V=是代数系统,B是S的非空子集,如果B对f1,f2,fk 都是封闭的,且B和S含有相同的代数常数,则称是V的子代数系统,简称子代数有时将子代数系统简记为B 例如N是的子代数,因为N对加法运算是封闭的N也是的子代数,因为N对加法运算是封闭的,且N中含有代数常数0N-0是的子代数,但不是的子代数,因为的代数常数0 N0 ,三、代数系统的同态与同构 定义5.12 设V1=，V2=是同类型的代数系统, 如果存在映射f: S1 S2 . 且对任意的x，y S1有 f(xy)= f(x)f(y)则称f是从V1 到V2的同态映射,简称同态. 为了书写的简便,有时经常省略上述表达式中的算符 和 ,而简记为 f(x y) = f(x) f(y)但应该记住,该表达式中左边的xy是在V1中的运算,而右边的 f(x) f(y)是在V2中的运算.,例 设V1=， V2= ， 做R到R+的映射 f: R R+ ，f(x)=3x ， 则f是V1到V2的同态映射. 定义5.13 设f 是V1=到V2=的同态，则称是V1在f下的同态像.,定义5.14 设f 是V1=到V2=的同态映射， (1) 若f是满射,则称为满同态,这时也称V2是V1的同态像. (2) 若 f是单射的,则称为单同态. (3) 若 f是双射的,则称为同构,记作 V1 V2 . (4) 若V1=V2=V,则称是群V的自同态. 类似的可以定义满自同态,单自同态和自同构.,四、同态映射的性质 同态映射保持元素的对应性 ，即 设f是代数系统V1到V2的同态映射,e1和e2分别为V1 和V2的单位元,则 f(e1) = e2 , f(a-1) =f (a) -1, aV1,例 V=,给定aZ,令a:Z Z, a(x)=ax 判断a是否为V到V的同态？ a为何值时a是单同态、满同态、同构？ 解：任取x,y Z, a(x+y)=a(x+y)= ax+ay= a(x)+a(y) 所以，是a是否为V到V的同态. 当a0时是单同态， a=1 时是满同态，也为同构.,例 设是字母的有穷集，称为字母表， 中的有限个字母组成的序列称为上的串. 对任意串，串中字母的个数叫做串的长度，记作 . 长度为0的串叫空串，记作. 对给定的自然数k， 令k=vi1 vi2 vik vij ,j=1,2, k 即k是上所有长度为k的串的集合. 特别地，有 0=， 记 +=12， *=0+,如下定义*上的二元运算 , 1, 2 *, 设1 =vi1 vi2 vim,,， 2 =vj1 vj2 vjn 则1 2 = vi1 vi2 vim vj1 vj2 vjn 令 V1= ,V2=, 定义：* N如下： * （)= 则是V1到V2的同态. （书上有问题,没有定义二元运算 P.97）,第6章 几个典型的代数系统 6.1 半群与群 一、群的定义 (1)、设V=是代数系统, 为二元运算,如果运算是可结合的,则称V为半群. (2)、设V=是半群,若eS是关于运算的单位元,则称V是含幺半群,也叫做独异点.有时也将独异点V记作V=. （3）、设V=是独异点，若S中每一元素 在S中都有逆元，则称V是群.,例 ,,都是半群,+是普通加法. 这 些半群中除外都是独异点. 是半群，也是独异点，其中是集合的对称差运算. 是半群，也是独异。