当前位置：文档之家 › 7格与布尔代数

7格与布尔代数

  • 格式：pdf
  • 大小：642.24 KB
  • 文档页数：72

下载文档原格式

  / 72

合集下载

离散数学习题解答(第五章)格与布尔代数

离散数学习题解答(第五章)格与布尔代数

离散数学习题解答习题五（第五章 格与布尔代数）1．设〈L ，≼〉是半序集，≼是L 上的整除关系。

问当L 取下列集合时，〈L ，≼〉是否是格。

a) L={1，2，3，4，6，12} b) L={1，2，3，4，6，8，12} c) L={1，2，3，4，5，6，8，9，10}[解] a) 〈L ，≼〉是格，因为L 中任两个元素都有上、下确界。

b) 〈L ，≼〉不是格。

因为L 中存在着两个元素没有上确界。

例如：812=LUB{8，12}不存在。

c) 〈L ，≼〉不是格。

因为L 中存在着两个元素没有上确界。

16312486312411倒例如：46=LUB{4，6}不存在。

2．设A ，B 是两个集合，f 是从A 到B 的映射。

证明：〈S ，⊆〉是〈2B，⊆〉的子格。

其中S={y|y=f (x)，x ∈2A}[证] 对于任何B 1∈S ，存在着A 1∈2A，使B 1=f （A 1），由于f(A 1)={y|y ∈B ∧(x)(x ∈A 1∧f (x)=y)}⊆B 所以B 1∈2B，故此S ⊆2B；又B 0=f (A)∈S (因为A ∈2A)，所以S 非空；对于任何B 1，B 2∈S ，存在着A 1，A 2∈2A，使得B 1=f (A 1)，B 2=f (A 2)，从而 L ∪B{B 1，B 2}=B 1∪B 2=f (A 1)f (A 2)=f (A 1∪A 2) （习题三的8的1）） 由于A 1∪A 2⊆A ，即A 1∪A 2∈2A，因此f (A 1∪A 2)∈S ，即上确界L ∪B{B 1，B 2}存在。

对于任何B 1，B 2∈S ，定义A 1=f –1(B 1)={x|x ∈A ∧f (x)∈B 1}，A 2=f -1(B 2)={x|x ∈A ∧f (x)∈B 2}，则A 1，A 2∈2A，且显然B 1=f (A 1)，B 2=f (A 2)，于是GLB{B 1，B 2}=B 1∩B 2=f (A 1)∩f (A 2) ⊇f (A 1∩A 2) （习题三的8的2））又若y ∈B 1∩B 2，则y ∈B ，且y ∈B 2。

离散数学作业册

离散数学作业册

第一章命题逻辑命题与逻辑联结词1.判断下列语句是否是命题，不是划“×”，是划“√”，且指出它的真值.(1)所有的素数都是奇数. ( ) 其真值( )(2)明天有离散数学课吗？ ( ) 其真值( )(3)326+>． ( ) 其真值( )(4)实践出真知. ( ) 其真值( )(5)这朵花真好看呀！ ( ) 其真值( )(6)5x=． ( ) 其真值( )(7)太阳系外有宇宙人． ( ) 其真值( )2.将下列命题符号化．(1)如果天下雨，那么我不去图书馆.(2)若地球上没有水和空气，则人类无法生存.(3)我们不能既划船又跑步．(4)大雁北回，春天来了.3.将下列复合命题分解成若干个原子命题，并找出适当的联结词.(1)天下雨，那么我不去图书馆.(2)若地球上没有水和空气，则人类无法生存.命题公式1. 判断下列各式是否是命题公式，不是的划“×”，是的划“√”．(1)(Q R∧S). ( )(2)((R(Q R)(P Q)). ( )(3) (P∨QR)S. ( )(4)((P Q)(Q P)). ( )2．写出五个常用命题联结词的真值表.真值表与等价公式1.指出下列命题的成真赋值与成假赋值．(1)(P∨Q).(2)P(Q P).2.构造真值表，判断下列公式的类型．(1)(P∧Q)∧(P∨Q).(2) P→(P∧┑Q))∨R.3.用等值演算法验证下列各等价式．(1) ((P→Q)∧(Q→R))→(P→R) T.(2)P(Q∧R)(P Q)∧(P R).(3)(P∨Q)∨(P∧Q)P．蕴涵式及其他联结词1.试证明下列各式为重言式．(1)(P Q)∧(Q R)(P R)．(2) (P→Q)→Q⇒P∨Q．(3)(P Q)⇒P Q．2.将下列公式化成与之等价且仅含{┑，∨}中联结词的公式．(1) (P∨Q)∧┑P(2) (P→(Q∨┑R))∧(┑P∧Q)3.证明{，∧}是最小全功能联结词组.4.设A、B、C为任意的三个命题公式，试问下面的结论是否正确？(1)若A∧C B∧C，则A B．(2)若A B，则A B．(3)若A C B C，则A B．对偶与范式1.试给出下列命题公式的对偶式．(1)T∨(P∧Q)．(2)(P∧Q)∧(P∨Q)．2.试求下列各公式的主析取范式和主合取范式．(1) (P→(Q∧R))∧(┑P→(┑Q→R))．(2)((P Q)∧Q)∨R．(3)(P(Q∨R))∧(P∨(Q R)).3.试用将公式化为主范式的方法，证明下列各等价式．(1) (┑P∨Q)∧(P→R)⇔P→(Q∧R)(2) ┑(P↔Q)⇔(P∧┑Q)∨(┑P∧Q)推理理论1.试用推理规则，论证下列各式．(1) ┑(P∧┑Q),┑Q∨R,┑R⇒┑P(2) P∨Q,Q→R,P→S,┑S⇒R∧(P∨Q)(3) ┑P∨Q,┑Q∨R,R→S⇒P→S(4) P∨Q,P→R,Q→S⇒R∨S第二章谓词逻辑词的概念与表示1.用谓词表达写出下列命题．(1)高斯是数学家，但不是文学家.(2)小王既是运动员也是大学生.(3)张宁和李强都是三好学生.(4)若是x奇数，则2x不是奇数.命题函数与量词1.用谓词表达式写出下列命题．(1)每个计算机系的学生都学离散数学.(2)直线A平行于直线B当且仅当直线A不相交于直线B.(3)不存在既是奇数又是偶数的自然数.(4)没有运动员不是强壮的.(5)有些有理数是实数但不是整数.(6)所有学生都钦佩某些教师.谓词公式与变元的约束1.利用谓词公式翻译下列命题． (1)没有一个奇数是偶数.(2)一个整数是奇数，如果它的平方是奇数.2. 设个体域为自然数集N ，令P(x)：x 是素数；E(x)：x 是偶数； O(x)：x 是奇数；D(x ，y)：x 整除y ．将下列各式译成汉语． (1)x(E(x)∧D(x ，6))． (2)x(O(x)y(P(x)D(x ，y)))．3.指出下列表达示中的自由变元和约束变元，并指明量词的辖域． (1)()()(,)()()x F x Q x y xP x R x ∀∧→∃∨． (2)x(P(x ，y)∨Q(z))∧y(R(x ，y)zQ(z))．4.设个体域为A ＝{a ，b ，c}，消去公式xP(x)∧xQ(x)中的量词．谓词演算的等价式与蕴含式1.试证下列等价式或蕴涵式,其中A(x),B(x)表示含x自由变量的公式,A,B 表示不含变量x（不论是自由的还是约束的）的公式.(1)（∀x A(x)→B）⇔(∃x(A(x)→B))．(2)（∃x A(x)→B）⇔∀x(A(x)→B)．2.试将下列公式化成等价的前束范式．(1)∃x（（┑∃yP(x,y)）→(∃zQ(z)→R(x))）．(2)x(F(x)G(x))(xF(x)xG(x))．谓词演算的推理理论1.证明下列推理．(1)所有有理数都是实数，某些有理数是整数。

离散数学第6章 格与布尔代数

离散数学第6章 格与布尔代数
设c是a∧b 的任一下界，即c ≤ a,c ≤ b 则 c∧a=c, c∧b=c c∧(a∧b)=(c∧a)∧b=c∧b=c ∴c ≤ a∧b 故 a∧b是a和b的最大下界
6-1 格的概念
5）下面证明 a∧b=aa∨b=b 若a∧b=a 则 a∨b=(a∧b)∨b=b 反之，若a∨b=b 则 a∧b=a∧(a∨b)=a
b用a∨b代替(∵两式中b是相互独立的) ∴a∨(a∧(a∨b))=a 即 a∨a=a. (2)格的等价定理：〈A，∨，∧〉代数系统，∨.∧满足交换性， 结合性，吸收性，则A上存在偏序关系≤，使〈A，≤〉是一个格
从格可引出代数系统〈A，∨，∧〉； 而从满足三个条件的〈A，∨，∧〉也可导出格〈A，≤〉 证明见书：（格中⑻⑼⑾三个性质很重要，决定了格）
(11) 要证 a≤a∨(a∧b) 第一式显然成立
a∨(a∧b)≤a
a≤a
a∧b≤a
∴a∨(a∧b) ≤a
∴a=a∨(a∧b)
6-1 格的概念
6、格的等价原理：格〈A，≤〉 (1)引理6-1.1：〈A，∨，∧〉代数系统，若∨, ∧满足吸收性，
则∨, ∧满足幂等性 证：a,b∈A. a∨(a∧b)=a a∧(a∨b)=a.
第六章 格与布尔代数
格论是近代数学的一个重要分支，由它所引出的布尔 代数在计算机科学中有很多直接应用。
格的概念 分配格 有补格 布尔代数 布尔表达式
6-1 格的概念
1、回忆偏序集〈A，≤〉，≤偏序关系：满足自反性，反对称性， 传递性。有限集合上的偏序集可用哈斯图来表示：
COV (A) {a,c, b,c, c, d, d,e, d, f }
∧也易求得 ∴ A，∨，∧〉是格〈A，|〉 诱导的代数系统
6-1 格的概念

代数系统简介

代数系统简介

代数系统简介一、代数系统的基本概念代数系统，也称为代数结构或代数系统，是数学中一个重要的概念，它由集合和定义在这个集合上的运算组成。

代数系统是代数学的基本研究对象，也是泛代数、抽象代数、代数学等领域中重要的研究对象。

代数系统通常由两个部分组成：一个是非空元素集合，称为代数系统的论域或标量域；另一个是定义在论域上的运算，这些运算需满足一定的性质或公理。

根据所涉及的运算不同，代数系统可分为不同类型，如群、环、域、格等。

代数系统的概念来源于对数学中不同分支中抽象概念的概括和总结，其研究范围包括数学中不同领域的许多分支。

例如，集合论、抽象代数、泛代数、拓扑学等都是研究代数系统的重要领域。

二、代数系统的分类根据所涉及的运算和性质的不同，代数系统有多种分类方式。

以下是其中几种常见的分类方式：1.根据所涉及的运算的性质，可以将代数系统分为有交换律和结合律的代数系统（如群、环、域）和没有交换律和结合律的代数系统（如格、布尔代数）。

2.根据运算是否涉及单位元和逆元，可以将代数系统分为有单位元的代数系统和无单位元的代数系统。

前者如群、环、域等，后者如格等。

3.根据所涉及的元素是否具有可交换性，可以将代数系统分为可交换的代数系统和不可交换的代数系统。

前者如交换群等，后者如李群等。

4.根据所涉及的元素是否具有无限性，可以将代数系统分为有限代数系统和无限代数系统。

前者如有限群等，后者如无限群等。

此外，还可以根据其他性质和特征对代数系统进行分类。

通过不同的分类方式，我们可以更好地了解和研究不同类型代数系统的特性和性质。

三、代数系统的性质代数系统的性质是指代数系统中元素之间通过运算所表现出来的关系和性质。

以下是几个常见的代数系统的性质：1.封闭性：如果对于代数系统中的任意两个元素x和y，它们的运算结果仍属于该集合，则称该运算满足封闭性。

封闭性是代数系统中一个重要的性质，它保证了运算结果的元素仍属于该系统。

2.结合律：如果对于代数系统中的任意三个元素x、y和z，有(x·y)·z=x·(y·z)，则称该运算满足结合律。

格和布尔代数

格和布尔代数
a,bL，若a≤b a∧b = a
分三步： 1) 证明’≤’是L上的偏序关系 2）证明 a,bL, {a,b}的下确界存在， 且 a∧b = glb(a,b)。 3）a,bL, {a,b}的上确界存在，且 lub(a,b) a∨b 具体证法见后面
1) 证明’≤’是L上的偏序关系 自反性：aL 由等幂律 a∧a=a, a≤a 反对称性：a,bL, 若a≤b, b≤a 则 a∧b=a, b∧a=b a = a∧b = b∧a = b 传递性：a,b,cL, 若 a≤b,b≤c 则a∧b=a, b∧c=b a∧c=(a∧b)∧c = a∧(b∧c)= a∧b=a a≤c
2、格的对偶原理
① 集合S的偏序关系≤的逆关系≥也是偏序关 系，若AS, 其中 ≤的glb(A) 对应于 ≥的lub(A), ≤的lub(A) 对应于 ≥的glb(A), 所以，若<S,≤>是格，则<S,≥>也是格， 称这两个格互为对偶。
2、格的对偶原理
② 因为<S,≤>的交是<S,≥>的并， <S,≤>的并是<S,≥>的交，
一般格只满足分配不等式： a∨(b∧c)≤(a∨b)∧(a∨c)
一、定义
设<L,∧,∨>是格，若a,b,cL，有： (1) a∧(b∨c)=(a∧b)∨(a∧c), (2) a∨(b∧c)=(a∨b)∧(a∨c), 则称 <L,∧,∨> 为分配格。
注：(1)(2)是互相等价的，由对偶原理，从一式可推
2）证明 a,bL, {a,b}的下确界存在， 且 a∧b=glb(a,b)。
a) 因为 (a∧b)∧a =(a∧a)∧b=a∧b a∧b≤a 同理a∧b≤b a∧b 是a,b的下界。

离散数学第五章格与布尔代数2

离散数学第五章格与布尔代数2
离散数学
§2.布尔代数
•布尔代数的定义 •布尔代数的性质 •布尔代数中的宏运算 •有限布尔代数的原子表示 •布尔函数与布尔表达式 •布尔环与布尔代数
2021/5/22
1
离散数学
§2. 布尔代数
定义1.布尔代数(Boolean algebra) 有补的分配格(B,≼, , , , 0, 1) 称为布尔代数。
(S, ,, , , 0, 1) 是布尔代数
这里：S={0,1}，00, 01, 11,其运算表如下：
2021/5/22
3
x
离散数学
x y xy 00 0 01 0 10 0
11 1
xy 0 1 1
1
xx
01 10
表2
通过变元代换，显见表2与表1是完全相同的。即，令
h:S 2X , h (0)= , h (1)= X (这里：X={a})
16
离散数学
[证].布尔代数中的对偶原理实质上来源于两个二元运 算 和 所具有的结合律、交换律、幂等律、吸收律、 分配律的对称性，半序关系≼和其逆关系≽的对称性； 最小元0和最大元1的对称性；以及任何元素x与其补元 x的对称性。
注：•布尔代数(B, ≽ , , , ,1 , 0)称为原布尔代数 (B , ≼ , , , , 0 , 1)的对偶布尔代数。实际上，它们互为对偶；
P Q = (P1 Q1, P2 Q2, , Pn Qn)
P = (P1 , P2 , , Pn) 即n元命题代数的序关系、运算、最小元和最大元的定 义都归结为一元命题代数(ℙ, ≼ , , , , F, T) 。
仿例5我们易证：
(ℙn, ≼ , , , , F, T)≅ (2X, ,, , , , X ) 这里：X={a1, a2, , an}，即 n元命题代数与n元集合代数是同构的。

格与布尔代数


例7.12 设B={0，1}，B n=BxBx…xB，B n中的元 素a=＜a1，a2，…，an＞，b=＜b1，b2，…，bn＞, 其中ai与bi取0或1，＜0，0，…，0＞表示为0n， ＜1，1，…，1＞表示为1n，定义*， ⊕ 与┐运算
如下：
a*b=＜a1*b1，a2*b2，…,an*bn＞,a⊕b＜a1⊕b1， a2⊕b2，…， an⊕bn＞, ┐a=＜┐a1， ┐a2，…，┐an ＞,可验证：＜Bn，*，⊕，┐，0n，1n＞符合条件 （H1）至（H4），故可构成布尔代数。
3、分配格的判定 定理7.7 格L是分配格，当且仅当L中不含有与钻 石格或五角格同构的子格。 推论7.1 （1）小于五元的格都是分配格；（2） 任意一条链都是分配格。 证明P130
例7.7 图7.4中哪个是分配格，哪个不是？
f
f
f
d e
e d
b
c
d
b
c c
e b
a
（a)L1
a
（b)L2
图7.4 格的示意图
7.1 格的基本概念
7.1.1 格的定义 1、格定义7.1 设＜A，≤＞是一个偏序集，对于 Ɐa,b∈A,子集{a，b}在A中都有一个最大下界(也 称为下确界，记为inf{a,b})和一个最小上界(也称 为上确界，记为sup{a,b}),则称＜A，≤＞为 格。
2、诱导的代数系统 定义7.2 设＜A，≤＞是一个格，如果在A上定义两 个二元运算，使得对Ɐa,b∈A，a∧b等于a和b的最 大下界，a∨b等于a和b的最小上界。则称＜A，∧， ∨ ＞为由格＜A，≤＞所诱导的代数系统。
⊕0 1 00 0 10 1
x ┐x
01 10
可验证＜B，*，⊕ ，┐，0，1＞是布尔格，也称为 二值布尔代数。

第六章 格代数

第六章 格和布尔代数
格是一种特殊的代数系统，特殊在:在代数系统中 引入了次序关系,让一个代数系统的载体具有序结构。 1847年由英国数学家G.Boole创立的布尔代数， 最初的设想是利用代数学的方法研究人类的思维规 律。经过后继者的研究，使得它与许多数学分支发 生了联系，如集合论、数理逻辑、代数系统、图论 与组合学。而到上世纪30年代突然发现它与工程技 术又有着意想不到的联系，1950年苏联的 M.A.aBрИЛoB发表了“继电器接点网络原理”，把 基于布尔代数的演算系统发展成为接点网络实用中 的通用理论。目前布尔代数已成为计算机科学的最 重要基础理论之一。
再证a≤b a∨b=b 设a≤b，而b≤b从而a∨b≤b∨b(=b) 而b≤a∨b,故a∨b=b(由≤的反对称性) 反之，设a∨b=b，而a≤a∨b 从而a≤b.
#
15
(11)定理6-1.7 a≤c a∨(b∧c) ≤(a∨b) ∧c Proof:设a≤c 则 a∨c=c Def6-2.2 而 a∨(b∧c)≤ (a∨b)∧(a∨c) 故 a∨(b∧c)≤ (a∨b)∧c 反之，设 a∨(b∧c)≤ (a∨b)∧c， 而 a≤ a∨(b∧c)， (a∨b)∧c ≤c 故 a ≤c（由≤的传递性） # (12)推论 (a∧b)∨(a∧c) ≤a∧(b∨(a∧c)) a∨(b∧(a∨c)) ≤(a∨b) ∧(a∨c) Proof:在(11)中因a∧c≤a可得第一式(以a∧c代替a,a 代c);因a≤a∨c可得第二式(以a代a，以a∨c代c). #
13
(9) 定理6-1.5 a∨(b∧c) ≤(a∨b) ∧(a∨c) (a∧b)∨(a∧c) ≤ a∧(b∨c)(分配不等式) Proof:a≤a∨b a≤a∨c 故a∧a≤(a∨b) ∧(a∨c) 而a= a∧a 故a ≤(a∨b) ∧(a∨c) 另外 b∧c≤b, b≤a∨b故b∧c≤a∨b(传递性) b∧c≤c, c≤a∨c故b∧c≤a∨c(传递性) 故b∧c =(b∧c) ∧(b∧c)≤(a∨b)∧(a∨c) 从而 a∨(b∧c)≤ (a∨b)∧(a∨c)

布尔代数

第五章布尔代数布尔代数最初是作为对逻辑思维法则的研究出现的。

英国哲学家George Boole于1847年的论文“逻辑之数学分析”及“思维法则之研究”中引入了布尔代数。

本世纪30年代C.E. Shannon发表了“继电器和开关电路的符号分析”一文，为布尔代数在工艺技术中的应用开创了道路。

50年代苏联科学家把布尔代数发展成为接点网络实用中的通用理论，从而使布尔代数成为计算机科学中的重要基础理论。

从逻辑上讲，布尔代数是一个命题演算系统;从抽象代数观点讲，布尔代数是一个代数系统;从集合的观点讲，它是一个集合代数;从工程技术的观点讲，布尔代数是电路代数，电子线路的设计离不开它;5.1 布尔代数的基本定义和性质定义5.1.1给定一个具有三个运算的代数结构<S，⊕，⊙，′>，其中，⊕，⊙是S上的二元运算，′是S上的一元运算，0，1∈S。

若对于 x，y，z∈S(1) x⊕y=y⊕x，x⊙y=y⊙x (交换律)(2)x⊕(y⊕z)=(x⊕y)⊕z，x⊙(y⊙z)=(x⊙y)⊙z(结合律)(3)x⊕(y⊙z)=(x⊕y)⊙(x⊕z)，x⊙(y⊕z)=(x⊙y)⊕(x⊙z)(分配律)(4)x⊕0=x，x⊙1=x (同一律)(5)x⊕x′=1，x⊙x′=0(有补律)则称<S，⊕，⊙，′>称为布尔代数(Boolean Algebra)，⊕，⊙，′分别称为它的并(布尔和)，交(布尔积)和补运算，0和1分别称为它的零元和么元。

一个布尔代数通常记为<S，⊕，⊙，′，0，1>。

例5.1.1二值（元）布尔代数<B，⊕，⊙，′，0，1>，其中B={0，1}1⊕1=1⊕0=0⊕1=1，0⊕0=0，1=0′1⊙1=1，1⊙0=0⊙1=0⊙0=0，0=1′例5.1.2集合代数<P(A)，∪，∩，′，Φ，A>例5.1.3*命题代数定理5.1.1在一个布尔代数中，0和1 都是唯一的;定理5.1.2在一个布尔代数中，任一元素的补元是唯一的;证明(利用同一律，有补律和分配律)定理5.1.3在一个布尔代数中<S，⊕，⊙，′0，1>中，则对∀x∈S，(x′) ′=x定理5.1.4条件同上，则0′=1，1′=0;定理5.1.5条件同上，则对∀x∈S，x⊕x=x，x⊙x=x(幂等律)证明(利用同一律，有补律和分配律)定理5.1.6条件同上，则对∀x∈S，x⊕1=1，x⊙0=0(零一律)证明(同定理5.1.5)定理5.1.7条件同上，则对∀x，y∈S，x⊕(x⊙y)=x，x⊙(x⊕y)=x(吸收律)证明(同定理5.1.5)定理5.1.8条件同上，则对∀x，y∈S，(x⊙y)′=x′⊕y′，(x⊕y) ′=x′⊙y′(De morgan律)证明(同定理5.1.5)定理5.1.9条件同上，若对x，y，z∈S，x⊙y=x⊙z，x⊕y=x⊕z，则y=z (消去律)证明(利用集合中类似证明方法)定理5.1.10 条件同上，则对∀x，y∈S，x⊙y=x⇔x⊕y=y证明(利用吸收律)对偶原理: 在布尔代数<S，⊕，⊙，′，0，1>中，若P是某个已经得到证明的定理，将定理中的条件和结论(1)⊕与⊙互换; (2) 0与1 互换则由此而得的新定理仍然成立;5.2 格定理5.2.1设<S，⊕，⊙，′，0，1>为一个布尔代数，则集合≤={<x，y>| x⊙y=x∧x∈S∧y∈S}称为S上的偏序关系。

离散数学(第二版)第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
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。


e

d
10
*9. a≤b a∨b=b a∧b=a 证明：⑴教材 P239 已证 a≤b a∧b=a 这里从略。 ⑵下面证明 a≤b a∨b=b 先证a≤b a∨b=b 设 a≤b，又b≤b ∴ a∨b≤ b 又∵ b≤a∨b 由≤反对称得 a∨b=b 再证 a∨b=b a≤b 已知 a∨b=b ∵ a≤ a∨b ∴ a≤b。 最后得 a≤b a∨b=b
三. 格的性质
<A,∨,∧>是由格<A,≤>诱导的代数系统。a,b,c,d∈A 1. a≤a∨b b≤a∨b a∧b≤a a∧b≤b 此性质由运算∨和∧的定义直接得证。
6
2.如果a≤b，c≤d，则 a∨c≤b∨d，a∧c≤b∧d。 证明：如果a≤b，又b≤b∨d, 由传递性得a≤b∨d, 类似由c≤d， d≤b∨d，由传递性得c≤b∨d, 这说明b∨d是{a,c}的上界，而a∨c是{a,c}的最小上界， 所以a∨c≤b∨d。 类似可证 a∧c≤b∧d。 推论：在一个格中，任何 a,b,c∈A，如果b≤c，则 a∨b≤a∨c，a∧b≤a∧c。 此性质称为格的保序性。 3. ∨和∧都满足交换律。即 a∨b=b∨a，a∧b=b∧a。 此性质由运算∨和∧的定义直接得证。
7
4. ∨和∧都满足幂等律。即 a∨a=a a∧a=a 证明：由性质1 得 a≤a∨a (再证a∨a≤a) 又≤自反得a≤a, 这说明a是{a}的上界，而a∨a是{a}的 最小 上界，所以 a∨a≤ a。最后由反对称得 a∨a=a 。 由对偶原理得 a∧a=a 5. ∨和∧都满足结合律。即 (a∨b)∨c =a∨(b∨c) ， (a∧b)∧c =a∧(b∧c) 。 证明：⑴先证明(a∨b)∨c ≤a∨(b∨c) ∵ a≤ a∨(b∨c) b≤b∨c ≤ a∨(b∨c) ∴ (a∨b) ≤a∨(b∨c) ∵ c≤b∨c ≤ a∨(b∨c) ∴ (a∨b)∨c ≤a∨(b∨c) ⑵同理可证 a∨(b∨c)≤(a∨b)∨c 最后由反对称得 (a∨b)∨c =a∨(b∨c) 类似可证 (a∧b)∧c =a∧(b∧c) 。
这是个很重要的定理，在以后经常用到此结论。
11
四.格的同态与同构
1.定义：设<A1,≤1> 和<A2, ≤2>是两个格，由它们诱导 的代数系统分别是<A1,∨1,∧1>和 <A2,∨2,∧2>，如果存 在映射f:A1A2 使得对任何a,b∈A1, f(a∨1b)=f(a)∨2f(b) f(a∧1b)=f(a)∧2f(b) 则称f是<A1,∨1,∧1>到 <A2,∨2,∧2>的同态映射。 也称<f(A1),≤2>是<A1,≤1> 的同态像。 如果 f 是双射的，就称f是<A1,∨1,∧1>到 <A2,∨2,∧2>， 的格同构，也称格<A1,≤1> 和<A2, ≤2>同构。
第七章 格与布尔代数
布尔代数是计算机逻辑设计的基础，它是由格引出的， 格又是从偏序集引出的。所以我们先回顾一下偏序集。 <A,≤>是偏序集:≤是A上自反,反对称和传递关系(偏序). 偏序集中的元素间的次序可以通过它的Hasse图反映出来. 例如A={1,2,3,6,12,24,36}, ≤是A上整除关系 24。 36。 其Hasse图如图所示，BA B≠Φ 12。 1. B的极小元与极大元 ６。 y是B的极小元y∈B∧x(x∈B∧x≤y) y是B的极大元y∈B∧x(x∈B∧y≤x) ２。 ３。 １。 例如{2,3,6}的极小元:2,3 极大元:6
12
例如<A,≤>, A={1,2,3,6}, ≤是A上整除关系。 <P(E),>, E={a,b} 它们诱导的代数系统分别是<A,∨,∧>和<P(E),∪,∩> 其中∨和∧分别是求两个数的最小公倍数和最大公约数. f P(E) A {a,b} 6 6 {a,b} 2 3 {a} {b} 3 {b} 2 {a} 1 Φ 1 Φ









f(2∨3)=f(6)={a,b} f(2)∪f(3)={a}∪{b}={a,b} f(2∧3)=f(1)=Φ f(2)∩f(3)={a}∩{b}=Φ f(2∨6)=f(6)={a,b} f(2)∪f(6)={a}∪{a,b}={a,b} f(2∧6)=f(2)={a} f(2) ∩ f(6)={a}∩{a,b}={a} 可见它们同构。格同构，它们的图的形状一定相同。
2
7-1 格 (Lattice)
一 . 基本概念 1. 格的定义 <A,≤>是偏序集，如果任何a,b∈A,使得{a,b}都有最大 下界和最小上界，则称<A,≤>是格。 右图的三个偏序 24。 36。 30。 2 集,哪个是格？ 12。
１5
<A,≤>不是格， 因为{24,36} 无最小上界。 １。 １。 <A,≤> <B,≤>和<C,≤> <B,≤> 是格。再看下面三个偏序集，哪个是格？
g <A,≤>

g <B,≤>
d
5
二. 格的对偶原理
设<A,≤>是格，≤的逆关系记作≥，≥也是偏序关系。 所以<A, ≥>也是格，<A,≥>的Hasse图是将<A,≤>的 Hasse图颠倒180º 即可。 格的对偶原理：设P是对任何格都为真的命题，如果将 P中的≤换成≥，∧换成∨，∨换成∧，就得到命题P’ , 称P’为P的对偶命题，则P’对任何格也是为真的命题。 例如：P: a∧b≤a P’: a∨b≥a {a,b}的最大下界≤a {a,b}的最小上界≥a
4
3. 由格诱导的代数系统 设<A, ≤>是格,在A上定义二元运算∨和∧为:a,b∈A a∨b=LUB {a,b}, {a,b}的最小上界.Least Upper Bound a∧b=GLB {a,b}, {a,b}的最大下界.Greatest Lower Bound 称<A,∨,∧>是由格<A,≤>诱导的代数系统. (∨-并,∧-交) a 例如右边的格中a∧b=b a∨b=a b∧c=e
8. ∨和∧不满足分配律。但有分配不等式： a a∨(b∧c)≤ (a∨b)∧(a∨c) ， b (a∧b)∨(a∧c)≤ a∧(b∨c) 。 我们先看右图的例子： c d∨(b∧e)=d∨c=d (d∨b)∧(d∨e) =a∧e=e d≤e 即 d∨(b∧e) ≤ (d∨b)∧(d∨e) 证明：⑴ ∵ a≤a∨b a≤a∨c ∴a ≤(a∨b)∧(a∨c) ∵ b∧c≤b≤ a∨b b∧c≤c≤ a∨c ∴ b∧c ≤(a∨b)∧(a∨c) 于是有 a∨(b∧c) ≤(a∨b)∧(a∨c) 由对偶原理得 a∧(b∨c)≥ (a∧b)∨(a∧c) 。 即 (a∧b)∨(a∧c)≤ a∧(b∨c) 。
1
2. B的最小元与最大元 24。 36。 y是B的最小元y∈B∧x(x∈By≤x) 12。 y是B的最大元y∈B∧x(x∈Bx≤y) ６。 {2,3,6}的最小元:无 最大元: 6 ２。 ３。 B如果有最小元(最大元), 则是唯一的。 １。 3. B的下界与上界 y是B的下界y∈A∧x(x∈By≤x) y是B的上界y∈A∧x(x∈Bx≤y) {2,3,6}的下界:1 上界: 6,12,24,36 4. B的最大下界(下确界)与最小上界(上确界) y是B的最大下界(下确界)：B的所有下界x,有x≤y。 y是B的最小上界(上确界)：B的所有上界x,有y≤x。 {2,3,6}下确界:1 上确界:6 (B若有下(上)确界，则唯一)
2).必要性：已知 f是格<A1,≤1> 到<A2, ≤2> 的同构映射， （证出：任取a,b∈A1, 若a≤1b f (a)≤2f(b) ） a) 先证 a≤1b f (a)≤2f(b) 任取a,b∈A1,设a≤1b ，由格同态保序性得 f(a)≤2 f(b) b)再证f (a)≤2f(b) a≤1b 设 f (a)≤2f(b)， ∴ f(a)=f(a)∧2f(b)=f(a∧1b) ∵f 是入射，∴ a=a∧1b 所以 a≤1b 由a),b)最后得 a≤1b f (a)≤2f(b) 。 定理证毕。 由格的同构得： 具有一、二、三个元素的格分别同构于含有一、二、 a a 三个元素的链。 b a b c

4. 子格：设<A,≤>是格, <A,∨,∧>是由 <A,≤>诱导的代数系统。B是A的非空子 a 集，如果∧和∨在B c b 上封闭，则称<B, ≤> b d e f e 是<A, ≤>的子格。

b



c

d

a

e

c f
a

b

c

<C,≤>是<A,≤>的 <C,≤> 子格。而<B,≤>不是. 因b∧c=dB, (判定子格：看去掉的元素是否影响封闭)
。 6。 。 1。 10。 ６。 4。 3。 2。 5。 ２。 ３。 3。
<C,≤>
3
a
b


1





d
c

2 4



3 5
b


c
e


6
d


e
这三个偏序集，都不是格，第一个与第三个是同构的。 因为 d和e无下界，也无最小上界；b,c虽有下界，但无 最大下界。 第二个图：2,3无最大下界，4,5无最小上界。 2. 平凡格：所有全序都是格，称之为平凡格。 因为全序中任何两个元素x,y，要么x≤y, 要么y≤x。 如果x≤y，则{x,y}的最大下界为x，最小上界为y。 如果y≤x，则{x,y}的最大下界为y，最小上界为 x 。 即这{x,y}的最大下界为较小元素，最小上界为较大元素.