第七章 格与布尔代数 布尔代数是计算机逻辑设计的基础，它是由格引出的， 格又是从偏序集引出的。所以我们先回顾一下偏序集。 <A,≤>是偏序集:≤是A上自反,反对称和传递关系(偏序). 偏序集中的元素间的次序可以通过它的Hasse图反映出来. 例如A={1,2,3,6,12,24,36}, ≤是A上整除关系 其Hasse图如图所示，BA B≠Φ ６。 １。 ３。 12。 ２。 24。 36。 1. B的极小元与极大元 y是B的极小元y∈B∧x(x∈B∧x≤y) y是B的极大元y∈B∧x(x∈B∧y≤x) 例如{2,3,6}的极小元:2,3 极大元:6

y是B的最小元y∈B∧x(x∈By≤x) y是B的最大元y∈B∧x(x∈Bx≤y) {2,3,6}的最小元:无 最大元: 6 ６。 １。 ３。 12。 ２。 24。 36。 2. B的最小元与最大元 y是B的最小元y∈B∧x(x∈By≤x) y是B的最大元y∈B∧x(x∈Bx≤y) {2,3,6}的最小元:无 最大元: 6 B如果有最小元(最大元), 则是唯一的。 3. B的下界与上界 y是B的下界y∈A∧x(x∈By≤x) y是B的上界y∈A∧x(x∈Bx≤y) {2,3,6}的下界:1 上界: 6,12,24,36 4. B的最大下界(下确界)与最小上界(上确界) y是B的最大下界(下确界)：B的所有下界x,有x≤y。 y是B的最小上界(上确界)：B的所有上界x,有y≤x。 {2,3,6}下确界:1 上确界:6 (B若有下(上)确界,则唯一)

7-1 格 (Lattice) 一 . 基本概念 1. 格的定义 <A,≤>是偏序集，如果任何a,b∈A,使得{a,b}都有最大 右图三个偏序 集,哪个是格？ 30。 3。 １。 2。 5。 10。 15。 6。 ６。 １。 ３。 12。 ２。 24。 36。 3。 4。 1。 2。 <A,≤>不是格， 因为{24,36} 无最小上界。 <B,≤>和<C,≤> 是格。再看下面三个偏序集，哪个是格？ <A,≤> <C,≤> <B,≤>

第一个与第三个是同构的。因为 d和e无下界，也无 最小上界；b,c虽有下界，但无最大下界。 第二个图：2,3无最大下界，4,5无最小上界。 a b  c e 1 2  3 4  5  6  e 第一个与第三个是同构的。因为 d和e无下界，也无 最小上界；b,c虽有下界，但无最大下界。 第二个图：2,3无最大下界，4,5无最小上界。 这三个偏序集，都不是格， 2. 平凡格：所有全序都是格，称之为平凡格。 因为全序中任何两个元素x,y，要么x≤y, 要么y≤x。 如果x≤y，则{x,y}的最大下界为x，最小上界为y。 如果y≤x，则{x,y}的最大下界为y，最小上界为 x 。 即这{x,y}的最大下界为较小元素，最小上界为较大元素.

设<A, ≤>是格,在A上定义二元运算∨和∧为:a,b∈A 3. 由格诱导的代数系统 设<A, ≤>是格,在A上定义二元运算∨和∧为:a,b∈A a∨b=LUB {a,b}, {a,b}的最小上界.Least Upper Bound a∧b=GLB {a,b}, {a,b}的最大下界.Greatest Lower Bound 称<A,∨,∧>是由格<A,≤>诱导的代数系统. (∨-并,∧-交) 例如右边的格中a∧b=b a∨b=a b∧c=e  e  a b   d  c 4. 子格：设<A,≤>是格, <A,∨,∧>是由 <A,≤>诱导的代数系统。B是A的非空子 集，如果∧和∨在B 上封闭，则称<B, ≤> 是<A, ≤>的子格。 b   a  c  f e   g  d <B,≤> <A,≤> d <C,≤> <C,≤>是<A,≤>的 子格。而<B,≤>不是. 因b∧c=dB, (判定子格：看去掉的元素是否影响封闭)

二. 格的对偶原理 三. 格的性质 设<A,≤>是格，≤的逆关系记作≥，≥也是偏序关系。 所以<A, ≥>也是格，<A,≥>的Hasse图是将<A,≤>的 Hasse图颠倒180º即可。 格的对偶原理：设P是对任何格都为真的命题，如果将 P中的≤换成≥，∧换成∨，∨换成∧，就得到命题P’ , 称P’为P的对偶命题，则P’对任何格也是为真的命题。 例如：P: a∧b≤a P’: a∨b≥a {a,b}的最大下界≤a {a,b}的最小上界≥a 三. 格的性质 <A,∨,∧>是由格<A,≤>诱导的代数系统。a,b,c,d∈A 1. a≤a∨b b≤a∨b a∧b≤a a∧b≤b 此性质由运算∨和∧的定义直接得证。

2.如果a≤b，c≤d，则 a∨c≤b∨d，a∧c≤b∧d。 证明：如果a≤b，又b≤b∨d, 由传递性得a≤b∨d, 类似由c≤d， d≤b∨d，由传递性得c≤b∨d, 这说明b∨d是{a,c}的上界，而a∨c是{a,c}的最小上界， 所以a∨c≤b∨d。 类似可证 a∧c≤b∧d。 推论：在一个格中，任何 a,b,c∈A，如果b≤c，则 a∨b≤a∨c，a∧b≤a∧c。 此性质称为格的保序性。 3. ∨和∧都满足交换律。即 a∨b=b∨a，a∧b=b∧a。 此性质由运算∨和∧的定义直接得证。

4. ∨和∧都满足幂等律。即 a∨a=a a∧a=a 由≤自反得a≤a, 这说明a是{a}的上界，而a∨a是{a}的 最小上界，所以 a∨a≤ a。最后由≤反对称得 a∨a=a 。 由对偶原理得 a∧a=a 5. ∨和∧都满足结合律。即 (a∨b)∨c =a∨(b∨c) ， (a∧b)∧c =a∧(b∧c) 。 证明：⑴先证明(a∨b)∨c ≤a∨(b∨c) ∵ a≤ a∨(b∨c) b≤b∨c ≤ a∨(b∨c) ∴ (a∨b) ≤a∨(b∨c) ∵ c≤b∨c ≤ a∨(b∨c) ∴ (a∨b)∨c ≤a∨(b∨c) ⑵同理可证 a∨(b∨c)≤(a∨b)∨c 最后由反对称得 (a∨b)∨c =a∨(b∨c) 类似可证 (a∧b)∧c =a∧(b∧c) 。

6. ∨和∧都满足吸收律。即 a∨( a∧b) =a， a∧(a∨b) =a。 证明：⑴显然有 a≤a∨( a∧b) ⑵.再证 a∨( a∧b) ≤a ∵ a≤ a a∧b ≤a ∴ a∨( a∧b) ≤a 最后由≤反对称得 a∨( a∧b) =a， 类似可证 a∧(a∨b) =a。 7. <A,∨,∧>是代数系统，如果∨和∧是满足吸收律的二 元运算，则∨和∧必满足幂等律。 证明：任取a,b∈A ∵ ∨和∧是满足吸收律。∴有 a∨( a∧b) =a ------⑴ a∧(a∨b) =a -------⑵。 由于上式中的b是任意的，可以令b=a∨b 并代入⑴式得 a∨(a∧(a∨b)) =a 由⑵式得 a∨a=a 同理可证a∧a=a

a∨(b∧c)≤ (a∨b)∧(a∨c) ， (a∧b)∨(a∧c)≤ a∧(b∨c) 。 我们先看右图的例子： b  8. ∨和∧不满足分配律。但有分配不等式： a∨(b∧c)≤ (a∨b)∧(a∨c) ， (a∧b)∨(a∧c)≤ a∧(b∨c) 。 我们先看右图的例子：  c  a b   e  d d∨(b∧e)=d∨c=d (d∨b)∧(d∨e) =a∧e=e d≤e 即 d∨(b∧e) ≤ (d∨b)∧(d∨e) 证明：⑴ ∵ a≤a∨b a≤a∨c ∴a ≤(a∨b)∧(a∨c) ∵ b∧c≤b≤ a∨b b∧c≤c≤ a∨c ∴ b∧c ≤(a∨b)∧(a∨c) 于是有 a∨(b∧c) ≤(a∨b)∧(a∨c) 类似可证(a∧b)∨(a∧c)≤ a∧(b∨c) 。

*9. a≤b a∨b=b  a∧b=a 证明：⑴教材 P239 已证 a≤b  a∧b=a 这里从略。 ⑵下面证明 a≤b a∨b=b 先证a≤b a∨b=b 设 a≤b，又b≤b ∴ a∨b≤ b 又∵ b≤a∨b 由≤反对称得 a∨b=b 再证 a∨b=b  a≤b 已知 a∨b=b ∵ a≤ a∨b ∴ a≤b。 最后得 a≤b a∨b=b 这是个很重要的定理，在以后用到此结论证明a≤b 。

四.格的同态与同构 1.定义：设<A1,≤1> 和<A2, ≤2>是两个格，由它们诱导 在映射f:A1A2 使得对任何a,b∈A1, f(a∨1b)=f(a)∨2f(b) f(a∧1b)=f(a)∧2f(b) 则称f是<A1,∨1,∧1>到 <A2,∨2,∧2>的同态映射。 也称<f(A1),≤2>是<A1,≤1> 的同态像。 如果 f 是双射的，就称f是<A1,∨1,∧1>到 <A2,∨2,∧2>， 的格同构，也称格<A1,≤1> 和<A2, ≤2>同构。

例如<A,≤>, A={1,2,3,6}, ≤是A上整除关系。 <P(E),>, E={a,b} 其中∨和∧分别是求两个数的最小公倍数和最大公约数.  Φ {b} {a}  {a,b}  1  3 2   6 f 6  3  1  {a} {a,b} Φ A P(E) f(2∨3)=f(6)={a,b} f(2)∪f(3)={a}∪{b}={a,b} f(2∧3)=f(1)=Φ f(2)∩f(3)={a}∩{b}=Φ f(2∨6)=f(6)={a,b} f(2)∪f(6)={a}∪{a,b}={a,b} f(2∧6)=f(2)={a} f(2)∩f(6)={a}∩{a,b}={a} 可见它们同构。格同构，它们的图的形状一定相同。

2. 格同态的保序性 定理：设f是格<A1,≤1> 到<A2, ≤2> 的同态映射，则对任 何a,b∈A1,如果a≤1b, 则 f(a)≤2f(b). 证明：令<A1,∨1,∧1>和 <A2,∨2,∧2>是格<A1,≤1> 和 <A2, ≤2>诱导的代数系统，任取a,b∈A1,设a≤1b, 则 a∧1b=a f(a∧1b)=f(a) 而f(a∧1b)= f(a)∧2f(b)，所以 f(a)∧2f(b)=f(a) ， 所以 f(a)≤2f(b). 3. 格同构的保序性 定理：设双射f是格<A1,≤1> 到<A2, ≤2> 的同构映射， 当且仅当 对任何a,b∈A1, 若 a≤1b  f (a)≤2f(b). <A2, ≤2>诱导的代数系统，

1).充分性：已知，任取a,b∈A1, 若a≤1b  f (a)≤2f(b). ( 应证出 f(a∧1b)=f(a)∧2f(b) f(a∨1b)=f(a)∨2f(b) ) a) 先证 f(a∧1b)=f(a)∧2f(b) 令a∧1b=c ∴ c≤1a , c≤1b , 由已知得 f(c)≤2f(a) 和 f(c)≤2f(b). 所以 f(c)≤2f(a)∧2f(b)---------⑴ 再证 f(a)∧2f(b)≤2 f(c) ： 由于f(a),f(b)∈A2 , 又∧2的封闭性得 f(a)∧2f(b)∈A2 , 又由f:A1A2是满射，必有d∈A1, 使得 f(d)=f(a)∧2f(b) 所以 f(d)≤2f(a) , f(d)≤2f(b) . 由已知条件得： d≤1a, d≤1b ∴ d≤1a∧1b=c , d≤1c , 于是得 f(d)≤2f(c) , 即　f(a)∧2f(b)≤2 f(c) --------⑵ 由⑴⑵得 f(c)=f(a)∧2f(b) 即 f(a∧1b)=f(a)∧2f(b) 。 b)类似可证 f(a∨1b)=f(a)∨2f(b) 所以 f是它们的同构映射.

2).必要性：已知 f是格<A1,≤1> 到<A2, ≤2> 的同构映射， （证出：任取a,b∈A1, 若a≤1b  f (a)≤2f(b) ） a) 先证 a≤1b  f (a)≤2f(b) 任取a,b∈A1,设a≤1b ，由格同态保序性得 f(a)≤2 f(b) b)再证f (a)≤2f(b)  a≤1b 设 f (a)≤2f(b)， ∴ f(a)=f(a)∧2f(b)=f(a∧1b) ∵f 是入射，∴ a=a∧1b 所以 a≤1b 由a),b)最后得 a≤1b  f (a)≤2f(b) 。 定理证毕。 由格的同构得如下结论： 具有一、二、三个元素的格分别同构于含有一、二、 三个元素的链。  a  b  c

作业 P242 (1) (2) (4) (7) 具有四个元素的格分别同构于下面两种格形式之一：  d  a  b  c  d  a b  c 具有五个元素的格分别同构于下面五种格形式之一：  e  c  d  a b  b c 作业 P242 (1) (2) (4) (7)

7-2 几个特殊格 一. 分配格 前面我们介绍一般的格，∧和∨只满足分配不等式。 a∨(b∧c)≤ (a∨b)∧(a∨c) ， (a∧b)∨(a∧c)≤ a∧(b∨c) 。 下面介绍的是满足分配律的格----分配格。 1. 定义： <A,∨,∧>是由格<A,≤>诱导的代数系统。如果 对a,b,c∈A，有 a∨(b∧c) =(a∨b)∧(a∨c) ， a∧(b∨c)= (a∧b)∨(a∧c) 则称<A,≤>是分配格。 例 <P(E),∪,∩>是分配格。

一个格是分配格的充分且必要条件是在该格中没有任 何子格与上述两个五元素非分配格之一同构。 用此方法可以判定下面两个格不是分配格： 2. 二个重要的五元素非分配格： 2∧(3∨5)=2∧30=2 (2∧3)∨(2∧5)=1∨1=1 c∧(b∨d)=c∧a=c (c∧b)∨(c∧d)=e∨d=d 可见它们都不是分配格。 3.分配格的判定：见书 P245 一个格是分配格的充分且必要条件是在该格中没有任 何子格与上述两个五元素非分配格之一同构。 用此方法可以判定下面两个格不是分配格：  3  1  30 2  5  d  e  a b  c  4  1  6 3  5  2  f  g  a d  c e b

4. 分配格的性质 1). 定理7-2.1. 在格中，如果∧对∨可分配，则∨对∧也 可分配。反之亦然。 证明：设<A,∨,∧>是由格<A,≤>诱导的代数系统。且∧ 对∨可分配。任取a,b,c∈A， a∧(b∨c)= (a∧b)∨(a∧c) 而 (a∨b)∧(a∨c) = ((a∨b)∧a)∨((a∨b)∧c) (分配) =a∨((a∨b)∧c)=a∨((a∧c)∨(b∧c)) (吸收、分配) = (a∨(a∧c))∨(b∧c) (结合) = a∨(b∧c) (吸收) 同理可证: 如果∨对∧可分配，则∧对∨也可分配. 2). 定理7-2.2. 所有链均为分配格。 证明：显然任何链都不会含有与五元素非分配格之一同 构的子格，所以链必是分配格。

3). 定理7-2.3 . 设<A, ≤>是分配格，对任何a,b,c∈A, 如果 有 a∧b=a∧c 及 a∨b=a∨c 则必有 b=c . 证明：任取a,b,c∈A, 设有 a∧b=a∧c 及 a∨b=a∨c b=b∨(a∧b) (吸收律) =b∨(a∧c) (代换) =(b∨a)∧(b∨c) (分配) =(a∨b)∧(b∨c) (交换) =(a∨c)∧(b∨c) (代换) = (a∧b)∨c (分配) = (a∧c)∨c (代换) =c (吸收律)

二. 有界格 1. 格的全上界与全下界 1).全上界:设<A, ≤>是格，如果存在元素a∈A 对任何x∈A, x≤a, 则称 a是格的全上界,记作1。 (即是A的最大元) 定理7-2.4 一个格如果有全上界，则是唯一的。 (我们已证明过，如果有最大元，则是唯一的) 2).全下界:设<A, ≤>是格，如果存在元素a∈A 对任何x∈A, a≤x, 则称 a是格的全下界,记作0。 (即是A的最小元) 定理7-2.5 一个格如果有全下界，则是唯一的。 从格的图形看：全上界1，就是图的最上边元素(只一个). 全下界0，就是图的最下边元素(只一个)。  b  0  1 a  c  1  c  0

2. 有界格定义：如果一个格存在全上界1与全下界0，则 称此格为有界格。 设<A, ≤>是有界格，则对任何a∈A, 有 因为a≤1, ∴ a∧1=a a∨1=1 0≤a ∴ a∧0=0 a∨0=a 由此看出：对于∧ 来说 1是么元，0是零元。 对于∨ 来说 0是么元，1是零元。 思考题： 是否所有格都是有界格？ 所有有限个元素的格都是有界格。 而无限个元素的格可能是无界格。 例如<I,≤>就是既无全上界也无全下界。

三. 有补格 回顾：集合的补集， 若 A∪B=E A∩B=Φ 则 ~A=B，~B=A 如E={a,b} ~E=Φ ~Φ=E 1. 元素的补元： 设<A,≤>是个有界格，a∈A, 如果存在 b∈A, 使得 a∨b=1 a∧b=0 则称a与b互为补元。 例：右边的格中 a的补元：c, e b的补元： 无 c的补元：a,d d的补元：c e的补元：a 0 的补元：1 1的补元：0  Φ {a,b} {a}  {b}  e  0  1 b  c d a

一个有界格中，如果每个元素都有补元，则称之为有 补格。 下述有界格中，哪些是有补格？ 2. 有补格的定义： 一个有界格中，如果每个元素都有补元，则称之为有 补格。 下述有界格中，哪些是有补格？  Φ {a,b} {a}  {b}  b  0  1 a  c  e  1 b d (1) (2) (3) (4) 上述有补格中，有些元素的补元不唯一，如(2)中的b, 那么什么样的有补格元素的补元唯一呢？ 就是有界分配格. 请看下面定理：

作业 P248 (2) (5) P252 (1) (3) (6) 定理7－2.6 在有界分配格中，如果元素有补元，则补元 是唯一的。 证明：设<A, ≤>是有界分配格，任取a∈A, 假设a有两个 补元b和c，则 a∧b=0 a∨b=1 a∧c=0 a∨c=1 于是有， a∧b= a∧c a∨b=a∨c 由分配格的定理7－2.3得 b=c ∴a的补元是唯一的。 四. 布尔格 如果一个格既是分配格又是有补格，则称之为布尔格。 布尔格中每个元素都有唯一补元，元素a的补元记作 。 显然<P(E),  >是布尔格。 下面介绍由布尔格诱导的代数系统－－布尔代数。 作业 P248 (2) (5) P252 (1) (3) (6)

7－3 布尔代数 Boolean Algebra 一. 定义 由布尔格<B, ≤>诱导的代数系统<B, ∨, ∧,¯>称之 为布尔代数。其中 ¯ 是“取补元”运算。 如果B是有限集合，则称它是有限布尔代数。 例如：令B＝{F,T}，∧表示合取，∨表示析取， 表示否定, <B,∨,∧,> 就是个布尔代数。 如上图所示。  T  F  Φ {a,b} {a}  {b} <P(E),∪,∩,~> 也是个布尔代数。 如右图所示。

二. 布尔代数的性质 设<B, ∨, ∧,¯>布尔代数, 任意x,y,z∈B, 有 ⑴交换律 x∨y=y∨x x∧y=y∧x ⑵结合律 x∨(y∨z)=(x∨y)∨z x∧(y∧z)=(x∧y)∧z ⑶幂等律 x∨x=x x∧x=x ⑷吸收律 x∨(x∧y)=x x∨(x∧y)=x ⑸分配律 x∨(y∧z)=(x∨y)∧(x∨z) x∧(y∨z)=(x∧y)∨(x∧z) ⑹同一律 x∨0=x x∧1=x ⑺零律 x∨1=1 x∧0=0 ⑻互补律 x∨ =1 x∧ =0 ⑼对合律 ⑽底－摩根定律

上述性质都可以由格，分配格,有界格，布尔格得到。下 面只证明底－摩根定律。 ，类似可证另一个。 所以

三. 布尔代数的同构 1. 定义：令<B1,∨1, ∧1, ¯>和 <B2,∨2, ∧2, ~>是两个布尔 代数，如果存在双射f:B1B2 ,对任何a,b∈B1 , 有 f(a∨1b)=f(a)∨2f(b) f(a∧1b)=f(a)∧2f(b) ~ f(a) f( )= 则称f是<B1,∨1,∧1 , ¯ >到 <B2,∨2,∧2 , ~ >的同构映射。 与格同构比较，多了一个关于补运算的同构关系等式。 为了引出有限布尔代数的元素个数的定理，下面介绍 原子的概念。

定义1: 设<B, ∨, ∧,¯>是布尔代数, 元素a∈B, a≠0, 对 2. 原子 定义1: 设<B, ∨, ∧,¯>是布尔代数, 元素a∈B, a≠0, 对 任何元素x∈B, 有x∧a=a, 或 x∧a=0, 则称a是原子。 定义2:<A,≤>是布尔格,在<A,≤>的哈斯图中称盖住全 下界0的元素为原子。 例如： 1。 e。 0。 d。 f。 b。 c。 a。  0 1 a  b

原子的判定： 定理7-3.1设<B,∨,∧,¯>是布尔代数，a∈B,且a≠0,则a 是原子的充分且必要条件是 对任何y∈B，如果y≤a, 则 y=0或y=a。 证明:必要性.设a 是原子, 且对任何y∈B，有y≤a (证出 y=0或y=a), 由原子定义得 y∧a=a, 或 y∧a=0, 而由y≤a 得 y∧a=y, 所以有y=0或y=a. 充分性. 已知对任何y∈B，如果y≤a, 则y=0或y=a。(证出 a是原子, 即证出对任何x∈B 有x∧a=a, 或 x∧a=0,), 任取x∈B, 令y=x∧a , 因x∧a≤a, 所以y≤a , 由已知条 件得 y=0 或 y=a , 即有 x∧a=a, 或 x∧a=0, 所以a是原子.

定理7-3.2 设a,b是布尔代数<B,∨,∧,¯>中的原子，如果 a≠b, 则a∧b=0, (如果a∧b≠0, 则 a=b) 证明:设a和b是B中原子, (由原子定义得: 对任何x∈B 有 x∧a=a, 或 x∧a=0,) 因为a是原子，而b∈B，所以 b∧a=a∧b=a，或者 b∧a=a∧b=0, 于是: 如果a∧b≠0，必有 a∧b=a 。 类似地， b是原子, 而a∈B, 所以a∧b=b, 或 a∧b=0, 此结论等价于: 如果a∧b≠0,必有 a∧b=b, 最后得 a=b. 所以得出, 如果a∧b≠0, 则 a=b. 或者得出，如果 a≠b, 则a∧b=0 .

定理7-3.3 设a,b1,b2 …bn是 布尔代数<B,∨,∧,¯>中的原 子，则a≤b1∨b2∨…∨bn的充分且必要条件为 对于某个i (1≤i≤n), 有a=bi. 证明:充分性显然成立, 因为对于某个i(1≤i≤n)，有a=bi , 必有 a≤b1∨b2∨…∨bn 必要性, 已知 a≤b1∨b2∨…∨bn ,则 a∧(b1∨b2∨…∨bn)=a (a∧ b1 )∨(a∧ b2)∨…∨ (a∧ bn)=a 如果每个(a∧ bi)=0 (1≤i≤n) 则 (a∧ b1 )∨(a∧ b2)∨…∨ (a∧ bn)=0 于是得a=0, 这与a是原子矛盾。所以至少有某个i (1≤i≤n), 使得 (a∧ bi)≠0 ，因为a和 bi都是原子, 由定理7-7.2 得 a=bi .

定理7-3.4 设b是有限布尔代数<B,∨,∧,¯>中的 非0元素, 则必存在原子a，使得a≤b. 2).如果b不是原子, 则必存在 b1∈B 使得0< b1<b, 如果b1不是原子, 则必存在 b2∈B 使得 0<b2< b1<b, 如此下去, 由于B是有限集合, 上述过程经过有限步后而 最终结束, 最后得到原子bk ,使得 0<bk<… b2< b1<b 令 bk=a, 于是a≤b. 例如，右图中每个非0元素x， 都存在原子a，使得a≤x. 1。 e。 0。 d。 f。 b。 c。 a。

定理7-3.5 有限布尔代数中，b∧ =0，当且仅当 b≤c。 30。 3。 1。 2。 5。 10。 15。 6。 例如 右图中, 2 ∧ =1(全下界0) 2≤6 证明: 充分性.已知 b≤c 又 于是 因为0是全下界, 所以 b∧ =0 必要性. 已知 b∧ =0 (证出b≤c, 即b∨c=c) b∨c=(b∨c)∧1=(b∨c)∧( c∨ )=(b∧ )∨c =0∨c=c 所以b∨c=c, 即b≤c

定理7-3.6 设<B,∨,∧,¯>是有限布尔代数，b非0元素， a1,a2 …ak是B中满足aj≤b的所有原子(j=1,2,…k), 则 b＝a1∨a2 ∨…∨ak且除原子次序不同外， 上述表达式是唯一的。 a1 a2 b  ak ... 0 证明:(1)令a1∨a2∨…∨ak ＝c (证出b=c 即证 b≤c且c≤b) a).证c≤b 显然成立, 因为每个ai≤b, (j=1,2,…k) 所以 a1∨a2∨…∨ak≤b 即 c≤b . b).证b≤c. (由定理7-4.5可知, 只要证出 b∧ =0 即可) 假设b∧ ≠0 , 由定理7-3.4得, 必存在原子a, 使得 a≤ b∧ , 而b∧ ≤b b∧ ≤ 由≤的传递性得 a≤b, a≤ . 因为a是原子, 且a≤b, b≠0, 由题意得a必是 a1,a2 ,…, ak中之一, 由定理7-3.3得a≤a1∨a2∨…∨ak 即 a≤c；又a≤ , 得 a≤c∧ 所以a≤0 与a是原子矛盾. 所以必有b∧ =0 所以 b≤c。 最后得 b=c

即得 b＝a1∨a2 ∨…∨ak …….① (2)证明上式是唯一的.假设还有原子b1,b2 ,…, bm∈B,使得 b＝b1∨b2 ∨…∨bm …….② (下面证{b1,b2,…,bm}={a1,a2,...,ak}) a). 任取bi∈{b1,b2,…,bm} , 由②式得{b1,b2,…,bm}中每个bj 有bj≤b (1≤j≤m) ,所以bi≤b，又 b＝a1∨a2 ∨…∨ak 所以 bi≤ a1∨a2 ∨…∨ak , 由于bi及每个aj (1≤j≤k)都是原子, 由定理7-3.3得, {a1,a2,...,ak }中必存在一个aj ,使得bi =aj 于是bi∈{a1,a2,…,ak} 所以{b1,b2,…,bm} {a1,a2,...,ak} b).类似可以证明 {a1,a2,...,ak} {b1,b2,…,bm} 最后得 {b1,b2,…,bm}={a1,a2,...,ak} 所以上述表达式在不考虑原子次序时, 形式是唯一的.

定理7-3.7 在布尔代数<B,∨,∧,¯>中，对B中任何原子a 和任何非0元素b, a≤b和a≤ 两式中有且仅有一个成立。 证明:假设上述两个式子都成立, 即a≤b和a≤ , 则有 a≤b∧ =0 , 这与 a是原子矛盾. 下面证明两个式中必有一个成立. 因为a∧b≤a , 而a是原子, 所以只能有a∧b=a 或 a∧b=0 如果a∧b=0 , 即 , 由定理7-3.5得, a≤ , 如果a∧b=a , 则 a≤b. 于是这两个式中必有一个成立.

{ 定理7-3.8 (Stone钻石定理)设<B,∨,∧,¯>是有限布尔代数, M是B中所有原子构成的集合，则 <B,∨,∧,¯>与<P(M),∪,∩,~>同构。 证明:构造映射 f: BP(M) 对于x∈B 1 2 3 5 6 10 15 30 Φ {2} {3} {5} {2,3} {2,5} {3,5} {2,3,5} B  P(M) f f(x)= { Φ x=0 {a|a∈M,a≤x} x≠0 先通过下边例子了解映射 f的形式: 30。 3。 1。 2。 5。 10。 15。 6。

1).先证明f是双射. a).证明f是入射: 只有x=0时, 才有 f(0)=Φ. 任取x1, x2∈B, x1≠0 x2≠0且x1≠x2 , 由定理3-7.6得, x1, x2可以写成如下形式: x1= a1∨a2∨…∨ak 其中原子ai≤ x1 (1≤ i≤ k) x2= b1∨b2∨…∨bm 其中原子bj≤ x2 (1≤j≤ m) 因为每个非0元素写成上述表达式的形式是唯一的, 又因 为x1≠x2 , 所以 {a1,a2,...,ak}≠{b1,b2,…,bm}. 由f 定义得 f(x1)={a1,a2,...,ak} f(x2)={b1,b2,…,bm} 故f(x1)≠f(x2) f入射. b). 证明f 满射: 任取M1∈P(M) 如果M1为Φ, 则f(0)= M1 , 如果M1≠Φ, 令M1={a1,a2,...,ak} , 由∨的封闭性得, 必存在 x∈B , 使得a1∨a2∨…∨ak =x, 显然每个ai≤x (1≤i≤k) , 故f(x)= M1, 所以f 是满射的. 最后由a)b)得 f是双射的.

2).证明f满足三个同构关系式. 任取x1, x2∈B, 因为f是双射, 必有M1, M2∈P(M),使得 f(x1)=M1, f(x2)=M2, a). 证明f(x1∧x2 )=f(x1)∩f(x2)=M1∩M2, 令f(x1∧x2 )=M3 , 即证明 M3 = M1∩M2 先证 M3 M1∩M2 如果 M3 =Φ 显然有 M3 M1∩M2 如果M3≠Φ, 任取a∈M3, 即 a∈f(x1∧x2 ) 由f 定义得a≤x1∧x2 ,又因为x1∧x2≤x1, x1∧x2≤x2 , 所以 a≤x1 a≤x2 由f 定义得a∈f(x1) a∈f(x2) 即 a∈M1 a∈M2 , 故 a∈M1∩M2, 所以 M3 M1∩M2

再证 M1∩M2 M3 如果 M1∩M2=Φ 显然有 M1∩M2  M3 如果 M1∩M2≠Φ, 任取a∈M1∩M2 a∈M1 a∈M2 即 a∈f(x1), a∈f(x2)，于是 a是满足a≤x1与a≤x2的原子, 所以 a≤x1∧x2 ，由f 定义得, a∈f(x1∧x2), 即 a∈M3 故 M1∩M2  M3 。 所以 M3 = M1∩M2 即 f(x1 ∧ x2 )=f(x1)∩f(x2)

b).证明 f(x1∨ x2 )=f(x1)∪f(x2)=M1∪M2, 令f(x1∨x2 )=M4 , 即证明 M4 = M1∪M2 先证 M4 M1∪M2 如果 M4 =Φ 显然有 M4 M1∪M2 如果M4≠Φ, 任取a∈M4, a∈f(x1∨x2 ) 由f 定义得a≤x1∨x2 ,则必有 a≤x1, 或者 a≤x2 , (因为如果a≤x1与a≤x2都不成立, 由定理7-3.7得 必有 与a是原子矛盾, 所以有 a≤x1 或 a≤ x2) 由f 定义得 a∈f(x1) 即a∈M1 或a∈f(x2) 即 a∈M2 于是有 a∈M1∪ M2, 所以 M4 M1∪M2

再证 M1∪M2  M4 如果 M1∪M2 =Φ 显然有 M1∪M2  M4 如果 M1∪M2≠Φ, 任取a∈M1∪M2 a∈M1 或者 a∈M2 如果a∈M1 则 a≤x1 a≤x1≤x1∨x2 ∴a∈f(x1∨x2), a∈M4 如果a∈M2 则 a≤x2 a≤x2≤x1∨x2 ∴a∈f(x1∨x2), a∈M4 所以M1∪M2  M4 最后得 M4 = M1∪M2 即 f(x1∨ x2 )=f(x1)∪f(x2)

3).证明 于是有 x1∨x2=1 x1∧x2=0 f(x1∨x2)=M f(x1∧x2)=Φ f(x1∨x2)=f(x1)∪f(x2)= M1∪M2 =M f(x1∧x2)=f(x1)∩f(x2)= M1∩M2 =Φ 所以 M2 =~M1 即 综上所述 由1).2).3)得 f(x1∧x2 )=f(x1)∩f(x2) f(x1∨x2)=f(x1)∪f(x2) 所以 <B,∨,∧,¯>与<P(M),∪,∩,~>同构。

推论1. 任何有限布尔代数的元素个数为2n (n=1,2,3,…) 因为|P(M)|= 2n 其中|M|=n 推论2. 两个有限布尔代数同构的充分且必要条件是元素 个数相同。 1。 e。 0。 d。 f。 b。 c。 a。  0 1 a  b

本节重点掌握布尔代数的性质，同构概念，Stone定理及 其推论。 作业 P260 （2） Φ {c} {b} {d} {a} {a,c,d} {a,b,d} {b,c,d} {a,b,c} {b,c} {a,d} {b,d} {a,c} {a,b,c,d} {c,d}  {a,b} 本节重点掌握布尔代数的性质，同构概念，Stone定理及 其推论。 作业 P260 （2）

7-4.布尔表达式 此内容在开关理论，逻辑设计中有着广泛的应用。 一. 布尔表达式概念 1.定义：设<B,∨,∧,¯>是布尔代数，其上的布尔表达式 递归定义如下： 1)B中任何元素是个布尔表达式。 2)任何变元x是个布尔表达式. E1 ¯ 3)如果E1 ,E2是个布尔表达式, 则 ,(E1∧E2),(E1∨E2)也 是布尔表达式。 4)有限次地应用规则1)--3),得到的符号串都是布尔表达式. b ¯ (x1∨ ) ——— 例如令B={0,1,a,b} (a∨ ), ((x∧y)∨ ), *表达式的最外层括号可以省略.

2.对布尔表达式赋值：设<B,∨,∧,¯>是布尔代数，含有 变元 x1,x2 …xn 的布尔表达式记作E(x1,x2,…xn), 对变元 x1,x2,…,xn分别用B中元素代替的过程，称之为对布尔表 达式赋值。 例如 B={0,1,a,b}  0 1 a  b (x1∨ ) ——— E(x1,x2)= (a∨ ) ——— a∨a ____ a ¯ E(a,b)= = = = b 一个的布尔表达式E(x1,x2,…xn), 经过赋值以后，就得到 一个值(即是B中一个元素)。 3.两个布尔表达式相等:设<B,∨,∧,¯>是布尔代数，含有 变元 x1,x2,…xn 的两个布尔表达式E1(x1,x2,…xn)和E2(x1,x2, …xn),如果不论对变元x1,x2 …xn分别用B中任何元素赋值, 都使得E1和E2的值相同,则称这两个表达式相等,记作 E1(x1,x2,…,xn)=E2(x1,x2,…,xn)

我们可以通过布尔代数的性质(10个)得到很多等式. 如 E1(x,y)=x∨(y∧ ) E2(x,y)= x∨y E1(x,y)=x∨(y∧ )= (x∨y)∧(x∨ )=(x∨y)∧1 = x∨y = E2(x,y) 二. 布尔函数 设<B,∨,∧,¯>是布尔代数，含有变元 x1,x2,…,xn 的布尔 表达式记作E(x1,x2,…xn),也可以看成是一个函数E:BnB, 称之为布尔函数. 布尔函数有两种表示方法: 1. 代数法: 例如 B={0,1} <B,∨,∧,¯>是布尔代数， 即是表达式表示法. 2. 真值表法: 见下面:

的真值表如下: x1 x2 x3 E(x1, x2 , x3) 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 0 1 1 1 1 1

三. 布尔表达式的范式 1. 有两个元素的布尔代数的布尔表达式的范式: <{0,1},∨,∧,¯>是两个元素的布尔代数 1). 析取范式(相当于命题公式的主析取范式) (1).小项: 含有n个变元的小项形式为: 其中 例如 都是小项. (2).布尔表达式的析取范式: 含有变元 x1,x2,…,xn 的布尔表达式E(x1,x2,…xn), 如果写成如下形式: A1∨A2∨...∨Am (m≥1) , 其中每个Ai (1≤i≤m)都是有n个变元的小项. 则称此式是 E(x1,x2,…xn)的析取范式. 例如:

2). 合取范式(相当于命题公式的主合取范式) (1). 大项:含有n个变元的大项形式为: 其中 例如 都是大项. (2).布尔表达式的合取范式: 含有变元 x1,x2,…,xn 的布尔表达式E(x1,x2,…xn),如果写成 如下形式: A1∧A2∧... ∧Am (m≥1) 其中每个Ai (1≤i≤m)都是有n个变元的大项. 则称此式是 E(x1,x2,…xn)的合取范式. 例如: 3). 析取范式与合取范式的写法: 方法1:列真值表 方法2:表达式的等价变换.

方法1. 用真值表求析取范式: 先介绍小项的性质, 以两个变元x1,x2为例 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 每一组赋值有且仅有一个小项为1. 根据一组赋值,求值为1的小项: 如果变元x,被赋值为0,则 在此小项中, x以 形式出现; 如果变元x,被赋值为1,则在 此小项中, x以原形x形式出现. 求E(x1,x2,…xn)的析取范式:先列出它的真值表,找出表中每个1对应的小项,然后用∨连接上述小项.

例如,求布尔代数<{0,1},∨,∧,¯>上的布尔表达式 x3 ¯ E(x1,x2,x3)=x1∧(x2∨ ) 的析取范式. x1 x2 x3 E (x1, x2 , x3) 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 1 1 1 x3 ¯ x2 E(x1,x2,x3)=(x1∧ ∧ )∨(x1∧ x2∧ )∨(x1∧ x2∧x3)

方法1. 用真值表求合取范式: 先介绍大项的性质, 以两个变元x1,x2为例 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 0 每一组赋值有且仅有一个大项为0. 根据一组赋值,求值为0的大项: 如果变元x被赋值为1, 则 在此大项中, x以 形式出现; 如果变元x被赋值为0, 则在 此大项中, x以原形x形式出现. 求E(x1,x2,…xn)的合取范式:先列出它的真值表,找出表中每个0对应的大项,然后用∧连接上述大项.

例如,求布尔代数<{0,1},∨,∧,¯>上的布尔表达式 x1 x2 x3 E (x1, x2 , x3) 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 1 1 1 x3 ¯ E(x1,x2,x3) =x1∧(x2∨ ) 的合取范式. x3 ¯ x2 x1 E(x1,x2,x3)=(x1∨x2∨x3)∧(x1∨x2∨ ) ∧ (x1∨ ∨x3)∧ (x1∨ ∨ ) ∧( ∨ x2∨ )

E(x1,x2,x3)=x1∧(x2∨ ) =(x1∧x2)∨(x1∧ ) 方法2. 用表达式的等价变换求析取范式: x3 ¯ E(x1,x2,x3)=x1∧(x2∨ ) =(x1∧x2)∨(x1∧ ) x2 ¯ x3 =(x1∧x2∧(x3∨ ))∨ (x1∧(x2∨ )∧ ) x2 ¯ x3 =(x1∧x2∧x3)∨(x1∧x2∧ )∨(x1∧x2∧ )∨(x1∧ ∧ ) x3 ¯ x2 =(x1∧x2∧x3)∨(x1∧x2∧ )∨(x1∧ ∧ ) 结果与前相同. 用表达式的等价变换求合取范式: x3 ¯ E(x1,x2,x3)=x1∧(x2∨ ) x3 ¯ x2 x1 =(x1∨(x2∧ )∨(x3∧ ))∧((x1∧ )∨x2∨ ) x3 ¯ x2 =(x1∨x2∨ x3 )∧(x1∨x2∨ )∧(x1∨ ∨x3 )∧(x1∨ ∨ ) x1 ¯ x3 ∧(x1∨x2∨ )∧ ( ∨x2∨ ) x3 ¯ x2 x1 =(x1∨x2∨ x3 )∧(x1∨x2∨ )∧(x1∨ ∨x3 )∧(x1∨ ∨ ) ∧ ( ∨x2∨ )

。 4). 应用：在楼梯处安装一个电灯，在楼下(楼上)有开关 X(Y) ，都可以控制此灯，使得有人上搂(或下搂) 按动开 4). 应用：在楼梯处安装一个电灯，在楼下(楼上)有开关 X(Y) ，都可以控制此灯，使得有人上搂(或下搂) 按动开 关X(Y) 灯就亮，上楼(或下楼) 完毕按动Y(X)开关后灯就 灭。请设计控制此灯的电路。 解：令L为灯，X和Y为开关，这是双 X Y L 1 1 0 1 0 1 0 1 1 0 0 0 X ¯ 位开关，即一端是X端，另一端是 , 假设开始时开关X合到X端，开关Y 合到Y端，此时L是灭的。列出真值表： 开关逻辑∧、∨定义为： X∧Y X∨Y 。 X Y ¯ L X ¯ Y L=(X∧ )∨( ∧Y) 开关的控制过程如下:

X Y  X Y X Y  X Y 

2. 一般的布尔代数的布尔表达式的范式: < B,∨,∧,¯>是布尔代数,含有变元 x1,x2,…,xn 的布尔表 达式E(x1,x2,…xn), 1). 小项: 是由n个变元和B中元素构成的如下形式,称为小 项. 其中 Cδ1δ2...δn为B中元素, 我们称之为小项的系数. 例如 B={0,1,a,b}, 下面就是E(x1,x2,x3)中的小项: 2). 布尔表达式E(x1,x2,...xn)的析取范式: 含有变元 x1,x2,…,xn 的布尔表达式E(x1,x2,…xn),如果写 成如下形式: A1∨A2∨...∨Am (m≥1) 其中每个Ai (1≤i≤m)都是有n个变元的小项. 则称此式是 E(x1,x2,…xn)的析取范式.

定理7-4.1. 设< B,∨,∧,¯>是布尔代数,含有变元 x1,x2,…,xn 的布尔表达式E(x1,x2,…xn), 则可以写成析取范式形式. 证明:令E(xi=a) =E(x1,x2,..,xi-1,a,xi+1,…,xn) 先通过对|E|归纳证明如下结论成立: 类似根据指 派求小项 xi ¯ E(x1,x2,…xn)=( ∧E(xi=0))∨(xi∧E(xi=1)) 这里|E|为E(x1,x2,…xn)的长度, 即其中所含有的B中元素 个数、 运算符号个数、变元个数的总和(含重复计数). 例如 先用下面例子理解上边式子的含义。 并验证结论成立.

(1). 如果|E|=1 则 E=a (a∈B) ,或者 E=xj, (xj是个变量) 如果E=a 则E(xi=0)=E(xi=1)=a E=a=(xixi)a=(xi a)(xi a) 分配律 = (xi E(xi=0))(xi E(xi=1)) 替换 如果E= xj, 若 xj=xi ,显然 E(xi=0)=0，E(xi=1)=1 ， E= xj=xi=(xi0)(xi 1) = (xi E(xi=0))(xi E(xi=1)) 替换 若 xj xi, 则 E(xi=0)=E(xi=1)= xj , E= xj=(xixi)xj=(xixj)(xixj) = (xi E(xi=0))(xi E(xi=1)) 替换 所以|E|=1时, 结论成立.

(2).假设|E|≤n 时, 结论成立. 即 (3).当|E|=n+1时, 分下面三种情况讨论: ① 如果E=E1∨E2 则|E1|≤n, |E2|≤n , 由(2)假设得,

②如果E=E1∧E2 则|E1|≤n, |E2|≤n , 由(2)假设得,

③如果

定理得证. 通过反复应用此定理, 就可以将E(x1,x2,…xn)写析取范 式形式.

E(x1,x2,…xn)=(xi ∨E(xi=0)) ∧ ( ∨ E(xi=1)) 3) 合取范式：类似地，先用归纳法证明： xi ¯ E(x1,x2,…xn)=(xi ∨E(xi=0)) ∧ ( ∨ E(xi=1)) xn ¯ x1 x2 xn-1 进而得到 E(x1,x2,…xn)的合取范式为: E(x1,x2,…xn) =(x1∨x2∨...∨xn∨E(0,0,…,0))∧ (x1∨x2∨...∨xn-1∨ ∨E(0,0,…0,1))∧... ∧ ( ∨ ∨...∨ ∨xn∨E(1,1,…,1,0))∧ ( ∨ ∨...∨ ∨E(1,1,…,1)) 其中 E(0,0…,0), E(0,0,…0,1) ,…, E(1,1,…1,0) 和 E(1,1,…,1) 就是所谓的“系数”. 实际上, 求E(x1,x2,…xn)的析取或者合取范式时, 就是求 这些“系数”. 下面看一个例子.

例.已知<B, ∨,∧ ,¯>是布尔代数, 其中B={0,a,b,1} 分别求出下面布尔表达式的析取范式和合取范式.  0 1 a  b 解. 先求四个系数: 析取范式为:

合取范式为: 本节重点掌握内容： 布尔表达式定义、析取范式和合取范式的写法。 作业：P269 (1)

本章内容小结： 1. 格的概念、格的性质. 格的同构. 2. 分配格的性质、判断. 有界格 有补格 布尔格概念性质. 2. 分配格的性质、判断. 有界格 有补格 布尔格概念性质. 3. 布尔代数的性质, Stone定理的应用. 4. 布尔表达式定义,范式的写法.

下面上第七章的习题课

习题课 P242 (1). 下面图哪些是格？ 1 d a b e f g i 5 2 l m o (a) (b)  c e f g  h i  j  k 5 2  4  6 l m  n o  q  r  p  3  8  7 (a) (b) (c) (d) (a)不是格 因为d和e没有下确界,也没有上确界. (d)不是格5和6没有下确界,7和8既没下确界,也没上确界. 进一步问,如果是格,哪些是分配格?哪些是有补格? (b)不是分配格,因去掉结点i后的子格如图所示  j  k  f g  h 但它是有补格. (c)不是分配格(去m,p),不是有补格.

(2). 设≤是L上的整除关系,下面偏序集中,哪些是格? a) L={1,2,3,4,6,12}, b) L={1,2,3,4,6,8,12,14} c) L={1,2,3,4,5,6,7,8,9,10,11,12} 解. 画出Hasse图如下:  12 4  6 2  3  1 8 5  1  7 14   2  11 10   9 12 1 (a) (b) (c) 可见只有(a)是格.

(4).设<A, ≤>是一个格,任取a,b∈A,a<b (即a≤b∧a≠b), 构造集合: B={x| x∈A且a≤x≤b}, 则<B, ≤>也是格. 证明:显然B是A的非空子集, (因为a≤a≤b,a≤b≤b,所以a,b∈B), 只要证明∧和∨在B上封闭即可. 任取x,y∈B, 由B的构成得a≤x≤b,a≤y≤b, 于是由格 的性质得,a≤x∨y≤b a≤x∧y≤b, 于是有 x∨y∈B , x∧y∈B , 说明∨和∧在B上封闭 . 所以<B, ≤>也是格.

(7).设a,b是格<A, ≤>中的两个元素,证明: a). a∧b=b 当且仅当a∨b=a. b). a∧b<b和a∧b<a,当且仅当 a与b是不可比较的. 证明:a)充分性: 已知a∨b=a b=b∧(b∨a)= b∧(a∨b) =b∧a=a∧b 必要性:已知a∧b=b , a=a∨(a∧b)=a∨b b)充分性:已知a与b是不可比较的. 因a∧b≤b, a∧b≤a, 如果a∧b=b, 则有b≤a, 如果a∧b=a, 则有a≤b, 都与a与b是不可比较的矛盾. 所以有: a∧b≤b∧ a∧b≠b,于是有 a∧b<b a∧b≤a∧ a∧b≠a,于是有 a∧b<a 必要性:已知a∧b<b和a∧b<a, 假设a与b是可比较的.则要 么a≤b,要么b≤a. 于是要么a∧b=a 要么a∧b=b. 这与 a∧b<b和a∧b<a矛盾.所以a与b是不可比较的.

(9).证明格中成立: a) (a∧b)∨(c∧d)≤(a∨c)∧(b∨d) b) (a∧b)∨(b∧c)∨(c∧a)≤(a∨b)∧(b∨c)∧(c∨a) 证明:a)∵ (a∧b)≤a≤(a∨c) ∴ (a∧b)≤(a∨c) ∵ (c∧d)≤c≤(a∨c) ∴ (c∧d)≤(a∨c) ∴ (a∧b)∨(c∧d)≤(a∨c) 同理 (a∧b)≤(b∨d) (c∧d)≤(b∨d) ∴ (a∧b)∨(c∧d)≤(b∨d) ∴(a∧b)∨(c∧d)≤(a∨c)∧(b∨d) b) ∵ (a∧b)≤(a∨b), (a∧b)≤(b∨c) ,(a∧b)≤(c∨a) ∴ (a∧b)≤(a∨b)∧(b∨c)∧(c∨a) 同理有 (b∧c)≤(a∨b)∧(b∨c)∧(c∨a) (c∧a)≤(a∨b)∧(b∨c)∧(c∨a) 最后得 (a∧b)∨(b∧c)∨(c∧a)≤(a∨b)∧(b∨c)∧(c∨a).

P248(2).下面哪个是分配格? (c) (b) (a) d a b  f (c) 解:判定一个格是否分配格,看它是否含有  g  a d  c e b (c)  1  2 3  4  5 (b) (a) d  c a b  f  e  f  g  a d  c e b (c) 解:判定一个格是否分配格,看它是否含有 五元素的非分配格形式的子格. (a)图好像可以去掉b或c后 得到如下图: d  c a f  e b  d  c a f 但它们不是(a)的子格. 因d∨e=b b∧c=e b,e不在子集里. ∴(a)是分配格.  3  1 2  4  5 d  c a f  e (b)也是分配格. (c)不是分配格.

(5).设<A,≤>是分配格,a,b∈A, 且a<b, 证明 f(x)=(x∨a)∧b 是一个从A到B的同态映射. 其中 B={x|x∈A且a≤x≤b} 证明:先证 f 是从A到B的映射:任取x∈A, 由f的定义得 f(x)=(x∨a)∧b) 显然 (x∨a)∧b≤b 而 (x∨a)∧b=(x∧b)∨(a∧b)=(x∧b)∨a (因a<b a∧b=a) ∴ a≤(x∨a)∧b≤b 即a≤f(x)≤b ∴f(x)∈B . ∴ dom f=A. 又由于∨和∧的定义知(x∧b)∨a是唯一的. 即f(x)是唯一的. 所以f 是从A到B的映射. 再证f 满足同态等式:任取x1,x2∈A, f(x1∧x2)=((x1∧x2)∨a)∧b=((x1∨a)∧(x2∨a))∧b =((x1∨a)∧b)∧((x2∨a)∧b) =f(x1)∧f(x2) f(x1∨x2)=((x1∨x2)∨a)∧b=((x1∨a)∨(x2∨a))∧b =((x1∨a)∧b)∨((x2∨a)∧b) =f(x1)∨f(x2) ∴f 是同态映射.

证明:设<A,≤>是格,且|A|≥2, 假设有a∈A,使得 =a ∴a≠0, a≠1, 但是有 P252(1). 给出有界格如图 a)哪些元素有补元? b)该格是分配格吗? c)该格是有补格吗? 解:a) a、c、d、f、g 无补元 ; b和e互为补元 ; 0和1互为补元. b) 不是分配格, 因为它含有子格如下图. 1 c a  b  d  f  g e   e  d a   f c) 它不是有补格,因为很多元素无补元. (3).证明具有两个或更多个元素的格中 不存 在以自身为补元的元素. a ¯ 证明:设<A,≤>是格,且|A|≥2, 假设有a∈A,使得 =a ∴a≠0, a≠1, 但是有 1=a∨ =a∨a=a 0=a∧ =a∧a=a 产生矛盾. 所以不存在以自身为补元的元素.

(4). 在有界分配格中,证明具有补元的那些元素组成一个 子格. x ¯ b a 证明: 设<A,≤>是有界分配格,令B={x| ∈A} 任取a,b∈B, , ∈B, ∨ ∈A, ∧ ∈A 下面证明∨和∧在B上封闭,即a∨b和a∧b都有补元: 所以<B,≤>是<A,≤>的子格.

(6).设<A,≤>是有界格, 对于任何x,y∈A, 证明 a). x∨y=0 , 则 x=y=0 b). x∧y=1, 则 x=y=1 证明: a) x=x∧(x∨y)=x∧0=0 y=y∧(y∨x)=y∧0=0 b) x=x∨(x∧y)=x∨1=1 y=y∨(y∧x)=y∨1=1 P260(2).设<S,∨,∧,¯>是布尔代数，x,y∈S, 证明: x≤y 当且仅当 证明: 充分性 已知 必要性: 已知 x≤y

P269(1).设 是<{0,1},∨,∧, ¯ > 上的一个布尔表达 式.分别写出它的析 取范式与合取范式. 方法1.用真值表 x1 x2 x3 E (x1, x2 , x3) 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 1 1

方法2. 用等价变换的方法. 这是析取范式. 求它的合取范式可能要麻烦一些. 下面求合取范式:

可见与用真值表求的结果相同.

格与布尔代数 到此结束