第6章格与布尔代数（课件）.ppt

Chapter 6 格与布尔代数 格论(1935)是一种重要的代数结构, 它是计算机语言的指称语义的理论基础，在计算机应用逻辑研究中有着重要作用. 布尔代数是英国数学家George Boole在1847年左右在对逻辑思维法则进行研究时提出的，后来很多数学家特别是E. V. Hungtington和E. H. Stone对布尔代数的进行了一般化研究，在1938年C. E. Shannon发表的A Symbolic Analysis of Relay and Switching Circuits 论文，为布尔代数在工艺技术 6.1 用偏序集定义的格 1.格的第一种定义 偏序集(L, ?)? Remark 偏序集(L, ?)中不是任意两个元素均存在上确界及下确界的. {c, b}, {a, d}? 6.2 用代数结构定义的格 1.格的第二种定义 Def 设(L, +, ?)是代数结构, +和?是L上的两个2元运算, 同时满足: (1)交换性. (2)结合性. (3)吸收性. 则称(L, +, ?)为格, 称这样定义的格为代数格. 由定义知, 格是具有两个2元运算的代数结构. 6.3 分配格 1.分配格的定义 有例子表明, 格不满足分配性. 例 6-9 举例说明在格(L, ?)中, 格的乘法运算“?”和格加法运算“+”相互不一定可分配. Solution 6.4 有补格 1.有界格 一般来说,格L不一定存在最大元与最小元. 例如,实数集R关于数的小于等于关系? 所作成的格(R, ?). Def 设(L, ?)是格, 若L存在最大元素1以及最小元素0, 则称(L, ?)为有界格(bounded lattice). 6.5 布尔代数 1.布尔代数的格定义 Def 元素个数 ?2 的有补分配格(B, ?)称为布尔代数(Boolean algebra)或布尔格. 偏序集与各种格之间的相互关系? 仅1个元素的有补分配格是布尔代数的退化情形，一般不作为布尔代数考虑，可参见布尔代数的公理化定义. 显然，在任何布尔代数或布尔格中有两个特殊元素，一个是其最小元0，一个是其最大元1. 当然0 ? 1. 6.6 有限布尔代数的结构 有限布尔代数与无限布尔代数? 对于集合代数(P(X), ?), 当|X| = n?1有限时P(X)有限, (P(X), ?)是有限布尔代数. Theorem (M. H. Stone)设 是有限布尔代数, 则存在有限集合X使得 与集合代数 ?, X)同构. 6.7 布尔表达式 布尔表达式的化简及其主范式表示在理论研究和实际应用中都有十分重要的意义. 1 布尔表达式的定义 Def 设 是布尔代数，则B上的布尔表达式(Boolean expression)递归定义如下: (1)B中的元素a, b, c等是布尔表达式. (2)取值于B的变元x1, x2,…等是布尔表达式. (3)若e1和e2是布尔表达式，则 , e1+e2 , e1? e2布尔表达式. (4)有限次使用(1)(2)(3)得到的字符串是仅有的布尔表达式. 2.补元?有补格 Def 设(L, +, ?)是有界格, a ? L, 若存在b ? L,使得a + b = 1且a ? b = 0, 则称b为a的补元(complement). 显然, 在任意有界格中, 若b为a的补元, 则a为b的补元； 0与1互为补元. 但对于有界格, 不是每个元素均有补元, 同时一个元素的补元未必唯一. 因此, 不能定义1元运算 . Def 设(L, +, ?)是有界格, 若L中每个元素都有补元, 则称(L, +, ?)为有补格(lattice complemented). 例6-14 证明: 对任意集合X, (P(X), ?)是有补格. Hint ?A ? P(X), X - A ? P(X): A ? (X - A) = X, A ? (X - A) = ?. 右图是有补格, 不是分配格. 几个重要结论. Theorem 6-13 在分配格中, 若一个元素存在补元,则补元是唯一的. Clearly. 根据定理6-13知, 在有补分配格中, 每个元素都有唯一的补元. 正因为如此, 在有补分配格中可以定义一个元素的补运算“ ”，它是其上的1元代数运算. 下述定理是有补分配格的重要性质. Theorem 6-14 设(L, +, ?)是有补分配格, 则De Morgan律成立, 即对于任意x, y ? L, 有 (1) (2) Proof (1) (2)? Theorem 6