离散数学第4章代数系统.ppt

离散数学离散数学西安交通大学西安交通大学电子与信息工程学院电子与信息工程学院计算机系计算机系1离散数学 5.环环 环的基本概念环的基本概念 环的基本性质环的基本性质 无零因子环和含零因子环无零因子环和含零因子环 整环与除环整环与除环2离散数学 5.环环定义定义1.环(ring)设(R,)是代数系统，和是R上的两个二元运算，若 (1)(R,)是交换群；(2)(R,)是半群；(3)对满足分配律：对任何a,b,cR，都有 a(bc)=(ab)(ac)(bc)a=(ba)(ca)；则称(R,)是环。注：在环中，由于(R,)是群，故关于有幺元存在，将关于的么元记为0，称为环的零元。在环中，由于(R,)是群，故R中每个元素有逆元，设aR，将a关于的逆元记为-a，称为a 的负元，且将a(-b)简记为 a-b3离散数学(即在环中可定义减法运算)。在环中，对于运算，若有幺元，则记为1或e。在环中，设aR，若a关于有逆元，则记为 a-1。以后谈到环，只讨论|R|2的情况，即不讨论一个元素的环。在环的定义中，不要求对满足分配律，只要求 对满足分配律。例例1.1.(I,+,)是环。我们称此环为整数环。这里：I是整数集合，+和是整数的普通加法运算和普通乘法运算。由前两节知 (1)(I,+)是交换群；(2)(I,)是半群；(3)对+满足分配律：由算术知识知整数乘法对整数加法满足分配律。即a,b,cI 有 a(b+c)=(a b)+(a c)由的交换律知对+满足分配律；由环的定义知(I,+,)是环。4离散数学例例2.(Mnn,+,)是环。我们称此环为矩阵环。这里：Mnn是 n n阶实矩阵的全体，与是矩阵的加法运算和乘法运算。由前两节知 (1)(Mnn,+)是交换群；(2)(Mnn,)是半群；(3)对+满足分配律：由线性代数知，矩阵乘法对矩阵加法满足分配律。即 A,B,CMnn,有：A(B+C)=(AB)+(AC)(B+C)A=(BA)+(CA)；由环的定义知(Mnn,+,)是环。5离散数学例例3.3.(Nm,+m,m)是环。我们称此环为整数模环。这里：Nm=0m,1m,m-1m，+m和m是Nm上的模加运算和模乘运算。由前两节知 (1)(Nm,+m)是交换群；(2)(Nm,m)是半群；(3)m对+m满足分配律：由于im,jm,kmNm,有 im m(jm+mkm)=im m(j+k)mod mm =(i(j+k)mod mm =(i j)+(i k)mod mm =(i j)mod mm+m(i k)mod m =(immjm)+m(immkm)由m的交换律知m对+m满足分配律；由环的定义知(Nm,+m,m)是环。6离散数学例例4.4.(2X,)是环。我们称此环为X的子集环 这里：X是一个非空集合，2X 是X的幂集，是集合的对称差运算,是集合的交运算。由前两节知 (1)(2X,)是交换群；(2)(2X,)是半群；(3)对满足分配律：由第一章2定理6(8)知集合的交运算对对称差运算满足分配律。即a,b,c2X，有 A(BC)=(AB)(AC)由的交换律知对满足分配律；由环的定义知(2X,)是环。7离散数学例例5 5(Px,+,)是环。我们称此环为多项式环。这里：Px 是实系数多项式的全体，+和是多项式的加法运算和乘法运算，由前两节知 (1)(Px,+)是交换群；(2)(Px,)是半群；(3)对+满足分配律：由于实数乘法对实数加法满足分配律，故多项式乘法对多项式加法满足分配律。即h(x),p(x),q(x)Px,有 h(x)(p(x)+q(x)=(h(x)p(x)+(h(x)q(x)由的交换律知对+满足分配律；由环的定义知(Px,+,)是环。8离散数学定义定义2.交换环 含幺环 交换含幺环 设(R,)是环。(1)若运算满足交换律，则我们称(R,)是交换环。(2)若关于运算有幺元，则我们称(R,)是含幺环。(3)若运算满足交换律又关于运算有幺元，则我们称(R,)是交换含幺环。9离散数学例例8在前面的例子中 (1)整数环(I,+,)是交换含幺环；关于运算的幺元是1；(2)矩阵环(Mnn,+,)是含幺环，但不是交换环；关于运算的幺元是单位矩阵E，矩阵乘法没有交换律；(3)整数模环(Nm,+m,m)是交换含幺环；关于m运算的幺元是1m；(4)X的子集环(2X,)是交换含幺环；关于运算的幺元是X；(5)多项式环(Px,+,)是交换含幺环；关于运算的幺元是零次多项式1；10离散数学定理定理1.1.环的基本性质 设(R,)是环。则a,b,cR,有 (1)零元：0a=a0=0 (加法幺元是乘法的零元)；(2)正负、负正得负：a(-b)=(-a)b=-(ab)；(3)负负得正：(-a)(-b)=ab；(4)(-1)a=-a(-1是乘法幺元1的负元)；(5)(-1)(-1)=1(-1的乘法逆元是其本身，即(-1)-1=-1)；(6)左分配律：a(b-c)=(ab)-(ac)(乘法对减法的)；右分配律：(bc)a=(ba)(ca)(乘法对减法的)。注：由定理1(1)的结论知，在环(R,)中，关于运算的幺元就是关于运算的零元。由于(R,)是交换群，故关于运算的幺元一定存在，因此关于运算的零元也一定存在。由于在一个代数系统中，零元是没有逆元的，因此在环(R,)中，(R,)不能构成群。11离散数学证.(1)只证a0=0 a0=(a0)0 =(a0)(a0)-(a0)=(a0)(a0)(-(a0)=(a0)(a0)(-(a0)(结合律)=(a(00)(-(a0)(分配律)=(a0)(-(a0)(00=0)=(a0)-(a0)=0；12离散数学(2)只证a(-b)=-(ab)a(-b)=(a(-b)0 =(a(-b)(ab)-(ab)=(a(-b)(ab)(-(ab)=(a(-b)(ab)(-(ab)(结合律)=(a(-b)b)(-(ab)(分配律)=(a0)(-(ab)(-b)b=0)=0(-(ab)(根据(1)a0=0)=-(ab)；13离散数学 (3)(-a)(-b)=-(a(-b)(根据(2)=-(-(ab)(根据(2)=ab (反身律)；(4)(-1)a=-(1a)(根据(2)=-a；(5)(-1)(-1)=11 (根据(3)=1；(6)只证a(b-c)=(ab)-(ac)a(b-c)=a(b(-c)=(ab)(a(-c)(分配律)=(ab)(-(ac)(根据(2)=(ab)-(ac)。14离散数学定义定义3.含零因子环 无零因子环 设(R,)是环。若在环(R,)中 (1)(aR)(bR)(a0b0ab=0)，则 称 环(R,)是含零因子环；称a是环中的左零因子，称b是环中的右零因子；(2)(aR)(bR)(a0b0ab0)，即环中无零因子(no nil-factor)，则称环(R,)是无零因子环。注：所谓含零因子，就是环中的两个元素，它们本身不是关于运算的零元，但它们的运算结果却是零元；于是就称此环为含零因子环。当一个环是交换环时，左零因子也就是右零因子，反之亦然；在这种情况下，左零因子、右零因子统称为零因子。如果在环中，不存在满足上述条件的元素，就称此环为无零因子环。15离散数学例例9.整数环(I,+,)是无零因子环 已知(I,+,)是环，由于任意两个不为零的整数相乘,其积不为零，故由定义3知(I,+,)是无零因子环。例例10.矩阵环(Mn n,+,)是含零因子环 已知(Mn n,+,)是环(n2)。不妨设n=2，于是有 即两个不为零的矩阵相乘其积为零矩阵。由定义3知是(Mn n,+,)含零因子环。16离散数学例例11.11.整数模环(Nm,+m,m)，当m为素数时，是无零因子环；当m不是素数时，是含零因子环。(1)当m为素数时，对任意的 im，jmNm，im 0m，(即i pm),jm 0m(即j qm),从而有i j km(否则，i j=km，由m是素数，则必有m i或m j，于是有 i=pm或 j=qm，矛盾)，即有 im mjm=(i j)mod mm 0m 即两个不为零的元素经过m运算后不为零。由定义3知(Nm,+m,m)是无零因子环。(2)当m不是素数时，必存在着im，jmNm，im 0m，jm 0m，使得 m=i j，即有im mjm=(i j)mod mm=0m 即im，jm是Nm中的零因子。由定义3知(Nm,+m,m)是含零因子环。17离散数学例例12.12.X的子集环(2X,)是含零因子环 已知(2X,)是环，其零元是空集。设|X|2,任取a，bX，且a b，于是有a,b2X且a,b，使得ab=。即两个不为零的元素相交后为零元。由定义3知(2X,)是含零因子环。例例13.多项式环(Px,+,)是无零因子环已知(Px,+,)是环，由于两个非零多项式相乘其积仍为一非零多项式，由定义3知(Px,+,)是无零因子环。18离散数学定义定义4.整环(integral domain)交换含幺的无零因子环称为整环。注：整环又称为整区。定义定义4.除环(division ring)每个非零元都有(乘法)逆元的含幺环称为除环。即，若含幺环(R,)满足：(aR)(a0a-1R)则称其为除环。19离散数学例例16在前面的例子中 (1)整数环(I,+,)是整环：因为整数环(I,+,)是交换含幺环(例8(1)，又是无零因子环(例9)。但整数环(I,+,)不是除环：因为在整数环(I,+,)中，除幺元1及其负元-1外，其它非零整数aI(a0)都没有(乘法)逆元(a-1=1/aI)。(2)矩 阵 环(Mnn,+,)不 是 整 环：因 为 矩 阵 环(Mnn,+,)不是交换环,矩阵的乘法没有交换律(例8(2)，而且还是含零因子环(例10)。矩 阵 环(Mnn,+,)也 不 是 除 环：因 为 矩 阵 环(Mnn,+,)中一些非零矩阵(行列式是零)关于矩阵乘法没有逆元(逆矩阵)。20离散数学(3)整数模环(Nm,+m,m)当m是素数时是整环：因为整数模环(Nm,+m,m)是交换含幺环(例8(3)，并且当m为素数时，又是无零因子环(例11)；并且也是除环(见下面注)。整数模环(Nm,+m,m)当m不是素数时不是整环：因为整数模环(Nm,+m,m)当m不是素数时是含零因子环(例11)；并且也不是除环(见下面注)。(4)X的子集环(2X,)不是整环：因为X的子集环(2X,)是含零因子环(例12)；并且也不是除环。21离散数学 (5)多 项 式 环(Px,+,)是 整 环：因 为 多 项 式 环(Px,+,)是交换含幺环(例8(5)，又是无零因子环(例13)。但多项式环(Px,+,)不是除环：因为有非零多项式axPx(a0)，关于多项式乘法没有逆元(否则，若axq(x)=1，则用比较系数法，可得 q(x)=0，于是又有axq(x)=0，矛盾)。注：在下面定理4中，将可证：在有限含幺环中 无零因子(非零元)有逆元；22离散数学定定理理2.在环(R,)中，无零因子消去律，即a,b,cR且a0，都有ab=acb=c；ba=cab=c。证.先证)：a,b,cR且a0，ab=ac (ab)-(ac)=0 (两边同时上-(ac)a(b-c)=0 (分配律)b-c=0 (a0及无零因子)b=c 次证)：用反证法。假设环中有零因子，因此，必有一对元素a,bR，a0且b0，使得ab=0。但是 a0=0，于是我们有ab=a0，由a0及消去律可得 b=0，这与已知b0 矛盾。这个矛盾说明假设错误，环中无零因子。23离散数学定理定理3.除环是含幺的无零因子环。注：因此，除环未必是整环，整环也未必是除环；除环要成为整环，差乘法交换律；整环要成为除环，差(非零元)有乘法逆元；证.除环是含幺环，因此只须证环无零因子 即可。假设环中有零因子a,bR，a0且b0，使得ab=0。则有 ab=0=0 b abb-1=0bb-1(两边同时乘上b-1,因a0 b0)a=0 与a0矛盾，所以环中无零因子。24离散数学定理定理4.在有限含幺环中，无零因子(非零元)有逆元。证.先证)：因环无零因子，故运算对R0是封闭的,因此(R0,)是代数系统。于是。在代数系统(R0,)中，因R有限,故对任何rR0，必有i,j N,ji 1(j-i 1),使得 ri=rj rj=ri rj-i ri=e ri (指数律、环含幺)rj-i=e (消去律)r-1=rj-i-1 即，非零元有逆元。次证)：同定理3。25离散数学注：关于消去律、无零因子、非零元有逆元之间的关系，见下图：消去律无零因子 有逆元 消去律无零因子 有逆元 当R有限时当R无限时定理2定理2定理4易证易证图1图226离散数学 6.域域 域的基本概念域的基本概念 有限域有限域 27离散数学 6.域域定义定义1.域(field)设(F,)是代数系统，和是R上的两个二元运算，若 (1)(F,)是交换群；(2)(F0,)是交换群；(3)对满足分配律：对任何a,b,cF，都有 a(bc)=(ab)(ac)；则称(F,)是域。注：在域(F,)中，由于(F0,)是交换群，以及 aF,0a=a0=0 因此，运算有交换律，所以对的分配律只写一条。28离散数学例例1.(Q,+,)是域。我们称为有理数域。这里：Q是有理数集，+,分别是普通的有理数的加法运算和乘法运算，则(Q,+,)是域。例例2.(R,+,)是域。我们称为实数域。这里：R是实数集，+,分别是普通的实数的加法运算和乘法运算，则(R,+,)是域。例例3.(C,+,)是域。我们称为复数域。这里：C是复数集，+,分别是普通的复数的加法运算和乘法运算，则(C,+,)是域。例例4.(X1,+,)是域。我们称为算术分类域。这里：X1=a+b :a,bQ，+,分别是普通数的加法运算和乘法运算。包含性：X1，X10；非空性：X1(因0=0+0 X1)X1 0(因1=1+0 X10)29离散数学 (1)(X1,+)是交换群；只须证它是交换群(R,+)的子群即可 封闭性：a+b ,c+d X1 (a+b )+(c+d )=(a+c)+(b+d)X1；有逆元：a+b X1，有-(a+b )=(-a)+(-b)X1，使(a+b )+(-a)+(-b)=0；故根据6定理14可知(X1,+)是交换群(R,+)的子群。因此，(X1,+)是交换群；(2)(X10,)是 交 换 群；只 须 证 它 是 交 换 群(R0,)的子群即可 封闭性：a+b ,c+d X10，于是a,b至少有一不为零，c,d至少有一不为零，从而 (a+b )(c+d )=(ac+2bd)+(ad+bc)X10否则 ac+2bd=0,ad+bc=0,由a,b至少有一不为零可反解出c=0,d=0(因为齐次线性方程组。30离散数学(否则a,b全为零与a,b至少有一不为零矛盾，或者全不为零且a/b是有理数，与其是无理数矛盾)，而这与c,d至少有一不为零矛盾。有逆元：a+b X10，有 (a+b )-1=(a-b )/(a2-2b2)X10 使 (a+b )(a-b )/(a2-2b2)=1；故根据6定理14可知(X10,)是交换群(R0,)的子群。因此，(X10,)是交换群；(3)对+满足分配律：由代数(R,+,)遗传；所以按定义1知则(X1,+,)是域。注：实际上易证(Xk,+,)都是域。这里Xk=a+b :a,bQ，其中pk是第k个素数。这正是我们为什么称此类域为算术分类域。31离散数学定理定理1.1.可交换的除环是域。证.除环是每个非零元都有(乘法)逆元的含幺环，它与域概念仅差(乘法)交换律。现在正好补齐，所以，可交换的除环是域。定理定理2.2.有限整环是域。证.整环是交换含幺的无零因子环，它与域概念仅差每个非零元都有(乘法)逆元。但在有限环的情况下，上节定理4已经证明：无零因子每个非零元都有(乘法)逆元 因此，有限整环是域。例例5在上节的例子中(参见上节例16)(1)整数环(I,+,)不是域：因为整数环(I,+,)虽是整环，32离散数学但不是有限环。实际上，它的非零整数aI(a0)，除幺元1及其负元-1外，都没有(乘法)逆元(a-1=1/aI)；(2)矩阵环(Mnn,+,)不是域：因为它是含零因子环，它的一些非零矩阵(行列式是零)关于矩阵乘法没有逆元(逆矩阵)；(3)整数模环(Nm,+m,m)当m是素数时是域：因为当m为素数时它是整环，并且又是有限的(|Nm|m)；整数模环(Nm,+m,m)当m不是素数时不是域：因为当m不是素数时，它是含零因子环，因而并非每个非零元都有(乘法)逆元；(4)X的子集环(2X,)不是域：因为它是含零因子环，因而并非每个非零元都有(乘法)逆元；(5)多项式环(Px,+,)不是域：因为有非零多项式关于多项式乘法没有逆元；33离散数学 环(I,+,)(Mnn,+,)(Nm,+m,m)(2X,)(Px,+,)运算m交换律有无有有有幺元1E 1mX1零因子无有m是素数m是合数有无无有整环是不是是不是不是是 除环不是不是是不是不是不是域不是不是是不是不是不是表334离散数学 第四章第四章 代数系统代数系统 重点要求重点要求 w掌握代数系统的概念掌握代数系统的概念,对几个定义对几个定义:运算的封闭性运算的封闭性、单位元单位元、零元零元、逆元逆元、等幂元及相关的结论有清晰的理解、等幂元及相关的结论有清晰的理解。给定集合和集合上的给定集合和集合上的运算能够判断该集合对运算是否封闭运算能够判断该集合对运算是否封闭;能够通过运算表确定单位元能够通过运算表确定单位元零元零元、逆元等逆元等(如果存在的话如果存在的话);对交换律对交换律、结合律结合律、分配律分配律、吸收吸收律律、消去律、消去律等的表示要十分清楚等的表示要十分清楚;给定集合和二元运算表能够判断给定集合和二元运算表能够判断运算是否满足结合律等等运算是否满足结合律等等。w掌握代数系统的同态和同构的定义能判断两个给定代数系统间的掌握代数系统的同态和同构的定义能判断两个给定代数系统间的某个映射是否为同态同构映射某个映射是否为同态同构映射。w掌握半群及含幺半群概念掌握半群及含幺半群概念。w掌握群的概念掌握群的概念,并能灵活运用群的一些基本性质并能灵活运用群的一些基本性质,理解群的同态和理解群的同态和同构同构。给定一个代数系统及其运算给定一个代数系统及其运算,能够判断是否为半群能够判断是否为半群、含幺半含幺半群群、群等群等。w掌握子群的概念并清楚其判别方法掌握子群的概念并清楚其判别方法。35离散数学w掌握环掌握环、整环整环、除环、除环的定义的定义,并熟悉环的基本性质并熟悉环的基本性质。给定集合及两给定集合及两个二元运算能够判断其是否为环个二元运算能够判断其是否为环、整环整环、除环、除环等等。w牢记消去律牢记消去律、无零因子、有逆元三者间的俩层关系及其运用、无零因子、有逆元三者间的俩层关系及其运用。w掌握域及有限域的定义掌握域及有限域的定义。36离散数学w第四章 代数系统 到此已经结束！37