布尔代数与布尔格

6.1.1 格的概念（lattices） 格的概念（ ） 虽然偏序集合的任何子集的上确界、 虽然偏序集合的任何子集的上确界、下确界并不一 定都存在，但存在，则必唯一， 定都存在，但存在，则必唯一，而格的定义保证了 任意两个元素的上确界、下确界的存在性。 任意两个元素的上确界、下确界的存在性。因此我 们通常用a∨b表示 ，b}的上确界，用a∧b表示 ， 表示{a， 的上确界 的上确界， 表示{a， 们通常用 ∨ 表示 ∧ 表示 b}的下确界，即 的下确界， 的下确界 a∨b=LUB{a,b}（Least upper bound）, ∨ （ ） a∧b=GLB{a,b}(Greatest lower bound), ∧
LUB{a, b} = LUB{a, b}, GLB{a, b} = GLB{a, b}
L B L B
为此我们考察下面的例子。 为此我们考察下面的例子。 如图6.1.4), 取 【例6.1.4】设〈A，≤〉是一个格 如图 】 ， 〉是一个格(如图
B1 = {b, d , h}, B2 = {a, b, d , h}, B3 = {a, b, d , f } B4 = {c, e, g , h}, B5 = {a, b, c, d , e, g , h},
计算机科学与技术学院
第6章 格和布尔代数 章
6.1.1 格的概念（lattices） 格的概念（ ）
表示正整数集， ”表示Z 上整除关系， （3）设Z+表示正整数集，“|”表示 +上整除关系，那么 ） 〈 Z+ ，|〉为格，其中并、交运算即为求两正整数最小公倍数 〉为格，其中并、 和最大公约数的运算， 和最大公约数的运算，即 m∨n＝LCM（m,n） m∧n＝GCD(m,n）, ∨ ＝ （ ） ∧ ＝ ） 由〈 Z+ ，|〉所诱导的代数系统为〈 Z+ ， ∨，∧ 〉。 〉所诱导的代数系统为〈 （4）任一全序集〈A， 〉是一个格。因为 a,b ∈A， ）任一全序集〈 ， 是一个格。 ， ∀

第三节 子布尔代数、积布尔代数、布尔代数同态
定义：给定布尔代数<B, , *, ’ , 0, 1>，≠T B
2015年6月6日星期六
若T对 、* 和 ’ 是封闭的，且：0, 1 T
称<T, , *, ’ , 0, 1>是<B, , *, ’ , 0, 1>的子布尔代 数 显然：<{0, 1}, , *, ’ , 0, 1>和<B, , *, ’ , 0, 1> 都是<B, , *, ’ , 0, 1>的(平凡)子布尔代数
则：<f(B),∨,∧, , f(0), f(1)>是布尔代数 （证明参见教材P170 —— 利用布尔代数的定义证明）
布尔代数同态
结论：
2015年6月6日星期六
若 f 是从布尔代数<B, , *, ’ , 0, 1>到格<S,∨,∧>的 格同态映射，且f是满射的，
则：<S,∨,∧>是布尔代数
并且可以用基本公式来定义布尔代数
布尔代数的定义 从这4个定律，可以推出所有布尔代数的公式
有兴趣的同学可以参阅 R. L. 古德斯坦因 著的
对于a, b B ， 有 定义：设<B, , *, ’ >是一个代数结构，其中：
2015年6月6日星期六
和 * 是B上的二元运算，’ 是B上的一元运算，且 0, 1 B
例9.15：设Bn是由0和1形成的n元组集合，且
2015年6月6日星期六
a = <a1, a2, …, an>，b = <b1, b2, …, bn> 0n = <0, 0, …, 0> ， 1n = <1, 1, …, 1> 对任意 a, b Bn，定义： a b = < a1∨b1, a2∨b2 , …, an∨bn > a * b = < a1∧b1, a2∧b2 , …, an∧bn > a’ = < a1, a2, …, an> < Bn,∨,∧, , F, T>是布尔代数（开关代数）

〈a2,b2〉∈L×S,有 〈a1,b1〉。〈a2,b2〉=〈a1*a2 , b1∧b2〉 〈a1,b1〉+〈a2,b2〉=〈a1 a2,b1∨b2〉
我们称〈L×S,*,+〉是格〈L,*, 〉和〈S,∧,∨〉 的直接乘积或积代数。
第7章 格与布尔代数
例2
(a) 图7.2―6给出了格〈｛1,2,4｝,D〉和 〈｛1,3｝,D〉的积代数。这个积代数和格〈S12,D〉的 图完全一样,只不过前者结点用〈a,b〉标记,后者结点用 ab标记而已。 (b) 记L=｛0,1｝,考虑格〈L,≤〉自身的积代数。这 里≤是通常意义的“小于或等于”。这些积代数是 〈L2,≤2〉,〈L3,≤3〉…〈Ln,≤n〉…。一般地说,在格
(e)图7.1―1(e)所示的哈斯图也是一个格。
第7章 格与布尔代数
图 7.1―1
第7章 格与布尔代数
图 7.1―2
第7章 格与布尔代数
7.1.2 格的对偶性原理和基本性质
给定一个偏序集合〈S,≤〉,≤的逆关系≥也是S中的 偏序关系,〈S,≥〉也是偏序集合,我们称偏序集合〈S,≤〉 和〈S,≥〉互为对偶。从图形上看,后者的哈斯图就是前 者哈斯图的上下颠倒。如果A S,则关系 ≤的lub(A)和 glb (A)就分别等同于关系≥的glb(A)和lub(A)。因此,如果 〈L,≤〉是一个格,则〈L,≥〉也是一个格,我们说这两个 格互为对偶。互为对偶的两个格〈L,≤〉和〈L,≥〉有着 密切关系:格〈L,≤〉中的保交正是格〈L,≥〉中的保联,
(14)模不等式的证明。 若a≤c,则a c=c,代入公式(13)得 a (b*c)≤(a b)*c 若a(b*c)≤(a b)*c,由于a≤a 传递性得a≤c。 (b*c ),(a b )*c≤c,根据

定义6.7 集合 L 中的偏序关系 R 与其逆关系 R1，称为互 相对偶的两个关系。 对任意 x, y∈L，xR1y yRx。 6.1.1 节例 6.4 中的 关系即为蕴涵关系 的逆关系。 因此，对任意 P, Q∈S， (P Q) (Q P)
【例6.7】设 n 是一个正整数，Sn 是 n 的所有因数的集合， 两个正整数的最大公因数 ，最小公倍数 可看作是 Sn 上两个代数运算，于是，(Sn, , ) 是一个格。
定理6.1 关于格的两种定义（以对应一个代数格；任意一个代 数格也都可以对应一个偏序格。
定义中没有要求 , 运算满足等幂律，实际上由 , 满足吸收律即可推出它们一定满足等幂律。任取 L 中元素
a，由 , 满足吸收律知
a(aa)＝a
a(aa)＝a
故
aa＝a(a(aa))
aa＝a(a(aa))
又由 , 满足吸收律知，上面两式的等式右端都等于 a。
因此，
aa＝a
aa＝a
即定义 6.3 中的 , 运算亦满足等幂律。
【例6.4】设 S 是所有的命题集合，定义 “” 关系如下： A B 当且仅当 B 蕴涵 A
则 (S, ) 是一个格。对 A, B∈S， sup{A, B}＝A∧B∈S inf{A, B}＝A∨B∈S
定义6.2 若格 L 的一个子集 M≠Ф 对于运算 和 封闭， 则 M 称作子格。
例如：a 是格 L 的一个固定元素，则使 X≥a(或 X≤a) 的 L 中元素 X 的集合，显然是一个子格。若 a≥b，则使 a≥X≥b 的 L 中元素 X 的集合是一个子格，这样的子格 叫作一个闭区间(商)，记作 M(a,b)。
例如，S6＝{1, 2, 3, 6}， S24＝{1, 2, 3, 4, 6, 8, 12, 24}。