高等学校计算机专业教材：《离散数学》课程PPT课件_第七章 格与布尔代数

第七章格与布尔代数 在红数学電蓝的钟产 泛深入的应 德江数投烈柔数传铃备的 澆删减外,貸他蓉应很好地掌撵 体 返回首页 2021/1/21

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

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

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

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

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

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

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

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

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

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

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