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

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

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

2、,环的实例,(1)整数集、有理数集、实数集和复数集关于普通的加法和乘法构成环，分别称为整数环Z，有理数环Q，实数环R 和 复数环C.(2)n(n2)阶实矩阵的集合Mn(R)关于矩阵的加法和乘法构成环，称为n阶实矩阵环.(3)集合的幂集P(B)关于集合的对称差运算和交运算构成环.(4)设Zn0,1,.,n1，和分别表示模n的加法和乘法，则构成环，称为模n的整数环.,6.2环与域,6,特殊的环,定义 设是环，(1)若环中乘法适合交换律，则称 R是交换环.(2)若环中乘法存在幺元，则称 R是含幺环.注：环中加法的单位元是乘法的零元。,（，分别是模n加法和乘法运算）都是交换环；不是交换环。,，都是含么

3、环，么元分别为1，1，1，1，单位矩阵。,6.2环与域,7,零因子的定义与存在条件,定义：设是环，若存在a b=0,且a0,b0,称a为R的左零因子，b为R的右零因子，环R不是无零因子环.若a,bR，a b=0 a=0b=0，则称R是无零因子环.,都是无零因子环；不一定是无零因子环，如n6时，有零因子2和3，但n5时是无零因子环。,6.2环与域,8,(4)若 既是交换环、含幺环，也是无零因子环，则称 R 是整环.(5)环|R|1,含幺和无零因子，且aR（a0，0是加法的单位元）有a-1 R，则称 R 是除环.(5)若 R为整环，|R|1,且aR*=R-0，a-1R,则称 R 为域.既是整环又是

4、除环，则是域。,9,特殊环的实例,(1)整数环Z、有理数环Q、实数环R、复数环C都是交换环、含幺环、无零因子环和整环.其中除Z之外都是域(2)令2Z=2z|zZ，则构成交换环和无零因子环.但不是含幺环和整环.(3)设nZ,n2,则 n 阶实矩阵的集合 Mn(R)关于矩阵加法和乘法构成环，它是含幺环，但不是交换环和无零因子环，也不是整环.(4)构成环，它是交换环、含幺环，但不是无零因子环和整环.注意：对于一般的 n,Zn是整环且是域 n是素数.,6.2环与域,10,例题,判断下列集合和给定运算是否构成环、整环和域.(1)A=a+bi|a,bQ,i2=1,运算为复数加法和乘法.(2)A=2z+1|

5、zZ,运算为普通加法和乘法(3)A=2z|zZ,运算为普通加法和乘法(4)A=x|x0 xZ,运算为普通加法和乘法.(5)，运算为普通加法和乘法,解(2),(4),(5)不是环.为什么？(1)是环,是整环,也是域.(3)是环,不是整环和域.,6.2环与域,11,环的性质,定理 设是环，则(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,反之：ab(a)b0，故(a)b的加法逆元是ab。(3)a,bR，(a)(b)=ab证明：(a)(b)=-(a(-b)=-(-(ab)=ab(4)a,

6、b,cR，a(bc)=abac，(bc)a=baca,6.2环与域,12,环中的运算,环中加法的交换律、结合律；乘法的结合律；乘法对加法的分配律.例 在环中计算(a+b)3,(ab)2解(a+b)3=(a+b)(a+b)(a+b)=(a2+ba+ab+b2)(a+b)=a3+ba2+aba+b2a+a2b+bab+ab2+b3(ab)2=(ab)(ab)=a2baab+b2 注：在初等代数中的加法和乘法运算都是在实数域中进行，乘法可交换,6.2环与域,13,格的定义,定义 设是偏序集，如果x,yS，x,y都有最小上界和最大下界，则称S关于偏序构成一个格。由于最小上界和最大下界的惟一性，可以把求

7、x,y的最小上界和最大下界看成 x 与 y 的二元运算和，即 xy 和 xy 分别表示 x 与 y 的最小上界和最大下界.注意：这里出现的和符号只代表格中的运算，而不再有其他的含义.,6.3格与布尔代数,14,格的实例,例 设n是正整数，Sn是n的正因子的集合.D为整除关系，则偏序集构成格.x,ySn，xy 是 lcm(x,y)，即 x 与 y 的最小公倍数.xy 是 gcd(x,y)，即 x 与 y 的最大公约数.下图给出了格，和.,6.3格与布尔代数,15,例 判断下列偏序集是否构成格，并说明理由.(1)，其中P(B)是集合B的幂集.(2)，其中Z是整数集，为小于等于关系.(3)偏序集的哈

8、斯图分别在下图给出.,格的实例（续）,解(1)是格.称为B的幂集格.(2)是格.(3)都不是格.,6.3格与布尔代数,16,格的性质：对偶原理,定义 设 f 是含有格中元素以及符号=,和的命题.令 f*是将 f 中的替换成,替换成,替换成,替换成所得到的命题.称 f*为 f 的对偶命题.例如,在格中：f 是(ab)cc,f*是(ab)cc.格的对偶原理：设 f 是含格中元素以及符号=,和等的命题.若 f 对一切格为真,则 f 的对偶命题 f*也对一切格为真.例如,若对一切格L都有 a,bL,aba，那么对一切格L都有 a,bL,aba,6.3格与布尔代数,17,格的性质：算律,定理 设是格,则

9、运算和适合交换律、结合律、幂等律和吸收律,即(1)a,bL 有 ab=ba,ab=ba(2)a,b,cL 有(ab)c=a(bc),(ab)c=a(bc)(3)aL 有 aa=a,aa=a(4)a,bL 有 a(ab)=a,a(ab)=a,6.3格与布尔代数,18,算律的证明,证(1)交换律.ab 是 a,b 的最小上界 ba 是 b,a的最小上界 a,b=b,a ab=ba.由对偶原理,ab=ba 得证.,6.3格与布尔代数,19,算律的证明（续）,(2)结合律.由最小上界的定义有(ab)caba(I)(ab)cabb(II)(ab)cc(III)由式(II)和(III)有(ab)cbc(I

10、V)由式(I)和(IV)有(ab)ca(bc).同理可证(ab)c a(bc).根据偏序的反对称性得到(ab)c=a(bc).由对偶原理,(ab)c=a(bc)得证.,20,算律的证明（续）,(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.2环与域,21,格作为代数系统的定义,定理 设是具有两个二元运算的代数系统,若对于和运算适合交换律、结合律、吸收律,则可以适当定义

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

12、cd)=d称 L3为钻石格,L4为五角格.,24,分配格的判定（续）,解 L1,L2和 L3都不是分配格.a,b,c,d,e 是 L1的子格,并且同构于钻石格；a,b,c,e,f 是 L2的子格,并且同构于五角格；a,c,b,e,f 是 L3的子格,也同构于钻石格.,例 说明图中的格是否为分配格,为什么？,25,全上界与全下界,定义 设L是格,若存在 aL 使得 xL 有 a x,则称 a 为 L 的全下界；若存在 bL 使得 xL 有 x b,则称 b 为 L 的全上界.说明：格 L 若存在全下界或全上界,一定是惟一的.一般将格 L 的全下界记为 0,全上界记为 1.,26,有界格定义及其性

13、质,定义 设 L是格,若 L存在全下界和全上界,则称 L为有界格,全下界记为0，全上界记为1.有界格 L 记为.注意：有限格 L=a1,a2,an是有界格,a1a2 an是 L 的全下界,a1a2an是全上界.0是关于运算的零元,运算的单位元.1 是关于运算的零元,运算的单位元.对于涉及有界格的命题,如果其中含有全下界0或全上界1,求其对偶命题时,必须将0与1互换.,27,补元的定义,定义 设是有界格,aL,若存在 bL使得ab=0 和 ab=1成立,则称 b 是 a 的补元.注意：若 b 是 a 的补元,那么 a 也是 b 的补元.a 和 b 互为补元.,28,实例:求补元,解：L1中 a,

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

15、.,31,布尔代数的定义,定义 如果一个格是有补分配格,则称它为布尔格或布尔代数.在布尔代数中，如果一个元素存在补元,则是惟一的.可以把求补元的运算看作是布尔代数中的一元运算.布尔代数标记为,其中为求补运算,32,布尔代数的实例,例 设 S110=1,2,5,10,11,22,55,110 是110的正因子集合.gcd 表示求最大公约数的运算 lcm表示求最小公倍数的运算.则 是否构成布尔代数？,33,布尔代数的等价定义,定义 设是代数系统,和是二元运算.若和运算满足交换律、结合律、幂等律、吸收律,即(1)a,bB有ab=ba,ab=ba(2)a,b,cB有 a(bc)=(ab)(ac),a(

16、bc)=(ab)(ac)(3)即存在0,1B,使得aB有 a1=a,a0=a(4)aB,存在 aB 使得 aa=0,aa=1 则称是一个布尔代数.可以证明，布尔代数的两种定义是等价的.,34,布尔代数的性质,定理 设是布尔代数,则(1)aB,(a)=a.(2)a,bB,(ab)=ab,(ab)=ab（德摩根律）注意：德摩根律对有限个元素也是正确的.,35,证明,证(1)(a)是 a的补元.a 是 a 的补元.由补元惟一性得(a)=a.(2)对任意 a,bB有(ab)(ab)=(aab)(bab)=(1b)(a1)=11=1,(ab)(ab)=(aba)(abb)=(0b)(a0)=00=0.所以 ab是 ab 的补元,根据补元惟一性可得(ab)=ab.同理可证(ab)=ab.,36,有限布尔代数的表示定理,定理 设 L 是有限布尔代数，则 L 含有 2n 个元素(nN)，且 L 与 同构，其中 S 是一个 n 元集合.结论：含有 2n 个元素的布尔代数在同构意义下只有一个.,