湘潭大学离散数学1课件-第十九章格与布尔代数.pdfVIP

第十九章 格与布尔代数 2022-4-1 离散数学 1 目录 n 本章介绍另外一类具有两种二元运算的代数系 统——格，以及特殊的格——布尔代数： n 格是描述集合或命题的代数系统，称为集合代 数或命题代数 n §19.1 格的定义 n §19.2 格的性质 n §19 3 几种特殊的格 n §19.4 布尔代数 n §19.5 有限布尔代数的结构 2022-4-1 离散数学 2 §19.1 格的定义 2022-4-1 离散数学 3 格的定义 n 定义19.1.1：设 L, ≤  是一个偏序集。如 果对任意a ，b ∈L ，{a ，b }在L 中都有最 大下界和最小上界，则称 L, ≤ 是一个格。 n 常将{a ，b }的最大下界记为inf {a, b }，最 小上界记为sup {a, b }。 2022-4-1 离散数学 4 复习定义2.4.5和定义2.4.6 n 上(下)界：设A, 是一个偏序集,BA,若存在 a ∈A ,使得对任何x ∈B都有x a(或a x) , 则称 a为B 的上(下)界。 （如果存在，上(下)界可在A 中，也可在B 中） n 上(下)确界：设A, 是一个偏序集，BA ， 若a是B 的一个上(下)界，且对B 的任何一个上 (下)界x ，均有a x (或x a) , 则称a为B 的上(下) 确界，也可称为最小上界 （或最大下界）。记 为a sup(B) (a inf(B) ) 。 2022-4-1 离散数学 5 几个是格的偏序集 (a) (b) (c) n 图(a) 中是一个全序集(链) ，自然是一个格。 n 不难验证，图(b)和图(c) 中的偏序集中任意两个 元素都有最小上界和最大下界，因而都是格。 2022-4-1 离散数学 6 并非所有偏序集都是格 (d) (e) (f) n 不是所有的偏序集都是格。 n 图(d), (e), (f)所表示的偏序集都不是格。不难 找出它们之中存在着两个元素，或没有最小上 界，或没有最大下界。 2022-4-1 离散数学 7 子集格 n 例1：设S是集合，ρ(S)是S的幂集。 于是  ρ(S),  是一个格，称为S的子集格。 因为： n 首先， ρ(S),  是一个偏序集； n 其次，对任意的A, B ∈ρ(S) ，有 sup {A, B} A ∪B ； inf {A, B} A ∩B 。 2022-4-1 离散数学