当前位置：文档之家 › 第十七章格与布尔代数

第十七章格与布尔代数

  • 格式：ppt
  • 大小：254.50 KB
  • 文档页数：23

下载文档原格式

  / 23

合集下载

代数结构-布尔代数与格

代数结构-布尔代数与格

布尔代数举例

({0, 1}, +, ⋅ , , 0, 1)为布尔代数 n度布尔函数全体也构成一个布尔代数

布尔和 布尔积 补函数 全取0的函数、全取1的函数

A的幂集也构成一个布尔代数(ρ(A), ⋂, ⋃, ∼, ∅, A）
布尔代数举例

Bn={(x1, …, xn)| xi∈B, i =1, …, n}构成布尔代数 x= (a1 , …, an), y=(b1 , …, bn), ai∈B, bi∈B
111 110
Bn as Product of n B’s

B1, ({0,1}, ∧, ∨, 1, 0, ’), is denoted as B. For any n≥1, Bn is the product B×B×...×B of B, n factors, where B×B×...×B is given the product partial order.
格中的原子
a
a a b c d (1) e (2) b c d b
c 原子 d e (3)
有限布尔代数的表示定理

任一有限布尔代数B 同构于 B中所有的原子构成的 集合A的幂集代数系统P(A)。 即(B, ∧, ∨, ', 0, 1) ≅ (P(A), ⋂, ⋃, ∼, ∅, A)

备注（关于无限布尔代数）

若 x∧y =x，则 x∨y = (x∧y) ∨ y = y //吸收律
若 x∨y =y，则 x∧ y = x∧ (x∨y) = x //吸收律


证明这个关系满足自反性、反对称性、传递性。 这个偏序构成一个格。

lub{x,y} 即为 x∨y。 glb{x,y} 即为 x∧y。

格与布尔代数

格与布尔代数

对P(S)中任一元素A,S与A的差集S-A是其唯一补元
因为:
(S-A)∪A=S和(S-A)∩A=Φ.
36
7.5 几种特殊的格
定义4(分配格) 格<L, ,*>称作一个分配格,如果对L中 任意元素a,b,c都有: (1) a*(bc)=(a*b)(a*c); (2) a(b*c)=(ab)*(ac). 例：幂集格<P(S),∩,∪>都是分配格. 格<P(S),∩,∪> 的两个二元运算分别是S幂集合上的交和并运算,交 对并和并对交都具有分配律;
M={c,d}
无上确界，下确界为e 上确界为a，下确界为b
12
7.1 偏序集
M={{a},{b}}
上确界{{a,b}}，下确界为
M={{a},{a,b}}
上确界{{a,b}}，下确界为{a}
M={{a},{b,c}}或 M={{a},{b},{c}}或
上确界{{a,b,c}}，下确界为
M={{a,b},{b,c}}
31
7.5 几种特殊的格
定义1 (有界格) 若格<L,≤>存在最大元和最小元，则称该格为有界格。
记最大元为1，最小元为0。记有界格为<L,≤,0,1>。
例： <P(S), , ,S>有界格。
32
7.5 几种特殊的格
定义2 (补元) 有界格<L,≤,0,1>中，如果a*b=0且ab=1. 则称元素b为a的补元。
18
7.2 格的定义
例. 设S是任意集合, 则< P(s), >为偏序格。
|S|=1
|S|=2
|S|=3 两个集合A，B的上确界是A∪B，下确界是A∩B

格与布尔代数

格与布尔代数

∴f 是 A1 到 A2 的格同态。
定理2：设f是由格<A1, ≤1>到格<A2, ≤2>的格同态，
第六章
1、格的基本概念
2、分配格 3、有补格
格与布尔代数
4、布尔代数
5、布尔表达式
非本次期末考试内容
§1 格的基本概念
定义1：设<A,≤>是一个偏序集，若A中任意两个 元素都有最大下界和最小上界，则称 <A,≤>为格。
36
12 4 2 3 1 12 6 3 1 2 3
24
不是格
2
6
格
格
图、三个偏序集哈斯图
就得到另一个命题P’，把P’称为P的对偶命题。
则P’对任意格也是真命题。（其中“≥”是“≤”的逆关系） 在<A,≤>中任何两个元素的∨的结果值必然等于 若<A,≤>是格，可证明<A,≥>也是一个格， 这两个元素在<A,≥>中∧的结果值； 任何两个元素的∧的结果值必然等于这两个元素在 且它们的哈斯图是上下颠倒的。 30 <A,≥>中∨的结果值；反之亦然。 1
5
< S6 , D >
< S8 , D >
1 < S30 , D >
1
2 4 6 3 5 7
1
2
3
6
4
7
5
这两个图是偏序关系，但不是格。
定义2：格代数 设<A,≤>是一个格，若在A上定义两个二元运算∨和 ∧,使得对于a,bA, a∨b等于a和b的最小上界,a∧b等于a和b的最大下界, 则称<A,∨,∧>为由格<A, ≤>所诱导的代数系统。

(优选)第篇格与布尔代数

(优选)第篇格与布尔代数

第2式证明由对偶原理从上式直接可得。
定理15-1.6 设<A, >是一个格,那么，对于任意的 a,bA, 都有：
ab(a∧b)=a(a∨b)=b
ab(a∧b)证明思路：
(1)先证 ab (a∧b)=a
由ab和a a ，根据定理15-1.2得 a a∧b
又根据a∧b的定义， 有
a∧b a
由二元关系的反对称性得 ：
（优选）第篇格与布尔代数
通常用a∨b 表示{a,b}的上确界,用a∧b 表示{a， b}的下确界,∨和∧分别称为保联(join)和保交(meet) 运算。由于对任何a，b，a∨b及a∧b都是A 中确定 的成员，因此 ∨,∧均为A上的运算。
例3 设S={a,b} ， (S) ={, {a},{b},{a,b}} 由格< (S), >诱导的代数系统为< (S),∨,∧> 。 其中∨为集合的并运算和∧为集合的交运算。
a∧b = a
(2) 再证 (a∧b)=a ab
设a∧b=a，则a =a∧bb ，这就证明了
(a∧b)=a ab
综合(1)和(2)得： ab(a∧b)
定理15-1.7 设<A, >是一个格,那么，对于任意的
a,b,cA, 都有： aca∨(b∧c) (a∨b)∧c
证明思路： (1)先证 ac a∨(b∧c) (a∨b)∧c 根据定理15-1.6有 ac (a∨c)=c 根据定理15-1.5有a∨(b∧c)(a∨b)∧(a∨c)
可以证明，若<A,>是格，则<A,R>也是格。 称R是的逆关系。记为。
格对偶原理可以叙述为：设P是对任意格都真的命题， 如果在命题P中把换成 ，∨换成∧，∧换成∨，就

离散数学格与布尔代数

离散数学格与布尔代数
<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）

离散数学-格和布尔代数

离散数学-格和布尔代数

的次序图如下
-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 的最大下界。

离散数学格的概念

其中 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 格的概念

Chapt22 格与布尔代数.


同理可证(a×b)(a×c) ≤ a×(bc)。
2019/5/12
离散数学
23
模不等式
定理22.2.4：设L, ≤是格， a, b, c∈L。于是， a≤b当且仅当a(b×c) ≤b×(ac)。
证明：若a≤b，则由定理22.2.1知， ab=b。又 由定理22.2.3知， a(b×c) ≤ (ab)×(ac) = b×(ac)。
≤的子格。
a1
例但如是，右若图S,所≤示是的L格, ≤，的其子中格L=，{而a1,S, a×2,,a3,a不4,一a5}定。是取LS,=×{a,1,a2的, a子3, a格5}。。
a2
a4
a3
显这然说明S,，≤偏是序L格, ≤的的子子格格和，代则数格的S,
×子,格的却定不义是是L有, 区×别, 的的。子格。因 为a2×a3= a4S。
因为aa××b(a=ibn)f{=a,inbf}{，a, asupb{=a,sbu}p}{a，, b所}。以 a×这(a两种b)运≤a算，满即足in如f{a下, s的up性{a质, b：}} ≤a (1又)交因换为律，：a≤aa×且ba=≤sbu×p{aa，, ba}，b所= 以baa是；
2019/5/12
离散数学
13
从代数系统来定义格
定义22.1.3：设L是一个集合，×和是L上的 两个二元封闭运算，若×和对a, b, c∈L， 满足：
(1)交换律： a×b= b×a， ab= ba； (2)结合律： a×(b×c) = (a×b) ×c,
a(bc) = (ab)c (3)吸收律： a×(ab) = a, a(a×b) = a。 则称代数系统L, ×, 是一个格。 L, ≤ 称为偏序格，L, ×, 称为代数格。

格与布尔代数

格与布尔代数后述，一部分关于格与一部分关于布尔代数。

关于格格是数学中的一种代数结构，它被广泛用于数学、计算机科学和逻辑学等领域。

在数学中，格是一种偏序集合，它具有两个基本运算：上下拟合和交并运算。

其中，上下拟合是指存在最小上估和最大下估，而交并运算则是指对于任意两个元素都可以求出它们的最大公共上界和最小公共下界。

尽管最初格是在点集拓扑学中发现的，但它们的概念在其他领域中也扮演着重要角色，例如，它们在科学中被用来定义空间，它们被用来解决许多计算机科学问题，例如，程序正确性证明，它们与数据结构有关，在逻辑学中，格被用来理解一些推理系统。

关于布尔代数布尔代数是一种代数结构，它被广泛用于逻辑学、电子工程和计算机科学中。

布尔代数是邓纳-Bier恩论文提出的一种基于命题逻辑的代数系统，其中对于两个命题P和Q，存在两个二元运算，即并（∨）和交（∧）。

这种代数系统可以用0和1表示，其中0表示假，1表示真。

布尔代数中的一些重要性质是：交换律、结合律、分配律等。

尽管在布尔代数中并和交这两个朴素的逻辑运算都不是独立产生的概念，但该理论在数学和计算机科学中有着重要应用。

布尔代数不仅用于设计电路和硬件，还用于在计算机程序和算法中描述逻辑条件，可编程逻辑和任意逻辑等方面。

格与布尔代数的关系虽然格和布尔代数看起来似乎是两种完全不同类型的代数结构，但它们之间有着密切的联系。

一些格配合着一些次区域可以构成布尔代数；同样，对于一个布尔代数而言，它也可以被看作是某个格所描述的偏序集合。

在交集上平凡地定义结构子格也叫布尔子格。

一个布尔代数的子集都可以看做是一种决策支持系统（Decision Support System，DSS）或决策信息系统（Decision Information System，DIS）。

由此可见，布尔代数是格论的一种特例，而格论是布尔代数的一种扩展。

总体而言，格与布尔代数的关系很紧密。

事实上，这种关系已经在数学和计算机科学的广泛应用中得到了充分的体现。

格与布尔代数


a∨0＝a 和 a∧1＝a 互为对偶命题。
有界格中的补元
定义 设<L,∧,∨,0,1>是有界格，a∈L， 若存在b∈L 使得 a∧b＝0 和 a∨b＝1 成立，则称b是a的补元。
说明 若b是a的补元，那么a也是b的补元。
换句话说，a和b互为补元。
有界格中补元的说明
在任何有界格中， 全下界0与全上界1互补。 对于其他元素，可能存在补元，也可能不存在补元。 如果存在，可能是唯一的，也可能是多个补元。
格与布尔代数
格的定义与性质
定义 设<S,≤>是偏序集，如果x,y∈S，{x,y}都有最小上界 和最大下界，则称S关于偏序≤作成一个格。
说明：由于最小上界和最大下界的唯一性，可以把求{x,y}的最 小上界和最大下界看成x与y的二元运算∨和∧。
x∨y：表示x与y的最小上界
x∧y：表示x和y的最大下界。
本章出现的∨和∧符号只代表格中的运算，而不再有其它的 含义。
格的实例
例 设n是正整数，Sn是n的正因子的集合。D为整除关系，则 偏序集<Sn,D>构成格。x,y∈Sn， x∨y是lcm(x,y)，即x与y的最小公倍数。 x∧y是gcd(x,y)，即x与y的最大公约数。 下图给出了格<S8,D>，<S6,D>和<S30,D>。
定义 设<L,∧,∨>是格，若a,b,c∈L，有
a∧(b∨c)＝(a∧b)∨(a∧c) a∨(b∧c)＝(a∨b)∧(a∨c)
则称L为分配格。
说明 上面两个等式互为对偶式。 在证明L为分配格时，只须证明其中的一个等式即可。
分配格的判别
定理 设L是格，则L是分配格当且仅当L中不含有与钻石格或 五角格同构的子格。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

❖ 对于一个代数系统[L;,],其中,为L上的 二元运算,它们满足L1～L4,此时有何特点
❖ 引理17.1:在[L;,]中二元运算,满足 L1～L4, 则 对 任 a,bL,ab=a, 当 且 仅 当 ab=b。
❖ 引理17.2：在[L;,]中,,满足L1～L4,在 L上定义二元关系≤:对任意a,bL,a≤b,当且 仅当ab=b，则(L;≤)为偏序集。
❖ L1～L4 ❖ 然后证明ab为a和b的最小上界 ❖ 即证明若存在uL,使得a≤u,b≤u, ❖ 必有ab≤u
❖ 定理17.3:如引理17.2所得之偏序集(L;≤) 为格。
❖ 定义17.4: [L;,]为一代数系统,,为定 义在L上的二元运算,当其满足L1～L4时， 称L为格。并称为积(或交),为和(或并)
❖ 定理17.4(保序性):格[L;,],任a,b,cL, 当b≤c时有ab≤ac及ab≤ac。
❖ 定义17.5:[L;,]为格,T, TL,T关于 ,封闭(即a,bT则abT, abT)时, 则称T为L的子格。
❖ 必须注意的是：当T为L的子格时,T一定 是格; 但当TL,T关于L中的偏序关系≤为 格时,T不一定是L的子格。
界,ab=glb(a,b)表示a,b的最大下界。
❖ 定义17.2:(L;≤)为格,如果a≤b,ab(记为 a<b),且不存在uL-{a,b}使a≤u≤b,则称b
覆盖a。
❖ 当a<b时,如有c1,,ckL(k1),使ci+1覆 盖ci(i=1,2,,k-1),且有a=c1<c2<<ck=b,
则称c1,,ck为连接a,b的链。如果L的任
❖ 例：A的幂集格[P(A);,]
❖ 群G的子群格[L(G);,]
❖ [Z+;,]
❖ (Z;)是格，但既无单位元，又无零元。
❖ 零元(单位元)存在则必唯一
❖ 定理：若格[L;,]存在零元0和单位元1， 则0和1分别是L的最小元和最大元。
❖ 由于具有零元和单位元的格一定有最小 元和最大元，称为有界格。
❖ 在格(L;≤)中，对任意两个元素a,bL,可 唯 一 确 定 ab 和 ab, 且 它 们 都 属 于 L， 和看作为集合L上的2个二元运算
❖ 定理17.1:(L;≤)为格,则对任意a,bL有: ❖ (1)a≤ab,b≤ab,ab≤a ab≤b; ❖ (2)a≤b当且仅当ab=b; ❖ (3)a≤b当且仅当ab=a。
❖ 例：S={1,2,3},S3={e,1, 2, 3, 4, 5} 为三次对称群，则(P(S3);)是格，并且 是完全格。取T={{e}, H1,H2,H3,H4,S3},其 中H1={e, 1}; H2={e, 2}; H3={e, 3}; H4={e, 4, 5}都是S3的子群，则(T; )是 格,但它不是(P(S3);)的子格。
何两个元素a<b,总有连接它们的链, 则称
L是离散的。有限的离散全序集的哈斯图
由一条链组成。
❖ 例:设G是一个群,L(G)表示G的所有子群 构成的集合,则L(G)关于集合包含关系 构成一个偏序集, 并且是格. 称为G的子群格
❖ 例:设G是一个群,P(G)表示G的所有正规 子群构成的集合,则P(G)关于集合包含关 系构成一个偏序集 并且是格. 称为G的不变子群格
❖ 定义17.3(L;≤)为偏序集, 当任AL有最大 下界,最小上界时,L显然是格,称为完全格。 L自身的最小上界是整个格L的最大元,记 为1;L自身的最大下界为整个格L的最小 元,记为0。于是任xL,x≤1,0≤x。
❖ 注意: 此处的子集A可以是有限的, 也可 以是无限的。
❖ 例如前面的子群格L(G)是完全格.
❖ 一、格的一般概念
❖ 偏序集(P;≤)是由一个非空的集合P 及在 P上定义的偏序关系≤构成
❖ 在偏序集(P;≤)中，若对任意a,bP有a≤b
或b≤a 时称P为全序。
❖ 定义17.1:设(L;≤)为偏序集, 如果对任意 的a,bL有最小上界与最大下界时,称L为
格 。 以 ab=lub(a,b) 表 示 a,b 的 最 小 上
❖ 非空集合L上和这两个二元运算所具 有性质，[L;,]为一个代数系统。
❖ 定理17.2:(L;≤)为格,任a,b,cL有:
❖ L1幂等律:aa=a,aa=a; ❖ L2交换律:ab=ba,ab=ba; ❖ L3结合律:a(bc)=(ab)c,
❖
a(bc)=(ab)c;
❖ L4吸收律:a(ab)=a, a(ab)=a。
❖ 例:取S={a,b,c},(P(S);)是一个格,其最 大元是S={a,b,c},最小元是。任取一个 子集合有最大下界和最小上界, 如 {{a},{a,c},{c}}的最大下界是,最小上界 是{c};它是一个完全格。
❖ 要说明的是并不是所有的格都是完全格.
❖ 二、作为代数系统的格
❖ (L;≤)为偏序集, 如果对任意的a,bL有最 小上界与最大下界时,称L为格。以 ab=lub(a,b) 表 示 a,b 的 最 小 上 界,ab=glb(a,b)表示a,b的最大下界。而 最小上界和最大下界都是L中的元素。
❖ 例:设B={0,1},≤n为定义在Bn上的关系, 对 任(a1,,an),(b1,,bn)Bn, (a1,,an)≤n (b1,,bn)当且仅当ai≤nbi(1in),显然这是 一个偏序关系。并且(Bn,≤n)是格.
❖ 格的定义是:设(L;≤)为偏序集, 如果对任意的 a,bL有最小上界与最大下界时,称L为格。
❖ 自反:
❖ 反对称:
❖ 传递:
❖ 在代数系统[L;,]中,,满足L1～L4,定义 在L上定义二元关系≤:对任意a,bL,a≤b,当 且仅当ab=b，则(L;≤)为偏序集。
❖ (L;≤)是否为格？
❖ 关键证明存在最小上界和最大下界 ❖ 因此考虑是否能证明ab,ab为最小上界
和最大下界 ❖ 先证明ab是a和b的上界, ❖ 即是否成立a≤ab, b≤ab
❖ 例：Z+表示正整数集，对任意a,bZ+,定 义:ab=(a,b) (最大公因子)
ab=[a,b] (最小公倍数)
,是Z+上的二元运算
它们满足L1～L4 取Z+的子集P={2n|n=1,2,}
有最大下界2,无最小上界，所以它不是 完全格。
❖ 定义：[L;,]为格，若L中存在元素0， 使得对任意的xL有x0=x,则称0为的 单位元，并称0是格的零元；若L中存在 元素1，使得对任意的xL有x1=x,则称 1为的单位元，并称1是格的单位元。