《离散数学 (12)》由会员分享，可在线阅读，更多相关《离散数学 (12)（35页珍藏版）》请在金锄头文库上搜索。
1、1,环与域,环的定义与实例环的运算性质子环及其判别环的同态整环与域,2,环的定义,定义14.24 设是代数系统，+和是二元运算. 如果满足以下条件: (1) 构成交换群， (2) 构成半群， (3) 运算关于+运算适合分配律，则称是一个环. 为了叙述的方便，通常称+运算为环中的加法，运算为环中的乘法. 环中加法单位元记作0，乘法单位元（如果存在）记作1. 对任何元素x，称x的加法逆元为负元，记作x. 若x存在乘法逆元的话，则称之为逆元，记作x1. 因此在环中写xy意味着x+(y).,3,环的实例,例1 (1) 整数集、有理数集、实数集和复数集关于普通的加法和乘法构成环，分别称为整数环Z，有理数
2、环Q，实数环R和复数环C.(2) n（n2）阶实矩阵集合Mn(R)关于矩阵的加法和乘法构成环，称为n阶实矩阵环.(3) 设Z0,1,.,n1，和分别表示模n的加法和乘法，则构成环，称为模n的整数环.,4,环的性质,定理14.11 设是环，则 (1) aR，a0 = 0a = 0 (2) a, bR，(a)b = a(b) = ab (3) a, b, cR，a(bc) = abac， (bc)a = baca (4) a1, a2, . , an, b1, b2, . , bmR（n, m2）,例2 在环中计算(a+b)3, (ab)2解 (a+b)3 = (a+b)(a+b)(a+b) =
3、(a2+ba+ab+b2)(a+b) = a3+ba2+aba+b2a+a2b+bab+ab2+b3 (ab)2 = (ab)(ab)=a2baab+b2,5,子环,定义14.25 设R是环，S是R的非空子集. 若S关于环R的加法和乘法也构成一个环，则称S为R的子环. 若S是R的子环，且SR，则称S是R的真子环.例如整数环Z，有理数环Q都是实数环R的真子环. 0和R也是实数环R的子环，称为平凡子环. 定理14.12 (子环判定定理) 设R是环, S是R的非空子集, 若(1) a,bS，abS(2) a,bS，abS则 S 是 R 的子环.,6,实例,例3 (1) 整数环，对于任意给定的自然数n
4、， nZ = nz | zZ 是 Z 的非空子集，根据判定定理，容易验证nZ是整数环的子环. (2) 考虑模 6 整数环， 0 , 0,3 , 0,2,4 , Z6是它的子环. 其中 0 和Z6是平凡的，其余的都是非平凡的真子环.,7,环同态,定义14.26 设R1和R2是环. f :R1R2,若对于任意的 x, yR1有 f(x+y)= f(x)+f(y), f(xy)= f(x) f(y)成立，则称 f 是环R1到 R2 的同态映射，简称环同态.例4 设R1=是整数环，R2=是模n的整数环. 令f :ZZn， f(x)= x modn，则x, yZ有f(x+y)=(x+y)mod n= x
5、mod n ymod n = f(x)f(y) f(xy)=(xy)mod n=xmod n ymod n = f(x)f(y) f 是R1到R2的同态，是满同态.,8,特殊的环,定义14.27 设是环， (1) 若环中乘法适合交换律，则称R是交换环. (2) 若环中乘法存在单位元，则称R是含幺环. (3) 若a, bR，ab=0 a=0b=0，则称R是无零因子环. (4) 若R既是交换环、含幺环，也是无零因子环，则称R是整环.零因子的实例：在模6整数环中，有32=0，而3和2都不是乘法的零元. 这时称3为左零因子，2为右零因子. 这种含有左零因子和右零因子的环就不是无零因子环.,9,实例,例
6、5 (1) 整数环Z、有理数环Q、实数环R、复数环C都是交换环、含幺环、无零因子环和整环. (2) 令2Z=2z|zZ，则构成交换环和无零因子环. 但不是含幺环和整环.(3) 设nZ, n2, 则n阶实矩阵的集合Mn(R)关于矩阵加法和乘法构成环，它是含幺环，但不是交换环和无零因子环，也不是整环.(4)构成环，它是交换环、含幺环，但不是无零因子环和整环. 可以证明对于一般的n, Zn是整环当且仅当n是素数.,10,域,定义14.28设R是整环，且R中至少含有两个元素. 若aR* , 其中R*=R0，都有a1R，则称R是域.例如有理数集Q、实数集R、复数集C关于普通的加法和乘法都构成域，分别称为
7、有理数域、实数域和复数域. 整数环Z是整环，而不是域. 对于模n的整数环Zn，若n是素数，那么Zn是域.,11,实例,(2) 不是环, 关于加法不封闭.,例6 判断下列集合和给定运算是否构成环、整环和域. 如果不构成, 说明理由. (1) A= a+bi | a,bQ, 其中i2= 1, 运算为复数加法和 乘法. (2) A=2z+1 | zZ, 运算为实数加法和乘法. (3) A=2z | z Z, 运算为实数加法和乘法. (4) A=x | x0 xZ, 运算为实数加法和乘法. (5), 运算为实数加法和乘法.,解 (1) 是环, 是整环, 也是域.,(3) 是环, 不是整环和域, 乘法没
8、有单位元.,(5) 不是环, 关于乘法不封闭.,(4) 不是环, A关于加法不构成群.,12,格与布尔代数,格的定义格的性质格的等价定义子格与格的同态特殊的格布尔代数的性质布尔代数的同态与同构,13,格的定义,定义14.29 设是偏序集，如果x, yS，x,y都有最小上界和最大下界，则称S关于偏序作成一个格. 由于最小上界和最大下界的惟一性，可以把求x,y的最小上界和最大下界看成 x与y 的二元运算和，即xy 和 xy 分别表示x与y的最小上界和最大下界. 注意：这里出现的和符号只代表格中的运算，而不再有其他的含义.,14,实例,例7 设n是正整数，Sn是n的正因子的集合. D为整除关系，则偏
9、序集构成格. x,ySn，xy是 lcm(x,y)，即x与y的最小公倍数；xy是 gcd(x,y)，即 x与y 的最大公约数. 实例：,15,实例(续),例8 判断下列偏序集是否构成格，并说明理由. (1) ，其中P(B)是集合B的幂集. (2) ，其中Z是整数集，为小于或等于关系. (3) 偏序集的哈斯图分别给下图,解: (1),(2)是格，(3)中的都不是格.,16,格的性质对偶原理,定义14.30 设 f 是含有格中元素以及符号=, , ,和的命题.令f*是将 f 中的替换成、替换成、替换成、替换成所得到的命题. 称 f* 为 f 的对偶命题. 例如在格中令 f 是 (ab)cc, f*
10、是 (ab)cc . 那么 f 与 f* 互为对偶命题. 格的对偶原理 设 f 是含有格中元素以及符号=、和等的命题，若 f 对一切格为真, 则 f 的对偶命题 f*也对一切格为真.例如, 对一切格L命题“a,bL, aba”都成立. 根据对偶原理，对一切格L，命题 “a,bL, aba”也为真.,17,格的性质算律,定理14.13 设是格, 则运算和适合交换律、结合律、幂等律和吸收律，即 (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
11、 和 a(ab)=a,18,证明,只证 (1) 和 (2). 根据对偶原理，只证其中一个等式即可. (1) ab是a, b的最小上界，ba是b, a的最小上界. 由于a, b=b, a, 所以 ab=ba. 由最小上界定义有下述不等式： (ab)caba (ab)cabb (ab)cc 由式 和 (ab)cbc 由式和有 (ab)ca(bc). 同理可证 (ab)ca(bc). 根据偏序的反对称性得 (ab)c=a(bc). ,19,定理,定理14.14 设是具有两个二元运算的代数系统，若 * 和运算满足交换、结合、吸收律，则可以适当定义 S 上偏序 ，使得 构成格，且导出的代数系统就是.证明
12、思路(1) 利用运算 或 * 定义 S 上的二元关系 R 证明 R 为 S 上的偏序，证明构成格(4) 证明对于格中任意两个元素x,y xy = x y, xy = x*y,20,格的等价定义,定义14.31 设是具有两个二元运算的代数系统，如果,满足交换、结合、吸收律，则称是格.实例： x, y, z Sn, gcd(x,y)=gcd(y,x), lcm(x,y)=lcm(y,x) gcd(x,gcd(y,z) = gcd(gcd(x,y),z) lcm(x,lcm(y,z)=lcm(lcm(x,y),z) gcd(x,lcm(x,y)=x, lcm(x,gcd(x,y)=x 定义 x|y
13、lcm(x,y)=y与是同一个格,21,格的子格与格同态,定义14.32 L的子格：L的非空子集S，且S关于L中 和 运算封闭.注意：对于子格元素，在原来格中求最大下界和最小上界.例如 G的子群格L(G)是格，但一定不是P(G)的子格. 实例：Klein四元群G=e, a, b, c， L(G)= , , , , G P(G)= , ,a, b, c, , , , a,b, a,c, b,c, e,a,b, e,a,c, e,b,c, a,b,c, G 在P(G)中,=e,a,b，在L(G)中， =G定义14.33 设 f:L1L2，若x,yL1，有 f(xy) = f(x)f(y)，f(xy) = f(x)f(y) 则称 f 为L1到 L2 的同态.,22,特殊的格,分配格有补格布尔格,
