1
代数系统第六章 格和布尔代数
§ 1格的概念
§ 2分配格
§ 3有补格
§ 4*布尔代数
2
§ 1格的概念
1.偏序集合格
,定义,格是一个偏序集合,其中每一对元素都拥有一个最小上界和最大下界。通常用表示 a和 b的最大下界，用 表示 a和 b的最小上界。即：
—— 称为元素 a和 b的保交运算，
—— 称为元素 a和 b的保联运算。
,L
Lba?,
ba? ba?
babaG L B},{
babaL U B},{
3
§ 1格的概念例：以下均为偏序集合格（ D为整除关系,Sn为 n的因子集合）。
4
§ 1格的概念
2.代数系统格
,定义,,设 是一个格，如果在 A上定义两个二元运算?和?，使得对于任意的 a,b?A,a?b等于 a和 b的最小上界,a?b等于 a和 b的最大下界，那么就称 <L,?,?> 为由格 所诱导的代数系统。
,L
,L
5
§ 1格的概念
3.格的主要性质：
(1)格的对偶原理设 <L,≤>是格，,≤”的逆关系,≥”与 L组成的偏序集
<L,≥>也是格。两者互为对偶。前者的 GLB,LUB恰好是后者的 LUB,GLB。如有关于 <L,≤>的有效命题，
将,≤”换成,≥”，,?”换成,?”,,?”换成
,?”，便能得到 <L,≥>的有效命题。反之亦然。
6
§ 1格的概念
(2)对格 <L,≤>中任意 a和 b，有 a≤a?b及 a?b≤a。
(3) <L,≤>是格。对任意 a,b,c,d?L，如 a≤b,c≤d，则
a?c≤ b?d,a?c≤b?d
7
8
§ 1格的概念
(4)（交换律）交和并运算是可交换的。
(5)（结合律）交和并运算是可结合的。
9
§ 1格的概念
(6)（幂等律）对 L中每一个 a，有 a?a=a,a?a=a。
(7)（吸收律）对 L中任意 a,b，
有 a?(a?b)=a a?(a?b)=a。
10
§ 2分配格对格所定义的代数系统 <L,?,?>，其运算?和?不一定满足分配律。
,定义,设 <L,?,?>是由 <L,≤>所诱导的代数系统。如果对任意的 a,b,c?L，满足：
a?(b? c)=(a? b)?(a? c)
及 a? (b? c)=(a? b)? (a? c)
则称 <L,≤>是分配格。
11
§ 2分配格讨论定义：
(1)定义中的两式互为对偶式。
(2)如 <L,≤>非为分配格，则有下面的分配不等式：
a? (b? c) ≤ (a? b)? (a? c)
a? (b? c) ≥ (a? b)? (a? c)
以及模不等式：
a≤c?a? (b? c) ≤ (a? b)? c
12
§ 2分配格
,定义,如对 L中任意 a,b,c有：
a≤c?a? (b? c) ＝ (a? b)? c
则称 <L,≤>为模格。
例：
13
§ 2分配格
,定理,如果格中交对并是分配的，那么并对交也是分配的，反之亦然。
证明：已知 a? (b? c) ＝ (a? b)? (a? c)
(a? b)? (a? c)=((a? b)? a)? ((a? b)? c)
=a? ((a? b)? c)
=a?((a? c)? (b? c))
=(a? (a? c))? (b? c)
=a? (b? c)
即：并对交也是分配的。
14
§ 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
∴ 分配格是模格
15
§ 2分配格
,定理,每个链均是分配格。
证明：设 <L,≤>是链。对任意 a,b,c?L
(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，
(a? b)? (a? c)＝ b? c
即,a? (b? c) ＝ (a? b)? (a? c)。得证。
16
§ 3有补格
,定义,设 <L,≤>是一个格，如果存在元素 a?L，对于任意的 x?L，都有：
a≤x
则称 a为格 <L,≤>的全下界，记格的全下界为 0。
例：
17
§ 3有补格
,定理,如果格 <L,≤>有全上界（全下界），那么它是唯一的。
证明：（反证法）设有两个全上界 a和 b，则由定义
a≤b，且 b≤a，由,≤”的反对称性,a＝ b。
,定义,设 <L,≤>是一个格，格中存在全上界和全下界，
则称该格为有界格。
18
§ 3有补格
,定理,如果 <L,≤>是有界格，全上界和全下界分别是 1
和 0，则对任意元素 a?L，有：
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)?L且 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。仿此可得另两式。
19
§ 3有补格
,定义,设 <L,≤>是一个有界格，对于 L中的一个元素 a，
如果存在 b?L，使得 a?b=1和 a?b= 0，则称元素 b是元素 a的补元。
讨论定义：
（ 1） ∵?和?是可交换的,∴ 补元是相互的。
（ 2）,即在有界格中,1和 0互为补元；
（ 3）由定义可知 L中一个元素的补元不一定是唯一的；
例：
101110,001010
20
东南大学远程教育离 散 数 学第 五十三讲主讲教师：仲新宇
21
§ 3有补格
,定义,在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。
讨论定义：
（ 1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；
（ 2）有补格一定是有界格，而有界格不一定是有补格。
请看下例：
22
§ 3有补格
,定义,在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。
讨论定义：
（ 1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；
（ 2）有补格一定是有界格，而有界格不一定是有补格。
请看下例：
23
§ 3有补格
,定理,在有界分配格中，若有一个元素有补元，则必是唯一的。
证明：
24
§ 4 布尔代数
,定义,一个有补分配格称为布尔格。
,定义,一个格 <L,≤>如果它既是有补格，又是分配格，
则它为有补分配格。我们把有补分配格中任一元素 a
的唯一补元记为 a。
讨论定义：
(1)布尔格中，每个元素有唯一的补元。
(2)我们可以定义 L上的一个一元运算，称为补运算，记为,-”。
-
25
§ 4 布尔代数
,定义,由布尔格 <L,≤>，可以诱导一个包括交，并和补运算的代数系统 <L,?,?,->，称此代数系统为布尔代数。
例：设 S是一个非空有限集,<?(S),?>是一个格，且是一个布尔格。由 <?(S),?>所诱导的代数系统为
<?(S),?,?,-> 是一个布尔代数。其中,?,?,-”分别是集合的交、并、补运算。
26
§ 4 布尔代数
,定理,对于布尔代数中任意两个元素 a,b，必定有
aa?
)(
baba
baba
27
§ 4 布尔代数证明：
28
§ 4 布尔代数
,定理,设 <A,?,?,->是由有限布尔格 <A,≤>所诱导的一个有限布尔代数,S是布尔格 <A,≤>中的所有原子的集合，则 <A,?,?,->和 <?(S),?,?,~>同构。
讨论定 理,
(1)当 布尔代数 <A,?,?,->的载体 A的基数 |A|是有限数时,
则称之为有限布尔代数。
(2)设 <A,?,?,->是一个布尔代数,a∈ A,如果 a盖住 0，则称元素 a是该布尔代数的一个 原子 。
例如：
29
东南大学远程教育离 散 数 学第 五十四讲主讲教师：仲新宇
30
§ 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}
31
§ 4 布尔代数
(3)A中除 0外的每个元素，都可以唯一地表示成原子的并。
该定理可得以下两个推论：
a)<B,*,?,’,0,1>与 <p(S),∪,∩,~,?,S>同构，
|p(S)|=2|s|所以,|B|=2|s|,故 任一有限布尔代数载体的基数是 2的幂。
b)任一有限布尔代数和它的原子集合 S构成的幂集集合代数 <p(S),∪,∩,~,?,S>同构，但后者又与任一基数相同的幂集集合代数同构，故 具有相同载体基数的有限布尔代数都同构。
32
§ 4 布尔代数格有界格 有补格布尔代数分配格结合律 吸收律交换律 幂等律同一律零一律 互补律分配律德 ·摩根律双重否定律
33
§ 4 布尔代数例：
设 A是一非空集合,?(A)是 A的幂集,可以验证,<?(A),∪,∩,~,?,A>是个布尔代数,称此为集合代数,其中运算为 ∪,∩,~,最小元?,最大元 A。
S是命题公式的全体,则 <S,∨,∧,?,0,1>是一个布尔代数,称之为命题代数。其中运算为 ∨,∧,?,最小元是恒假公式 0,最大元是恒真公式 1。
34
§ 4 布尔代数因此，
从逻辑观点看，布尔代数是命题演算系统。
从集合论观点看，布尔代数是集合代数。
从抽象代数的观点看，布尔代数是一个代数系统。
35
第三篇小结通过本篇的学习应该达到以下基本要求：
(1)给定集合与运算的解析表达式，写出该运算的运算表。
(2)给定集合和运算，判别该集合对运算是否封闭。
(3)给定二元运算，说明运算是否满足交换律、结合律、
幂等律、分配律和吸收律。
(4)给定集合 S上的二元运算，求出该运算的幺元、零元、
幂等元和所有可逆元素的逆元。
(5)给定集合 S和二元运算 *，能判定 <S,*>是否构成半群、
独异点和群。
36
第三篇小结
(6)给定半群 S和子集 B，判定 B是否为 S的子半群；给定独异点 V和子集 B，判定 B是否为 V的子独异点，给定群 G和子集 H，判定 H是否为 G的子群。
(7)求循环群的所有生成元。
(8)给定代数系统 V1=<S1,o>,V2=<S2,*>，其中,o”
和” *“为二元运算，判定?,S1? S2是否为 V1到 V2
的同态映射。如果是，说明?是否为单同态、满同态和同构，并求出同态象?(V1)。
(9)判别格、分配格、有界格、有补格和布尔格。求有界格的全上界,全下界和给定元素的补元。
37
例题选讲例 1.
设,S＝ {a,b}，则 S上可以定义多少个二元运算？其中有
4个运算如下表所示，则有哪些满足交换律，哪些满足幂等律，哪些有幺元，哪些有零元？
1 a b
a a a
b a a
2 a b
a a b
b b a
3 a b
a b a
b a a
4 a b
a a b
b a b
38
例题选讲例 2.
对以下定义的集合和运算判别它们能否构成代数系统？
如能，请说明是构成哪一种代数系统？
(1),＋为普通加法；
(2),*为普通乘法；
(3),≤ 为小于等于关系；
},.,,,2,1,0{1 nS
}2,0,21{2?S
}3,2,1,0{3?S
39
例题选讲
代数系统第六章 格和布尔代数
§ 1格的概念
§ 2分配格
§ 3有补格
§ 4*布尔代数
2
§ 1格的概念
1.偏序集合格
,定义,格是一个偏序集合,其中每一对元素都拥有一个最小上界和最大下界。通常用表示 a和 b的最大下界，用 表示 a和 b的最小上界。即：
—— 称为元素 a和 b的保交运算，
—— 称为元素 a和 b的保联运算。
,L
Lba?,
ba? ba?
babaG L B},{
babaL U B},{
3
§ 1格的概念例：以下均为偏序集合格（ D为整除关系,Sn为 n的因子集合）。
4
§ 1格的概念
2.代数系统格
,定义,,设 是一个格，如果在 A上定义两个二元运算?和?，使得对于任意的 a,b?A,a?b等于 a和 b的最小上界,a?b等于 a和 b的最大下界，那么就称 <L,?,?> 为由格 所诱导的代数系统。
,L
,L
5
§ 1格的概念
3.格的主要性质：
(1)格的对偶原理设 <L,≤>是格，,≤”的逆关系,≥”与 L组成的偏序集
<L,≥>也是格。两者互为对偶。前者的 GLB,LUB恰好是后者的 LUB,GLB。如有关于 <L,≤>的有效命题，
将,≤”换成,≥”，,?”换成,?”,,?”换成
,?”，便能得到 <L,≥>的有效命题。反之亦然。
6
§ 1格的概念
(2)对格 <L,≤>中任意 a和 b，有 a≤a?b及 a?b≤a。
(3) <L,≤>是格。对任意 a,b,c,d?L，如 a≤b,c≤d，则
a?c≤ b?d,a?c≤b?d
7
8
§ 1格的概念
(4)（交换律）交和并运算是可交换的。
(5)（结合律）交和并运算是可结合的。
9
§ 1格的概念
(6)（幂等律）对 L中每一个 a，有 a?a=a,a?a=a。
(7)（吸收律）对 L中任意 a,b，
有 a?(a?b)=a a?(a?b)=a。
10
§ 2分配格对格所定义的代数系统 <L,?,?>，其运算?和?不一定满足分配律。
,定义,设 <L,?,?>是由 <L,≤>所诱导的代数系统。如果对任意的 a,b,c?L，满足：
a?(b? c)=(a? b)?(a? c)
及 a? (b? c)=(a? b)? (a? c)
则称 <L,≤>是分配格。
11
§ 2分配格讨论定义：
(1)定义中的两式互为对偶式。
(2)如 <L,≤>非为分配格，则有下面的分配不等式：
a? (b? c) ≤ (a? b)? (a? c)
a? (b? c) ≥ (a? b)? (a? c)
以及模不等式：
a≤c?a? (b? c) ≤ (a? b)? c
12
§ 2分配格
,定义,如对 L中任意 a,b,c有：
a≤c?a? (b? c) ＝ (a? b)? c
则称 <L,≤>为模格。
例：
13
§ 2分配格
,定理,如果格中交对并是分配的，那么并对交也是分配的，反之亦然。
证明：已知 a? (b? c) ＝ (a? b)? (a? c)
(a? b)? (a? c)=((a? b)? a)? ((a? b)? c)
=a? ((a? b)? c)
=a?((a? c)? (b? c))
=(a? (a? c))? (b? c)
=a? (b? c)
即：并对交也是分配的。
14
§ 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
∴ 分配格是模格
15
§ 2分配格
,定理,每个链均是分配格。
证明：设 <L,≤>是链。对任意 a,b,c?L
(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，
(a? b)? (a? c)＝ b? c
即,a? (b? c) ＝ (a? b)? (a? c)。得证。
16
§ 3有补格
,定义,设 <L,≤>是一个格，如果存在元素 a?L，对于任意的 x?L，都有：
a≤x
则称 a为格 <L,≤>的全下界，记格的全下界为 0。
例：
17
§ 3有补格
,定理,如果格 <L,≤>有全上界（全下界），那么它是唯一的。
证明：（反证法）设有两个全上界 a和 b，则由定义
a≤b，且 b≤a，由,≤”的反对称性,a＝ b。
,定义,设 <L,≤>是一个格，格中存在全上界和全下界，
则称该格为有界格。
18
§ 3有补格
,定理,如果 <L,≤>是有界格，全上界和全下界分别是 1
和 0，则对任意元素 a?L，有：
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)?L且 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。仿此可得另两式。
19
§ 3有补格
,定义,设 <L,≤>是一个有界格，对于 L中的一个元素 a，
如果存在 b?L，使得 a?b=1和 a?b= 0，则称元素 b是元素 a的补元。
讨论定义：
（ 1） ∵?和?是可交换的,∴ 补元是相互的。
（ 2）,即在有界格中,1和 0互为补元；
（ 3）由定义可知 L中一个元素的补元不一定是唯一的；
例：
101110,001010
20
东南大学远程教育离 散 数 学第 五十三讲主讲教师：仲新宇
21
§ 3有补格
,定义,在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。
讨论定义：
（ 1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；
（ 2）有补格一定是有界格，而有界格不一定是有补格。
请看下例：
22
§ 3有补格
,定义,在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。
讨论定义：
（ 1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；
（ 2）有补格一定是有界格，而有界格不一定是有补格。
请看下例：
23
§ 3有补格
,定理,在有界分配格中，若有一个元素有补元，则必是唯一的。
证明：
24
§ 4 布尔代数
,定义,一个有补分配格称为布尔格。
,定义,一个格 <L,≤>如果它既是有补格，又是分配格，
则它为有补分配格。我们把有补分配格中任一元素 a
的唯一补元记为 a。
讨论定义：
(1)布尔格中，每个元素有唯一的补元。
(2)我们可以定义 L上的一个一元运算，称为补运算，记为,-”。
-
25
§ 4 布尔代数
,定义,由布尔格 <L,≤>，可以诱导一个包括交，并和补运算的代数系统 <L,?,?,->，称此代数系统为布尔代数。
例：设 S是一个非空有限集,<?(S),?>是一个格，且是一个布尔格。由 <?(S),?>所诱导的代数系统为
<?(S),?,?,-> 是一个布尔代数。其中,?,?,-”分别是集合的交、并、补运算。
26
§ 4 布尔代数
,定理,对于布尔代数中任意两个元素 a,b，必定有
aa?
)(
baba
baba
27
§ 4 布尔代数证明：
28
§ 4 布尔代数
,定理,设 <A,?,?,->是由有限布尔格 <A,≤>所诱导的一个有限布尔代数,S是布尔格 <A,≤>中的所有原子的集合，则 <A,?,?,->和 <?(S),?,?,~>同构。
讨论定 理,
(1)当 布尔代数 <A,?,?,->的载体 A的基数 |A|是有限数时,
则称之为有限布尔代数。
(2)设 <A,?,?,->是一个布尔代数,a∈ A,如果 a盖住 0，则称元素 a是该布尔代数的一个 原子 。
例如：
29
东南大学远程教育离 散 数 学第 五十四讲主讲教师：仲新宇
30
§ 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}
31
§ 4 布尔代数
(3)A中除 0外的每个元素，都可以唯一地表示成原子的并。
该定理可得以下两个推论：
a)<B,*,?,’,0,1>与 <p(S),∪,∩,~,?,S>同构，
|p(S)|=2|s|所以,|B|=2|s|,故 任一有限布尔代数载体的基数是 2的幂。
b)任一有限布尔代数和它的原子集合 S构成的幂集集合代数 <p(S),∪,∩,~,?,S>同构，但后者又与任一基数相同的幂集集合代数同构，故 具有相同载体基数的有限布尔代数都同构。
32
§ 4 布尔代数格有界格 有补格布尔代数分配格结合律 吸收律交换律 幂等律同一律零一律 互补律分配律德 ·摩根律双重否定律
33
§ 4 布尔代数例：
设 A是一非空集合,?(A)是 A的幂集,可以验证,<?(A),∪,∩,~,?,A>是个布尔代数,称此为集合代数,其中运算为 ∪,∩,~,最小元?,最大元 A。
S是命题公式的全体,则 <S,∨,∧,?,0,1>是一个布尔代数,称之为命题代数。其中运算为 ∨,∧,?,最小元是恒假公式 0,最大元是恒真公式 1。
34
§ 4 布尔代数因此，
从逻辑观点看，布尔代数是命题演算系统。
从集合论观点看，布尔代数是集合代数。
从抽象代数的观点看，布尔代数是一个代数系统。
35
第三篇小结通过本篇的学习应该达到以下基本要求：
(1)给定集合与运算的解析表达式，写出该运算的运算表。
(2)给定集合和运算，判别该集合对运算是否封闭。
(3)给定二元运算，说明运算是否满足交换律、结合律、
幂等律、分配律和吸收律。
(4)给定集合 S上的二元运算，求出该运算的幺元、零元、
幂等元和所有可逆元素的逆元。
(5)给定集合 S和二元运算 *，能判定 <S,*>是否构成半群、
独异点和群。
36
第三篇小结
(6)给定半群 S和子集 B，判定 B是否为 S的子半群；给定独异点 V和子集 B，判定 B是否为 V的子独异点，给定群 G和子集 H，判定 H是否为 G的子群。
(7)求循环群的所有生成元。
(8)给定代数系统 V1=<S1,o>,V2=<S2,*>，其中,o”
和” *“为二元运算，判定?,S1? S2是否为 V1到 V2
的同态映射。如果是，说明?是否为单同态、满同态和同构，并求出同态象?(V1)。
(9)判别格、分配格、有界格、有补格和布尔格。求有界格的全上界,全下界和给定元素的补元。
37
例题选讲例 1.
设,S＝ {a,b}，则 S上可以定义多少个二元运算？其中有
4个运算如下表所示，则有哪些满足交换律，哪些满足幂等律，哪些有幺元，哪些有零元？
1 a b
a a a
b a a
2 a b
a a b
b b a
3 a b
a b a
b a a
4 a b
a a b
b a b
38
例题选讲例 2.
对以下定义的集合和运算判别它们能否构成代数系统？
如能，请说明是构成哪一种代数系统？
(1),＋为普通加法；
(2),*为普通乘法；
(3),≤ 为小于等于关系；
},.,,,2,1,0{1 nS
}2,0,21{2?S
}3,2,1,0{3?S
39
例题选讲
