离散数学5.

离散数学第五章代数系统的一般性质第三篇代数系统第五章代数系统的一般性质第六章几个典型的代数系统离散数学第三篇代数系统离散数学第五章代数系统的一般性质引入这一部分在集合、关系和函数等概念基础上，研究更为抽象的对象——代数系统。所谓的代数系统是由集合和集合上定义若干个运算而组成的系统。称之为代数系统。主要研究代数系统的性质和特殊的元素；代数系统与代数系统之间的关系，如代数系统的同态和同构。主要内容如下：5.1二元运算及其性质5.2代数系统5.3同态与同构6.1半群6.2群6.3环与域离散数学第三篇代数系统离散数学第五章代数系统的一般性质5.1.1二元运算的基本概念定义5.1设S为集合,函数f:S×S→S称为S上的一个二元运算,简称为二元运算.f:N×N→N,f(x,y)＝x＋y例如:普通的减法不是自然数集合上的二元运算,因为两个自然数相减可能得负数,而负数不属于N.这时也称集合N对减法运算不封闭.例5.11)自然数集N上的乘法是N上的二元运算,但除法不是.5.1二元运算及其性质离散数学第五章代数系统的一般性质2)整数集合Z上的加法、减法和乘法是Z上的二元运算,而除法不是.3)非零实数集R*上的乘法和除法都是R*上的二元运算,而加法、减法不是.4)设Mn(R)表示所有n阶实矩阵的集合(n≥2),即则矩阵加法和乘法都是Mn(R)上的二元运算.5)S为任意集合,则∪,∩,-,为S的幂集P(S)上的二元运算.6)S为集合,SS是S上的所有函数的集合,则合成运算◦是SS上的二元运算.5.1二元运算及其性质离散数学第五章代数系统的一般性质5.1二元运算及其性质5.1.1二元运算的基本概念§算符:通常用◦,*,∙,…等符号表示二元运算,称为算符.设f:S×S→S是S上的二元运算,对任意的x,yS,如x与y的运算结果是z,即f(x,y)＝z,可利用算符◦简记为x◦y=z离散数学第五章代数系统的一般性质5.1二元运算及其性质§N元运算定义5.2设S为集合,n为正整数,则函数称为S上的一个n元运算,简称为n元运算.例:求一个数的相反数是实数集R上的一元运算;求一个数的倒数是非零实数集R*上的一元运算;在幂集合P(S)上,如果规定全集为S,那么求集合的绝对补运算可以看作是P(S)上的一元运算;在空间直角坐标系中求某一点(x,y,z)的坐标在x轴上的投影可以看作是实数集R上的三元运算,因为f(x,y,z)=x,参加运算的是3个有序实数,结果也是实数.离散数学第五章代数系统的一般性质5.1.1二元运算的基本概念§使用算符表示n元运算若f(a1,a2,···,an)=b,则可记为◦(a1,a2,···,an)＝b前缀表示法：◦(a)＝b一元运算,◦(a1,a2)＝b二元运算,◦(a1,a2,a3)＝b三元运算.如果集合S是有穷集,S上的一元和二元运算也可以用运算表给出.表5.1和5.2是一元和二元运算表的一般形式.注意:本书所涉及的代数系统仅限于一、二元运算5.1二元运算及其性质离散数学第五章代数系统的一般性质离散数学第五章代数系统的一般性质5.1二元运算及其性质5.1.1二元运算的基本概念例5.2设S＝{1,2},给出P(S)上的运算~和的运算表,其中全集为S.解:所求的运算表如表5.3、表5.4所示.离散数学第五章代数系统的一般性质5.1二元运算及其性质5.1.1二元运算的基本概念例5.3设S={1,2,3,4},定义S上二元运算如下：x◦y=(xy)mod5,x,yS,求◦的运算表.解:(xy)mod5是xy除以5的余数,得运算表如下:◦123411234224133314244321离散数学第五章代数系统的一般性质5.1二元运算及其性质5.1.2二元运算的性质定义5.3设◦为S上的二元运算,如果对任意的x,yS都有x◦y＝y◦x,则称运算◦在S上是可交换的,或者说.在S上适合交换律.§例如,实数集上的加法和乘法都是可交换的,但减法不可交换,在幂集P(S)上的∪,∩,都是可交换的,但相对补不是可交换的.例5.4设Q是有理数集合,△是Q上的二元运算,对任意的a,bQ,a△b=a+b－a×b,问运算△是否可交换.解:因为a△b=a+b－a×b=b+a－b×a=b△a所以△在有理数上是可交换的离散数学第五章代数系统的一般性质5.1.2二元运算的性质定义5.4设◦为S上的二元运算,如果对任意的x,y,zS都有(x◦y)◦z＝x◦(y◦z),则称运算◦在S上是可结合的,或者说,在S上适合结合律.例:普通的加法和乘法在N,Z,Q,R上都是可结合的;∪,∩,在幂集P(S)上也是可结合的;矩阵加法和乘法在Mn(R)上是可结合的,其中矩阵加法还是可交换的,但矩阵乘法不是可交换的.5.1二元运算及其性质离散数学第五章代数系统的一般性质5.1.2二元运算的性质例5.5设A是一个非空集合,*是A上的二元运算,如果对于任意的a,b∈A,都有(a*b)＝b,证明*是可结合运算.证明:因为对于任意的a,b,c∈A(a*b)*c=b*c=ca*(b*c)=a*c=c所以(a*b)*c=a*(b*c),即:*在A上是可结合的.5.1二元运算及其性质离散数学第五章代数系统的一般性质5.1.2二元运算的性质定义5.5设◦为S上的二元运算,如果对任意的xS都有x◦x=x,则称该运算◦适合幂等律,也可以说S中的全体元素都是幂等元.§例如,幂集P(S)上∪和∩适合幂等律,但对称差不适合幂等律(除非P(S)=),是运算的幂等元;自然数集上的加、减、乘、除都不适合幂等律.5.1二元运算及其性质离散数学第五章代数系统的一般性质5.1.2二元运算的性质定义5.6设◦和*是S上的两个二元运算,如果对任意的x,y,zS有x*(y◦z)=(x*y)◦(x*z),(y◦z)*x＝(y*x)◦(z*x),则称运算*对◦是可分配的,也称*对◦适合分配律.§例如,在实数集上普通乘法对加法是可分配的,在n阶实矩阵的集合Mn(R)上矩阵乘法对矩阵加法是可分配的,而在幂集P(S)上∪和∩是互相可分配的.5.1二元运算及其性质离散数学第五章代数系统的一般性质5.1.2二元运算的性质例5.6设A={α,β},在A上定义两个二元运算*,△,如下表所示.问运算△对于*运算可分配吗？运算*对于运算△呢？*αβααβββα△αβαααβαβ解:容易验证△对于*运算可分配,但*运算对于运算△不可分配.因为:β*(α△β)=β*α=β(β*α)△(β*β)=β△α=α5.1二元运算及其性质离散数学第五章代数系统的一般性质5.1.2二元运算的性质定义5.7设◦和*是S上的两个可交换的二元运算,如果对任意的x,yS都有x*(x◦y)＝x,x◦(x*y)＝x,则称◦和*满足吸收律.§例如,在幂集P(S)上∪和∩是满足吸收律的.例5.7设集合N为自然数全体,在N上定义两个二元运算◦和*,对于任意x,yN,都有x◦y＝max(x,y),x*y＝min(x,y)验证◦和*满足吸收律.解:对于任意a,bNa◦(a*b)=max(a,min(a,b))=aa*(a◦b)=min(a,max(a,b))=b因此,◦和*满足吸收律5.1二元运算及其性质离散数学第五章代数系统的一般性质5.1二元运算及其性质5.1.2二元运算的性质§左幺元,右幺元,幺元定义5.8设◦为S上的二元运算,如果存在元素el(或er)∈S使得对任何x∈S,都有el◦x＝x(或x◦er=x),则称el(或er)是S中关于运算◦的一个左幺元(或右幺元).若e∈S关于◦既是左幺元,又是右幺元,则称e为S上关于运算◦的幺元.离散数学第五章代数系统的一般性质5.1二元运算及其性质§谁是幺元?自然数集合上的加法运算的幺元是谁?自然数集合上的乘法运算的幺元是谁?在Mn(R)上的矩阵加法的幺元是谁?在Mn(R)上的矩阵乘法的幺元是谁?在幂集P(S)上的∪运算的幺元是谁?在幂集P(S)上的∩运算的幺元是谁?R*是非零实数集,任意的a,bR*有a◦b=a,运算◦的幺元是谁?离散数学第五章代数系统的一般性质5.1二元运算及其性质§左幺元,右幺元,幺元定理5.1设◦为S上的二元运算,el,er分别为运算◦的左幺元和右幺元,则有el＝er＝e.且e为S上关于运算◦的唯一的幺元.证明:el＝el◦erel◦er＝er所以el=er把el＝er记作e.假设S中存在幺元e’,则有e’=e◦e’＝e所以,e是S中关于运算◦的唯一的幺元。离散数学第五章代数系统的一般性质5.1二元运算及其性质5.1.2二元运算的性质§左零元,右零元,零元定义5.9设◦为S上的二元运算,若存在元素l(或r)S使得对任意的xS,有l◦x＝l(或x◦r＝r)则称l(或r)是S上关于运算◦的左零元(或右零元);若∈S关于运算◦既是左零元,又是右零元,则称为S上关于运算◦的零元.如:﹡自然数集N上普通乘法的零元是0;普通加法无零元;﹡Mn(R)上矩阵乘法的零元是全为0的n阶矩阵;矩阵加法无零元.离散数学第五章代数系统的一般性质5.1.2二元运算的性质§左零元,右零元,零元﹡在幂集P(S)上∪运算的零元是S;∩运算的零元是.﹡R*是非零实数集,任意的a,bR*有a◦b=a,运算◦的左零元为R*的任意元素;无零元.定理5.2设◦为S上的二元运算,l,r分别为运算◦的左零元和右零元,则有l＝r＝;且为S上关于运算◦的唯一的零元.5.1二元运算及其性质离散数学第五章代数系统的一般性质5.1.2二元运算的性质定理:给定集合A,*是A上的一个二元运算,且集合A中元素的个数大于1.如果运算*有幺元e和零元θ,则θ≠e.证明:用反证法,设θ=e,那么对于任意xA,必有x=e*x=θ*x=θ=e于是,A中所有元素都是相同的,这与A中含有多个元素相矛盾.5.1二元运算及其性质离散数学第五章代数系统的一般性质5.1二元运算及其性质5.1.2二元运算的性质§左逆元,右逆元,逆元定义5.10设◦为S上的二元运算,eS为运算◦的幺元.对于任意的xS,如果存在ylS(或yrS)使得yl◦x＝e(或x◦yr＝e),则称yl(或yr)是x的左(或右)逆元.若yS既是x的左逆元,又是x的右逆元,则称y是x的逆元.﹡自然数集关于加法运算只有0有逆元0,其他数无逆元.﹡整数集关于加法运算的逆元为它的相反数.﹡Mn(R)上矩阵乘法的逆元是M-1.﹡在幂集P(S)上∪运算的逆元,只有有逆元.离散数学第五章代数系统的一般性质5.1.2二元运算的性质§左逆元,右逆元,逆元定理5.3设◦为S上可结合的二元运算,e为该运算的幺元.对于xS,如果存在左逆元yl和右逆元yr,则有yl＝yr＝y,即y是x的唯一的逆元.证明:yl＝yl◦e＝yl◦(x◦yr)=(yl◦x)◦yr＝e◦yr＝yr令yl=yr=y,假设y’S是x的逆元,则有y’＝y’◦e＝y’◦(x◦y)＝(y’◦x)◦y＝e◦y＝y.§由这个定理可知,对于可结合的二元运算来说,元素x的逆元如果存在则一定是唯一的.通常把这个唯一的逆元记作x-1.5.1二元运算及其性质离散数学第五章代数系统的一般性质5.1.2二元运算的性质定义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.1二元运算及其性质离散数学第五章代数系统的一般性质5.1.2二元运算的性质例5.8对于下面给定的集合和该集合上的运算,指出该运算的性质,并求出它的幺元,零元和所有可逆元素的逆元.(1)Z+,x,yZ+,x*y=lcm(x,y),即求x,y的最小公倍数.(2)Q,x,yQ,x*y=x+y-xy5.1二元运算及其性质离散数学第五章代数系统的一般性质解:(1)*运算可交换,可结合,是幂等的.xZ+,x*1=1*x=x,