离散数学专业课件,适合数学专业和计算机专业的同学学习

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

离散数学专业课件,适合数学专业和计算机专业的同学学习

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

离散数学专业课件,适合数学专业和计算机专业的同学学习

7-1 格 (Lattice)一 . 基本概念1. 格的定义 <A,≤>是偏序集，如果任何 ∈A,使得 是偏序集， 使得{a,b}都有最大 是偏序集 如果任何a,b∈ 使得 都有最大 下界和最小上界，则称<A,≤>是格。 下界和最小上界，则称 是格。 是格 2

4。 36。 30。 2 右图的三个偏 12。 序集， 序集， 6。 1 5。 1 10。 <A,≤>不是格， 不是格， 不是格 6。 4 3。 因为{24,36} 2。 5。 因为 2。 3。 3 最小上界。 无最小上界。 1。 1。 <B,≤><C,≤> <C,≤> <A,≤> <B,≤> 是格。 是格。

。 。 。 。

离散数学专业课件,适合数学专业和计算机专业的同学学习

a b d e c 2 4

1 3 5 6 b d

a c 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}的最大下界为 ，最小上界为 x 。 的最大下界为y, 如果 ， 的最大下界为 即这{x,y}的最大下界为较小元素，最小上界为较大元素 的最大下界为较小元素， 即这 的最大下界为较小元素 最小上界为较大元素.

离散数学专业课件,适合数学专业和计算机专业的同学学习

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 例如右边的格中a∧ 例如右边的格中 ∧b=b a∨b=a b∧c=e ∨ ∧ 4. 子格：设<A,≤>是格 <A,∨,∧>是 子格： 是格, ∨∧ 是 是格 b c d 诱导的代数系统。 是 的 由<A,≤>诱导的代数系统。B是A的 诱导的代数系统 e a a 非空子集，如果∧ 非空子集，如果∧ a b c b c 上封闭， 和∨在B上封闭，则 上封闭 d b c e f e f 称<B, ≤>是<A, ≤> 是 d g g 的子格。 的子格。 <B,≤> <C,≤> <C,≤>是<A,≤>的子格。 <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 都满足幂等律 幂等律。 ∨ ∧ 证明：由性质1 再证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

离散数学专业课件,适合数学专业和计算机专业的同学学习

8. ∨和∧不满足分配律。但有分配不等式： 满足分配律 但有分配不等式 分配律。 不等式： a a∨(b∧c)≤ (a∨b)∧(a∨c) , ∨ ∧ ∨ ∧ ∨ b (a∧b)∨(a∧c)≤ a∧(b∨c) 。 ∧ ∨ ∧ ∧ ∨ 我们先看右图的例子 先看右图的例子： 我们先看右图的例子： c 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∨c)≥ (a∧b)∨(a∧c) 。 ∧ ∨ ∧ ∨ ∧ 即 (a∧b)∨(a∧c)≤ a∧(b∨c) 。 ∧ ∨ ∧ ∧ ∨

e d

离散数学专业课件,适合数学专业和计算机专业的同学学习

*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 ∨ 这是个很重要的定理，我们在以后经常用到此论。 这是个很重要的定理，我们在以后经常用到此论。

离散数学专业课件,适合数学专业和计算机专业的同学学习

四.格的同态与同构1.定义：设<A1,≤1> 和<A2, ≤2>是两个格，由它们诱导 定义： 是两个格， 定义 是两个格 的代数系统分别是<A ∨ ∧ 和 的代数系统分别是 1,∨1,∧1>和 <A2,∨2,∧2>,如果存 ∨ ∧ , 在映射f:A 使得对任何a,b∈ 在映射 1→A2 使得对任何 ∈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>, ∨ ∧ 到 ∨ ∧ , 的格同构，也称格<A 同构。 的格同构，也称格 1,≤1> 和<A2, ≤2>同构。 同构

离散数学专业课件,适合数学专业和计算机专业的同学学习

例如<A,≤>, A={1,2,3,6}, ≤是A上整除关系。 上整除关系。 例如 是 上整除关系 <P(E), >, E={a,b} 它们诱导的代数系统分别是<A,∨,∧>和<P(E),∪,∩> 它们诱导的代数系统分别是 ∨∧ 和 ∪ 其中∨ 分别是求两个数的 是求两个数的最小公倍数和最大公约数. 其中∨和∧分别是求两个数的 和 数 f A→ P(E) {a,b} 6 6 {a,b} 2 1 3 {a} Φ {b} 3 2 1 {b} {a} Φ

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. 格同态的保序性 定理： 是格 是格<A 同态映射 映射， 定理：设f是格 1,≤1> 到<A2, ≤2> 的同态映射，则对任 如果a≤ 何a,b∈A1,如果 1b, 则 f(a)≤2f(b). ∈ 如果 证明： 是格<A 证明：令<A1,∨1,∧1>和 <A2,∨2,∧2>是格 1,≤1> 和 ∨ ∧ 和 ∨ ∧ 是格 <A2, ≤2>诱导的代数系统，任取 ∈A1,设a≤1b, 则 诱导的代数系统， 诱导的代数系统 任取a,b∈ 设 a∧1b=a f(a∧1b)=f(a) 即 f(a)∧2f(b)=f(a) ∧ ∧ ∧ 所以 f(a)≤2f(b). 3. 格同构的保序性 定理： 是格 是格<A 同构映射 映射， 定理：设f是格 1,≤1> 到<A2, ≤2> 的同构映射，当且仅 对任何a,b∈ 当 对任何 ∈A1, 若 a≤1b f (a)≤2f(b). 证明： 是格<A 证明：令<A1,∨1,∧1>和 <A2,∨2,∧2>是格 1,≤1> 和 ∨ ∧ 和 ∨ ∧ 是格 <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:A 是双射，必有d∈ 又由 1→A2是双射，必有 ∈A1, 使得 f(a)∧2f(b)=f(d) ∧ 所以 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(a)∧2f(b)=f(c) ∧ 即 f(a∧1b)=f(a)∧2f(b) 。

∧ ∧ b)类似可证 f(a∨1b)=f(a)∨2f(b) 所以 f是它们的同构映射 类似可证 ∨ ∨ 是它们的同构映射

离散数学专业课件,适合数学专业和计算机专业的同学学习

2).必要性：已知 f是格 1,≤1> 到<A2, ≤2> 的同构映射， 必要性： 是格<A 同构映射 映射， 必要性 是格 证出：任取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)再证 (a)≤2f(b) a≤1b 再证f 再证 设 f (a)≤2f(b), ∴ f(a)=f(a)∧2f(b)=f(a∧1b) , ∧ ∧ 是双射， ∵f 是双射，∴ a=a∧1b 所以 a≤1b ∧ 最后得 若a≤1b f (a)≤2f(b) 。 定理证毕。 定理证毕。 由格的同构得： 由格的同构得： 具有一、 三个素的格分别同构于含有一、 具有一、二、三个素的格分别同构于含有一、二、三 a 个元素的链。 个元素的链。 a b a b c

离散数学专业课件,适合数学专业和计算机专业的同学学习

具有四个素的格分别同构于下面两种格形式之一： 具有四个素的格分别同构于下面两种格形式之一： a a b b c c d d 具有五个素的格分别同构于下面五种格形式之一： 具有五个素的格分别同构于下面五种格形式之一： a b c d e a a b c e d b e a cb d c d e c e a b d

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

离散数学专业课件,适合数学专业和计算机专业的同学学习

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 (吸收律 吸收律) 吸收律