离散数学(第二版)第7章格和布尔代数和
- 格式：ppt
- 大小：3.95 MB
- 文档页数：18
下载文档原格式
合集下载
离散数学中的布尔函数和布尔代数
离散数学是一门研究离散结构和离散对象的数学学科，它在计算机科学等领域扮演着重要的角色。
布尔函数和布尔代数是离散数学中的重要概念之一，它们在逻辑电路设计、计算机编程等方面具有广泛的应用。
布尔函数是一种将布尔域上的值映射为布尔域上的值的函数。
布尔域上的值只有两个：真和假。
布尔函数的输入和输出都是布尔值。
布尔函数可以通过真值表、函数表达式或者逻辑电路图表示。
常见的布尔运算有与运算、或运算、非运算等。
布尔函数可以定义在不同的布尔变量上，而布尔变量可以取真或假两个值。
通过组合不同的布尔运算，可以构造出复杂的布尔函数。
布尔代数是研究布尔函数性质和运算规则的代数系统。
布尔代数的基本操作有与运算、或运算、非运算等。
与运算、或运算和非运算是布尔函数的基本运算，在布尔代数中具有特殊的性质。
例如，与运算满足交换律、结合律和分配律；或运算满足交换律、结合律和分配律；非运算满足德摩根定律。
布尔代数还有很多其他的运算规则，如吸收律、零元律、幂等律等。
这些运算规则可以用来简化布尔函数，使其更加简洁明了。
布尔函数和布尔代数在逻辑电路设计中起着重要的作用。
逻辑电路是一种基础的电子电路，用来完成逻辑运算。
布尔函数可以用来描述逻辑电路的功能，布尔代数可以用来简化逻辑电路。
通过布尔函数和布尔代数可以设计出各种复杂的逻辑电路，如逻辑门、多路选择器、时序电路等。
逻辑电路在计算机硬件中广泛应用，是计算机工作的基础。
因此，研究布尔函数和布尔代数不仅有助于理解离散数学的基本概念，也对计算机科学和工程领域有着重要的实际意义。
此外，布尔函数和布尔代数在计算机编程中也具有重要的应用。
计算机程序是一系列指令的集合，通过执行这些指令实现特定的功能。
布尔函数可以用来描述程序中的条件和逻辑关系，判断某个条件是否成立，从而确定程序的执行路径。
布尔代数可以用来简化程序的逻辑表达式，使程序更加高效和可读。
在编程语言中，布尔变量和布尔运算是基础数据类型和基本运算符之一，它们与布尔函数和布尔代数密切相关。
离散数学中的代数系统和布尔代数
离散数学是数学的一个重要分支，研究的是离散结构和离散对象的性质。
代数系统和布尔代数是离散数学中的两个重要概念。
代数系统是研究集合上的运算的一种数学结构。
它由集合和一组运算所组成，其中运算可以是两个对象相互运算得到一个新的对象，也可以是一个对象自身经过某种运算得到一个新的对象。
代数系统包括了很多种类，例如群、环、域等等。
其中，布尔代数是代数系统的一种重要类型。
布尔代数是一种二元代数系统，它研究的是关于真值和逻辑运算的代数。
在布尔代数中，我们考虑的对象是命题，而运算包括了与、或、非等等。
布尔代数主要用于逻辑运算和电路设计中。
布尔代数中的命题可以用真和假来表示，它们分别对应于数学中的1和0。
与、或、非等运算在布尔代数中也有对应的符号，分别是∧、∨、¬。
这些符号在逻辑运算中扮演重要角色。
布尔代数的运算有很多有趣的性质。
比如，与运算满足交换律、结合律、分配律等等；或运算满足交换律、结合律、分配律等等；非运算满足逆运算和恒等律。
这些性质使得布尔代数具有很强的推理和运算能力。
布尔代数在逻辑运算中有着广泛的应用。
在计算机科学中，布尔代数被用于电路设计和逻辑推理；在人工智能领域，布尔代数被用于知识表示和推理；在运筹学中，布尔代数被用于约束求解和优化问题。
布尔代数的应用广泛而深入，是离散数学中的重要工具之一。
总结起来，离散数学中的代数系统和布尔代数是两个重要的概念。
代数系统研究的是集合上的运算，而布尔代数研究的是关于真值和逻辑运算的代数。
布尔代数具有许多有趣的性质和广泛的应用，是离散数学中的一个重要工具。
离散数学 格与布尔代数共89页
66、节制使快乐增加并使享受加强。 ——德 谟克利 特 67、今天应做的事没有做，明天再早也 是耽误 了。——裴斯 泰洛齐 68、决定一个人的一生，以及整个命运 的，只 是一瞬 之间。 ——歌 德 69、懒人无法享受休息之乐。——拉布 克 70、浪费时间是一桩大罪过。——卢梭
离散数学 格与布尔代数
21、没有人陪你走一辈子，所以你要 适应孤 独，没 有人会 帮你一 辈子， 所以你 要奋斗 一生。 22、当眼泪流尽的时候，留下的应该 是坚强 。 23、要改变命运，首先改变自己。
24、勇气很有理由被当作人类德性之 首，因 为这种 德性保 证了所 有其余 的德性 。--温 斯顿． 丘吉尔 。 25、梯子的梯阶从来不是用来搁脚的 ，它只 是让人 们的脚 放上一 段时间 ，以便 让别一 只脚能 够再往 上登。
离散数学格与布尔代数
<L, > <L, , *>
§7.1 格
例 < P(S) ， >是格 表示为<P(S), , * > 又可表示为< P(S) ,∪,∩>
例 <Z+,≤>,或 <Z+,|> <Z+, , * > <Z+, LCM,GCD>
§7.2 格——代数系统
格〈L，≤〉中自然存在两个运算 和 * ，从而 派生出一个代数系统〈L，，*〉
6
<S15,|>,
2
2019/10/5
30
10
15
3
5
1
§7.1 格
例 判断图中的哈斯图表示的偏序集是否构成格,说明为什么。
d c
b a
(a)
e d
c b
a (b)
f
d
e
d
e
c
b
c
a (c)
a
b
(d)
e
c
d
a
b
(e)
2019/10/5
§7.1 格
例 设Z+为正整数集合，对于a,b Z+，关系“≤”定义为： a≤b当 且仅当a整除b。则偏序集<Z+,≤>构成格，
并、交 运算的性质
定理１ 设〈L，≤〉是一个格，并运算与交运算 * 满足 如下性质：
L1 a a ＝ a
a*a＝a
（幂等律）
L2 a b ＝ b a a * b ＝ b * a （交换律）
L3 （a b） c ＝ a （b c）
§7.1 格
例 < P(S) ， >是格 表示为<P(S), , * > 又可表示为< P(S) ,∪,∩>
例 <Z+,≤>,或 <Z+,|> <Z+, , * > <Z+, LCM,GCD>
§7.2 格——代数系统
格〈L，≤〉中自然存在两个运算 和 * ，从而 派生出一个代数系统〈L，，*〉
6
<S15,|>,
2
2019/10/5
30
10
15
3
5
1
§7.1 格
例 判断图中的哈斯图表示的偏序集是否构成格,说明为什么。
d c
b a
(a)
e d
c b
a (b)
f
d
e
d
e
c
b
c
a (c)
a
b
(d)
e
c
d
a
b
(e)
2019/10/5
§7.1 格
例 设Z+为正整数集合，对于a,b Z+，关系“≤”定义为： a≤b当 且仅当a整除b。则偏序集<Z+,≤>构成格，
并、交 运算的性质
定理１ 设〈L，≤〉是一个格，并运算与交运算 * 满足 如下性质：
L1 a a ＝ a
a*a＝a
（幂等律）
L2 a b ＝ b a a * b ＝ b * a （交换律）
L3 （a b） c ＝ a （b c）
离散数学(第二版)第7章格和布尔代数和
第七章 格和布尔代数
离散数学(第二版)第7章格和布尔代 数和
第七章 格和布尔代数
7.1 格 与 子 格
本章将讨论另外两种代数系统——格与布尔代数， 它 们与群、 环、 域的基本不同之处是： 格与布尔代数的基集 都是一个偏序集。 这一序关系的建立及其与代数运算之间 的关系是介绍的要点。 格是具有两个二元运算的代数系统， 它是一个特殊的偏序集， 而布尔代数则是一个 特殊的格。
于是， 我们有下列对偶原理。
第七章 格和布尔代数
定理7.1.2 如果命题P在任意格〈L， 〉上成立， 则
将L中符号∨， ∧，
∧， ∨，
P*在任意格〈L， 〉上也成立， 这里P*称为P的对偶式。
在上述对偶原理中， “如果命题P在任意格〈L， 〉
上成立”的含义是指当命题P中的变量取值于L中， 且上确
界运算为∨， 下确界运算为∧， 则P对于它们也成立。
第七章 格和布尔代数
再设a=a∧b， 则a∨b=(a∧b)∨b=b(由吸收律)， 即
a∨b=b。
最后， 设b＝a∨b， 则由a a∨b可得a b。
因此， (1)中3个命题的等价性得证。
(2) 因为 a a∨b， a a∨c, 故a (a∨b)∧(a∨c)。 又
因为
b∧c b a∨b b∧c c a∨c
条件是b a, 则〈L, 也是偏序集。 我们把偏序集〈L, 和〈L, 称为是相互对偶的。 并且它们所对应的哈
斯图是互为颠倒的。 关于格我们有同样的性质。 定理7.1.1 若〈L, 是一个格， 则〈L, 也是一
个格, 且它的并、 交运算∨r, ∧r对任意a, b∈L满足 a∨rb=a∧b，a∧rb=a∨b
证明 先证幂等性成立。 由吸收律知 a∧a＝a∧(a∨(a∧b))＝a a∨a＝a∨(a∧(a∨b))＝a
离散数学(第二版)第7章格和布尔代 数和
第七章 格和布尔代数
7.1 格 与 子 格
本章将讨论另外两种代数系统——格与布尔代数， 它 们与群、 环、 域的基本不同之处是： 格与布尔代数的基集 都是一个偏序集。 这一序关系的建立及其与代数运算之间 的关系是介绍的要点。 格是具有两个二元运算的代数系统， 它是一个特殊的偏序集， 而布尔代数则是一个 特殊的格。
于是， 我们有下列对偶原理。
第七章 格和布尔代数
定理7.1.2 如果命题P在任意格〈L， 〉上成立， 则
将L中符号∨， ∧，
∧， ∨，
P*在任意格〈L， 〉上也成立， 这里P*称为P的对偶式。
在上述对偶原理中， “如果命题P在任意格〈L， 〉
上成立”的含义是指当命题P中的变量取值于L中， 且上确
界运算为∨， 下确界运算为∧， 则P对于它们也成立。
第七章 格和布尔代数
再设a=a∧b， 则a∨b=(a∧b)∨b=b(由吸收律)， 即
a∨b=b。
最后， 设b＝a∨b， 则由a a∨b可得a b。
因此， (1)中3个命题的等价性得证。
(2) 因为 a a∨b， a a∨c, 故a (a∨b)∧(a∨c)。 又
因为
b∧c b a∨b b∧c c a∨c
条件是b a, 则〈L, 也是偏序集。 我们把偏序集〈L, 和〈L, 称为是相互对偶的。 并且它们所对应的哈
斯图是互为颠倒的。 关于格我们有同样的性质。 定理7.1.1 若〈L, 是一个格， 则〈L, 也是一
个格, 且它的并、 交运算∨r, ∧r对任意a, b∈L满足 a∨rb=a∧b，a∧rb=a∨b
证明 先证幂等性成立。 由吸收律知 a∧a＝a∧(a∨(a∧b))＝a a∨a＝a∨(a∧(a∨b))＝a
离散数学-格和布尔代数
的次序图如下
-1 的次序图如下
6 2 1 3 2
1 3 6
若 < L; > 是一个偏序集，则对于任意元素 l1, l2, l3 L，有以 下六个关系式成立： l1 l1 若 l1 l2，l2 l1，则 l1 = l2 若 l1 l2，l2 l3，则 l1 l3 l1 l1 若 l1 l2，l2 l1，则 l1 = l2 (7-1) (7-2) (7-3) (7-1) (7-2)
60以上说明与格一样布尔代数也是一个代数系统该代数系统可取交换律分配律同一律和互补律作为公二元运算是一元运算若这些运算满足交换律分配律同一律和互补律则称称作集合代数它是一个布尔代数
第二部分 抽象代数
0
第七章
格和布尔代数
格是 Birkhoff (1884 - 1944) 在 20 世纪 30 年代提出的，格的提出 以子集为背景。 历史上最初出现的格是英国数学家 George Boole 于 1854 年提出 的，是他在研究命题演算中发现的，通常称为布尔格或布尔代 数。 格和布尔代数的理论成为计算机硬件设计和通讯系统设计中的 重要工具。格论是计算机语言的指称语义的理论基础。格是一 种特殊的偏序集，也可以看作是有两个二元运算的代数系统， 布尔代数是一种特殊的格。在保密学、开关理论、计算机理论 和逻辑设计以及其他一些科学和工程领域中，都直接应用了格 与布尔代数。 1
7.2 格及其性质
一、格的定义
定义7-5 设 < L; > 是一个偏序集，如果 L 中任意两个元素都 存在着最大下界和最小上界，则称 < L; > 是格。 由于每对元素的最大下界和最小上界唯一，故引入记号： l1 l2 = glb(l1, l2)，l1 l2 = lub(l1, l2)， 其中 和 均可看作是集合 L 上的二元运算，分别称为交和并。 注：若 < L; > 是一个格，则意味着 < L; > 也是一个形为 < L; , > 的代数系统，其中 和 是 L 上的两个二元运算， 对于任意 l1, l2 L，l1 l2 表示在偏序 “ ” 意义下，l1 和 l2 的最小上界，l1 l2 表示 l1 和 l2 的最大下界。
离散数学布尔代数
一个非零元素b，至少存在一个原子a，使得a ≤ b。 1
证明：若b本身就是一个原子，则b ≤ b，得证。c
df
若b不是原子，肯定存在b1，使得0 ≤ b1 ≤ b， a
be
若b1是原子，则定理得证；
0
否则，若b1不是原子，则必存在b2，使得0 ≤ b2 ≤ b1 ≤ b
∵<A, ≤>是一个有全下界的有限格，
定理1：对于布尔代数中任意两个元素 a, b，必定有
(1) ( a ) = a， (2) a∨b = a∧b ， (3) a∧b = a∨b
3
❖ 布尔代数
定义3：设<A,∨1,∧1, - > 和<B,∨2,∧2, ~ >是两个布尔代数， 如果存在A到B的双射 f，对于a,bA，有
f (a∨1b) = f (a) ∨2 f (b)
2、对a,bA，有 f (a∧b) = f (a)∩f (b)
9
❖ 格与布尔代数
定理3 ( Stone表示定理 ) ：
设<A,∨,∧, - >是由有限布尔格<A, ≤>所诱导的一个有 限布尔代数，S是布尔格<A, ≤>中的所有原子的集合，则 < A,∨,∧, - >< P(S),∪,∩, ~ >同构。 分析：要证两个代数系统同构，分为以下几步：
1、找一个双射函数 f: A P(S)
∴a ≤ c ，又∵a ≤ c， ∴a ≤ c ∧ c，即 a ≤ 0，
这与a是原子相矛盾， ∴假设错
∴b ∧ c = 0，由引理1得： b≤c ∴b=c，即：b= a1∨a2∨... ∨ak
7
❖ 格与布尔代数
证明(2)：设b的另一种表示形式为 b = aj1∨aj2∨... ∨ajt 其中aj1,aj2,……,ajt是A中原子。∵b是 aj1,aj2,……,ajt 的最小上界， ∴有aj1≤b, aj2≤b,…,ajt≤b，而a1,a2,……,ak是A中满足 a j ≤b的所有原子， {aj1,aj2,…,ajt}是{a1,a2,…,ak}的子集，即 |{aj1,aj2,…,ajt}|<=|{a1,a2,…,ak}|， 即：t ≤ k。(下面证 t < k 是不可能的)
离散数学格与布尔代数
6
<S15,|>,
2
2019/10/12
30
10
15
3
5
1
§7.1 格
例 判断图中的哈斯图表示的偏序集是否构成格,说明为什么。
d c
b a
(a)
e d
c b
a (b)
f
d
e
d
e
c
b
c
a (c)
a
b
(d)
e
c
d
a
b
(e)
2019/10/12
§7.1 格
例 设Z+为正整数集合，对于a,b Z+，关系“≤”定义为： a≤b当 且仅当a整除b。则偏序集<Z+,≤>构成格，
Input A B Cin
00 0 00 1 01 0 01 1 10 0 10 1 11 0 11 1
Output S Cout
00 10 10 01 10 01 01 11
S A BCin A BCin A BCin A BCin
Cout A B Cin A B Cin A B Cin A B Cin
§7.2 格——代数系统
证〈L，≤〉为要求的格
a，b∈L，（a * b）* a ＝ a*（a * b）＝（a * a）*b＝a*b，
故a*b≤a，
L3
L1
同理a*b≤b，因此a*b是｛a，b｝的下界，
又设c是｛a，b｝的任一下界，即c≤a，c≤b，则a * c＝c，b * c＝c，于是（a * b）* c＝a *（b * c）＝a * c＝c，即c≤a * b， 所以a * b是｛a，b｝的最大下界，即a * b＝inf｛a，b｝，
离散数学格的概念
其中 I+ 是正整数，D是整除关系，A={a,b,c} Sn ={n的所有因子}如：S6={1,2,3,6}、S12={1,2,3,4,6,12}、 解：< I+ , D>是格
∵整除关系是偏序关系，对a,bI， a、b的最小上界等于a、b的最小公倍数， a、b的最大下界等于a、b的最大公约数。
❖ 基本概念
< B2 , D >是否 < S30 , D >的子格?
30
6
30
10
6 15
2
3
10
15
1 ∨1 2 3 6 11236 22266
2
53
5
∧1 2 3 6
1
11111
21212
说明：
33636 66666
31133 61236
(1) 子格必是格。
运算∨和∧在B1上封闭，B1 S30 且B1 ≠Ø, ∴ < B1, D >是 < S30 , D >的子格； 同理可证< B2 , D >是 < S30 , D >的子格
例：A={a, b, c }, < P(A) , > 所诱导的代数系统为？
< P(A),∪,∩>
❖ 基本概念
定义3:设<A,≤ >是一个格，由其所诱导的代数系统为 <A,∨,∧>。设BA且B ≠Ø ，如果运算∨和∧在B上封闭， 则称<B,≤ > 是<A,≤ >的子格。
❖ 基本概念
例2：B1 = {1,2,3,6} ， B2 = {5,10,15,30} ，< B1, D >和
离散数学
❖ 格与布尔代数 1 格的概念
∵整除关系是偏序关系，对a,bI， a、b的最小上界等于a、b的最小公倍数， a、b的最大下界等于a、b的最大公约数。
❖ 基本概念
< B2 , D >是否 < S30 , D >的子格?
30
6
30
10
6 15
2
3
10
15
1 ∨1 2 3 6 11236 22266
2
53
5
∧1 2 3 6
1
11111
21212
说明：
33636 66666
31133 61236
(1) 子格必是格。
运算∨和∧在B1上封闭，B1 S30 且B1 ≠Ø, ∴ < B1, D >是 < S30 , D >的子格； 同理可证< B2 , D >是 < S30 , D >的子格
例：A={a, b, c }, < P(A) , > 所诱导的代数系统为？
< P(A),∪,∩>
❖ 基本概念
定义3:设<A,≤ >是一个格，由其所诱导的代数系统为 <A,∨,∧>。设BA且B ≠Ø ，如果运算∨和∧在B上封闭， 则称<B,≤ > 是<A,≤ >的子格。
❖ 基本概念
例2：B1 = {1,2,3,6} ， B2 = {5,10,15,30} ，< B1, D >和
离散数学
❖ 格与布尔代数 1 格的概念
离散数学课件_7 格与布尔代数
布尔代数可用相互独立的亨廷顿公理给出, 即一个代数系统 (L, ∧,∨,-,0,1)是布 尔代数当且仅当交换律、分配律、同一律 及互补律成立;
有限布尔代数同构于某个集合上的幂集构 成的布尔代数；
两个有限布尔代数同构当且仅当它们所含 的元素个数相同.
返回本章首页
5 2019/12/4
本章小结
第七章 格与布尔代数
布尔代数是计算机科学最重要的基础理论之 一,它在开关网络及数字电路的设计上有广 泛深入的应用. 布尔代数是计算机科学工作者必备的基础知 识，应掌握格与布尔代数的一般理论和方法， 除§3 Stone定理的证明细节可根据具体情 况删减外，其他内容应很好地掌握.
返回首页
1 2019/12/4
本章我们介绍了代数格、偏序格，并证 明了这两种格的等价性，此外我们还介 绍了对偶原理、分配格、有补格、布尔 代数等概念.布尔代数是数字逻辑的基 础、在学习数字逻辑时会更深刻地体会 到布尔代数在计算机中的应用.
返回本章首页
6 2019/12/4
第一节 格的概念(1)
格有两种等价的定义:一种是从偏序集 的角度给出格的定义，这种定义可以借 助哈斯（Hasse）图来表示，因而比较 直观，易于理解，这样定义的格称为偏 序格；另一种是从代数系统的角度来给 出格的定义，这种定义方法我们在上一 章的群、环的定义中已有所体会，用代 数系统的方法定义的格称为代数格.
主要概念有:有界格、余元素(或补元素) 、 有余格、分配格等.
主要结论有: 1.格的基本性质(见教材定理7.2.1); 2.序集构成的格是分配格; 3.在有界分配格中,若某个元素有补元,
则补元惟一.ຫໍສະໝຸດ 返回本章首页4 2019/12/4
第三节 布尔代数
有限布尔代数同构于某个集合上的幂集构 成的布尔代数；
两个有限布尔代数同构当且仅当它们所含 的元素个数相同.
返回本章首页
5 2019/12/4
本章小结
第七章 格与布尔代数
布尔代数是计算机科学最重要的基础理论之 一,它在开关网络及数字电路的设计上有广 泛深入的应用. 布尔代数是计算机科学工作者必备的基础知 识，应掌握格与布尔代数的一般理论和方法， 除§3 Stone定理的证明细节可根据具体情 况删减外，其他内容应很好地掌握.
返回首页
1 2019/12/4
本章我们介绍了代数格、偏序格，并证 明了这两种格的等价性，此外我们还介 绍了对偶原理、分配格、有补格、布尔 代数等概念.布尔代数是数字逻辑的基 础、在学习数字逻辑时会更深刻地体会 到布尔代数在计算机中的应用.
返回本章首页
6 2019/12/4
第一节 格的概念(1)
格有两种等价的定义:一种是从偏序集 的角度给出格的定义，这种定义可以借 助哈斯（Hasse）图来表示，因而比较 直观，易于理解，这样定义的格称为偏 序格；另一种是从代数系统的角度来给 出格的定义，这种定义方法我们在上一 章的群、环的定义中已有所体会，用代 数系统的方法定义的格称为代数格.
主要概念有:有界格、余元素(或补元素) 、 有余格、分配格等.
主要结论有: 1.格的基本性质(见教材定理7.2.1); 2.序集构成的格是分配格; 3.在有界分配格中,若某个元素有补元,
则补元惟一.ຫໍສະໝຸດ 返回本章首页4 2019/12/4
第三节 布尔代数
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
条件是b a, 则〈L, 也是偏序集。 我们把偏序集〈L, 和〈L, 称为是相互对偶的。 并且它们所对应的哈
斯图是互为颠倒的。 关于格我们有同样的性质。 定理7.1.1 若〈L, 是一个格， 则〈L, 也是一
个格, 且它的并、 交运算∨r, ∧r对任意a, b∈L满足 a∨rb=a∧b，a∧rb=a∨b
现在我们深入地讨论格的性质。
第七章 格和布尔代数
定理7.1.3 设〈L, 是一个格， 那么对L中任何元素 a, b, c， 有
(1) a a∨b， b a∨b a∧b a， a∧b b
(2) 若a b， c d， 则a∨c b∨d， a∧c b∧d。 (3) 若a b， 则a∨c b∨c， a∧c b∧c。 这个性质 称为格的保序性。
在第四章， 对偏序集的任一子集可引入上确界(最小上 界)和下确界(最大下界)的概念，但并非每个子集都有上确 界或下确界， 例如在图7.1.1中哈斯图所示的偏序集里， {a， b}没有上确界， {e， f}没有下确界。 不过， 当某子集的上、 下确界存在时， 这个上、 下确界是唯一确定的。
第七章 格和布尔代数
第七章 格和布尔代数
离散数学(第二版)第7章格和布尔代 数和
第七章 格和布尔代数
7.1 格 与 子 格
本章将讨论另外两种代数系统——格与布尔代数， 它 们与群、 环、 域的基本不同之处是： 格与布尔代数的基集 都是一个偏序集。 这一序关系的建立及其与代数运算之间 的关系是介绍的要点。 格是具有两个二元运算的代数系统， 它是一个特殊的偏序集， 而布尔代数则是一个 特殊的格。
【例 7.1.1】 (1) 对任意集合S， 偏序集〈P(S)，〉为格， 其中并、 交运算即为集合的并、 交运算， 即
B∨C＝B∪C B∧C＝B∩C 封闭于P(S), 这里B, C∈P(S)。
第七章 格和布尔代数
(2) 设L为命题公式集合，
L上的
偏序关系(
)， 那么，
〈L, 为格， 对任何命题公式 A， B， A∨B=A∨B，
由式(7.1.3)、 (7.1.4)得 a∧(b∧c) (a∧b)∧c
同理可证 (a∧b)∧c a∧(b∧c)
(7.1.4) (7.1.5) (7.1.6)
第七章 格和布尔代数
(7.1.5)、 (7.1.6)， 所以a∧(b∧c)=
(a∧b)∧c。
利用对偶原理可得a∨(b∨c)=(a∨b)∨c。
(4) 由定理7.1.3的(1)可知a∧(a∨b) a； 另一方面，
因此我们通常用a∨b表示{a， b}的上确界， 用a∧b 表示{a， b}的下确界， 并记作a∨b=LUB{a, b}(least upper bound), a∧b=GLB{a, b}(greatest lower bound), ∨和∧分别 称为并(join)和交(meet)运算。 由于对任何a， b， a∨b及 a∧b都是L中确定的成员， 因此∨, ∧均为L上的二元运算。
a∨c b∨d 将a∧c≤b∧d的证明留给读者。
第七章 格和布尔代数
(3) 将(2)中的a代替b， b代替c， c代替d即可得证。
证毕
定理7.1.4 设〈L, 是一个格， 那么对L中任意元素
a, b, c， 有
(1) a∨a=a， a∧a＝a
(幂等律)
(2) a∨b=b∨a， a∧b=b∧a
(交换律)
于是， 我们有下列对偶原理。
第七章 格和布尔代数
定理7.1.2 如果命题P在任意格〈L， 〉上成立， 则
将L中符号∨， ∧，
∧， ∨，
P*在任意格〈L， 〉上也成立， 这里P*称为P的对偶式。
在上述对偶原理中， “如果命题P在任意格〈L， 〉
上成立”的含义是指当命题P中的变量取值于L中， 且上确
界运算为∨， 下确界运算为∧， 则P对于它们也成立。
图7.1.1
第七章 格和布尔代数
定义7.1.1 如果偏序集〈L， 〉中的任何两个元素的 子集都有上确界和下确界, 则称偏序集〈L， 〉为格 (lattice)。
虽然偏序集合的任何子集的上确界、 下确界并不一定 都存在， 但存在， 则必唯一，而格定义保证了上确界、 下 确界的存在性。
第七章 格和布尔代数
(3) a∨(b∨c)=(a∨b)∨c, a∧(b∧c)=(a∧b)∧c(结合律)
(4) a∧(a∨b)=a， a∨(a∧b)=a
(吸收律)
第七章 格和布尔代数
证明
(1) 由自反性可得 a a， 所以 a是a的一个上界， 因为
a∨a 是a与a的最小上界， 因此a∨a a。
由定理7.1.3的(1)可知a a∨a。
第七章 格和布尔代数
证明 (1) 因为a∨b是a的一个上界， 所以a a∨b； 同理有b a∨b。 由对偶原理可得a∧b a， a∧b b。 (2) 由题设知a b， c d， 由(1)有b b∨d，d b∨d，
a b∨d， c b∨d。 这说明b∨d是a和c的一个上界， 而a∨c是a和c的最小 上界， 所以， 必有
所以a∨a=a。 利用对偶原理可得
a∧a＝a。
(2) 由格的并∨与交∧运算的定义知满足交换律。
(3) 由下确界定义知
a∧(b∧c) b∧c b
(7.1.1)
a∧(b∧c) a
(7.1.2)
a∧(b∧c) b∧c c
(7.1.3)
第七章 格和布尔代数
由式(7.1.1)、 (7.1.2)得 a∧(b∧c) a∧b
A∧B=A∧B(等式右边的∨， ∧为#43;表示正整数集， |表示Z+上整除关系， 那么 〈Z+， |〉为格， 其中并、 交运算即为求两正整数最小公 倍数和最大公约数的运算， 即
m∨n＝LCM(m, n) m∧n＝GCD(m, n)
第七章 格和布尔代数
另外， 若将〈L, 中的小于等于关系换成大于等于 即对于L中任何两个元素a, b定义a b的充分必要
由定义可知， 并非所有的偏序集都能构成格， 我们用 Hasse图表示偏序集， 图7.1.2中哪个能构成格？
第七章 格和布尔代数
图7.1.2
第七章 格和布尔代数
图7.1.2中哈斯图(a)、 (b)、 (c)所规定的偏序集是格， 图(d)、 (e)及图7.1.1所规定的偏序集不是格, 因为图中{a, b} 无上确界。
斯图是互为颠倒的。 关于格我们有同样的性质。 定理7.1.1 若〈L, 是一个格， 则〈L, 也是一
个格, 且它的并、 交运算∨r, ∧r对任意a, b∈L满足 a∨rb=a∧b，a∧rb=a∨b
现在我们深入地讨论格的性质。
第七章 格和布尔代数
定理7.1.3 设〈L, 是一个格， 那么对L中任何元素 a, b, c， 有
(1) a a∨b， b a∨b a∧b a， a∧b b
(2) 若a b， c d， 则a∨c b∨d， a∧c b∧d。 (3) 若a b， 则a∨c b∨c， a∧c b∧c。 这个性质 称为格的保序性。
在第四章， 对偏序集的任一子集可引入上确界(最小上 界)和下确界(最大下界)的概念，但并非每个子集都有上确 界或下确界， 例如在图7.1.1中哈斯图所示的偏序集里， {a， b}没有上确界， {e， f}没有下确界。 不过， 当某子集的上、 下确界存在时， 这个上、 下确界是唯一确定的。
第七章 格和布尔代数
第七章 格和布尔代数
离散数学(第二版)第7章格和布尔代 数和
第七章 格和布尔代数
7.1 格 与 子 格
本章将讨论另外两种代数系统——格与布尔代数， 它 们与群、 环、 域的基本不同之处是： 格与布尔代数的基集 都是一个偏序集。 这一序关系的建立及其与代数运算之间 的关系是介绍的要点。 格是具有两个二元运算的代数系统， 它是一个特殊的偏序集， 而布尔代数则是一个 特殊的格。
【例 7.1.1】 (1) 对任意集合S， 偏序集〈P(S)，〉为格， 其中并、 交运算即为集合的并、 交运算， 即
B∨C＝B∪C B∧C＝B∩C 封闭于P(S), 这里B, C∈P(S)。
第七章 格和布尔代数
(2) 设L为命题公式集合，
L上的
偏序关系(
)， 那么，
〈L, 为格， 对任何命题公式 A， B， A∨B=A∨B，
由式(7.1.3)、 (7.1.4)得 a∧(b∧c) (a∧b)∧c
同理可证 (a∧b)∧c a∧(b∧c)
(7.1.4) (7.1.5) (7.1.6)
第七章 格和布尔代数
(7.1.5)、 (7.1.6)， 所以a∧(b∧c)=
(a∧b)∧c。
利用对偶原理可得a∨(b∨c)=(a∨b)∨c。
(4) 由定理7.1.3的(1)可知a∧(a∨b) a； 另一方面，
因此我们通常用a∨b表示{a， b}的上确界， 用a∧b 表示{a， b}的下确界， 并记作a∨b=LUB{a, b}(least upper bound), a∧b=GLB{a, b}(greatest lower bound), ∨和∧分别 称为并(join)和交(meet)运算。 由于对任何a， b， a∨b及 a∧b都是L中确定的成员， 因此∨, ∧均为L上的二元运算。
a∨c b∨d 将a∧c≤b∧d的证明留给读者。
第七章 格和布尔代数
(3) 将(2)中的a代替b， b代替c， c代替d即可得证。
证毕
定理7.1.4 设〈L, 是一个格， 那么对L中任意元素
a, b, c， 有
(1) a∨a=a， a∧a＝a
(幂等律)
(2) a∨b=b∨a， a∧b=b∧a
(交换律)
于是， 我们有下列对偶原理。
第七章 格和布尔代数
定理7.1.2 如果命题P在任意格〈L， 〉上成立， 则
将L中符号∨， ∧，
∧， ∨，
P*在任意格〈L， 〉上也成立， 这里P*称为P的对偶式。
在上述对偶原理中， “如果命题P在任意格〈L， 〉
上成立”的含义是指当命题P中的变量取值于L中， 且上确
界运算为∨， 下确界运算为∧， 则P对于它们也成立。
图7.1.1
第七章 格和布尔代数
定义7.1.1 如果偏序集〈L， 〉中的任何两个元素的 子集都有上确界和下确界, 则称偏序集〈L， 〉为格 (lattice)。
虽然偏序集合的任何子集的上确界、 下确界并不一定 都存在， 但存在， 则必唯一，而格定义保证了上确界、 下 确界的存在性。
第七章 格和布尔代数
(3) a∨(b∨c)=(a∨b)∨c, a∧(b∧c)=(a∧b)∧c(结合律)
(4) a∧(a∨b)=a， a∨(a∧b)=a
(吸收律)
第七章 格和布尔代数
证明
(1) 由自反性可得 a a， 所以 a是a的一个上界， 因为
a∨a 是a与a的最小上界， 因此a∨a a。
由定理7.1.3的(1)可知a a∨a。
第七章 格和布尔代数
证明 (1) 因为a∨b是a的一个上界， 所以a a∨b； 同理有b a∨b。 由对偶原理可得a∧b a， a∧b b。 (2) 由题设知a b， c d， 由(1)有b b∨d，d b∨d，
a b∨d， c b∨d。 这说明b∨d是a和c的一个上界， 而a∨c是a和c的最小 上界， 所以， 必有
所以a∨a=a。 利用对偶原理可得
a∧a＝a。
(2) 由格的并∨与交∧运算的定义知满足交换律。
(3) 由下确界定义知
a∧(b∧c) b∧c b
(7.1.1)
a∧(b∧c) a
(7.1.2)
a∧(b∧c) b∧c c
(7.1.3)
第七章 格和布尔代数
由式(7.1.1)、 (7.1.2)得 a∧(b∧c) a∧b
A∧B=A∧B(等式右边的∨， ∧为#43;表示正整数集， |表示Z+上整除关系， 那么 〈Z+， |〉为格， 其中并、 交运算即为求两正整数最小公 倍数和最大公约数的运算， 即
m∨n＝LCM(m, n) m∧n＝GCD(m, n)
第七章 格和布尔代数
另外， 若将〈L, 中的小于等于关系换成大于等于 即对于L中任何两个元素a, b定义a b的充分必要
由定义可知， 并非所有的偏序集都能构成格， 我们用 Hasse图表示偏序集， 图7.1.2中哪个能构成格？
第七章 格和布尔代数
图7.1.2
第七章 格和布尔代数
图7.1.2中哈斯图(a)、 (b)、 (c)所规定的偏序集是格， 图(d)、 (e)及图7.1.1所规定的偏序集不是格, 因为图中{a, b} 无上确界。