《离散数学第九章代数系统.ppt》由会员分享，可在线阅读，更多相关《离散数学第九章代数系统.ppt（44页珍藏版）》请在三一办公上搜索。
1、1,第三部分 代数结构,主要内容代数系统-二元运算及其性质、代数系统和子代数半群与群-半群、独异点、群环与域-环、整环、域格与布尔代数-格、布尔代数,2,第九章 代数系统,主要内容二元运算及其性质一元和二元运算定义及其实例二元运算的性质代数系统代数系统定义及其实例子代数积代数代数系统的同态与同构,3,9.1 二元运算及其性质,定义9.1 设S为集合，函数f：SSS 称为S上的二元运算，简称为二元运算S中任何两个元素都可以进行运算，且运算的结果惟一S中任何两个元素的运算结果都属于S，即S对该运算封闭,例1(1)自然数集合N上的加法和乘法是N上的二元运算，但减法和除法不是(2)整数集合Z上的加法、
2、减法和乘法都是Z上的二元运算，而除法不是(3)非零实数集R*上的乘法和除法都是R*上的二元运算，而加法和减法不是,4,实例,(4)设Mn(R)表示所有n 阶(n2)实矩阵的集合，即 则矩阵加法和乘法都是Mn(R)上的二元运算.(5)S为任意集合，则、为P(S)上二元运算.(6)SS为S上的所有函数的集合，则合成运算为SS上二元运算.,5,一元运算的定义与实例,定义9.2 设S为集合，函数 f:SS 称为S上的一元运算，简称一元运算.例2(1)求相反数是整数集合Z,有理数集合Q和实数集合R上的一元运算(2)求倒数是非零有理数集合Q*,非零实数集合R*上一元运算(3)求共轭复数是复数集合C上的一元
3、运算(4)在幂集P(S)上规定全集为S，则求绝对补运算是P(S)上的一元运算.(5)设S为集合，令A为S上所有双射函数的集合，ASS，求一个双射函数的反函数为A上的一元运算.(6)在n(n2)阶实矩阵的集合Mn(R)上，求转置矩阵是Mn(R)上的一元运算.,6,二元与一元运算的表示,1算符可以用,等符号表示二元或一元运算，称为算符.对二元运算，如果 x 与 y 运算得到 z，记做 xy=z对一元运算,x的运算结果记作x.,2表示二元或一元运算的方法:解析公式和运算表公式表示 例 设R为实数集合，如下定义R上的二元运算：x,yR,x y=x.那么 34=3，0.5(3)=0.5,7,运算表：表示
4、有穷集上的一元和二元运算,运算表,二元运算的运算表 一元运算的运算表,8,例3 设 S=P(a,b)，S上的和 运算的运算表如下,运算表的实例,9,二元运算的性质,定义9.3 设为S上的二元运算,(1)若对任意x,yS 有 xy=yx,则称运算在S上满足交换律.(2)若对任意x,y,zS有(xy)z=x(yz),则称运算在S上满足结 合律.(3)若对任意xS 有 xx=x,则称运算在S上满足幂等律.,定义9.4 设和为S上两个不同的二元运算,(1)若对任意x,y,zS有(xy)z=(xz)(yz)，z(xy)=(zx)(zy),则称运算对运算满足分配律.(2)若和都可交换,且对任意x,yS有
5、x(xy)=x，x(xy)=x,则称和运算满足吸收律.,10,实例,Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA为从A到A的函数集，|A|2,11,实例,Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA为从A到A的函数集，|A|2,12,特异元素：单位元、零元,定义9.5 设为S上的二元运算,(1)如果存在el(或er)S，使得对任意 xS 都有 elx=x(或 xer=x)，则称el(或er)是S中关于运算的左(或右)单位元.若eS关于运算既是左单位元又是右单位元，则称e为S上关于运算的单位元.单位元
6、也叫做幺元.(2)如果存在 l(或 r)S，使得对任意 xS 都有 l x=l(或 x r=r)，则称 l(或 r)是S 中关于运算的左(或右)零元.若 S 关于运算既是左零元又是右零元，则称为S上关于运算的零元.,13,可逆元素和逆元,(3)设为S上的二元运算,令e为S中关于运算的单位元.对于xS，如果存在yl(或yr)S使得 ylx=e（或xyr=e）则称yl(或 yr)是x的左逆元（或右逆元）.关于运算，若yS 既是 x 的左逆元又是 x 的右逆元，则称 y为x的逆元.如果 x 的逆元存在，就称 x 是可逆的.,14,实例,15,惟一性定理,定理9.1 设为S上的二元运算，el和er分别
7、为S中关于运算的左和右单位元，则el=er=e为S上关于运算的惟一的单位元.证：el=eler(er为右单位元)eler=er(el为左单位元)所以el=er,将这个单位元记作e.假设e也是 S 中的单位元，则有 e=ee=e.惟一性得证.类似地可以证明关于零元的惟一性定理.注意：当|S|2，单位元与零元是不同的；当|S|=1时，这个元素既是单位元也是零元.,16,定理9.2 设为S上可结合的二元运算,e为该运算的单位元,对于xS 如果存在左逆元 yl 和右逆元 yr,则有 yl=yr=y,且 y是 x 的惟一的逆元.证：由 ylx=e 和 xyr=e 得 yl=yle=yl(xyr)=(yl
8、x)yr=eyr=yr令yl=yr=y,则 y 是 x 的逆元.假若 yS 也是 x 的逆元,则 y=ye=y(xy)=(yx)y=ey=y所以 y 是 x 惟一的逆元.说明：对于可结合的二元运算，可逆元素 x 只有惟一的逆 元，记作 x1,惟一性定理,17,9.2 代数系统,定义9.6 非空集合S和S上k个一元或二元运算f1,f2,fk组成的系统称为代数系统,简称代数，记做.实例：(1),是代数系统，+和分别表示普通加法和乘法.(2)是代数系统，和分别表示 n 阶(n2)实矩阵的加法和乘法.(3)是代数系统，Zn0,1,n-1，和分别表示模n的加法和乘法，对于x,yZn，xy=(xy)mod
9、n，xy=(xy)modn(4)是代数系统，和为并和交，为绝对补,18,代数系统的成分与表示,构成代数系统的成分：集合（也叫载体，规定了参与运算的元素）运算（这里只讨论有限个二元和一元运算）代数常数（通常是与运算相关的特异元素：如单位元等）研究代数系统时，如果把运算具有的特异元素也作为系统的性质之一，那么这些特异元素可以作为系统的成分，叫做代数常数.例如：代数系统：集合Z,运算+,代数常数0代数系统：集合P(S),运算和，无代数常数,19,代数系统的表示,(1)列出所有的成分：集合、运算、代数常数（如果存在）如,(2)列出集合和运算，在规定系统性质时不涉及具有单位元 的性质（无代数常数）如,(
10、3)用集合名称简单标记代数系统 在前面已经对代数系统作了说明的前提下使用 如代数系统Z,P(B),20,同类型与同种代数系统,定义9.7(1)如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是同类型的代数系统.(2)如果两个同类型的代数系统规定的运算性质也相同，则称为同种的代数系统.例如 V1=,V2=V1,V2是同类型的代数系统，它们都含有2个二元运算,2个代数常数.,21,运算性质比较,V1=,V2=,所以,V1,V2是同类型的代数系统,但不是同种的代数系统.,22,子代数系统,定义9.8设V=是代数系统，B是S的非空子集，如果B对f1,f2,fk 都
11、是封闭的，且B和S含有相同的代数常数，则称是V的子代数系统，简称子代数.有时将子代数系统简记为B.,实例N是的子代数，N也是的子代数N0是的子代数，但不是的子代数说明：子代数和原代数是同种的代数系统对于任何代数系统V=，其子代数一定存在.,23,关于子代数的术语,(1)最大的子代数：就是V本身(2)最小的子代数：如果令V中所有代数常数构成的集合是 B，且B对V中所有的运算都是封闭的，则B就构成了V的 最小的子代数(3)最大和最小的子代数称为V 的平凡的子代数(4)若B是S的真子集，则B构成的子代数称为V的真子代数.例 设V=,令 nZ=nz|zZ,n为自然数，则nZ是V的子 代数 当n=1和0
12、时，nZ是V的平凡的子代数，其他的都是V的非 平凡的真子代数.,24,积代数,定义9.9 设V1=和V2=是同类型的代数系统，和为二元运算，在集合AB上如下定义二元运算，,AB，有=称V=为V1与V2的积代数，记作V1V2.这时也称V1和V2为V的因子代数.,实例 Z2=0,1，V=，V1V2=Z2Z2=,=注意：积代数的定义可以推广到具有多个运算的同类型的代数系统,模2的加法:x,y Z2x y=(x+y)mod 2,25,积代数,实例 已知Z2=0,1，V=，其中为模2的加法:x,y Z2,有x y=(x+y)mod 2.求 V1V2=,注意：积代数的定义可以推广到具有多个运算的同类型的代
13、数系统,解:Z2Z2=,26,积代数,例 V1=,V2=,积代数为,ZM2(R),o=,27,积代数的性质,定理9.3 设V1=和V2=是同类型的代数系统，V1V2=是它们的积代数.(1)如果 和 运算是可交换（可结合、幂等）的，那么运算也是可交换（可结合、幂等）的(2)如果 e1 和 e2（1和2）分别为 和 运算的单位元（零元），那么（）也是运算的单位元（零元）(3)如果 x 和 y 分别为和 运算的可逆元素，那么也是运算的可逆元素，其逆元就是,即积代数能够保持因子代数中的许多良好的性质.,28,9.3 代数系统的同态与同构,引言,在现实社会中，存在着很多代数系统，但仔细分析这些众多的代数
14、系统发现，有些代数系统，他们之间表面上似乎不相同，但他们实际上“相同”。如有两个代数系统和，其运算“*”和“。”分别定义如下表,29,9.3 代数系统的同态与同构,代数系统V1=和V2=,若把表1中的奇和偶分别替换成正和负,就可以得到表2,表1,表2,这个替换可以表示成函数:,F=,在双射F的作用下,代数系统V1转换成了代数系统V2.,它们是同构的,都是抽象代数系统a,b的实例.,30,9.3 代数系统的同态与同构,定义9.10 设V1=和V2=是同类型的代数系统，f:AB，且x,yA 有 f(xy)=f(x)f(y),则称 f 是V1到V2的同态映射，简称同态.,31,9.3 代数系统的同态
15、与同构,同态分类：,(1)f 如果是单射，则称为单同态(2)如果是满射，则称为满同态，这时称V2是V1的同态像，记作V1V2(3)如果是双射，则称为同构，也称代数系统V1同构于V2，记作V1V2(4)如果V1=V2，则称作自同态,32,实例(判断自同态),例 V=,判断下面的哪些函数是V 的自同态？(1)f(x)=|x|(2)f(x)=2x(3)f(x)=x2(4)f(x)=1/x(5)f(x)=x(6)f(x)=x+1,解(2),(5),(6)不是自同态.(1)是同态，f(xy)=|xy|=|x|y|=f(x)f(y)(3)是同态，f(xy)=(xy)2=x2 y2=f(x)f(y)(4)是
16、同态，f(xy)=1/(xy)=1/x 1/y=f(x)f(y),33,实例(课本P177 例9.11),(1)设V1=,V2=其中Z为整数集，+为普通加法；Zn=0,1,n1，为模n加.令 f:ZZn，f(x)=(x)mod n 那么 f 是V1到V2的满同态,(3)设V=，其中Z为整数集，+为普通加法.aZ，令 fa:ZZ，fa(x)=ax，那么 fa 是V的自同态.当a=0时称 f0 为零同态；当a=1时，称 fa 为自同构；除此之外其他的 fa 都是单自同态.,(2)设V1=,V2=，其中R和R*分别为实数集与非零实数集，+和 分别表示普通加法与乘法令 f:RR*，f(x)=ex 则
17、f 是V1到V2的单同态.,34,第九章 习题课,主要内容代数系统的构成：非空集合、封闭的二元和一元运算、代数常数 二元运算性质和特异元素：交换律、结合律、幂等律、分配律、吸收律、单位元、零元、可逆元和逆元同类型的与同种的代数系统子代数的定义与实例积代数的定义与性质代数系统的同态与同构,35,基本要求,判断给定集合和运算能否构成代数系统判断给定二元运算的性质求而二元运算的特异元素了解同类型和同种代数系统的概念了解子代数的基本概念计算积代数判断函数是否为同态映射和同构映射,36,练习1,1设运算为Q上的二元运算，x,yQ,xy=x+y+2xy,(1)判断运算是否满足交换律和结合律，并说明理由.(
18、2)求出运算的单位元、零元和所有可逆元素的逆元.,(1)运算可交换，可结合.任取 x,yQ,xy=x+y+2xy=y+x+2yx=y x,任取 x,y,zQ,(xy)z=(x+y+2xy)+z+2(x+y+2xy)z=x+y+z+2xy+2xz+2yz+4xyz x(yz)=x+(y+z+2yz)+2x(y+z+2yz=x+y+z+2xy+2xz+2yz+4xyz,37,(2)设运算的单位元和零元分别为 e 和，则对于任意 x 有 xe=x 成立，即 x+e+2xe=x e=0 由于运算可交换，所以 0 是幺元.对于任意 x 有x=成立，即 x+2x=x+2x=0=1/2 给定 x，设 x 的
19、逆元为 y,则有 xy=0 成立，即 x+y+2xy=0(x 1/2)因此当x 1/2时，是x的逆元.,练习1解答,38,2下面是三个运算表(1)说明那些运算是可交换的、可结合的、幂等的.(2)求出每个运算的单位元、零元、所有可逆元素的逆元,练习2,39,解,练习2解答,(1)*满足交换律，满足结合律，不满足幂等律.不满足交换律，满足结合律，满足幂等律.满足交换律，满足结合律，不满足幂等律.(2)*的单位元为b，没有零元，a1=c,b1=b,c1=a 的单位元和零元都不存在，没有可逆元素.的单位元为 a，零元为c，a1=a，b,c不是可逆元素.说明：关于结合律的判断需要针对运算元素的每种选择进
20、行验证，若|A|=n，一般需要验证n3个等式.单位元和零元不必参与验证.通过对具体运算性质的分析也可能简化验证的复杂性.,40,判别运算性质的方法,通过运算表可以判别运算性质,也可以求运算的特异元素.具体办法如下:如果运算表的元素关于主对角线对称分布,那么运算可交换的.如果主对角线元素的排列顺序与表头元素的顺序一样,那么运算是幂等的.如果一个元素所在行和列的元素排列顺序都与表头元素排列顺序一致,那么这个元素是单位元.如果一个元素的行和列元素都是这个元素自身,那么这个元素是零元.,41,练习3,3.设G为非0实数集R*关于普通乘法构成的代数系统，判断下述函数是否为G的自同态？如果不是，说明理由.
21、如果是，判别它们是否为单同态、满同态、同构.(1)f(x)=|x|+1(2)f(x)=|x|(3)f(x)=0(4)f(x)=2,42,解答,解(1)不是同态,因为 f(22)=f(4)=5,f(2)f(2)=33=9(2)是同态，不是单同态，也不是满同态，因为 f(1)=f(1),且 ran f 中没有负数.(3)不是G 的自同态，因为 f 不是 G 到 G 的函数(4)不是G 的自同态，因为 f(22)=2,f(2)f(2)=22=4 说明：判别或证明同态映射的方法(1)先判断（或证明）f 是G1 到 G2的映射 f:G1G2.如果已 知 f:G1G2，则这步判断可以省去.(2)x,y G
22、1,验证 f(xy)=f(x)f(y)(3)判断同态性质只需判断函数的单射、满射、双射性即可.,43,相关算法-运算的表示,根据不同运算的特点，各种运算在计算机系统中的表示方法也有所不同，有些运算可以用数学等式表示，有些可以用矩阵表示。1.等式法例如，在代数系统中，运算定义为：对于任意,该系统的实现算法为：,getResult(a,b)c=a/2+b/2；return c；,44,相关算法-运算的表示,2.矩阵法例如，在代数系统中，运算定义为：对于任意,该代数系统的运算实现算法为：,getResult(a,b)aIndex=getIndex(a)；bIndex=getIndex(b)；return c；,
