哈尔滨理工大学科解程 离影数
离格与分配格 散 数 学 哈尔滨理工大学本科生课程 计算机系
第六章格与布尔代数 这一章将介绍另一类代数系统,这就是格。 格论大体上是在1935年左右形成的,它不仅是 代数学的一个分支,而且在近代解析几何,半 序空间等方面也都有重要的作用。我们在这里 只介绍格的一些基本知识以及几个具有特别性 质的格—分配格、有补格
第六章 格与布尔代数 这一章将介绍另一类代数系统,这就是格。 格论大体上是在1935年左右形成的,它不仅是 代数学的一个分支,而且在近代解析几何,半 序空间等方面也都有重要的作用。我们在这里 只介绍格的一些基本知识以及几个具有特别性 质的格——分配格、有补格
学习《格与布尔代数》 这一章的要求 学习目的与要求 本章在已经学过的群、环和域几个代数系统的 基础上,进一步学习格这个新的代数系统,并 且学习在计算机科学中有重要应用的布尔代数。 通过本章的学习,使学生进一步了解格的基本 概念,掌握布尔代数的运算规律,为学习数字 逻辑、计算机硬件设计等课程打下数学基础
学习《格与布尔代数》 这一章的要求 一、学习目的与要求 本章在已经学过的群、环和域几个代数系统的 基础上,进一步学习格这个新的代数系统,并 且学习在计算机科学中有重要应用的布尔代数。 通过本章的学习,使学生进一步了解格的基本 概念,掌握布尔代数的运算规律,为学习数字 逻辑、计算机硬件设计等课程打下数学基础
二、知识点 1.格的概念,偏序集上的并运算、 偏序集上的交运算。 2.分配格、有补格; 3.布尔代数、 Stone表示定理及其推 论,布尔表达式、布尔函数、开关代数的 概念
二、知识点 1.格的概念,偏序集上的并运算、 偏序集上的交运算。 2.分配格、有补格; 3.布尔代数、Stone表示定理及其推 论,布尔表达式、布尔函数、开关代数的 概念
、要求 1.识记 根据哈斯图识别是否是格,分配格、有补格, 模格,布尔格、布尔代数。 2.领会 格同构的概念,分配格与模格的关系,格的 全上界的唯一性证明, Stone表示定理、布尔表达 式、析取范式和合取范式。 3.简单应用 开关代数
三、要求 1.识记 根据哈斯图识别是否是格,分配格、有补格, 模格,布尔格、布尔代数。 2.领会 格同构的概念,分配格与模格的关系,格的 全上界的唯一性证明,Stone表示定理、布尔表达 式、析取范式和合取范式。 3.简单应用 开关代数
复习 1偏序集 定义3-121:设A是一个集合,如果A上的一个关系R满足 自反性、反对称性和传递性,则称R是A上的一个偏序关 系,记作≤。称作偏序集。 2.最大元、最小元 定义3-12.6:设是一个偏序集,且B是A的子集, 若有某个元素b∈B,对于B中的每一个元素x,有x≤b,则 称b为的最大元;同理,若有某个元素b∈B,对于B 中的每一个元素x,有b≤X,则称b为的最小元
复习 1.偏序集 定义3-12.1:设A是一个集合,如果A上的一个关系R满足 自反性、反对称性和传递性,则称R是A上的一个偏序关 系,记作≤ 。称作偏序集。 2. 最大元、最小元 定义3-12.6:设是一个偏序集,且B是A的子集, 若有某个元素bB,对于B中的每一个元素x,有x≤b,则 称b为的最大元;同理,若有某个元素bB,对于B 中的每一个元素x,有b≤x,则称b为的最小元
3哈斯图 定义3-122:在偏序集|X、y∈A,y盖住x}。 对于给定偏序集,它的盖住关系是唯一的, 所以可用盖住的性质画出偏序集合图,或称哈斯图,其作 图规则为 (1)小圆圈代表元素。 (2)如果xy且xy,将代表y的小圆圈画在代表x的小圆圈 之上。 (3如果∈cOvA,则在x与y之间用直线连结
3.哈斯图 定义3-12.2:在偏序集中,如果x、y∈A,x≤y, x≠y,且没有其他元素z,使x≤z,z≤y,则称元素y盖住元 素x。记COVA={|x、y∈A,y盖住x}。 对于给定偏序集,它的盖住关系是唯一的, 所以可用盖住的性质画出偏序集合图,或称哈斯图,其作 图规则为: (1)小圆圈代表元素。 (2)如果x≤y且x≠y,将代表y的小圆圈画在代表x的小圆圈 之上。 (3)如果∈COVA,则在x与y之间用直线连结
4.上界、下界 定义3-127:设是一偏序集且BcA,a是B的任一上 界,若对B的所有上界y均有asy,则称a是B的最小上界(上 确界),记作LUBB。同理,b是B的任一下界,若对B的所有 下界z均有zsb,则称b是B的最大下界(下确界),记作GLBB
4. 上界、下界 定义3-12.7:设是一偏序集,对于BA,如有a∈A, 且对任意元素x∈B,都有x≤a,则称a为B的上界。同理,对 任意元素x∈B,都有a≤x,则称a为B的下界。 5. 上确界、下确界 定义3-12.8:设是一偏序集且BA,a是B的任一上 界,若对B的所有上界y均有a≤y,则称a是B的最小上界(上 确界),记作LUBB。同理,b是B的任一下界,若对B的所有 下界z均有z≤b,则称b是B的最大下界(下确界),记作GLBB
6-1格的概念 在第三章中,我们介绍了偏序集的概念,偏序集就是由 个集合A以及A上的一个偏序关系“≤”所组成的一个代数 系统。我们知道,对于偏序集来说,它的任一个子 集不是必定存在最小上界或最大下界的。 例如,在由图6-1.1所示的偏序集中,{,b}的最小上 界是c,但没有最大下界;{e,升的最大下界是d,但没有最 小上界。 图6-1,1
6-1 格的概念 在第三章中,我们介绍了偏序集的概念,偏序集就是由 一个集合A以及A上的一个偏序关系“≤”所组成的一个代数 系统。我们知道,对于偏序集来说,它的任一个子 集不是必定存在最小上界或最大下界的。 例如,在由图6-1.1所示的偏序集中,{a,b}的最小上 界是c,但没有最大下界;{e,f}的最大下界是d,但没有最 小上界
今后,我们把{a,b}的最小上界(最大下界) 称为元素a,b的最小上界(最大下界)。 图6-1.2 由图6-12所示的偏序集都有这样一个共同的特 性,那就是在这些偏序集中,任何两个元素都 有最小上界和最大下界。我们把具有这种性质 的偏序集称作格
今后,我们把{a,b}的最小上界(最大下界) 称为元素a,b的最小上界(最大下界)。 由图6-1.2所示的偏序集都有这样一个共同的特 性,那就是在这些偏序集中,任何两个元素都 有最小上界和最大下界。我们把具有这种性质 的偏序集称作格