人民邮电出版社：《离散数学》第七章 格与布尔代数（刘贵龙）

第七章格与布尔代数 在红澄要数电聲的長件春产 泛深入的应角 边兽机科学买作者备的 除:以单理的明能计体稽 删减外 应很好地掌 返回首页 2021/1/21

2021/1/21 1 第七章 格与布尔代数 布尔代数是计算机科学最重要的基础理论之 一,它在开关网络及数字电路的设计上有广 泛深入的应用. 布尔代数是计算机科学工作者必备的基础知 识，应掌握格与布尔代数的一般理论和方法， 除§3 Stone定理的证明细节可根据具体情 况删减外，其他内容应很好地掌握. 返回首页

第一节格的概念(1) ●格有两种等价的定义:一种是从偏序集的 角度给出格的定义,这种定义可以借助 哈斯( Hasse)图来表示,因而比较直 观,易于理解,这样定义的格称为偏序 格;另一种是从代数系统的角度来给出 格的定义,这种定义方法我们在上一章 的群、环的定义中已有所体会,用代数 系统的方法定义的格称为代数格. 返回本章首页 2021/121

2021/1/21 2 第一节 格的概念(1) ⚫ 格有两种等价的定义:一种是从偏序集的 角度给出格的定义，这种定义可以借助 哈斯（Hasse）图来表示，因而比较直 观，易于理解，这样定义的格称为偏序 格；另一种是从代数系统的角度来给出 格的定义，这种定义方法我们在上一章 的群、环的定义中已有所体会，用代数 系统的方法定义的格称为代数格. 返回本章首页

第一节格的概念(2) ●主要概念有:偏序格、代数格、对偶、子 格、格的同态、格的同构等. 主要结论有: 1偏序格与代数格相互等价,是一回事因 而统称为格; 2格中的对偶原理成立; 返回本章首页少 3 2021/121

2021/1/21 3 第一节 格的概念(2) ⚫ 主要概念有:偏序格、代数格、对偶、子 格、格的同态、格的同构等. ⚫ 主要结论有: 1.偏序格与代数格相互等价,是一回事,因 而统称为格; 2.格中的对偶原理成立; 返回本章首页

第二节有余格与分配格 本节讨论两类特殊的格即有余格和分配格, 这两类格有较好的代数性质,也是比较接 近布尔代数的两类格 主要概念有有界格、余元素(或补元素) 有余格、分配格等. ●主要结论有: 1格的基本性质(见教材定理721) 2序集构成的格是分配格; 3在有界分配格中,若某个元素有补元则补 元惟 返回本章首页 2021/121

2021/1/21 4 第二节 有余格与分配格 ⚫ 本节讨论两类特殊的格,即有余格和分配格， 这两类格有较好的代数性质，也是比较接 近布尔代数的两类格. ⚫ 主要概念有:有界格、余元素(或补元素) 、 有余格、分配格等. ⚫ 主要结论有: 1.格的基本性质(见教材定理7.2.1); 2.序集构成的格是分配格; 3.在有界分配格中,若某个元素有补元,则补 元惟一. 返回本章首页

第三节布尔代数 有余的分配格称为布尔代数布尔代数有 好的代数性庋,有相当广泛应用,应很好 地掌握它 布尔代数可用相互独立的亨廷顿公理给出 即一个代数系统(0①是布尔代数 当且仅当交换律、分配律、同一律及互剂 律成立; 有限布尔代数同构于某个集合上的幂集构 成的布尔代数; 两个有限布尔代数同构当且仅当它们所 的元素个数相同 5 返回本章首页 2021/121

2021/1/21 5 第三节 布尔代数 ⚫ 有余的分配格称为布尔代数,布尔代数有 良好的代数性质, 有相当广泛应用,应很好 地掌握它. ⚫ 布尔代数可用相互独立的亨廷顿公理给出, 即一个代数系统 (L, ∧,∨,-,0,1)是布尔代数 当且仅当交换律、分配律、同一律及互补 律成立; ⚫ 有限布尔代数同构于某个集合上的幂集构 成的布尔代数； ⚫ 两个有限布尔代数同构当且仅当它们所含 的元素个数相同. 返回本章首页

本章小结 ●本章我们介绍了代数格、偏序格,并证 明了这两种格的等价性,此外我们还介 绍了对偶原理、分配格、有补格、布尔 代数等概念布尔代数是数字逻辑的基础、 在学习数字逻辑时会更深刻地体会到布 尔代数在计算机中的应用 6 返回本章首页 2021/121

2021/1/21 6 本章小结 ⚫ 本章我们介绍了代数格、偏序格，并证 明了这两种格的等价性，此外我们还介 绍了对偶原理、分配格、有补格、布尔 代数等概念.布尔代数是数字逻辑的基础、 在学习数字逻辑时会更深刻地体会到布 尔代数在计算机中的应用. 返回本章首页