《离散数学》几个典型的代数系统-2(环域格).ppt

《《离散数学》几个典型的代数系统-2(环域格).ppt》由会员分享，可在线阅读，更多相关《《离散数学》几个典型的代数系统-2(环域格).ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章 几个典型的代数系统环的定义定义 设是代数系统，+和是二元运算.如果满足以下条件:（1）构成交换群（2）构成半群（3）运算关于+运算适合分配律则称是一个环.6.26.26.26.2环环环环与与与与域域域域2环中的术语通常称+运算为环中的加法，运算为环中的乘法.-环中加法幺元记作 0.对任何元素 x，称 x 的加法逆元为负元，记作x.-乘法幺元（如果存在）记作 1.若 x 存在乘法逆元的话，则称之为逆元，记作 x1.环中加法幺元0恰好是乘法的零元.6.26.26.26.2环环环环与与与与域域域域3理解理解一个集合，两种运算，六个条件：-加法结合律-加法交换律-加法存在单位元（零元）-加法存

2、在逆元（副元）-乘法存在结合律-乘法对加法的分配律6.26.26.26.2环环环环与与与与域域域域4环的实例 (1)整数集、有理数集、实数集和复数集关于普通的加法和乘法构成环，分别称为整数环Z，有理数环Q，实数环R 和 复数环C.(2)n(n2)阶实矩阵的集合Mn(R)关于矩阵的加法和乘法构成环，称为n阶实矩阵环.(3)集合的幂集P(B)关于集合的对称差运算和交运算构成环.(4)设Zn0,1,.,n1，和分别表示模n的加法和乘法，则构成环，称为模n的整数环.6.26.26.26.2环环环环与与与与域域域域5特殊的环特殊的环定义 设是环，(1)若环中乘法适合交换律，则称 R是交换环.(2)若环中

3、乘法存在幺元，则称 R是含幺环.注：环中加法的单位元是乘法的零元。,（，分别是模n加法和乘法运算）都是交换环；不是交换环。,，都是含么环，么元分别为1，1，1，1，单位矩阵。6.26.26.26.2环环环环与与与与域域域域6零因子的定义与存在条件定义：设是环，若存在a b=0,且a0,b0,称a为R的左零因子，b为R的右零因子，环R不是无零因子环.若a,bR，a b=0 a=0b=0，则称R是无零因子环.,都是无零因子环；不一定是无零因子环，如n6时，有零因子2和3，但n5时是无零因子环。6.26.26.26.2环环环环与与与与域域域域7(4)若 既是交换环、含幺环，也是无零因子环，则称 R

4、是整环.(5)环|R|1,含幺和无零因子，且aR（a0，0是加法的单位元）有a-1 R，则称 R 是除环.(5)若 R为整环，|R|1,且aR*=R-0，a-1R,则称 R 为域.既是整环又是除环，则是域。8特殊环的实例特殊环的实例(1)整数环整数环Z、有理数环有理数环Q、实数环实数环R、复数环复数环C都是交都是交换环、含幺环、无零因子环和整环换环、含幺环、无零因子环和整环.其中除其中除Z之外都之外都是域是域(2)令令2Z=2z|zZ，则，则构成交换环和无零构成交换环和无零因子环因子环.但不是含幺环和整环但不是含幺环和整环.(3)设设n Z,n 2,则则n 阶实矩阵的集合阶实矩阵的集合Mn(R

5、)关于矩阵关于矩阵加法和乘法构成环，它是含幺环，但不是交换环和加法和乘法构成环，它是含幺环，但不是交换环和无零因子环，也不是整环无零因子环，也不是整环.(4)构成环，它是交换环、含幺环，但不是构成环，它是交换环、含幺环，但不是无零因子环和整环无零因子环和整环.注意：对于一般的注意：对于一般的n,Zn是整环且是域是整环且是域n是素数是素数.6.26.26.26.2环环环环与与与与域域域域9例题判断下列集合和给定运算是否构成环、整环和域判断下列集合和给定运算是否构成环、整环和域.(1)A=a+bi|a,b Q,i2=1,运算为复数加法和乘法运算为复数加法和乘法.(2)A=2z+1|z Z,运算为普

6、通加法和乘法运算为普通加法和乘法(3)A=2z|z Z,运算为普通加法和乘法运算为普通加法和乘法(4)A=x|x0 x Z,运算为普通加法和乘法运算为普通加法和乘法.(5)，运算为普通加法和乘法，运算为普通加法和乘法解解(2),(4),(5)不是环不是环.为什么？为什么？(1)是环是环,是整环是整环,也是域也是域.(3)是环是环,不是整环和域不是整环和域.6.26.26.26.2环环环环与与与与域域域域10环的性质定理 设是环，则(1)aR，a0=0a=0证明：a0a(0+0)=a0+a0,由消去律a00(2)a,bR，(a)b=a(b)=ab证明：(a)bab=(-a+a)b=0b=0,反之

7、：ab(a)b0，故(a)b的加法逆元是ab。(3)a,bR，(a)(b)=ab证明：(a)(b)=-(a(-b)=-(-(ab)=ab(4)a,b,cR，a(bc)=abac，(bc)a=baca6.26.26.26.2环环环环与与与与域域域域11环中的运算环中加法的交换律、结合律；环中加法的交换律、结合律；乘法的结合律；乘法的结合律；乘法对加法的分配律乘法对加法的分配律.例例 在环中计算在环中计算 (a a+b b)3 3,(,(a a b b)2 2解解 (a a+b b)3 3=(=(a a+b b)()(a a+b b)()(a a+b b)=(=(a a2 2+baba+abab+

8、b b2 2)()(a a+b b)=a a3 3+baba2 2+abaaba+b b2 2a a+a a2 2b b+babbab+abab2 2+b b3 3 (a a b b)2 2=(=(a a b b)()(a a b b)=)=a a2 2 baba abab+b b2 2 注：在初等代数中的加法和乘法运算都是在实数域中进行，乘法可交换注：在初等代数中的加法和乘法运算都是在实数域中进行，乘法可交换6.26.26.26.2环环环环与与与与域域域域12格的定义定义定义 设设 是偏序集，如果是偏序集，如果 x x,y y S S，x x,y y 都有都有最小上界和最大下界，则称最小上界

9、和最大下界，则称S S关于偏序关于偏序 构成一个构成一个格。格。由于最小上界和最大下界的惟一性，可以把求由于最小上界和最大下界的惟一性，可以把求 x x,y y 的最小上界和最大下界看成的最小上界和最大下界看成 x x 与与 y y 的二元运算的二元运算和和，即，即 x xy y 和和 x xy y 分别表示分别表示 x x 与与 y y 的最小上界和的最小上界和最大下界最大下界.注意：这里出现的注意：这里出现的和和符号只代表格中的运算，符号只代表格中的运算，而不再有其他的含义而不再有其他的含义.6.36.36.36.3格格格格与与与与布布布布尔尔尔尔代代代代数数数数13格的实例例例设设n是正

10、整数，是正整数，Sn是是n的正因子的集合的正因子的集合.D为为整除关系，则偏序集整除关系，则偏序集构成格构成格.x,ySn，xy 是是lcm(x,y)，即即x 与与y 的最小公倍数的最小公倍数.xy 是是gcd(x,y)，即即x 与与y 的最大公约数的最大公约数.下图给出了格下图给出了格，和和.6.36.36.36.3格格格格与与与与布布布布尔尔尔尔代代代代数数数数14例例判断下列偏序集是否构成格，并说明理由判断下列偏序集是否构成格，并说明理由.(1)，其中其中P(B)是集合是集合B的幂集的幂集.(2)，其中其中Z是整数集，是整数集，为小于等于关系为小于等于关系.(3)偏序集的哈斯图分别在下图

11、给出偏序集的哈斯图分别在下图给出.格的实例（续）解解(1)是格是格.称称为为B的幂集格的幂集格.(2)是格是格.(3)都不是格都不是格.6.36.36.36.3格格格格与与与与布布布布尔尔尔尔代代代代数数数数15格的性质：对偶原理定义定义设设f 是含有格中元素以及符号是含有格中元素以及符号=,和和的的命题命题.令令f*是将是将f 中的中的 替换成替换成,替换成替换成,替换成替换成,替换成替换成所得到的命题所得到的命题.称称f*为为f 的的对偶命题对偶命题.例如例如,在格中：在格中：f 是是(ab)c c,f*是是(ab)c c.格的对偶原理：格的对偶原理：设设f 是含格中元素以及符号是含格中元

12、素以及符号=,和和等的命题等的命题.若若f 对一切格为真对一切格为真,则则f 的对偶命题的对偶命题f*也对一切格为真也对一切格为真.例如例如,若对一切格若对一切格L都有都有 a,bL,ab a，那么对一那么对一切格切格L都有都有 a,bL,ab a6.36.36.36.3格格格格与与与与布布布布尔尔尔尔代代代代数数数数16格的性质：算律格的性质：算律定理定理设设是格是格,则运算则运算和和适合交换律、结适合交换律、结合律、幂等律和吸收律合律、幂等律和吸收律,即即(1)a,bL有有 ab=ba,ab=ba(2)a,b,cL有有(ab)c=a(bc),(ab)c=a(bc)(3)aL有有aa=a,a

13、a=a(4)a,bL有有a(ab)=a,a(ab)=a6.36.36.36.3格格格格与与与与布布布布尔尔尔尔代代代代数数数数17算律的证明证(1)交换律.ab 是a,b的最小上界ba 是b,a的最小上界a,b=b,a ab=ba.由对偶原理,ab=ba 得证.6.36.36.36.3格格格格与与与与布布布布尔尔尔尔代代代代数数数数18算律的证明（续）(2)结合律.由最小上界的定义有(ab)caba(I)(ab)cabb(II)(ab)cc(III)由式(II)和(III)有(ab)cbc(IV)由式(I)和(IV)有(ab)ca(bc).同理可证(ab)c a(bc).根据偏序的反对称性得到

14、(ab)c=a(bc).由对偶原理,(ab)c=a(bc)得证.19算律的证明（续）(3)幂等律.显然a aa,又由a a 得aa a.由反对称性aa=a.用对偶原理,aa=a 得证.(4)吸收律.显然有a(ab)a(V)由a a,ab a 可得a(ab)a (VI)由式(V)和(VI)可得a(ab)=a根据对偶原理,a(ab)=a 得证.6.26.26.26.2环环环环与与与与域域域域20格作为代数系统的定义定理定理设设是具有两个二元运算的代数系统是具有两个二元运算的代数系统,若对于若对于 和和 运算适合交换律、结合律、吸收律运算适合交换律、结合律、吸收律,则则可以适当定义可以适当定义S中的

15、偏序中的偏序,使得使得构成格构成格,且且 a,bS有有 ab=a b,ab=a b.根据定理根据定理,可以给出格的另一个等价定义可以给出格的另一个等价定义.定义定义设设是代数系统是代数系统,和和 是二元运算是二元运算,如果如果 和和 运算运算满足交换律、结合律和吸收律满足交换律、结合律和吸收律,则则构成格构成格.21分配格定义定义 设是格,若a,b,cL,有 a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称 L 为分配格.注意：以上条件互为充分必要条件这两个等式中只要有一条成立，另一条一定成立.在证明L为分配格时,只须证明其中的一个等式即可.22分配格的定义（续）L1和和L2是分配

16、格是分配格,L3和和L4不是分配格不是分配格.在在L3中中,b(cd)=b，(bc)(bd)=a在在L4中中,c(bd)=c，(cb)(cd)=d称称L3为为钻石格钻石格,L4为为五角格五角格.23分配格的判定（续）解解L1,L2和和L3都不是分配格都不是分配格.a,b,c,d,e 是是L1的子格的子格,并且同构于钻石格；并且同构于钻石格；a,b,c,e,f 是是L2的子格的子格,并且同构于五角格；并且同构于五角格；a,c,b,e,f 是是L3的子格的子格,也同构于钻石格也同构于钻石格.例例 说明图中的格是否为分配格说明图中的格是否为分配格,为什么为什么？24全上界与全下界定义 设L是格,若存

17、在 aL 使得 xL 有 a x,则称 a 为 L 的全下界；若存在 bL 使得 xL 有 x b,则称 b 为 L 的全上界.说明：格 L 若存在全下界或全上界,一定是惟一的.一般将格 L 的全下界记为 0,全上界记为 1.25有界格定义及其性质定义 设 L是格,若 L存在全下界和全上界,则称 L为有界格,全下界记为0，全上界记为1.有界格 L 记为.注意：有限格 L=a1,a2,an是有界格,a1a2 an是 L 的全下界,a1a2an是全上界.0是关于运算的零元,运算的单位元.1 是关于运算的零元,运算的单位元.对于涉及有界格的命题,如果其中含有全下界0或全上界1,求其对偶命题时,必须将

18、0与1互换.26补元的定义定义 设是有界格,aL,若存在 bL使得ab=0 和 ab=1成立,则称 b 是 a 的补元.注意：若 b 是 a 的补元,那么 a 也是 b 的补元.a 和 b 互为补元.27实例:求补元解：解：L L1 1中中 a,ca,c互补互补,b b没补元没补元.L L2 2中中 a,da,d互补互补,b,cb,c 互补互补.L L3 3中中 a,ea,e互补互补,b b 的补元是的补元是 c c和和d d,c c 的补元是的补元是 b b和和d d,d d 的补元是的补元是b b和和c c.L L4 4中的中的 a,ea,e互补互补,b b 的补元是的补元是 c c和和d

19、 d,c c 的补元是的补元是b b,d d 的补元是的补元是 b b.28有界分配格中补元惟一性定理定理设设是有界分配格是有界分配格.若若L中元素中元素a 存在补元存在补元,则存在惟一的补元则存在惟一的补元.证证假设假设b,c 是是a 的补元的补元,则有则有ac=1,ac=0,ab=1,ab=0从而得到从而得到ac=ab,ac=ab,由于由于L是分配格是分配格,b=c.29有补格的定义定义定义设设是有界格是有界格,若若L 中所有元素都中所有元素都有补元存在有补元存在,则称则称L 为为有补格有补格.例如例如,下图下图中的中的L2,L3和和L4是有补格是有补格,L1不是有补格不是有补格.30布尔

20、代数的定义定义定义如果一个格是有补分配格如果一个格是有补分配格,则称它为则称它为布尔格布尔格或或布尔布尔代数代数.在布尔代数中，如果一个元素存在补元在布尔代数中，如果一个元素存在补元,则是惟一则是惟一的的.可以把求补元的运算看作是布尔代数中的一元可以把求补元的运算看作是布尔代数中的一元运算运算.布尔代数标记为布尔代数标记为,其中其中为求补为求补运算运算31布尔代数的实例例例设设S110=1,2,5,10,11,22,55,110是是110的正的正因子集合因子集合.gcd表示求最大公约数的运算表示求最大公约数的运算lcm表示求最小公倍数的运算表示求最小公倍数的运算.则则是否构成布尔代数？是否构成

21、布尔代数？32布尔代数的等价定义定义定义设设是代数系统是代数系统,和和 是二元运算是二元运算.若若 和和 运算满足交换律、结合律、幂等律、吸收律运算满足交换律、结合律、幂等律、吸收律,即即(1)a,bB有有a b=b a,a b=b a(2)a,b,cB有有a(b c)=(a b)(a c),a(b c)=(a b)(a c)(3)即存在即存在0,1B,使得使得 aB有有a 1=a,a 0=a(4)aB,存在存在a B 使得使得a a=0,a a=1则称则称是一个是一个布尔代数布尔代数.可以证明，布尔代数的两种定义是等价的可以证明，布尔代数的两种定义是等价的.33布尔代数的性质定理定理设设是布

22、尔代数是布尔代数,则则(1)aB,(a)=a.(2)a,bB,(ab)=a b,(ab)=a b（德摩根律）德摩根律）注意：德摩根律对有限个元素也是正确的注意：德摩根律对有限个元素也是正确的.34证明证证(1)(a)是是a 的补元的补元.a 是是a 的补元的补元.由补元惟由补元惟一性得一性得(a)=a.(2)对任意对任意a,bB有有(ab)(a b)=(aa b)(ba b)=(1b)(a 1)=11=1,(ab)(a b)=(aba)(abb)=(0b)(a0)=00=0.所以所以a b 是是ab 的补元的补元,根据补元惟一性可得根据补元惟一性可得(ab)=a b.同理可证同理可证(ab)=a b.35有限布尔代数的表示定理定理定理设设L 是有限布尔代数，则是有限布尔代数，则L 含有含有2n个元素个元素(n N)，且且L与与同构，其中同构，其中 S是是一个一个n元集合元集合.结论结论：含有：含有2n个元素的布尔代数在同构意义下只有个元素的布尔代数在同构意义下只有一个一个.36