离散数学第9章-代数系统

CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen1离散数学DiscreteMathematicsCHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen2第九章代数系统§9.1二元运算§9.2代数系统本章在集合、关系和函数等概念基础上，研究更为复杂的对象——代数系统，研究代数系统的性质和特殊的元素，代数系统与代数系统之间的关系。如代数系统的同态、满同态和同构，这些概念较为复杂也较为抽象，是本课程中的难点。它们将集合、集合上的运算以及集合间的函数关系结合在一起进行研究。前面四章内容是本章的基础，熟练地掌握集合、关系、函数等概念和性质是理解本章内容的关键。主要内容如下：CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen39.1二元运算及其性质二元运算定义及其实例一元运算定义及其实例运算的表示二元运算的性质交换律、结合律、幂等律、消去律分配律、吸收律二元运算的特异元素单位元零元可逆元素及其逆元CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen4二元运算的定义及其实例定义9.1设S为集合,函数f：S×S→S称为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上二元运算.∪,∩,－,.合成运算∘.CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen5二元运算的实例（续）(7)设Mn(R)表示所有n阶(n≥2)实矩阵的集合，即njiRaaaaaaaaaaRMijnnnnnnn,...,2,1,,)(212222111211矩阵加法和乘法都是Mn(R)上的二元运算.例9.2设R为实数集合,定义R上的二元运算*：x,y∈R,x*y=x.计算：３*４,(-5)*0.2,0*1/2.解：3*4=3,(-5)*0.2=-5,0*1/2=0.CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen6一元运算的定义与实例定义9.2设S为集合，函数f：S→S称为S上的一元运算，简称为一元运算.例9.3(1)Z,Q和R上的一元运算:(2)非零有理数集Q*，非零实数集R*上的一元运算:(3)复数集合C上的一元运算:(4)幂集P(S)上,全集为S:(5)A为S上所有双射函数的集合，ASS:(6)在Mn(R)(n≥2)上:求相反数求倒数求共轭复数求绝对补运算~求反函数求转置矩阵算符：∘,∗,·,,等符号,表示二元或一元运算对二元运算∘，如果x与y运算得到z，记作x∘y=z；对一元运算∘,x的运算结果记作∘x表示二元或一元运算的方法：公式、运算表注意：在同一问题中不同的运算使用不同的算符二元与一元运算的表示CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen7公式表示例设R为实数集合，如下定义R上的二元运算∗：x,y∈R,x∗y=y.那么3∗4=40.5∗(-3)=-3运算表（表示有穷集上的一元和二元运算）二元与一元运算的表示（续）∘a1a2…an∘aia1a2...ana1∘a1a1∘a2…a1∘ana2∘a1a2∘a2…a2∘an.........an∘a1an∘a2…an∘ana1a2...an∘a1∘a2...∘anCHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen8运算表的实例{1}{1}{1,1}{1}{2}{1,2}例9.4S=P({1,2}),,∼分别为对称差和绝对补运算{1,2}为全集）的运算表∼的运算表解：例9.5Z5={0,1,2,3,4},,分别为模5加法与乘法0123401234解：0123401234a∼a{1}{2}{1,2}{a}{1}{1,1}{1}{1.2}{2}{2}{1,2}{1}{1,2}{2}{1}{1,2}{1}{2}01234123402340134012401230000001234024130314204321CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen9二元运算的性质定义9.3~5设∘为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上满足幂等律.集合运算交换律结合律幂等律Z,Q,R普通加法+普通乘法Mn(R)(n2)矩阵加法+矩阵乘法P(B)并交相对补对称差AA(|A|2)函数符合实例分析有有有有有有有有有有有有有有有无无无无无无无无无无无有CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen10二元运算的性质（续）定义9.6~7设∘和∗为S上两个不同的二元运算,(1)如果x,y,z∈S有(x∗y)∘z=(x∘z)∗(y∘z);z∘(x∗y)=(z∘x)∗(z∘y)则称∘运算对∗运算满足分配律.(2)如果∘和∗都可交换,并且x,y∈S有x∘(x∗y)=x;x∗(x∘y)=x则称∘和∗运算满足吸收律.集合运算分配律吸收律Z,Q,R普通加法+与乘法对+可分配无+对不分配Mn(R)矩阵加法+与乘法对+可分配无+对不分配P(B)并与交对可分配有对可分配交与对称差对可分配无对不分配实例分析CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen11二元运算的特异元素单位元定义9.8设∘为S上的二元运算,如果存在el（或er）S，使得对任意x∈S都有el∘x=x(或x∘er=x)，则称el(或er)是S中关于∘运算的左(或右)单位元.若e∈S关于∘运算既是左单位元又是右单位元，则称e为S上关于∘运算的单位元.单位元也叫做幺元.零元定义9.9设∘为S上的二元运算,如果存在θl（或θr）∈S，使得对任意x∈S都有θl∘x=θl(或x∘θr=θr)，则称θl(或θr)是S中关于∘运算的左(或右)零元.若θ∈S关于∘运算既是左零元又是右零元，则称θ为S上关于运算∘的零元.CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen12二元运算的特异元素（续）可逆元素及其逆元定义9.10令e为S中关于运算∘的单位元.对于x∈S，如果存在yl（或yr）∈S使得yl∘x=e（或x∘yr=e），则称yl(或yr)是x的左逆元(或右逆元).关于∘运算，若y∈S既是x的左逆元又是x的右逆元，则称y为x的逆元.如果x的逆元存在，就称x是可逆的.CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen13实例分析集合运算单位元零元逆元Z,Q,R普通加法+普通乘法Mn(R)矩阵加法+矩阵乘法P(B)并交对称差0无X的逆元x10X的逆元x1(x-1属于给定集合)n阶全0矩阵无X逆元Xn阶单位矩阵n阶全0矩阵X的逆元X1（X是可逆矩阵）B的逆元为BB的逆元为B无X的逆元为XCHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen14惟一性定理定理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时，这个元素既是单位元也是零元.CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen15惟一性定理（续）定理9.4设∘为S上可结合的二元运算,e为该运算的单位元,对于x∈S如果存在左逆元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的逆元.假若y’∈S也是x的逆元,则y'=y’∘e=y’∘(x∘y)=(y’∘x)∘y=e∘y=y所以y是x惟一的逆元.说明：对于可结合的二元运算，可逆元素x只有惟一的逆元，记作x1.CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen16消去律定义9.11设∘为V上二元运算，如果x,y,zV，若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乘法不满足消去律.CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen17例题分析解(1)∘运算可交换，可结合，不满足幂等律，满足消去律。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+z-xy-xz-yz+xyzx∘(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,yQ,x∘y=x+y-xy,(1)指出∘运算的性质.(2)求∘运算的单位元、零元和所有可逆元.CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen18给定x，设x的逆元为y,则有x∘y=0成立，即x+y-xy=0(x=1)因此当x1时，是x的逆元.1xyx1xyx例题分析（续）(2)设∘运算的单位元和零元分别为e和，则x有x∘e=x成立，即x+e-xe=xe=0由于∘运算可交换，所以0是幺元.x有x∘=成立，即x+-x=x-x=0=1∘运算不满足幂等律：因为2Q，但2∘2=2+2-22=0≠2。∘运算满足消去律。x,y,zQ,（x≠1）有x∘y=x∘zx+y-xy=x+z-xz(y-z)=x(y-z)y=z故∘运算满足左消去律。CHAPTERTEN4/26/20206:57PMDiscreteMath.,ChenChen19例题分析（续）例9.7(1)说明那些运算是交换的、可结合的、幂等的.(2)求出运算的单位元、零元、所有可逆元素的逆元.abc∘abcabcabccababcbcaabcaaabbbcccabcabcbccccc解(1)满足交换、结合律；∘满足结合、幂等律；满足交换、结合律.(2)的单位元为b,没零元，a1=c,b1=b,c1=a∘的单位元和零元都不存在，没有可逆元素