离散数学_7格与布尔代数(2)

三. 格的性质<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} Φ

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教学研究离散数学_7格与布尔代数(2)全文阅读和word下载服务。