离散数学-代数系统

第5章代数系统离散数学本章说明本章的主要内容–一元和二元运算定义及其实例–二元运算的性质–代数系统定义及其实例–子代数与后面各章的关系–是后面典型代数系统的基础5.1二元运算及其性质5.2代数系统本章小结作业本章内容5.1二元运算及其性质定义5.1设S为集合，函数f：S×S→S称为S上的二元运算，简称为二元运算。举例f:N×N→N，f(x,y)＝x+y是自然数集合N上的二元运算f:N×N→N，f(x,y)＝x-y不是自然数集合N上的二元运算称N对减法不封闭。说明验证一个运算是否为集合S上的二元运算主要考虑两点：S中任何两个元素都可以进行这种运算，且运算的结果是唯一的。S中任何两个元素的运算结果都属于S，即S对该运算是封闭的。（1）自然数集合N上的加法和乘法是N上的二元运算，但减法和除法不是。（2）整数集合Z上的加法、减法和乘法都是Z上的二元运算，而除法不是。（3）非零实数集R*上的乘法和除法都是R*上的二元运算，加法、减法不是。（4）设S＝{a1,a2,…,an}，aiaj=ai为S上二元运算。例5.1例5.1（5）设Mn(R)表示所有n阶(n≥2)实矩阵的集合，即111212122212(),,1,2,...,nnnijnnnnaaaaaaMRaRijnaaa则矩阵加法和乘法都是Mn(R)上的二元运算。（6）S为任意集合，则∪、∩、－、为P(S)上的二元运算。（7）SS为S上的所有函数的集合，则合成运算为SS上的二元运算。一元运算定义5.2设S为集合，函数f：S→S称为S上的一元运算，简称为一元运算。例5.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)上的一元运算。一元运算举例可以用、、·、、、等符号表示二元或一元运算，称为算符。–设f:S×S→S是S上的二元运算，对任意的x,y∈S，如果x与y的运算结果为z，即f(x,y)＝z，可以利用算符简记为xy=z。–对一元运算，x的运算结果记作x。例题设R为实数集合，如下定义R上的二元运算x,y∈R，xy=x。那么34=3，0.5(3)=0.5。二元与一元运算的算符函数的解析公式运算表（表示有穷集上的一元和二元运算）二元运算的运算表anan…ana2ana1an……………a2an…a2a2a2a1a2a1an…a1a2a1a1a1an…a2a1一元运算的运算表anan……a2a2a1a1aiai二元与一元运算的表示例5.4设S={1,2}，给出P(S)上的运算和~的运算表，其中全集为S。的运算表{1}{2}{1,2}{1,2}{1}{1,2}{2}{2}{2}{1,2}{1}{1}{1,2}{2}{1}{1,2}{2}{1}~的运算表{1,2}{1}{2}{2}{1}{1,2}~aiai解答例5.4例5.5设S={1,2,3,4}，定义S上的二元运算如下xy＝(xy)mod5，x,y∈S求运算的运算表。解答例5.5123411234224133314244321定义5.3设为S上的二元运算，如果对于任意的x,y∈S都有xy=yx，则称运算在S上满足交换律。定义5.4设为S上的二元运算，如果对于任意的x,y,z∈S都有(xy)z=x(yz)，则称运算在S上满足结合律。说明：若+适合结合律，则有(x+y)+(u+v)＝x+y+u+v。二元运算的性质二元运算的性质定义5.5设为S上的二元运算，如果对于任意的x∈S有xx=x，则称运算在S上满足幂等律。如果S中的某些x满足xx=x，则称x为运算的幂等元。举例：普通的加法和乘法不适合幂等律。但0是加法的幂等元，0和1是乘法的幂等元。例题Z,Q,R分别为整数、有理数、实数集；Mn(R)为n阶实矩阵集合,n2；P(B)为幂集；AA为从A到A的函数集，|A|2。集合运算交换律结合律幂等律Z,Q,R普通加法+普通乘法有有有有无无Mn(R)矩阵加法+矩阵乘法有无有有无无P(B)并∪交∩相对补对称差有有无有有有无有有有无无AA函数复合无有无定义5.6设和为S上两个二元运算，如果对于任意的x,y,z∈S，有x(yz)＝(xy)(xz)（左分配律）(yz)x＝(yx)(zx)（右分配律）则称运算对运算满足分配律。说明：若*对运算分配律成立，则*对运算广义分配律也成立。x(y1y2…yn)＝(xy1)(xy2)…(xyn)(y1y2…yn)x＝(y1x)(y2x)…(ynx)二元运算的性质定义5.7设和为S上两个可交换的二元运算，如果对于任意的x,y∈S，都有x(xy)＝xx(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)并∪与交∩∪对∩可分配∩对∪可分配有交∩与对称差∩对可分配无例题定义5.8设为S上的二元运算，如果存在元素el（或er）S，使得对任意x∈S都有elx=x(或xer=x)则称el(或er)是S中关于运算的一个左单位元(或右单位元)。若e∈S关于运算既是左单位元又是右单位元，则称e为S上关于运算的单位元。单位元也叫做幺元。运算可以没有左单位元和右单位元。运算可以只有左单位元。运算可以只有右单位元。运算可以既有左单位元，又有右单位元。说明二元运算中的特异元素—单位元二元运算中的特异元素—零元定义5.9设为S上的二元运算，如果存在元素θl（或θr）∈S，使得对任意x∈S都有θlx=θl(或xθr=θr)，则称θl(或θr)是S上关于运算的左零元(或右零元)。若θ∈S关于运算既是左零元又是右零元，则称θ为S上关于运算的零元。运算可以没有左零元和右零元。运算可以只有左零元。运算可以只有右零元。运算可以既有左零元，又有右零元。说明二元运算中的特异元素—逆元定义5.10设为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是可逆的。运算可以没有左逆元和右逆元。运算可以只有左逆元。运算可以只有右逆元。运算可以既有左逆元，又有右逆元。说明特异元素的实例集合运算单位元零元逆元Z,Q,R普通加法普通乘法01无0x的逆元xx的逆元x1Mn(R)矩阵加法矩阵乘法n阶全0矩阵n阶单位矩阵无n阶全0矩阵x逆元xx的逆元x1（x可逆）P(B)并∪交∩BB的逆元为B的逆元为B定理5.1定理5.1设为S上的二元运算，el、er分别为运算的左单位元和右单位元，则有el=er=e且e为S上关于运算的唯一的单位元。el＝eler(er为右单位元)eler＝er(el为左单位元)所以el=er，将这个单位元记作e。假设e也是S中的单位元，则有e=ee=e所以，e是S中关于运算的唯一的单位元。证明定理5.2定理5.2设为S上的二元运算，l和r分别为运算的左零元和右零元，则有l=r=且为S上关于运算的唯一的零元。l＝lr(r为左零元)lr＝r(l为右零元)所以l=r，将这个零元记作。假设也是S中的零元，则有==所以，是S中关于运算的唯一的零元。证明定理5.3定理5.3设为S上的二元运算，e和分别为运算的单位元和零元，如果S至少有两个元素，则e。用反证法。假设e=，则x∈S有x＝xe＝x＝这与S中至少含有两个元素矛盾。所以，假设不成立，即e。证明定理5.4定理5.4设为S上可结合的二元运算，e为该运算的单位元，对于x∈S，如果存在左逆元yl和右逆元yr，则有yl=yr=y且y是x的唯一的逆元。由ylx=e和xyr=e，得证明yl=yle令yl=yr=y，则y是x的逆元。=yl(xyr)=(ylx)yr=eyr=yr假若yS也是x的逆元，则y=ye=y(xy)=(yx)y=ey=y所以y是x唯一的逆元，记作x1。消去律定义5.11设为S上的二元运算，如果对于任意的x,y,z∈S，满足以下条件：（1）若xy＝xz且x，则y＝z（左消去律）（2）若yx＝zx且x，则y＝z（右消去律）则称运算满足消去律。例如：整数集合上的加法和乘法都满足消去律。幂集P(S)上的并和交运算一般不满足消去律。例5.6例5.6对于下面给定的集合和该集合上的二元运算，指出该运算的性质，并求出它的单位元、零元和所有可逆元素的逆元。（1）Z+，x,y∈Z+，xy＝lcm(x,y)，即求x和y的最小公倍数。（2）Q，x,yQ，xy=x+y-xy解答（1）运算可交换、可结合、是幂等的。xZ+，x1=x，1x=x，1为单位元。不存在零元。只有1有逆元，是它自己，其他正整数无逆元。（2）Q，x,yQ，xy=x+y-xy运算满足交换律，因为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-xy)z=x+y+z-xy-xz-yz+xyzx(yz)=x(y+z-yz)=x+(y+z-yz)-x(y+z-yz)=x+y+z-xy-xz-yz+xyz运算不满足幂等律，因为2Q，但22=2+2-22＝02运算满足消去律，因为x,y,zQ，x1(1为零元)，有xy=xzx+y-xy=x+z-xzy-z=x(y-z)y=z由于是可交换的，所以右消去律成立。同理可证明左消去律成立，所以消去律成立。例5.60是运算的单位元，因为xQ，有x0=x+0-x0=x=0x1是运算的零元，因为xQ，有x1=x+1-x1=1=1xxQ，欲使xy=0和yx=0成立，即x+y-xy=0得(1)xyxx=-1所以，1(1)xxxx=-1例5.7例5.7设A={a,b,c}，A上的二元运算、、如表所示。(1)说明、、运算是否满足交换律、结合律、消去律和幂等律。(2)求出关于、、运算的单位元、零元和所有可逆元素的逆元。abcaabcbbcaccab运算满足交换律、结合律和消去律，不满足幂等律。单位元是a，没有零元，且a-1=a，b-1=c，c-1=b。运算满足交换律、结合律和幂等律，不满足消去律。单位元是a，零元是b，只有a有逆元，a-1=a。运算满足结合律和幂等律，不满足交换律和消去律。没有单位元，没有零元，没有可逆元。解答abcaabcbbbbccbcabcaabcbabccabc复习分析5.2代数系统定义5.12非空集合S和S上k个一元或二元运算f1,f2,…,fk组成的系统称为一个代数系统，简称代数，记做S,f1,f2,…,fk。5.2代数系统实例：N,＋、Z,＋,