中北大学离散数学第六章格和布尔代数分析

证明：（反证法）设有两个全上界a和b，则由定义 a≤b，且b≤a，由“≤”的反对称性， a＝b。
[定义]设<L,≤>是一个格，格中存在全上界和全下 界，则称该格为有界格。
16
§6.3 有补格
[定理]如果<L,≤>是有界格，全上界和全下界分别 是1和0，则对任意元素aL，有： a1=1a=1 ，a1=1a=a， a0=0a=a ，a0=0a=0。
证明：因为1≤a1， 又因(a1)L且1是全上界，∴a1≤1， ∴ a1=1。由交换律：1a＝a1=1。 因为a≤a，a≤1，∴a a≤a1，即：a≤a1， 又a1≤a， ∴ a1=a。仿此可得另两式。
17
§6.3 有补格
[定义]设<L,≤>是一个有界格，对于L中的一个元素 a，如果存在bL，使得ab=1和ab=0，则称元素 b是元素a的补元。
6
§6.1格的概念
(2)对格<L,≤>中任意a和b，有a≤ab及ab≤a。 (3)<L,≤>是格。对任意a,b,c,dL，如a≤b，
c≤d，则ac≤ bdபைடு நூலகம் ac≤bd
(4)（交换律）交和并运算是可交换的。 (5)（结合律）交和并运算是可结合的。
7
§6.1 格的概念
(6)（幂等律）对L中每一个a，有aa=a，aa=a。
2
§6.1 格的概念
1.偏序集合格
L,
[定义]格是一个偏序集合
，其中每一对元素
a,b L都拥有一个最小上界和最大下界。通常用
a b表示a和b的最大下界，用 a b 表示a和b的最 小上界。即：
GLB{a,b} a b ——称为元素a和b的保交运算，
LUB{a,b} a b——称为元素a和b的保联运算。
3
§6.1 格的概念
例：以下均为偏序集合格（D为整除关系，Sn为n的因 子集合）。
4
§6.1 格的概念
2.代数系统格 [定义]设 L, 是一个格，如果在A上定
义两个二元运算和，使得对于任意的a，bA， ab等于a和b的最小上界，ab等于a和b的最大 下界，那么就称<L, ,L,> 为由格 所诱导的代数系统。
13
§6.2 分配格
[定理]每个链均是分配格。 证明：设<L,≤>是链。对任意a，b，cL (1)若a≤b或a≤c，则 a (b c) ＝ a，
(a b) (a c)＝a 即： a (b c) ＝ (a b) (a c) (2)若a≥b且a≥c，则 a (b c) ＝ b c，
第六章 格和布尔代数
§6.1 格的概念 §6.2 分配格 §6.3 有补格 §6.4* 布尔代数
1
第六章 格和布尔代数
教学目的及要求： 深刻理解和掌握格与布尔代数的基本概念和基本 运算。 教学内容： 格的概念、分配格、有补格、布尔代数、布尔表 达式。 教学重点：格、布尔代数、布尔表达式。 教学难点：布尔代数、布尔表达式。
9
§6.2 分配格
讨论定义： (1)定义中的两式互为对偶式。 (2)如<L,≤>非为分6配. 格，则有下面的分配不等式：
a (b c) ≤ (a b) (a c) a (b c) ≥ (a b) (a c) 以及模不等式： a≤ca (b c) ≤ (a b) c
10
§6.2 分配格
(7)（吸收律）对L中任意a，b，有
a(ab)=a
a(ab)=a。
8
§6.2 分配格
对格所定义的代数系统<L,,>，其运算和不一 定满足分配律。
[定义]设<L,,>是由<L,≤>所诱导的代数系统。 如果对任意的a,b,cL，满足： a (b c)=(a b) (a c) 及 a (b c)=(a b) (a c) 则称<L,≤>是分配格。
讨论定义： （1）∵ 和是可交换的，∴补元是相互的。 （2）0 1 0 1 0 0,0 1 1 1 0 1,在有界格 中，1和0互为补元； （3）由定义可知L中一个元素的补元不一定唯一；
例：
18
§6.3 有补格
[定义]在一个有界格中，如果每个元素都至少有一 个补元素，则称此格为有补格。
讨论定义： （1）在有补格中，每一个元素一定存在补元（不一
定是一个补元）； （2）有补格一定是有界格，而有界格不一定是有补
格。请看下例：
19
§6.3 有补格
[定义]在一个有界格中，如果每个元素都至少有一 个补元素，则称此格为有补格。
讨论定义： （1）在有补格中，每一个元素一定存在补元（不一
定是一个补元）； （2）有补格一定是有界格，而有界格不一定是有补
[定义]如对L中任意a，b，c有： a≤ca (b c) ＝ (a b) c
则称<L,≤>为模格。 例：
11
§6.2 分配格
[定理]如果格中交对并是分配的，那么并对交也是 分配的，反之亦然。
证明：已知a(bc)＝(ab)(ac) (ab)(ac)=((ab)a)((ab)c) =a((ab)c) =a((ac)(bc)) =(a(ac))(bc) =a(bc)
(a b) (a c)＝ b c 即：a (b c) ＝ (a b) (a c)。得证。
14
§6.3 有补格
[定义]设<L,≤>是一个格，如果存在元素aL，对 于任意的x L，都有： a≤x 则称a为格<L,≤>的全下界，记格的全下界为0。
例：
15
§6.3 有补格
[定理]如果格<L,≤>有全上界（全下界），那么它 是唯一的。
5
§6.1 格的概念
3.格的主要性质： (1)格的对偶原理 设<L,≤>是格，“≤”的逆关系“≥”与L组成的偏
序集 <L, ≥>也是格。两者互为对偶。前者的GLB，LUB 恰好是后者的LUB，GLB。如有关于<L,≤>的有效 命题，将“≤”换成“≥”，“”换成“”， “”换成 “”，便能得到<L, ≥>的有效命题。 反之亦然。
即：并对交也是分配的。
12
§6.2 分配格
[定理]分配格是模格。 证明：由于a (b c) ＝ (a b) (a c) (1)若a≤c，则a c=c，代入上式得
a (b c) ＝ (a b) c (2)若a (b c) ＝ (a b) c，则
a≤ a (b c) ＝ (a b) c≤c，即： a≤c ∴分配格是模格