离散数学 第十三讲

《离散数学 第十三讲》由会员分享，可在线阅读，更多相关《离散数学 第十三讲（44页珍藏版）》请在金锄头文库上搜索。

1、2006-5-18北京邮电大学电子工程学院16.2 环与域环与域?6.2.1 环环域是特殊的环，它们都是具有两个二元运算的代 数系统，通常我们把这两个二元运算分别称为域是特殊的环，它们都是具有两个二元运算的代 数系统，通常我们把这两个二元运算分别称为“加法加法 +”和和“乘法乘法”。 定义定义6.16 设设是代数系统，是代数系统，R为集合，为集合，+, 为二 元运算，如果： （为二 元运算，如果： （1）为为Abel群群（交换群）（交换群） （2）为半群 （为半群 （3）乘法）乘法对加法对加法+ 满足分配律 则称满足分配律 则称是是环环。2006-5-18北京邮电大学电子工程学院2例例6.9K

2、lein四元群，证明四元群，证明是一个环。是一个环。ea bc ae cb bc ea cb aee a b cea bc 证明：（证明：（1） 为半群为半群（运算封闭，可结合）（运算封闭，可结合）（2） 为为Abel群群（已证明）（已证明）（3）运算对运算可分配运算对运算可分配ee ee ea ea eb eb ec ece a b cea bc2006-5-18北京邮电大学电子工程学院3， ，都是环，其中都是环，其中Z、Q、R 分别表示整数、有理数和实数集，分别表示整数、有理数和实数集，+和和分别表示普通 加法和乘法。分别表示普通 加法和乘法。定义定义6.17 在环在环中，如果乘法具有交换

3、律，则 称中，如果乘法具有交换律，则 称R是是交换环交换环；如果乘法运算有幺元，则称；如果乘法运算有幺元，则称R为为含幺 环含幺 环；如果存在；如果存在a,b R，a0且且b0，但，但ab=0，则称，则称a 为为R中的中的左零因子左零因子， b为为R中的中的右零因子右零因子；如果环；如果环R既 不含左零因子，又不含右零因子，则称既 不含左零因子，又不含右零因子，则称R为无零因子 环。为无零因子 环。2006-5-18北京邮电大学电子工程学院4例例6.9：， ， 都是交 换环。都是交 换环。不是交换环，因为矩阵的乘法一般不满 足交换律。不是交换环，因为矩阵的乘法一般不满 足交换律。， ，是无零因

4、子环，但是无零因子环，但不一定是无零因子环，如：不一定是无零因子环，如：中有中有 23=0，但，但2和和3都不是零元，所以都不是零元，所以不是无 零因子环，但不是无 零因子环，但是无零因子环。是无零因子环。2006-5-18北京邮电大学电子工程学院5定义定义6.18 若环若环是交换环、含幺环和无零因 子环，则称是交换环、含幺环和无零因 子环，则称R为整环。为整环。定义定义6.19 若环若环至少含两个元素，且是含幺 环和无零因子环，并且对任意的至少含两个元素，且是含幺 环和无零因子环，并且对任意的a R（a0）， 有：）， 有：a-1 R，则称，则称R为除环。为除环。?6.2.2 域 定义域 定

5、义6.20 若环若环既是整环，又是除环，则称既是整环，又是除环，则称R 为域。 如：为域。 如：是整环但不是除环是整环但不是除环（逆元一般不存 在）（逆元一般不存 在），因此不是域；而，因此不是域；而是域。是域。2006-5-18北京邮电大学电子工程学院6例例6.10 设设p为素数，证明为素数，证明是域。证明：因是域。证明：因p为素数，为素数，p2，所以|，所以| Zp|2显然，显然， Zp关于模关于模p乘法可交换，单位元是乘法可交换，单位元是1，且对任意 的，且对任意 的 i,j Zp，i0，有：，有：i j=0 p整除整除i j j=0所以，所以， Zp为无零因子的整环。为无零因子的整环。

6、Zp关于乘法构成有限半群，且关于乘法构成有限半群，且Zp关于满足消 去律。关于满足消 去律。Zp的幺元是的幺元是1，易知，易知Zp中任意元素的逆元存在，则中任意元素的逆元存在，则 Zp是域。是域。2006-5-18北京邮电大学电子工程学院7例例6.11 判断下列集合关于给定的运算是否构成环、整 环和域。如果不构成，请说明理由。判断下列集合关于给定的运算是否构成环、整 环和域。如果不构成，请说明理由。( )( )( )( )( ) ( )312,23,32,12223Aaba bZAaba bQAaba bZAA=+=+=+，关于数的加法和乘法。，关于数的加法和乘法。，关于数的加法和乘法。解：

7、是环和整环，但不是域。如，但没有逆元。是环、整环和域。 不是环、不是整环、也不是域。因为 关于数的乘法不封闭。2006-5-18北京邮电大学电子工程学院8( )( )( ) ( )24,15,4225111 1111 1111 1001 111 100Aabi a bZiabAa bZbaiAiAA=+= = =，关于复数的加法和乘法。，关于矩阵的加法和乘法。解： 是环和整环，但不是域。如，但 在 中没有逆元。是环，但不是整环（不是无零因子的）和域。考虑矩阵和，它们都是 中的矩阵，且满足：，因此11 1 111 1A 和分别是左零因子和右零因子，则 不是无零因子环。因此它不是整环和域。2006

8、-5-18北京邮电大学电子工程学院9定理定理定理定理6.11 6.11 设设设设 是是是是环，则：环，则：环，则：环，则：（1 1） a a R R， a a 0=00=0 a a =0=0（2 2） a a, ,b b R R，( (- - a)a) b b= = a a ( (- -b)=b)=- -( (a a b)b)（3 3） a a, ,b b R R，( (- - a)a) ( (- -b)= b)= a a b b（4 4） a,b,ca,b,c R R，a a (b(b- -c)=ac)=a b b- - a a c c (b(b- -c)c) a a=b=b a a- -

9、c c a a证明证明证明证明：（：（：（：（1 1） a a 0= 0= a a ( (0+0)= 0+0)= a a 0+ 0+ a a 0 0，则：则：则：则：0= 0= a a 0 0 。（2 2）( (- -a)a) b+ ab+ a b=b=( (- -a+a)a+a) b=0b=0 b=0b=0则：则：则：则：( (- -a)a) b b是是是是a a b b的的的的加法逆元。加法逆元。加法逆元。加法逆元。同理可证：同理可证：同理可证：同理可证：a a ( (- -b)=b)=- -(a(a b)b)（3 3）( (- -a)a) ( (- -b)=b)=- -(a (a ( (

10、- -b)b)=)=- -( (- -(a(a b)b)=a)=a b b（4 4）a a (b(b- -c)= c)= a a (b+(b+(- -c)=ac)=a b+ ab+ a ( (- -c)= ac)= a b b- - a a c c同理可证：同理可证：同理可证：同理可证：(b(b- -c)c) a a=b=b a a- - c c a a由（由（1）看出，加法的幺元）看出，加法的幺元0恰好是乘法的零元。恰好是乘法的零元。2006-5-18北京邮电大学电子工程学院106.3 格与布尔代数格与布尔代数注意，本节中的注意，本节中的“ ”和和“ ”不再表示逻辑符号，而 是偏序集中的两个

11、运算符。不再表示逻辑符号，而 是偏序集中的两个运算符。 定义定义6.21 设设是偏序集，若是偏序集，若x,y A，x,y的最 小上界和最大下界存在，且属于的最 小上界和最大下界存在，且属于A，则称，则称A关于构成关于构成 格格，分别记为，分别记为x y和和x y。 例例6.12 构成格，其中构成格，其中Sp表示表示n的正因子的集 合，的正因子的集 合，D表示整除关系。显然，表示整除关系。显然，x,y Sp， x y表示表示x与与y 的最小公倍数的最小公倍数x,y，x y表示表示x与与y的最大公约数的最大公约数(x,y)。2006-5-18北京邮电大学电子工程学院1112481236和和是格。是

12、格。 略，见略，见P1462006-5-18北京邮电大学电子工程学院12例例6.3.2 判断下列图中的偏序集是否构成格，为什么？判断下列图中的偏序集是否构成格，为什么？bcdef（1）aabc de（2）abcedf（3）不是格。因为不是格。因为 e,f 没有上界。不是格。因为 没有上界。不是格。因为b,d 虽有上界虽有上界c和和e，但 没有最小上界。不是格。因为 ，但 没有最小上界。不是格。因为d,e 虽有下界虽有下界a,b和和c， 但没有最大下界。， 但没有最大下界。2006-5-18北京邮电大学电子工程学院13定理定理6.12（对偶原理）（对偶原理） 设设 f 是含有格中的元素以及符 号

13、是含有格中的元素以及符 号=、 、的命题，令、 、的命题，令f *是将是将f 中的改写为 、改写为、改写为、改写为所得到的命 题，称为中的改写为 、改写为、改写为、改写为所得到的命 题，称为f 的对偶命题。 若的对偶命题。 若f 对一些格为真，则对一些格为真，则f *也对一切格为真。也对一切格为真。2006-5-18北京邮电大学电子工程学院14定理定理6.13 设设为格，则运算和满足交换律、 结合律、等幂律和吸收律，即： （为格，则运算和满足交换律、 结合律、等幂律和吸收律，即： （1） ） a,b L，有：，有： a b= b a a b= b a （2） ） a,b,c L，有：，有： (

14、a b) c=a (b c) (a b) c=a (b c) （3） ） a L，有：，有： a a=a a a=a （4） ） a,b L，有：，有： a (a b)=a a (a b)=a 证明：（证明：（4） a (a b) a 又由于：又由于：a a a b a ，则：，则： a (a b) a 则：则： a (a b) =a2006-5-18北京邮电大学电子工程学院15定义定义6.22 设设是格，若是格，若a,b L，有：，有： a (b c)=(a b) (a c) a (b c)= (a b) (a c) 则称则称L为分配格。为分配格。 定义定义6.23 若在格若在格中存在一个元素中存在一个元素a，对 ，对 b L，有，有ab（或（或a b），则称），则称a为格为格L的全下界 （或全上界）。 一个格的全下界 （或全上界）。 一个格L的全下界如果存在，则一定唯一，记为的全下界如果存在，则一定唯一，记为 0；一个格；一个格L的全上界如果存在，则一定唯一，记为的全上界如果存在，则一定唯一，记为 1。具有全上界和全下界的格称为有界格，记为。具有全上界和全下界的格称为有界格，记为 所有的有限元的格都是有界格，但所有的有限元的格都是有界