第七格与布尔代数.pptVIP

* § 4 布尔代数 《定义》一个格A,≤如果它既是有补格，又是分配格，则它为有补分配格。我们把有补分配格中任一元素a的唯一补元记为a。 《定义》一个有补分配格称为布尔格。 讨论定义： (1)布尔格中，每个元素有唯一的补元。 (2)我们可以定义A上的一个一元运算，称为补运算，记为“-”。 - * § 4 布尔代数 《定义》由布尔格A,≤，可以诱导一个 包括交，并和补运算的代数系统A,?,?,-，称此代数系统为布尔代数。 例：设S是一个非空有限集，?(S),?是一个格，且是一个布尔格。由?(S),?所诱导的代数系统为 ?(S), ?,?,- 是一个布尔代数。其中“?,?,-”分别是集合的交、并、补运算。 * § 4 布尔代数 例： 设A是一非空集合,?(A)是A的幂集,可以验证, ?(A),∪,∩,~,?,A是个布尔代数,称此为集合代数,其中运算为∪, ∩, ~,全下界?,全上界A。 * § 4 布尔代数 《定理》对于布尔代数中任意两个元素a,b，必定有 * 定义：当布尔代数A,?,?,-的载体A的基数|A|是有限数时,则称之为有限布尔代数。 定义：设A,?,?,-是一个布尔代数，a∈A,如果a盖住0，则称元素a是该布尔代数的一个原子。 § 4 布尔代数 布尔代数A,?,?,-中除0外的每个元素，都可以唯一地表示成原子的并。 例如： * § 4 布尔代数 例：?(S),?,?,~,?,S，其中S={a,b,c}， 在这个布尔代数中的元素分三种情况： （ⅰ）界：全上界S，全下界? ； （ⅱ）{a},{b},{c}单个元素集合的元素； （ⅲ）二，三个元素作为集合的元素，但它们均可用单个元素的集合的元素来表述： {a,b}={a}?{b} ,{a,c}={a}?{c}, {b,c}={b}?{c}, {a,b,c}={a}?{b}?{c} 。 {a,c} {a,b,c} {a,b} {b,c} {a} {c} {b} ? * 本章将介绍其他的代数系统——格和布尔代数，格论是数学的一个分支，不仅在近代解析集合有重要的作用，而且在计算机领域也有一定的用途；布尔代数形成比较早，在19世纪，就已经有了相当的发展，布尔代数是研究和逻辑、集合等运算有关的知识。 * 定义 设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(下确界) 复习偏序关系中的上界，下界，上确界与下确界 * 例：偏序集(｛2,3,5,7,14,15,21｝,/)，“/”为整除关系。 其hasze图如下：｛2,7｝的最小上界、最大下界各为什么？｛2,3｝呢？｛5,14｝呢？ ｛2,7｝的最小上界为14。最大下界无。 ｛2,3｝的最小上界无，最大下界无。 ｛5,14｝的最小上界无，最大下界无。 §1 格的概念 * 然而也存在这样一类偏序集，它的每一对元素都有最小上界和最大下界，如：偏序集(｛1,2,3,4,6,8,12,24｝,/)：其Hasze图如下： * 一、格 1．定义：设A, ≤是一个偏序集，若对A中的任两个元素a、b，都有最小上界和最大下界，则称 A, ≤为格。 其中上确界 lub {a,b}，记为a∨b,称为a和b的并。 下确界 glb {a,b}，记为a∧b,称为a和b的交。 将∨、∧，看作集合上的两个二元运算，故格A, ≤所诱导的代数系统记作A，∨，∧ 。 * 一、格 下述偏序集能构成格的是（ ？） (a) (b) (c) (d) b b c d e f a c d f a b c d e f g h a b c d e f √ a c * 一、格 2、对偶格：若A, ≤是一个偏序集，则A, ≥也是一个偏序集，其中“≥”是“≤”的逆关系。 若A, ≤是一个格，则A, ≥也是一个格，称这两个格互为对偶。 若将关于格A, ≤的命题中符号≤，≥，∨、∧，分别用≥，≤，∧、∨，代替，则得到一个新的命题，称这个新命题为原命题的对偶命题。 定理：对于格中的一个真命题，其对偶命题亦真。 * 二、格的性质 定理1：若A， ≤ 是一个格，则对任意a、b 、c?A，有 （1）a≤a∨b， b≤a∨b （2）a∧b≤a ，a∧b≤b （3）若a≤c且b≤c，则a∨b≤c