离散数学_7格与布尔代数

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

第七章 格与布尔代数布尔代数是计算机逻辑设计的基础，它是由格引出的， 布尔代数是计算机逻辑设计的基础，它是由格引出的， 格又是从偏序集引出的。所以我们先回顾一下偏序集 回顾一下偏序集。 格又是从偏序集引出的。所以我们先回顾一下偏序集。 <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 的最大下界 的最小上界

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