离散数学第九章的课件.

1第三部分代数结构主要内容代数系统----二元运算及其性质、代数系统和子代数半群与群----半群、独异点、群环与域-----环、整环、域格与布尔代数----格、布尔代数2第九章代数系统主要内容二元运算及其性质一元和二元运算定义及其实例二元运算的性质代数系统代数系统定义及其实例子代数积代数代数系统的同态与同构39.1二元运算及其性质定义9.1设S为集合，函数f：SSS称为S上的二元运算，简称为二元运算．验证一个运算是否为集合S上的二元运算主要考虑两点：–S中任何两个元素都可以进行运算，且运算的结果惟一．–S中任何两个元素的运算结果都属于S，即S对该运算封闭．例9.1(1)自然数集合N上的加法和乘法是N上的二元运算，但减法和除法不是．(2)整数集合Z上的加法、减法和乘法都是Z上的二元运算，而除法不是．(3)非零实数集R*上的乘法和除法都是R*上的二元运算，而加法和减法不是．4实例(4)设Mn(R)表示所有n阶(n≥2)实矩阵的集合，即则矩阵加法、减法和乘法都是Mn(R)上的二元运算.(5)S为任意集合，则∪、∩、－、为P(S)上二元运算.(6)SS为S上的所有函数的集合，则合成运算为SS上二元运算.njiRaaaaaaaaaaRMijnnnnnnn,...,2,1,,)(212222111211类似于二元运算，也可以定义集合S上的一元运算。5一元运算的定义与实例定义9.2设S为集合，函数f:S→S称为S上的一元运算，简称一元运算.例9.3(1)求相反数是整数集合Z,有理数集合Q和实数集合R上的一元运算(2)求倒数是非零有理数集合Q*,非零实数集合R*上的一元运算(3)求共轭复数是复数集合C上的一元运算(4)在幂集P(S)上规定全集为S，则求绝对补运算~是P(S)上的一元运算.(5)设S为集合，令A为S上所有双射函数的集合，ASS，求一个双射函数的反函数为A上的一元运算.(6)在n(n≥2)阶实矩阵的集合Mn(R)上，求转置矩阵是Mn(R)上的一元运算.6二元与一元运算的表示1．算符可以用◦,∗,·,,,等符号表示二元或一元运算，称为算符.对二元运算◦，如果x与y运算得到z，记做x◦y=z对一元运算,x的运算结果记作x.2．表示二元或一元运算的方法:解析公式和运算表公式表示例设R为实数集合，如下定义R上的二元运算∗：x,y∈R,x∗y=x.那么3∗4=3，0.5∗(3)=0.5，0∗(1/2)=07运算表：表示有穷集S上的二元运算和一元运算运算表二元运算的运算表一元运算的运算表a1a2...ana1a2...ana1a1a1a2…a1ana2a1a2a2…a2an………ana1ana2…anana1a2...anaia1a2…ana1a2...ana1a2...ana1a1a1a2…a1ana2a1a2a2…a2an………ana1ana2…anana1a2...anaia1a2…an8例9.4设S={1,2},给出P(S)上的运算~和的运算表,其中全集为S.运算表的实例{1}{2}{1,2}{1}{2}{1,2}{1}{2}{1,2}{1}{1,2}{2}{2}{1,2}{1}{1,2}{2}{1}9例9.5设S={1,2,3,4},定义S上的二元运算◦如下:x◦y=(xy)mod5,任意x,y∈S求运算◦的运算表运算表的实例◦12341234123424133142432110二元运算的性质定义9.3设◦为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上满足幂等律.定义9.4设◦和∗为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,则称◦和∗运算满足吸收律.11实例Z,Q,R分别为整数集、有理数集、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA为从A到A的函数集，|A|2集合运算交换律结合律幂等律Z,Q,R普通加法+普通乘法有有有有无无Mn(R)矩阵加法+矩阵乘法有无有有无无P(B)并交相对补对称差有有无有有有无有有有无无AA函数复合无有无12集合运算分配律吸收律Z,Q,R普通加法+与乘法对+可分配+对不分配无Mn(R)矩阵加法+与乘法对+可分配+对不分配无P(B)并与交对可分配对可分配有交与对称差对可分配无实例Z,Q,R分别为整数集、有理数集、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA为从A到A的函数集，|A|213特异元素：单位元、零元定义9.8设◦为S上的二元运算,(1)如果存在el(或er)S，使得对任意x∈S都有el◦x=x(或x◦er=x)，则称el(或er)是S中关于◦运算的左(或右)单位元.若e∈S关于◦运算既是左单位元又是右单位元，则称e为S上关于◦运算的单位元.单位元也叫做幺元.(2)如果存在l(或r)∈S，使得对任意x∈S都有l◦x=l(或x◦r=r)，则称l(或r)是S中关于◦运算的左(或右)零元.若∈S关于◦运算既是左零元又是右零元，则称为S上关于运算◦的零元.14可逆元素和逆元(3)设◦为S上的二元运算,令e为S中关于运算的单位元.对于x∈S，如果存在yl(或yr)∈S使得yl◦x=e（或x◦yr=e）则称yl(或yr)是x的左逆元（或右逆元）.关于◦运算，若y∈S既是x的左逆元又是x的右逆元，则称y为x的逆元.如果x的逆元存在，就称x是可逆的.15实例集合运算单位元零元逆元Z,Q,R普通加法+普通乘法01无0x逆元xx逆元x1(x1给定集合)Mn(R)矩阵加法+矩阵乘法n阶全0矩阵n阶单位矩阵无n阶全0矩阵X逆元XX的逆元X1（X可逆）P(B)并交对称差BB无的逆元为B的逆元为BX的逆元为X16惟一性定理定理9.1设◦为S上的二元运算，el和er分别为S中关于运算的左和右单位元，则el=er=e为S上关于◦运算的惟一的单位元.证：el=el◦er(er为右单位元)el◦er=er(el为左单位元)所以el=er,将这个单位元记作e.假设e也是S中的单位元，则有e=e◦e=e.惟一性得证.类似地可以证明关于零元的惟一性定理（定理9.4）.注意：当|S|2，单位元与零元是不同的；当|S|=1时，这个元素既是单位元也是零元.17定理9.2设◦为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惟一性定理18练习11．设∘运算为Q上的二元运算，x,yQ,x∘y=x+y+2xy,(1)判断∘运算是否满足交换律和结合律，并说明理由.(2)求出∘运算的单位元、零元和所有可逆元素的逆元.(1)∘运算可交换，可结合.任取x,yQ,x∘y=x+y+2xy=y+x+2yx=y∘x,任取x,y,zQ,(x∘y)∘z=(x+y+2xy)+z+2(x+y+2xy)z=x+y+z+2xy+2xz+2yz+4xyzx∘(y∘z)=x+(y+z+2yz)+2x(y+z+2yz)=x+y+z+2xy+2xz+2yz+4xyz19(2)设∘运算的单位元和零元分别为e和，则对于任意x有x∘e=x成立，即x+e+2xe=xe=0由于∘运算可交换，所以0是幺元.对于任意x有x∘=成立，即x++2x=x+2x=0=1/2给定x，设x的逆元为y,则有x∘y=0成立，即x+y+2xy=0(x≠1/2)因此当x1/2时，是x的逆元.xxy21xx21解答1．设∘运算为Q上的二元运算，x,yQ,x∘y=x+y+2xy,(1)判断∘运算是否满足交换律和结合律，并说明理由.(2)求出∘运算的单位元、零元和所有可逆元素的逆元.202．下面是三个运算表(1)说明哪些运算是可交换的、可结合的、幂等的.(2)求出每个运算的单位元、零元、所有可逆元素的逆元练习2abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*21解解答(1)*满足交换律，满足结合律，不满足幂等律.∘不满足交换律，满足结合律，满足幂等律.·满足交换律，满足结合律，不满足幂等律.2．下面是三个运算表(1)说明哪些运算是可交换的、可结合的、幂等的.(2)求出每个运算的单位元、零元、所有可逆元素的逆元abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*22解解答(2)*的单位元为b，没有零元，a1=c,b1=b,c1=a∘的单位元和零元都不存在，没有可逆元素.·的单位元为a，零元为c，a1=a，b,c不是可逆元素.说明：关于结合律的判断需要针对运算元素的每种选择进行验证，若|A|=n，一般需要验证n3个等式.单位元和零元不必参与验证.通过对具体运算性质的分析也可能简化验证的复杂性.2．下面是三个运算表(1)说明哪些运算是可交换的、可结合的、幂等的.(2)求出每个运算的单位元、零元、所有可逆元素的逆元abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*abcbcccccabcaaabbbcccabccababcbcaabcabc·abc∘abc*23作业书本第178页第1题第2题书本第179页第7题第8题249.2代数系统定义9.12非空集合S和S上k个一元或二元运算f1,f2,…,fk组成的系统称