离散数学格和布尔代数-武汉大学.pdf

离散数学 第六章 格和布尔代数 黄 正华 Email: huangzh@whu.edu.cn 武汉大学 数学与统计学院 November 10, 2010 黄正华 (武汉大学) 离散数学 第六章 格和布尔代数 November 10, 2010 1 / 99 目录 1 格的概念 2 分配格 3 有补格 4 布尔代数 5 布尔表达式 黄正华 (武汉大学) 离散数学 第六章 格和布尔代数 November 10, 2010 2 / 99 1 格的概念 2 分配格 3 有补格 4 布尔代数 5 布尔表达式 黄正华 (武汉大学) 离散数学 第六章 格和布尔代数 November 10, 2010 3 / 99 格与布尔代数 格是另一类代数系统. 格的理论形成于 1935 年前后, 是代数学的一个分支. 本章主要介绍 格的基本知识, 特殊的格: 分配格, 有补格; 布尔代数. 黄正华 (武汉大学) 离散数学 第六章 格和布尔代数 November 10, 2010 3 / 99 格的定义 Definition 1.1 (偏序) 如果集合 上的关系 具有 1 自反性, 2 反对称性, 3 传递性. 则称之为偏序. ⟨, ⟩ 称为偏序集. 黄正华 (武汉大学) 离散数学 第六章 格和布尔代数 November 10, 2010 4 / 99 Example 1.2 设 = {1, 2, 3, 4, 6, 12}, = {2, 3, 6, 12, 24, 36}. 集合 和 上的 整除关系 “ | ” 就构成两个偏序集: ⟨, | ⟩, ⟨, | ⟩. 它们的哈斯 图如下: 12 24 36 4 6 12 2 3 6 1 2 3 (a) ⟨, | ⟩ (b) ⟨, | ⟩ 黄正华 (武汉大学) 离散数学 第六章 格和布尔代数 November 10, 2010 5 / 99 Example 1.2 设 = {1, 2, 3, 4, 6, 12}, = {2, 3, 6, 12, 24, 36}. 集合 和 上的 整除关系 “ | ” 就构成两个偏序集: ⟨, | ⟩, ⟨, | ⟩. 它们的哈斯 图如下: 12 24 36 4 6 12 2 3 6 1 2 3 (a) ⟨, | ⟩ (b) ⟨, | ⟩ 虽然都是偏序集, 但是它们有一个重要的差别: ⟨, | ⟩ 中“每两个元素构成的集合”都有最大下界和最小上界. 但