离散数学第9章 代数系统ppt课件.ppt

1/15/2023 7:06 PM,Discrete Math.,Chen Chen,1,离散数学Discrete Mathematics,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,2,第九章 代数系统,9.1 二元运算9.2 代数系统,本章在集合、关系和函数等概念基础上，研究更为复杂的对象代数系统，研究代数系统的性质和特殊的元素，代数系统与代数系统之间的关系。如代数系统的同态、满同态和同构，这些概念较为复杂也较为抽象，是本课程中的难点。它们将集合、集合上的运算以及集合间的函数关系结合在一起进行研究。前面四章内容是本章的基础，熟练地掌握集合、关系、函数等概念和性质是理解本章内容的关键。主要内容如下：,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,3,9.1 二元运算及其性质,二元运算定义及其实例 一元运算定义及其实例 运算的表示 二元运算的性质交换律、结合律、幂等律、消去律分配律、吸收律 二元运算的特异元素单位元零元可逆元素及其逆元,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,4,二元运算的定义及其实例,定义9.1 设 S 为集合,函数 f：SSS 称为 S 上的二元运算,简称为二元运算.也称 S 对 f 封闭.验证一个运算是否为集合S上的二元运算主要考虑两点：1.S中任何两个元素都可以进行这种运算，且运算结果是唯一的；2.S中任何两个元素的运算结果都属于S，即S对该运算是封闭的。,例9.1(1)N 上的二元运算：(2)Z 上的二元运算：(3)非零实数集 R*上的二元运算:(4)设 S=a1,a2,an,ai aj=ai:(5)幂集 P(S)上的二元运算：(6)SS 为 S 上的所有函数的集合：,加法、乘法.加法、减法、乘法.乘法、除法.为 S 上二元运算.,.合成运算.,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,5,二元运算的实例（续）,(7)设 Mn(R)表示所有 n 阶(n2)实矩阵的集合，即,矩阵加法和乘法都是 Mn(R)上的二元运算.,例9.2 设R为实数集合,定义R上的二元运算*：x,yR,x*y=x.计算：*,(-5)*0.2,0*1/2.解：3*4=3,(-5)*0.2=-5,0*1/2=0.,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,6,一元运算的定义与实例,定义9.2 设 S 为集合，函数 f：SS 称为 S 上的一元运算，简称为一元运算.,例9.3(1)Z,Q 和 R 上的一元运算:(2)非零有理数集 Q*，非零实数集 R*上的一元运算:(3)复数集合 C 上的一元运算:(4)幂集 P(S)上,全集为 S:(5)A 为 S 上所有双射函数的集合，ASS:(6)在 Mn(R)(n2)上:,求相反数 求倒数 求共轭复数 求绝对补运算 求反函数 求转置矩阵,算符：,等符号,表示二元或一元运算 对二元运算，如果 x 与 y 运算得到 z，记作xy=z；对一元运算,x 的运算结果记作 x 表示二元或一元运算的方法：公式、运算表注意：在同一问题中不同的运算使用不同的算符,二元与一元运算的表示,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,7,公式表示 例 设 R 为实数集合，如下定义 R 上的二元运算：x,yR,x y=y.那么 3 4=4 0.5(-3)=-3运算表（表示有穷集上的一元和二元运算）,二元与一元运算的表示（续）,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,8,运算表的实例,例9.4 S=P(1,2),分别为对称差和绝对补运算1,2为全集）,的运算表,的运算表,解：,例9.5 Z5=0,1,2,3,4,分别为模 5 加法与乘法,解：,a 1 1,1,1 1.2 2,2 1,2 1,1,2 2 1,1,2,1,2,0 1 2 3 4,1 2 3 4 0,2 3 4 0 1,3 4 0 1 2,4 0 1 2 3,0 0 0 0 0,0 1 2 3 4,0 2 4 1 3,0 3 1 4 2,0 4 3 2 1,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,9,二元运算的性质,定义9.35 设 为 S 上的二元运算,(1)如果x,y S 有 x y=y x,则称运算在 S 上满足交换律.(2)如果x,y,z S 有(x y)z=x(y z),则称运算在 S 上满足结合律.(3)如果x S 有x x=x,则称运算在 S 上满足幂等律.,实例分析,有,有,有,有,有,有,有,有,有,有,有,有,有,有,有,无,无,无,无,无,无,无,无,无,无,无,有,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,10,二元运算的性质（续）,定义9.67 设 和 为 S 上两个不同的二元运算,(1)如果 x,y,zS 有(x y)z=(x z)(y z);z(x y)=(z x)(z y)则称 运算对 运算满足分配律.(2)如果 和 都可交换,并且 x,yS 有 x(x y)=x;x(x y)=x 则称 和 运算满足吸收律.,实例分析,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,11,二元运算的特异元素,单位元定义9.8 设为S上的二元运算,如果存在el（或er）S，使得对任意 xS 都有 el x=x(或 x er=x)，则称 el(或 er)是 S 中关于 运算的 左(或右)单位元.若 eS 关于 运算既是左单位元又是右单位元，则称 e 为 S 上关于 运算的 单位元.单位元也叫做 幺元.,零元定义9.9 设 为 S 上的二元运算,如果存在l（或r）S，使得对任意 xS 都有 l x=l(或 x r=r)，则称l(或r)是 S 中关于 运算的 左(或右)零元.若S关于运算既是左零元又是右零元，则称为 S 上关于运算 的 零元.,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,12,二元运算的特异元素（续）,可逆元素及其逆元 定义9.10 令 e 为 S 中关于运算的单位元.对于 xS，如果存在yl（或 yr）S 使得 yl x=e（或 x yr=e），则称 yl(或 yr)是 x 的 左逆元(或右逆元).关于 运算，若 yS 既是 x 的左逆元又是 x 的右逆元，则称 y 为 x 的逆元.如果 x 的逆元存在，就称 x 是可逆的.,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,13,实例分析,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,14,惟一性定理,定理9.1 设 为S上的二元运算，el 和 er 分别为 S 中关于运算的左和右单位元，则 el=er=e 为 S 上关于 运算的惟一的单位元.证 el=el er=er 所以 el=er,将这个单位元记作 e.假设 e 也是 S 中的单位元，则有 e=e e=e.惟一性得证.类似地可以证明关于零元的惟一性定理.定理9.2 设 为S上的二元运算，l 和r 分别为 S 中关于运算的左和右零元，则 l=r=为 S 上关于 运算的惟一的零元.定理9.3 当|S|2，单位元与零元是不同的；当|S|=1 时，这个元素既是单位元也是零元.,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,15,惟一性定理（续）,定理9.4 设 为 S 上可结合的二元运算,e 为该运算的单位元,对于 xS 如果存在左逆元 yl 和右逆元 yr,则有 yl=yr=y,且 y 是 x 的惟一的逆元.证 由 yl x=e 和 x yr=e 得 yl=yl e=yl(x yr)=(yl x)yr=e yr=yr 令 yl=yr=y,则 y 是 x 的逆元.假若 yS 也是 x 的逆元,则 y=y e=y(x y)=(y x)y=e y=y 所以 y 是 x 惟一的逆元.说明：对于可结合的二元运算，可逆元素 x 只有惟一的逆元，记作 x1.,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,16,消去律,定义9.11 设为V上二元运算，如果 x,y,zV，若 x y=x z，且 x不是零元，则 y=z;若 y x=z x,且 x 不是零元，则 y=z.那么称 运算满足 消去律.实例:(1)Z,Q,R 关于普通加法和乘法满足消去律.(2)Mn(R)关于矩阵加法满足消去律，但是关于乘法不满足消去律.(3)Zn关于模 n 加法满足消去律，当 n 为素数时关于模 n乘法满足消去律.当 n 为合数时关于模 n 乘法不满足消去律.,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,17,例题分析,解(1)运算可交换，可结合，不满足幂等律，满足消去律。x,yQ,x y=x+y-xy=y+x-yx=y x,即有 运算可交换。x,y,zQ,(x y)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-xy-xz-yz+xyz 故(x y)z=x(y z)，即有 运算可结合。,例9.6 设 运算为 Q 上的二元运算，x,yQ,xy=x+y-xy,(1)指出运算的性质.(2)求 运算的单位元、零元和所有可逆元.,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,18,给定 x，设 x 的逆元为 y,则有 x y=0 成立，即 x+y-xy=0(x=1)因此当 x 1时，是 x 的逆元.,例题分析（续）,(2)设运算的单位元和零元分别为 e 和，则 x 有 xe=x 成立，即 x+e-xe=x e=0 由于 运算可交换，所以 0 是幺元.,x 有 x=成立，即 x+-x=x-x=0=1,运算不满足幂等律：因为2Q，但 2 2=2+2-22=0 2。,运算满足消去律。x,y,zQ,（x1）有x y=x z x+y-xy=x+z-xz(y-z)=x(y-z)y=z 故 运算满足左消去律。,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,19,例题分析（续）,例9.7(1)说明那些运算是交换的、可结合的、幂等的.(2)求出运算的单位元、零元、所有可逆元素的逆元.,解(1)满足交换、结合律；满足结合、幂等律；满足交换、结合律.,(2)的单位元为 b,没零元，a1=c,b1=b,c1=a 的单位元和零元都不存在，没有可逆元素.的单位元为 a，零元为c,a1=a.b,c不可逆.,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,20,例题分析（续）,例 设 A=a,b,c,构造 A 上的二元运算*使得 a*b=c,c*b=b,且*运算是幂等的、可交换的，给出关于*运算的一个运算表，说明它是否可结合，为什么？,c,b,根据幂等律和已知条件a*b=c,c*b=b 得到运算表,根据交换律得到新的运算表,方框 可以填入a,b,c中任一选定的符号,完成运算表,不结合，因为(a*b)*b=c*b=b,a*(b*b)=a*b=c,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,21,由运算表判别算律的一般方法,交换律：运算表关于主对角线对称幂等律：主对角线元素排列与表头顺序一致消去律：所在的行与列中没有重复元素单位元:所在的行与列的元素排列都与表头一致零元：元素的行与列都由该元素自身构成A 的可逆元：a 所在的行中某列(比如第 j 列)元素为 e，且第 j 行 i 列的元素也是 e，那么 a 与第 j 个元素互逆结合律：除了单位元、零元之外，要对所有3个元素的组合验证表示结合律的等式是否成立,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,22,代数系统定义同类型代数系统子代数,9.2 代数系统,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,23,代数系统定义与实例,定义 9.12非空集合 S 和 S 上 k 个一元或二元运算 f1,f2,fk 组成的系统称为一个代数系统,简称代数，记做 V=.,实例:(1),是代数系统，+和 分别表示普通加法和乘法.(2)是代数系统，+和 分别表示n 阶(n2)实矩阵的加法和乘法.(3)是代数系统，Zn0,1,n-1，和 分别表示模 n 的加法和乘法，x,yZn，xy=(xy)mod n，xy=(xy)mod n(4)也是代数系统，和为并和交，为绝对补,S 称为代数系统的载体，S 和运算叫做代数系统的成分.有的代数系统定义指定了S中的特殊元素，称为代数常数,例如二元运算的单位元.有时也将代数常数作为系统的成分.,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,24,同类型代数系统,定义9.13 如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称这两个代数系统具有相同的构成成分,也称它们是 同类型的 代数系统.例:V1=,V2=,为 n 阶全 0 矩阵，E 为 n 阶单位矩阵 V3=,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,25,子代数,定义9.14 设V=是代数系统，B 是 S 的非空子集，如果 B 对 f1,f2,fk 都是封闭的，且 B 和 S 含有相同的代数常数，则称 是 V 的子代数系统，简称 子代数.有时将子代数系统简记为 B.实例 N是 和的子代数.N0是的子代数，但不是的子代数说明：代数和原代数是同类型的代数系统 对于任何代数系统 V，其子代数一定存在.,最大的子代数 就是V 本身.如果V 中所有代数常数构成集合 B，且 B 对V 中所有运算封闭，则 B 就构成了V 的最小的子代数.最大和最小子代数称为V 的平凡的子代数.若 B 是 S 的真子集，则 B 构成的子代数称为V 的真子代数.,1/15/2023 7:06 PM,Discrete Math.,Chen Chen,26,子代数,例9.8 设V=，令 nZ=nz|zZ，n 为自然数，则(1)nZ 是 V 的子代数,(2)当 n=1 和 0 时，nZ 是 V 的平凡的子代数，(3)其他的n都是 V 的非平凡的真子代数.,