离散数学(三)

一、本部分的主要内容代数系统----二元运算及其性质、代数系统和子代数半群与群----半群、独异点、群环与域-----环、整环、域格与布尔代数----格、布尔代数二、本部分的基本要求掌握代数系统的基本概念掌握各种重要的代数系统的定义和性质了解和使用基本的证明方法第三部分代数结构主要内容二元运算及其性质一元和二元运算定义及其实例二元运算的性质代数系统代数系统定义及其实例子代数与后面各章的关系是后面典型代数系统的基础第十章代数系统一、二元运算与一元运算的定义1.二元运算的定义与实例定义10.1设S为集合,函数f：S×S→S称为S上的二元运算,简称为二元运算.也称S对f封闭.例（1）加法、乘法是自然数集合N上的二元运算，减法和除法不是.（2）加法、减法和乘法是整数集合Z上的二元运算，而除法不是.（3）乘法、除法是非零实数集R*上的二元运算，加法、减法不是.（4）设S={a1,a2,…,an},aiaj=ai为S上二元运算.第一节二元运算及其性质（5）设Mn(R)表示所有n阶(n≥2)实矩阵的集合，即njiRaaaaaaaaaaRMijnnnnnnn,...,2,1,,)(212222111211则矩阵加法和乘法都是Mn(R)上的二元运算.（6）S为任意集合，则∪、∩、－、为P(S)上的二元运算.（7）SS为S上的所有函数的集合，则合成运算为SS上的二元运算.2.一元运算的定义与实例定义10.2设S为集合，函数f：S→S称为S上的一元运算，简称为一元运算.例（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)上的一元运算.二、二元与一元运算的表示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运算表（表示有穷集上的一元和二元运算）二元运算的运算表一元运算的运算表a1a2…anaia1a2...ana1a1a1a2…a1ana2a1a2a2…a2an....ana1ana2…anana1a2...ana1a2an例A=P({a,b}),,∼分别为对称差和绝对补运算（{a,b}为全集）的运算表∼的运算表{a}{b}{a,b}x∼x{a}{b}{a,b}{a}{b}{a,b}{a}{a.b}{b}{b}{a,b}{a}{a,b}{b}{a}{a}{b}{a,b}{a,b}{a}{b}三、二元运算的性质1．主要算律定义10.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上满足幂等律.定义10.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,则称和∗运算满足吸收律.例Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA为从A到A的函数集，|A|2集合运算交换律结合律幂等律Z,Q,R普通加法+普通乘法有有有有无无Mn(R)矩阵加法+矩阵乘法有无有有无无P(B)并交相对补对称差有有无有有有无有有有无无AA函数符合无有无例Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA为从A到A的函数集，|A|2集合运算分配律吸收律Z,Q,R普通加法+与乘法对+可分配+对不分配无Mn(R)矩阵加法+与乘法对+可分配+对不分配无并与交对可分配对可分配有P(B)交与对称差对可分配无2．特异元素：单位元、零元和逆元定义10.5设为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上关于运算的零元.（3）可逆元素及其逆元令e为S中关于运算的单位元.对于x∈S，如果存在yl（或yr）∈S使得ylx=e（或xyr=e），则称yl（或yr）是x的左逆元（或右逆元）.关于运算，若y∈S既是x的左逆元又是x的右逆元，则称y为x的逆元.如果x的逆元存在，就称x是可逆的.例特异元素的实例集合运算单位元零元逆元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的逆元为X3．惟一性定理.定理10.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.惟一性得证.类似地可以证明关于零元的惟一性定理.注意：当|S|2，单位元与零元是不同的；当|S|=1时，这个元素既是单位元也是零元..定理10.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.一、代数系统的定义与实例1．代数系统的定义定义10.6非空集合S和S上k个一元或二元运算f1,f2,…,fk组成的系统称为一个代数系统,简称代数，记做S,f1,f2,…,fk.实例：N,＋,Z,＋,·,R,＋,·是代数系统，+和·分别表示普通加法和乘法.Mn(R),＋,·是代数系统，＋和·分别表示n阶(n≥2)实矩阵的加法和乘法.Zn,,是代数系统，Zn＝{0,1,…,n-1}，和分别表示模n的加法和乘法，对于x,y∈Zn，xy=(x＋y)modn，xy=(xy)modnP(S),,,~也是代数系统，和为并和交，~为绝对补第二节代数系统2.代数系统的成分与表示（1）构成代数系统的成分：集合（也叫载体，规定了参与运算的元素）运算（这里只讨论有限个二元和一元运算）代数常数（通常是与运算相关的特异元素：如单位元等）研究代数系统时，如果把运算具有它的特异元素也作为系统的性质之一，那么这些特异元素可以作为系统的成分，叫做代数常数.例如：代数系统Z,+,0：集合Z,运算+,代数常数0代数系统P(S),∪,∩：集合P(S),运算∪和∩，无代数常数（2）代数系统的表示列出所有的成分：集合、运算、代数常数（如果存在）如Z,+,0,P(S),∪,∩列出集合和运算，在规定系统性质时不涉及具有单位元的性质（无代数常数）如Z,+,P(S),∪,∩用集合名称简单标记代数系统在前面已经对代数系统作了说明的前提下使用如代数系统Z,P(B)3．同类型与同种代数系统定义10.7（1）如果两个代数系统中运算的个数相同，对应运算的元数相同，且代数常数的个数也相同，则称它们是同类型的代数系统.（2）如果两个同类型的代数系统规定的运算性质也相同，则称为同种的代数系统.例如V1=R,+,·,0,1,V2=Mn(R),+,·,,E,为n阶全0矩阵，E为n阶单位矩阵V3=P(B),∪,∩,,BV1,V2,V3是同类型的代数系统，它们都含有2个二元运算,2个代数常数.V1,V2是同种的代数系统，V1,V2与V3不是同种的代数系统V1,V2,V3的运算性质比较V1V2V3+可交换、可结合·可交换、可结合+满足消去律·满足消去律·对+可分配+对·不可分配+与·没有吸收律+可交换、可结合·可交换、可结合+满足消去律·满足消去律·对+可分配+对·不可分配+与·没有吸收律∪可交换、可结合∩可交换、可结合∪不满足消去律∩不满足消去律∩对∪可分配∪对∩可分配∪与∩满足吸收律二、子代数系统1．定义定义10.8设V=S,f1,f2,…,fk是代数系统，B是S的非空子集，如果B对f1,f2,…,fk都是封闭的，且B和S含有相同的代数常数，则称B,f1,f2,…,fk是V的子代数系统，简称子代数.有时将子代数系统简记为B.2．实例N是Z,＋的子代数，N也是Z,＋,0的子代数N{0}是Z,＋的子代数，但不是Z,＋,0的子代数说明：子代数和原代数是同种的代数系统对于任何代数系统V=S,f1,f2,…,fk，其子代数一定存在.3．关于子代数的术语（1）最大的子代数：就是V本身（2）最小的子代数：如果令V中所有代数常数构成的集合是B，且B对V中所有的运算都是封闭的，则B就构成了V的最小的子代数（3）平凡的子代数：最大和最小的子代数称为V的平凡的子代数（4）真子代数：若B是S的真子集，则B构成的子代数称为V的真子代数.例设V=Z,+,0,令nZ={nz|zZ},n为自然数，则nZ是V的子代数当n=1和0时，nZ是V的平凡的子代数，其他的都是V的非平凡的真子代数.一、本章的主要内容及要求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+4xyz一、练习1．设运算为Q上的二元运算，x,yQ,xy=x+y+2xy,（1）判断运算是否满足交换律和结合律，并说明理由.（2）求出运算的单位元、零元和所有可逆元素的逆元.解（2）设运算的单位元和零元分别为e和，则对于任意x有xe=x成立，即x+e+2xe=xe=01+2x=0由于运算可交换，所以0是幺元.对于任意x有x=成立，即x++2x=x+2x=0=1/2给定x，设x的