第13讲 环和域, 格与布尔代数 主要内容: 1.环和域的有关内容. 2格与布尔代数的有关内容.

5.3 环和域 群仅一个2元运算,环是有两个2元运算的代数结构. 1. 环的定义 Def 设(R, +, )是含两个2元运算的代数结构，若 5.3 环和域 群仅一个2元运算,环是有两个2元运算的代数结构. 1. 环的定义 Def 设(R, +, )是含两个2元运算的代数结构，若 (1) (R, +)是Abel群. (2) (R, )是半群. (3)对+可分配: 则称(R, +, )是环(ring).

环的加法? 环的乘法? 下面是几种常见的环的例子. 例5-17 容易验证关于数的加法和乘法运算,下列代数结构是环. (1)(Z, +, )(整数环). (2)(R, +, ).

例5-18 设R是所有n阶元素取值整数的矩阵组成的集合, 则R对于矩阵的加法运算+和矩阵的乘法运算构成环,称为矩阵环. 例5-19 验证：Zm = {0, 1, 2, …, m-1}对于模m加法运算+m和模m乘法运算 m构成环, 称为模m剩余类环. 例5-20 设所有实数集合R上的关于x的多项式组成的集合为R[x],则R[x]对应多项式的加法运算+和多项式的乘法运算构成环,称为R上的多项式环.

2. 几种特殊的环. Def 5-26 设(R, +, )是环,若 (1)R中的可交换,则(R, +, )称是交换环. (2)R中的有幺元,则称(R, +, )是含幺环,其乘法幺元记为1. (3)对于任意x  0, y  0, 均有x  y  0,则称(R, +, )是无零因子环,其中0是环的零元. (4) (R, +, )是含幺、无零因子、交换环,则称(R, +, )为整环(integral domain). (5) (R, +, )是含幺环且任意x  0关于乘法运算都有逆元, 则称(R, +, )为除环.

关于交换环或含幺环的判断是容易的, 对于无零因子环有以下说明. (a)环的零元是加法幺元. (b)对于整数环(Z, +, ), 因为其零元是0, 对于任意x  0, y  0, 均有x  y  0, 所以整数环(Z, +, )是无零因子环. (c)若x  0, y  0, 而x  y = 0, 则称x和y是零(的)因子. 含有零因子的环称为有零因子环. 例如, 对于模6剩余类环(Z6, +6, 6),其零元为0, 显然, 2 6 3 = 0, 所以2和3是零因子,因此, 环(Z6, +6, 6)是有零因子环.

例5-31 对于m > 1,模n剩余类环(Zm, +m, m)是无零因子环的充要条件是m为素数. Proof ()(反证) ()

很容易验证, (Z, +, )是整环但不是除环. 下面介绍一个重要的除环的例子—四元数除环. 例5-22 R = {a + bi + cj +dk|a, b, c, d  R}, (R, +, )是除环.

用复数表示平面上的向量.(用数而不是几何). 空间中的向量: 要同时具有实数和复数的性质, 3个分量可以吗? 15年以后, William R. Hamilton在1843年10月16日步行在Brougham桥上时,思想的电路接通了,想到了用i, j, k扮演i的角色. (1) a + bi + cj +dk, a, b, c, d  R. (2) 乘法不满足交换律. 作用: 存在一个四元数用来旋转, 伸长或缩短一个给定的空间向量成另一个给定的空间向量, 在计算机图形图像中用.

Def 5-17 设(F, +, )是环, 若(F – {0}, )是Abel群, 则称(F, +, )是域(field). 3.域的定义 Def 5-17 设(F, +, )是环, 若(F – {0}, )是Abel群, 则称(F, +, )是域(field). 对于域(F, +, ), 有 |F|  2. 例5-23 验证: (R, +, )是域, 而整数环(Z, +, )不是域. Field

例5-24 证明: 域是整环, 但整环不一定是域. Theorem 5-29 阶2的有限整环是域. Proof f单射:

4.有限域 有限域(finite field)称为Galois域, 有q个元素的Galois域记为GF(q). 有限域理论在计算机密码学中有着非常重要的应用, 特别是研究公钥密码学中的大素数测试算法. 例5-25 验证: 环(Z5, +5, 5)是域, 但(Z6, +6, 6)不是域. Hint

Theorem 5-5 环(Zm, +m, m)是域当且仅当是m素数. Proof ()(Zm, +m, m)是无零因子环. ()

下面将不加证明地给出几个关于有限域的结论,先给出域的同态与同构的定义. Def 设(F1, +, )和(F2, , ⊙)是域, 若: F1  F2且分别保持域的加法运算和乘法运算, 则称为(F1, +, )到(F2, , ⊙)的域同态映射. 若是双射且是域同态映射,则称为(F1, +, )到(F2, , ⊙)的域同构映射,又称域(F1, +, )与(F2, , ⊙)同构,记为(F1, +, )  (F2, , ⊙).

Theorem 5-6下面结论成立: (1)设(F, +, )是有限域, 则存在素数p和正整数n使得|F| = pn. (2)对于任意素数p和正整数n, 存在pn个元素的有限域. (3)元素个数相同的有限域是同构的. 作业 习题5.3 1, 11, 13.

5-4 格与布尔代数 格论(1935)是一种重要的代数结构, 它是计算机语言的指称语义的理论基础，在计算机应用逻辑研究中有着重要作用. 布尔代数是英国数学家George Boole在1847年左右在对逻辑思维法则进行研究时提出的，后来很多数学家特别是E. V. Hungtington和E. H. Stone对布尔代数的进行了一般化研究，在1938年C. E. Shannon发表的A Symbolic Analysis of Relay and Switching Circuits 论文，为布尔代数在工艺技术

格和布尔代数都是按“序结构”进行的讨论，它们本质上也是代数结构. 中的应用开创了先河, 作为计算机设计基础的《数字逻辑》就是布尔代数. 格和布尔代数都是按“序结构”进行的讨论，它们本质上也是代数结构.

1.格的定义和性质 偏序集(L, )? Remark 偏序集(L, )中不是任意两个元素均存在上确界及下确界的. {c, b}, {a, d}?

Def 设(L, )是偏序集, 若L中任意两个元素都存在上确界以及下确界, 则称(L, )是格(lattice) 钻石格与五角格?

例5-26 证明: (P(X), )是格, 其中P(X)是集合X的幂集. Proof (cf. Chapter 1) A, B  P(X), (1)sup{A, B} = A  B, (2)inf{A, B} = A  B.

例5-27 证明: (Dn, |)是格, 其中Dn是自然数n的正因数组成的集合, | 是其上的整除关系. Proof (cf. Chapter 2)

例5-28 令F是所有合式公式(WFF)组成的集合,  是公式间的逻辑蕴涵关系, 则(F, )是格. Proof (cf. Chapter 3) A, B  F, (1)sup{A, B} = A  B, (2)inf{A, B} = A  B.

Def 设(L, )是格, x + y = sup{x,y}, x ∙ y = inf{x,y}. 格中的“+”是求上确界运算, 可以看作是格的加法运算, 读作“加”；同样, 格中的“”是求下确界运算, 可以看作是格的乘法运算, 读作“乘”. (与环中的“加”和“乘”, 以及数的“加”和“乘”不同) (与布尔代数的运算一致)

由于“上确界上界”以及“下界下确界”,根据定义易知 Theorem 5-7 设(L, )是格,则对于任意x, y  L, 有 (1)x  x + y, y  x + y. (2)x ∙ y  x, x ∙ y  y.

(L, )与(L, )? Def 5-21对于任意关于格(L, )的命题, 将命题前提和结论中的(1) 改为; (2)+ 改为; (3)  改为+；(4)0改为1；(5)1改为0所得到的命题称为原命题的对偶命题. Theorem 5-8 对于任意关于格(L, )的真命题,其对偶命题亦为真. 如 (1)x  x + y, y  x + y; (2)x ∙ y  x, x ∙ y  y. 在格的性质中, 有很多都是成对(dual)出现的.

Theorem 5-9(保序性) 设(L, )是格, 对于任意xi, yi  L, i = 1, 2: Proof (1) x1 + x2 是{x1 , x2}的上确界; (2) y1 + y2 是{x1 , x2}的上界: 设(L, )是格, x  L, x + x = x, x ∙ x = x.

格的特征性质. Theorem 5-10 格(L, )满足: (1)交换性. (2)结合性. (3)吸收性. Proof (3)x  x, x ∙ y  x  x+ (x ∙ y) x; 显然, x  x+ (x ∙ y), 所以x+ (x ∙ y) = x. x ∙ (x + y) = x? (仿上; 对偶)

设(L, +, ∙)是代数结构, +和是L上的两个2元运算, 同时满足: (1)交换性. (2)结合性. (3)吸收性. 格是具有两个2元运算的代数结构. 可以证明偏序格和代数格本质相同.

在序结构的讨论中，保序映射是一个很重要的概念. Def 5-22 保序映射可以进一步推广到一般的关系R上考虑. 例5-29?

2.分配格(distributive lattice)的定义 有例子表明, 格不满足分配性. 例 5-30 举例说明在格(L, )中, 格的乘法运算“”和格加法运算“+”相互不一定可分配. Solution

钻石格? 五角格?

Def 设(L, +, ∙)是格, 若格的乘法运算“”对格的加法运算“+”可分配 (或格的加法运算“+”对格的乘法运算“”可分配), 则称(L, +, ∙)是分配格. 例5-31 证明: (P(X), )是分配格. 其他例子?

钻石格和五角格是两个非常重要的非分配格的例子. 我们只给出 Theorem 5-11 (1) 小于5个元素的格为分配格. (2) 任意链是分配格.

Theorem 5-12 设(L, +, ∙)是格, 则L是分配格的充要条件是对于任意x, y, z  L,由x + y = x + z和x ∙ y = x ∙ z可以推出y = z. Remark 由x + y = x + z可以推出y = z? x ∙ y = x ∙ z? Proof () y = y + (x ∙ z) = (y +x) ∙(y + z) = (z +x) ∙(y + z) = (x ∙ y) + z = (x ∙ z) + z = z. ()? 判断一个格是否分配格?

3.有补格 一般来说,格L不一定存在最大元与最小元. 例如,实数集R关于数的小于等于关系 所作成的格(R, ). Def 设(L, )是格, 若L存在最大元素1以及最小元素0, 则称(L, )为有界格(bounded lattice).

例5-32 证明: 对任意集合X, (P(X), )是有界格. Hint 最小元素: . 显然, 任意有限格是有界格(?).

Def 5-25 设(L, +, ∙)是有界格, a  L, 若存在b  L,使得a + b = 1且a ∙ b = 0, 则称b为a的补元(complement). 因此, 不能定义1元运算 .

Def 5-26 设(L, +, ∙)是有界格, 若L中每个元素都有补元, 则称(L, +, ∙)为有补格(lattice complemented). 例5-34 证明: 对任意集合X, (P(X), )是有补格. Hint A  P(X), X - A  P(X): A  (X - A) = X, A  (X - A) = . 右图是有补格, 不是分配格.

Theorem 5-13 在分配格中, 若一个元素存在补元,则补元是唯一的. Clearly. 根据定理5-13知, 在有补分配格中, 每个元素都有唯一的补元. 正因为如此, 在有补分配格中可以定义一个元素的补运算“ ”，它是其上的1元代数运算.

下述定理是有补分配格的重要性质. Theorem 5-14 设(L, +, ∙)是有补分配格, 则De Morgan律成立, 即对于任意x, y  L, 有 (1) (2) Proof (1) (2)?

4.布尔代数 Def 元素个数 2 的有补分配格(B, )称为布尔代数(Boolean algebra)或布尔格. 偏序集与各种格之间的相互关系? 仅1个元素的有补分配格是布尔代数的退化情形，一般不作为布尔代数考虑，可参见布尔代数的公理化定义. 显然，在任何布尔代数或布尔格中有两个特殊元素，一个是其最小元0，一个是其最大元1. 当然0  1.

在任意布尔代数(B, )中可以定义3种代数运算: 对于任意x, y  B, (a)布尔加“+”: x + y = sup{x, y}. (b)布尔乘“”: x ∙ y = inf{x, y}. (c)布尔补“ ”: x的补元. 例5-35 设|X|  1, 证明: (P(X), )是布尔代数, 称为集合代数: , X) .

例5-36 证明: (F, )是布尔代数, 其中F是所有合式公式组成的集合, 是公式间的逻辑蕴涵关系,称为逻辑代数, F中的元素是逻辑表达式: 特别地,令G是所有命题公式组成的集合,则称(G, )为命题代数. 令H是仅含命题变元p1, p2,…, pn的所有命题公式组成的集合,则(H, )是布尔代数,这时 由于集合代数和逻辑代数都是布尔代数,因此它们有完全相似的性质.

布尔代数的性质： Theorem 5-15 设(B, )是布尔代数, I. (B, )是格; II. (B, )是分配格; III. (B, )是有补格; IV. (B, )是有补分配格.

以下是布尔代数的特征性质,参见下面的布尔代数的公理化定义. 交换律. 分配律. 幺元律： 有补律：

布尔代数的公理化定义 Def (E. V. Hungtington) 设B是集合, |B|  2, “+”和“”是B上的两个2元代数运算, “ ”是B上的1元代数运算,且满足 (1)交换律. (2)分配律. (3)幺元律: (4)有补律: 则称 是布尔代数. Remark (1) 按这种定义需强调两个0元运算. (2) 布尔代数的两种定义是等价的.

两个布尔代数同构? 有限布尔代数与无限布尔代数?对于集合代数(P(X), ), 当|X| = n1有限时P(X)有限, (P(X), )是有限布尔代数. 下面给出有限布尔代数的结构定理. Theorem (M. H. Stone)设 是有限布尔代数, 则存在有限集合X使得 与集合代数 , X)同构.

由Stone定理有 Corollary 1 任意有限布尔代数的元素个数为2n,其中n为正整数. Corollary 2 在同构意义下, 2n个元素的有限布尔代数是唯一的, 其中n为正整数. 作业 习题5-4 1, 3, 5, 7, 9, 11, 13.