《离散数学.环与域优秀PPT.ppt》由会员分享，可在线阅读，更多相关《离散数学.环与域优秀PPT.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1现在学习的是第1页，共38页环的定义环的定义定义定义 设设是代数系统，是代数系统，+和和是二元运算是二元运算.如果满足以下条件如果满足以下条件:（1）构成构成交换群交换群（2）构成构成半群半群（3）运算关于运算关于+运算适合运算适合分配律分配律则称则称是一个是一个环环.2现在学习的是第2页，共38页环中的术语环中的术语通常称通常称+运算为环中的运算为环中的加法加法，运算为环中的运算为环中的乘法乘法.环中加法幺元记作环中加法幺元记作0.乘法幺元（如果存在）记作乘法幺元（如果存在）记作1.环中加法幺元环中加法幺元0恰好是乘法的零元恰好是乘法的零元.对任何元素对任何元素x，称，称x 的加法逆元为的
2、加法逆元为负元负元，记作，记作 x.若若x 存在乘法逆元的话，则称之为存在乘法逆元的话，则称之为逆元逆元，记作，记作x 1.3现在学习的是第3页，共38页环的实例环的实例 (1)整数集、有理数集、实数集和复数集关于普整数集、有理数集、实数集和复数集关于普通的加法和乘法构成环，分别称为通的加法和乘法构成环，分别称为整数环整数环Z，有有理数环理数环Q，实数环实数环R 和和复数环复数环C.(2)n(n2)阶实矩阵的集合阶实矩阵的集合Mn(R)关于矩阵的加关于矩阵的加法和乘法构成环，称为法和乘法构成环，称为n阶实矩阵环阶实矩阵环.(3)集合的幂集集合的幂集P(B)关于集合的对称差运算和关于集合的对称差
3、运算和交运算构成环交运算构成环.(4)设设Zn0,1,.,n1，和和 分别表示模分别表示模n的的加法和乘法，则加法和乘法，则构成环，称为构成环，称为模模n的整的整数环数环.4现在学习的是第4页，共38页特殊的环特殊的环定义定义 设设是环，是环，(1)若环中乘法若环中乘法适合交换律，则称适合交换律，则称R是是交换环交换环.(2)若环中乘法若环中乘法存在幺元，则称存在幺元，则称R是是含幺环含幺环.(3)若若 a,bR，a b=0a=0b=0，则称，则称R是是无零因无零因子环子环.(4)若若R 既是交换环、含幺环，也是无零因子环，既是交换环、含幺环，也是无零因子环，则称则称R 是是整环整环.(5)若
4、若R为整环，为整环，|R|1,且且 a R*=R-0，a-1 R,则称则称R 为为域域.5现在学习的是第5页，共38页 零因子的定义与存在条件零因子的定义与存在条件设设是环，若存在是环，若存在ab=0,且且a 0,b 0,称称a 为为左零因子，左零因子，b为右零因子，环为右零因子，环R 不是无零因子环不是无零因子环.实例实例，其中，其中2 3=0，2和和3都是零因子都是零因子.无零因子环的条件：无零因子环的条件：可以证明：可以证明：ab=0a=0 b=0消去律消去律6现在学习的是第6页，共38页特殊环的实例特殊环的实例(1)整数环整数环Z、有理数环、有理数环Q、实数环、实数环R、复数环、复数环
5、C都是交换环、都是交换环、含幺环、无零因子环和整环含幺环、无零因子环和整环.其中除其中除Z之外都是域之外都是域(2)令令2Z=2z|zZ，则，则构成交换环和无零因子构成交换环和无零因子环环.但不是含幺环和整环但不是含幺环和整环.(3)设设n Z,n 2,则则n 阶实矩阵的集合阶实矩阵的集合Mn(R)关于矩阵加关于矩阵加法和乘法构成环，它是含幺环，但不是交换环和无法和乘法构成环，它是含幺环，但不是交换环和无零因子环，也不是整环零因子环，也不是整环.(4)构成环，它是交换环、含幺环，但不是无零因构成环，它是交换环、含幺环，但不是无零因子环和整环子环和整环.注意：对于一般的注意：对于一般的n,Zn是
6、整环且是域是整环且是域n是素数是素数.7现在学习的是第7页，共38页例题例题判断下列集合和给定运算是否构成环、整环和域判断下列集合和给定运算是否构成环、整环和域.(1)A=a+bi|a,b Q,i2=1,运算为复数加法和乘法运算为复数加法和乘法.(2)A=2z+1|z Z,运算为普通加法和乘法运算为普通加法和乘法(3)A=2z|z Z,运算为普通加法和乘法运算为普通加法和乘法(4)A=x|x0 x Z,运算为普通加法和乘法运算为普通加法和乘法.(5)，运算为普通加法和乘法，运算为普通加法和乘法解解(2),(4),(5)不是环不是环.为什么？为什么？(1)是环是环,是整环是整环,也是域也是域.(
7、3)是环是环,不是整环和域不是整环和域.8现在学习的是第8页，共38页环的性质环的性质定理定理设设是环，则是环，则(1)aR，a0=0a=0(2)a,bR，(a)b=a(b)=ab(3)a,bR，(a)(b)=ab(4)a,b,cR，a(b c)=ab ac，(b c)a=ba ca9现在学习的是第9页，共38页环中的运算环中的运算环中加法的交换律、结合律；环中加法的交换律、结合律；乘法的结合律；乘法的结合律；乘法对加法的分配律乘法对加法的分配律.例例在环中计算在环中计算(a+b)3,(a b)2解解(a+b)3=(a+b)(a+b)(a+b)=(a2+ba+ab+b2)(a+b)=a3+ba
8、2+aba+b2a+a2b+bab+ab2+b3(a b)2=(a b)(a b)=a2 ba ab+b2注：在初等代数中的加法和乘法运算都是在实数域中进行，乘法可交换注：在初等代数中的加法和乘法运算都是在实数域中进行，乘法可交换10现在学习的是第10页，共38页6.3 格与布尔代数格与布尔代数n格的定义与实例格的定义与实例n格的性质格的性质 对偶原理对偶原理 交换律、结合律、幂等律、吸收律交换律、结合律、幂等律、吸收律n 格的等价定义格的等价定义n 子格子格n 格的同构格的同构n 特殊的格：分配格、有界格、有补格、布尔格特殊的格：分配格、有界格、有补格、布尔格 11现在学习的是第11页，共3
9、8页格的定义格的定义定义定义设设是偏序集，如果是偏序集，如果 x,y S，x,y都有都有最小上界和最大下界，则称最小上界和最大下界，则称S关于偏序关于偏序 构成一个构成一个格。格。由于最小上界和最大下界的惟一性，可以把求由于最小上界和最大下界的惟一性，可以把求x,y的最小上界和最大下界看成的最小上界和最大下界看成x 与与y 的二元运算的二元运算和和，即，即xy 和和xy 分别表示分别表示x 与与y 的最小上界和的最小上界和最大下界最大下界.注意：这里出现的注意：这里出现的和和符号只代表格中的运算，符号只代表格中的运算，而不再有其他的含义而不再有其他的含义.12现在学习的是第12页，共38页 格
10、的实例格的实例例例设设n是正整数，是正整数，Sn是是n的正因子的集合的正因子的集合.D为为整除关系，则偏序集整除关系，则偏序集构成格构成格.x,ySn，xy 是是lcm(x,y)，即，即x 与与y 的最小公倍数的最小公倍数.xy 是是gcd(x,y)，即，即x 与与y 的最大公约数的最大公约数.下图给出了格下图给出了格，和和.13现在学习的是第13页，共38页例例判断下列偏序集是否构成格，并说明理由判断下列偏序集是否构成格，并说明理由.(1)，其中，其中P(B)是集合是集合B的幂集的幂集.(2)，其中，其中Z是整数集，是整数集，为小于等于关系为小于等于关系.(3)偏序集的哈斯图分别在下图给出偏
11、序集的哈斯图分别在下图给出.格的实例（续）格的实例（续）解解(1)是格是格.称称为为B的的幂集格幂集格.(2)是格是格.(3)都不是格都不是格.14现在学习的是第14页，共38页格的性质：对偶原理格的性质：对偶原理定义定义设设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 a15现在学习的是第15页，共38页格的性质：算律格的性质：算律定理定理设设是格是格,则运算则运算和和适合交换律、结适合交换律、结合律、幂等律和吸收律合律、幂等律和吸收律,即即(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)=a16
13、现在学习的是第16页，共38页算律的证明算律的证明证证(1)交换律交换律.ab 是是a,b的最小上界的最小上界ba 是是b,a的最小上界的最小上界a,b=b,a ab=ba.由对偶原理由对偶原理,ab=ba 得证得证.17现在学习的是第17页，共38页算律的证明（续）算律的证明（续）(2)结合律结合律.由最小上界的定义有由最小上界的定义有(ab)c ab a(I)(ab)c ab b(II)(ab)c c(III)由式由式(II)和和(III)有有(ab)c bc(IV)由式由式(I)和和(IV)有有(ab)c a(bc).同理可证同理可证(ab)c a(bc).根据偏序的反对称性得到根据偏序
14、的反对称性得到(ab)c=a(bc).由对偶原理由对偶原理,(ab)c=a(bc)得证得证.18现在学习的是第18页，共38页算律的证明（续）算律的证明（续）(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 得证得证.19现在学习的是第19页，共38页格作为代数系统的定义格作为代数系统的定义定理定理设设是具有两个二元
15、运算的代数系统是具有两个二元运算的代数系统,若对于若对于 和和 运算适合交换律、结合律、吸收律运算适合交换律、结合律、吸收律,则则可以适当定义可以适当定义S中的偏序中的偏序,使得使得构成格构成格,且且 a,bS有有 ab=a b,ab=a b.根据定理根据定理,可以给出格的另一个等价定义可以给出格的另一个等价定义.定义定义设设是代数系统是代数系统,和和 是二元运算是二元运算,如果如果 和和 运算运算满足交换律、结合律和吸收律满足交换律、结合律和吸收律,则则构成格构成格.20现在学习的是第20页，共38页子格的定义及判别子格的定义及判别定义定义设设是格是格,S 是是L 的非空子集的非空子集,若若
16、S 关于关于L中运算中运算和和仍构成格仍构成格,则称则称S是是L 的子格的子格.例例设格设格L 如图所示如图所示.令令S1=a,e,f,g,S2=a,b,e,g S1不是不是L的子格的子格,S2是是L的子格的子格.因为对于因为对于 e,f S1，ef S1.21现在学习的是第21页，共38页格同态格同态定义定义设设L1和和L2是格是格,f:L1L2,若若 a,bL1有有 f(ab)=f(a)f(b),f(ab)=f(a)f(b)成立成立,则称则称f 为格为格L1到到L2的同态映射的同态映射,简称简称格同态格同态.22现在学习的是第22页，共38页分配格定义分配格定义定义定义设设是格是格,若若
17、a,b,cL,有有a(bc)=(ab)(ac)a(bc)=(ab)(ac)则称则称L 为为分配格分配格.注意：以上条件互为充分必要条件注意：以上条件互为充分必要条件这两个等式中只要有一条成立，另一条一定成立这两个等式中只要有一条成立，另一条一定成立.在证明在证明L为分配格时为分配格时,只须证明其中的一个等式即可只须证明其中的一个等式即可.23现在学习的是第23页，共38页分配格的定义（续）分配格的定义（续）L1和和L2是分配格是分配格,L3和和L4不是分配格不是分配格.在在L3中中,b(cd)=b，(bc)(bd)=a在在L4中中,c(bd)=c，(cb)(cd)=d称称L3为为钻石格钻石格,
18、L4为为五角格五角格.24现在学习的是第24页，共38页分配格的判定及其性质分配格的判定及其性质定理定理设设L 是格是格,则则L 是分配格当且仅当是分配格当且仅当L 不含有不含有与钻石格或五角格同构的子格与钻石格或五角格同构的子格.证明省略证明省略.定理定理格格L 是分配格当且仅当是分配格当且仅当 a,b,cL,ab=ac且且ab=ac b=c.推论推论(1)小于五元的格都是分配格小于五元的格都是分配格.(2)任何一条链都是分配格任何一条链都是分配格.25现在学习的是第25页，共38页分配格的判定（续）分配格的判定（续）解解L1,L2和和L3都不是分配格都不是分配格.a,b,c,d,e 是是L
19、1的子格的子格,并且同构于钻石格；并且同构于钻石格；a,b,c,e,f 是是L2的子格的子格,并且同构于五角格；并且同构于五角格；a,c,b,e,f 是是L3的子格的子格,也同构于钻石格也同构于钻石格.例例 说明图中的格是否为分配格说明图中的格是否为分配格,为什么？为什么？26现在学习的是第26页，共38页全上界与全下界全上界与全下界定义定义设设L是格是格,若存在若存在aL 使得使得 xL 有有a x,则称则称a 为为L 的的全全下界下界；若存在若存在bL 使得使得 xL 有有x b,则称则称b 为为L 的的全全上界上界.说明：说明：格格L 若存在全下界或全上界若存在全下界或全上界,一定是惟一
20、的一定是惟一的.一般将格一般将格L 的全下界记为的全下界记为0,全上界记为全上界记为1.27现在学习的是第27页，共38页有界格定义及其性质有界格定义及其性质定义定义设设L是格是格,若若L存在全下界和全上界存在全下界和全上界,则称则称L为为有界格有界格,全下界记为全下界记为0，全上界记为，全上界记为1.有界格有界格L 记为记为.注意：有限格注意：有限格L=a1,a2,an是有界格是有界格,a1a2an是是L 的全下界的全下界,a1a2an是全上界是全上界.0是关于是关于运算的零元运算的零元,运算的单位元运算的单位元.1是关于是关于运算的零元运算的零元,运算的单位元运算的单位元.对于涉及有界格的
21、命题对于涉及有界格的命题,如果其中含有全下界如果其中含有全下界0或全或全上界上界1,求其对偶命题时求其对偶命题时,必须将必须将0与与1互换互换.28现在学习的是第28页，共38页补元的定义补元的定义定义定义设设是有界格是有界格,aL,若存在若存在bL使得使得ab=0和和ab=1成立成立,则称则称b 是是a 的的补元补元.注意：若注意：若b 是是a 的补元的补元,那么那么a 也是也是b 的补元的补元.a 和和b 互为补元互为补元.29现在学习的是第29页，共38页实例实例:求补元求补元 解：解：L1中中a,c互补互补,b没补元没补元.L2中中a,d互补互补,b,c互补互补.L3中中a,e互补互补
22、,b 的补元是的补元是c和和d,c 的补元是的补元是b和和d,d 的补元是的补元是b和和c.L4中的中的a,e互补互补,b 的补元是的补元是c和和d,c 的补元是的补元是b,d 的补元是的补元是b.30现在学习的是第30页，共38页有界分配格中补元惟一性有界分配格中补元惟一性定理定理设设是有界分配格是有界分配格.若若L中元素中元素a 存在补元存在补元,则存在惟一的补元则存在惟一的补元.证证假设假设b,c 是是a 的补元的补元,则有则有ac=1,ac=0,ab=1,ab=0从而得到从而得到ac=ab,ac=ab,由于由于L是分配格是分配格,b=c.31现在学习的是第31页，共38页有补格的定义有
23、补格的定义定义定义设设是有界格是有界格,若若L 中所有元素都中所有元素都有补元存在有补元存在,则称则称L 为为有补格有补格.例如例如,下图中的下图中的L2,L3和和L4是有补格是有补格,L1不是有补格不是有补格.32现在学习的是第32页，共38页布尔代数的定义布尔代数的定义定义定义如果一个格是有补分配格如果一个格是有补分配格,则称它为则称它为布尔格布尔格或或布尔布尔代数代数.在布尔代数中，如果一个元素存在补元在布尔代数中，如果一个元素存在补元,则是惟一则是惟一的的.可以把求补元的运算看作是布尔代数中的一元可以把求补元的运算看作是布尔代数中的一元运算运算.布尔代数标记为布尔代数标记为,其中其中为
24、求补为求补运算运算33现在学习的是第33页，共38页布尔代数的实例布尔代数的实例例例设设S110=1,2,5,10,11,22,55,110是是110的正的正因子集合因子集合.gcd表示求最大公约数的运算表示求最大公约数的运算lcm表示求最小公倍数的运算表示求最小公倍数的运算.则则是否构成布尔代数？是否构成布尔代数？34现在学习的是第34页，共38页布尔代数的等价定义布尔代数的等价定义定义定义设设是代数系统是代数系统,和和 是二元运算是二元运算.若若 和和 运算满足交换律、结合律、幂等律、吸收律运算满足交换律、结合律、幂等律、吸收律,即即(1)a,bB有有a b=b a,a b=b a(2)a
25、,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则称则称是一个是一个布尔代数布尔代数.可以证明，布尔代数的两种定义是等价的可以证明，布尔代数的两种定义是等价的.35现在学习的是第35页，共38页布尔代数的性质布尔代数的性质定理定理设设是布尔代数是布尔代数,则则(1)aB,(a)=a.(2)a,bB,(ab)=a b,(ab)=a b（德摩根律）（德摩根律）注意：德摩根律对有限个元素也是正确的注意：德摩根律对有限个元素也是正确的.36现
26、在学习的是第36页，共38页证明证明证证(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.37现在学习的是第37页，共38页有限布尔代数的表示定理有限布尔代数的表示定理定理定理设设L 是有限布尔代数，则是有限布尔代数，则L 含有含有2n个元素个元素(n N)，且，且L与与同构，其中同构，其中 S是是一个一个n元集合元集合.结论结论：含有：含有2n个元素的布尔代数在同构意义下只有个元素的布尔代数在同构意义下只有一个一个.38现在学习的是第38页，共38页