离散数学第六章格与布尔代数.ppt

§6.3有补格《定理》如果格A,≤有全上界（全下界），那么它是唯一的。证明：（反证法）设有两个全上界a和b，则由定义 a≤b，且b≤a，由“≤”的反对称性，a＝b。《定义》设A,≤是一个格，如果格中存在全上界和全下界，则称该格为有界格。*第29页，共47页，星期日，2025年，2月5日§6.3有补格《定理》如果A,≤是有界格，全上界和全下界分别是1和0，则对任意元素a?A，有： a?1=1?a=1，a?1=1?a=a， a?0=0?a=a，a?0=0?a=0。证明：因为1≤a?1， 又因(a?1)?A且1是全上界，∴a?1≤1， ∴a?1=1。由交换律：1?a＝a?1=1。 因为a≤a，a≤1，∴a?a≤a?1，即：a≤a?1，又a?1≤a，∴a?1=a。仿此可得另两式。*第30页，共47页，星期日，2025年，2月5日§6.3有补格《定义》设A,≤是一个有界格，对于A中的一个元素a，如果存在b?A，使得a?b=1和a?b=0，则称元素b是元素a的补元。讨论定义：（1）∵?和?是可交换的，∴补元是相互的。（2），即在有界格中，1和0互为补元；（3）由定义可知A中一个元素的补元不一定是唯一的；可能存在多个补元，也可能不存在补元。*第31页，共47页，星期日，2025年，2月5日§6.3有补格《定义》在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。讨论定义：（1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。*第32页，共47页，星期日，2025年，2月5日如图所示的格，是有补格吗？该格是有界格，却不是有补格。§6.3有补格*第33页，共47页，星期日，2025年，2月5日*第1页，共47页，星期日，2025年，2月5日§6.1 格的概念本章将介绍其他的代数系统——格和布尔代数，格论是数学的一个分支，不仅在近代解析集合有重要的作用，而且在计算机领域也有一定的用途；布尔代数形成比较早，在19世纪，就已经有了相当的发展，布尔代数是研究和逻辑、集合等运算有关的知识。*第2页，共47页，星期日，2025年，2月5日定义设A,?为偏序集,B?A,y?A.(1)若?x(x?B→x?y)成立,则称y为B的上界;(2)若?x(x?B→y?x)成立,则称y为B的下界;(3)令C={y|y为B的上界},若C有最小元素，则称该最小元素为B的最小上界或上确界,记为LUB(上确界)(4)令D={y|y为B的下界},若D有最大元素，则称该最大元素为为B的最大下界或下确界,记为GLB(下确界)复习偏序关系中的上界，下界，上确界与下确界*第3页，共47页，星期日，2025年，2月5日§6.1 格的概念例：偏序集(｛2,3,5,7,14,15,21｝,/)，“/”为整除关系。其hasze图如下：｛2,7｝的最小上界、最大下界各为什么？｛2,3｝呢？｛5,14｝呢？｛2,7｝的最小上界为14。最大下界无。｛2,3｝的最小上界无，最大下界无。｛5,14｝的最小上界无，最大下界无。*第4页，共47页，星期日，2025年，2月5日然而也存在这样一类偏序集，它的每一对元素都有最小上界和最大下界，如：偏序集(｛1,2,3,4,6,8,12,24｝,/)：其Hasze图如下：§6.1 格的概念*第5页，共47页，星期日，2025年，2月5日一、格1．定义：设A,≤是一个偏序集，若对A中的任两个元素a、b，都有最小上界和最大下界，则称 A,≤为格。其中上确界lub{a,b}，记为a∨b,称为a和b的并。下确界glb{a,b}，记为a∧b,称为a和b的交。将∨、∧，看作集合上的两个二元运算，故格A,≤所诱导的代数系统记作A，∨，∧。*第6页，共47页，星期日，2025年，2月5日一、格下述偏序集能构成格的是（？）(a)(b)(c)(d)bbcdefacdfabcdefghabcdef√ac*第7页，共47页，星期日，2025年，2月5日一、格2、对偶格：若A,≤是一个偏序集，则A,≥也是一个偏序集，其中“≥”是“≤”