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

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. 所有链均为分配格。 所有链均为分配格 分配格。 证明： 证明：显然任何链都不会含有与五元素非分配格之一同 构的子格，所以链必是分配格。 构的子格，所以链必是分配格。

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