当前位置：文档之家 › 离散数学-新第七章

离散数学-新第七章

  • 格式：ppt
  • 大小：1.21 MB
  • 文档页数：61

下载文档原格式

  / 61

合集下载

离散数学第7章

离散数学第7章

1 v2e4v4e3v3e2v2
初级回路(圈)
2 v2e5v5e6v4e3v3e2v2
初级回路(圈)
3 v2e4v4e3v3e2v2e5v5e6v4e3v3e2v2 复杂回路
…………
5、图中最短的回路。 如图：
6、性质。
定理：在一个
n
阶图中，若从顶点vi
到
v
存在
j
通路(vi vj ) ，则从 vi 到 vj 存在长度小于等于
n 1的通路。
推论：在一个
n
阶图中，若从顶点vi
到
v
存在
j
通路(vi vj ) ，则从 vi 到 vj 存在长度小于等于
n 1的初级通路。
6、性质。
定理：在一个 n 阶图中，若vi 到自身存在回路， 则从 vi 到自身存在长度小于等于n 的回路。 推论：在一个 n 阶图中，若vi 到自身存在一个 简单回路，则从vi到自身存在长度小于等于 n
如例1的(1)中，
v1
v5
e1与 v1, v2 关联的次数均为1， e1
e6
e2 与 v2 关联的次数为2， e2 v2 e4 e5
v4
边 e1, e4, e5, e6都是相邻的， v5 为孤立点，v4 为悬挂点，
e3 v3
e6 为悬挂边，e2 为环，e4, e5 为平行边，重数2，
G 为多重图。
孤立点——无边关联的点。
环——一条边关联的两个顶点重合，称此边
为环 (即两顶点重合的边)。
3、相关概念。 (2) 悬挂点——只有一条边与其关联的点，所
对应的边叫悬挂边。 (3) 平行边——关联于同一对顶点的若干条边
称为平行边。平行边的条数称为重数。 多重图——含有平行边的图。 简单图——不含平行边和环的图。

离散数学第七章部分答案

离散数学第七章部分答案

列各组数中，那些能构成无向图的度数列？那些能构成无向简单图的度数列？（1）1，1，1，2，3（2）2，2，2，2，2（3）3，3，3，3（4）1，2，3，4，5（5）1，3，3，3解答：（1），（2），（3），（5）能构成无向图的度数列。

（1），（2），（3）能构成五项简单图的度数列。

设有向简单图D 的度数列为2，2，3，3，入度列为0，0，2，3，试求D 的出度列。

解：因为 出度=度数-入度，所以出度列为2，2，1，0。

设D 是4阶有向简单图，度数列为3，3，3，3。

它的入度列（或出度列）能为1，1， 1，1吗？解：由定理可知，有向图的总入度=总出度。

该有向图的总入度=1+1+1+1=4,总出度=2+2+2+2=8,4！=8，所以它的出度列（或入度列）不能为1，1，1，1。

35条边，每个顶点的度数至少为3的图最多有几个顶点？解：根据握手定理，所有顶点的度数之和为70，假设每个顶点的度数都为3，则 n 为小于等于370的最大整数，即：２３ ∴ 最多有23个顶点7.7 设n 阶无向简单图G 中，δ（G ）=n-1，问△（G ）应为多少？解： 假设n 阶简单图图n 阶无向完全图，在K n 共有2)1(-n n 条边，各个顶点度数之和为n （n-1）∴每个顶点的度数为nn n )1(-=n-1 ∴△（G ）=δ（G ）=n-1一个n （n ≥２）阶无向简单图Ｇ中，n 为奇数，有r 个奇度数顶点，问Ｇ的补图G 中有几个奇度顶点？解：在K n 图中，每个顶点的度均为（n-1），n 为奇数，在Ｇ中度为奇数的顶点在G 中仍然为奇数，∴共有r 个奇度顶点在G 中７.９ 设Ｄ是n 阶有向简单图，Ｄ’是Ｄ的子图，已知Ｄ’的边数m ’＝n （n-1），问Ｄ的边数m 为多少？解： 在Ｄ’中m ’＝n （n-1） 可见Ｄ’为有个n 阶有向完全图，则Ｄ＝Ｄ’ 即Ｄ’就是Ｄ本身，∴m=n （n-1）有向图D 入图所示。

求D 中长度为4 的通路总数，并指出其中有多少条是回路？又有几条是V3到V4的通路？答: D中长度为四的通路总数：15其中有3条是回路2条是V3到V4的通路评语：此题的结果是对的，但是应该写出求解过程，即：先写出邻接矩阵A，然后求A的四次幂，通过矩阵指出通路或回路的条数。

离散数学(第二版)第7章格和布尔代数和

离散数学(第二版)第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

离散数学第七章二元关系

离散数学第七章二元关系

19
证明
(2) 任取<x,y>, <x,y>∈(FG)1 <y,x>∈FG t (<y,t>∈F∧<t,x>∈G) t (<x,t>∈G1∧<t,y>∈F1) <x,y>∈G1 F1 所以 (F G)1 = G1 F1
20
关系运算的性质
定理7.3 设R为A上的关系, 则 RIA= IAR=R <x,y> <x,y>∈RIA t (<x,t>∈R∧<t,y>∈IA) t (<x,t>∈R∧t=y∧y∈A) <x,y>∈R
例如 A = P(B) = {,{a},{b},{a,b}}, 则 A上的包含关系是 R = {<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>, <{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>} 类似的还可以定义： 大于等于关系, 小于关系, 大于关系, 真包含关系等.
注意： 关系矩阵适合表示从A到B的关系或A上的关系（A,B为有 穷集） 关系图适合表示有穷集A上的关系
11
实例
例4 A={1,2,3,4}, R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}, R的关系矩阵MR和关系图GR如下：
1 1 0 0 0 0 1 1 MR 0 0 0 0 0 1 0 0
10
关系的表示

离散数学第七章__环

离散数学第七章__环
规定:
n na a a a (n)a (na), 0a 0
则有：
ma na (m n)a m na mn a
0a a 0 0（0为Ｒ中零元）
n(a b) na nb
定义 一个集合（Ｒ，+，。）叫做环，假如
(a)(b) ab
a(b1 b2 bn ) ab1 ab2 abn
a b
ibn amb1 ambn
(na) b a(nb) n(ab)
规定：
n n a aa a
a0 和
ab ac ab ac 0 a(b c) 0
得
b c 0 即 b c 消去律成立。
反之，假设消去律成立，因为
ab 0 ab a 0
所以由消去律知若 a
0则 b0
所以环Ｒ没有零因子。
推论: 一个环若有一个消去律成立，则另一个消去律 也成立。
a0 1
定义（含单位元的环）：（R，。）是单元半 群 常见的环：整数环，有理数环，实数环。 推论：（R，。）不可能构成群。 （因为0元无逆元）
运算规则：
(a b)c ac bc c(a b) ca cb
0a a 0 0 （0为Ｒ中零元）
(a)b a(b) ab
则对任何整数都有
a a a
m n
mn
(a ) a
m n
mn
定义：若在一个环Ｒ里
a 0, b 0 但 ab 0
则称a是环Ｒ的一个左零因子，b是环Ｒ的一个右零因子。
例 Ｒ＝｛所有模n的剩余类｝规定R中的加法和乘法如 下：
[a] [b] [a b] [a][b] [ab]

离散数学-新第七章

离散数学-新第七章

是可传递的。
由上证得 ~也是偏序关系。
2
例1 设 A=1,2,3,6，定义 A 上的整除关系 ：
当旦仅当 a 整除 b 时，有 a b 。
由定义 = ( 1 , 1 ) ( 1 , 2 ) ,( 1 , 3 ) , ( 1 , 6 ) ,2 , 2 ) ( ( 2 , 6 , ) ( 3 , 3 ) ,( 3 , 6 , ) ( 6 , 6 , )
第七章 格
一偏序集
1.偏序集
定义7-1 集合L和定义在 L 上的偏序关系 “≤”
一起称为偏序集，用<L；≤ >表示。
<R；≤>，<I：≤>，<2U；>和<N；|>都是偏 序集。
~
若 是集合A上的偏序关系，则 的逆关系 也必是Ａ上的偏序关系，证明如下：
1
１．对任意的 a Ａ，因为 自反，所以有
(7 4) (75 ) (74 ) (75 )
(71)~(75)、(71)~(75)这十个 关系式代表了格。 的定义
12
2．格的性质
定理7-3 在格<L；≤>中，对于任意 1,2L
以下三式中若任意一式成立，那么其它两式也成立.
( 1 )( l 1 l 2 l 1 )( 2 ; )( l 1 l 2 l 2 )( 3 ; ) ( l 2 l 1 )
于是，由（5-5） l1l1(l1l2) （2）
由（1)、(2）和反对称性
得l1(l1l2)l1.
18
定理7-7 （等幂律） 设＜L；≤＞是格，则对任意 l L ，有
(a )l l l; (b )l l l.
证明 （a）由定理7-6 ,

《离散数学》课件-第七章 图的基本概念

• 〔u，v〕∈E1〔f(u)，f(v)〕∈E2 • (或<u，v>∈E1 <f(u)，f(v)>∈E2) • 且重数相同，则称G1同构于G2，记为
• G1 G2。
• 显然，两图的同构是相互的，即G1同构 于G2，G2同构于G1。
• 由同构的定义可知，不仅结点之间要具 有一一对应关系，而且要求这种对应关 系保持结点间的邻接关系。对于有向图 的同构还要求保持边的方向。
V={a,b,c,d},E={e1,e2,e3,e4,e5,e6}
e1=(a,b), e2=(a,c), e3=(b,d), e4=(b,c), e5=(d,c), e6=(a,d).
它的图形如下图(a)或(b)所示:
a
a
b
d
b
d
c
c
(a)
(b)
如果有些边是有向边，另一些边是无向边， 图G称为混合图。
第七章 图的基本概念
– 7.1 无向图及有向图 – 7.2 通路、回路、图的连通性 – 7.3 图的矩阵表示 – 7.4 最短路径及关健路径
7.1 无向图和有向图
• 什么是图?可用一句话概括，即：图是用 点和线来刻划离散事物集合中的每对事 物间以某种方式相联系的数学模型。
Konigsberg(哥尼斯堡)七桥问题
为偶数.
定理7.2 在任何有向图中,所有结点的入度之 和必等于它们的出度之和.
证明:因为有向图中的每一条有向边都恰好对应 一个出度和一个入度.故所有结点的出度之 和恰好等于有向边的总数.同样地, 所有结 点的入度之和恰好也等于有向边的总数.因 此它们相等.
设V={v1,…,vn}为G的顶点集，则称{d(v1),…d(vn)} 为G的度数序列。
• 如果G2无孤立结点，且由E2所唯一确定，即 以E2为边集，以E2中边关联的结点全体为顶 点集，则称G2是边集E2的导出子图。

离散数学第7章群、环和域

所以，(x∗y)∗z=x∗(y∗z)，故<R,*>是一个半群。 7.1.2 独异点 定义7.1.3 设G,*是半群，如果运算*的单位元eG，
则称半群G,*为含幺半群或独异点。
第7章 群、环和域
若G,*为独异点，且*是可交换的，则称G,*为可换 的独异点。
例如，设A是任一集合，P (A)是A的幂集合。集合并运算 ∪在P (A)上是封闭的，并运算∪的单位元P (A)，所以半 群<P (A),∪>是独异点；交运算∩在P (A)上也是封闭的，交运 算∩的单位元AP (A)，所以半群<P (A),∩>也是独异点。显
第7章 群、环和域
⑴ (a–1)–1=a ⑵ a*b有逆元，且(a*b)–1=b–1*a–1 证明：⑴ 因a*a–1=a–1*a =e，故(a–1)–1=a ⑵ 因(a*b)*(b–1* a–1)=(a*(b*b–1)*a–1
=a*e*a–1=a*a–1=e 又
(b–1* a–1)*(a*b)=(b–1*a–1)*(a*b) =b–1*(a–1*a)*b=b–1*e*b=b–1*b=e
第7章 群、环和域
返回总目录
第7章 群、环和域
第7章 群、环和域
7.1半群和独异点
7.1.1广群和半群 代数系统<S,*>又称为广群。 定义7.1.1 设<S,*>是代数系统，*是S上的二元运算，如 果*满足结合律，则称代数系统<S,*>为半群。
例如，代数系统<I,＋>、R,·、<P(a),∪>、<P(a),∩>、
则称该群为阿贝尔(Abel)群，或称可交换群。 整数加法群I,＋中的加法运算是可交换的，所以，整
数加法群是阿贝尔群，群R-0,·中的乘法运算也是可交 换的，所以，R-0,·也是阿贝尔群。

离散数学第七章图的基本概念


4.无向图的连通性
若无向图G中任何两顶点都连通,则称G是连通图.
对于任意的无向图G.设V1,V2,…,Vk是顶点之间连通关系的 等价类,则称他们的导出子图为G的连通分支.用p(G)表示G 的连通分支数.
V1 e1
e2 e3
V3
e4 V2
V4
a
de
h
i
b
c
f
g
5.有向图的连通性
若略去有向图D中各边的键头,所得无向图是无向连通图,则 称D是弱连通图(或称D是连通图).
(2) mij d (vi )(i 1,2,..., n)
j 1
mn
nm
n
(3) mij mij d(vi ) 2m
j1 i1
i1 j1
i 1
m
(4) mij 0 vi是孤立点 j 1
(5)若第j列与第k列相同, 则说明e j与ek为平行边.
2.有向图的关联矩阵
设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em} 1, vi为ej的始点
e1,e2,e3},{e1,e2,
e2
e4},{e9}等边割集 ,e9是桥.
e3 V4
e5 e6
V5 e4
V6
e9
V7
7.3 图的矩阵表示
1.无向图的关联矩阵
设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}
令mij为顶点vi与ej的关联次数, 则称(mij)n×m为G的关联矩阵.记为M(G)
若Γ 满足:vi-1,vi为ei的端点(若G为有向图,vi-1是ei的始 点,vi是ei的终点)i=1,2,…,k,则称Γ 为G中通路,v0,vk分 别称为通路的始点和终点,Γ 中边的数目k称为通路长度.

离散数学--第7章 图论-2(路与连通)

u1 v4 v1 v4 v3 u4 v2 u4 u3 G2 v3 u u13 v1 u2 v2 u2
15
连通图可以看成是只有一个连通分支的图，即 w(G ) 1 。
返回 结束
7.2.2 图的连通性
4、有向图的连通
强连通—— G 中任一对顶点都互相可达 (双向) 连通 单向连通—— G 中任一对顶点至少一 向可达
路
10
(vi v j ) ，则从 vi 到 v j 存在长度小于等于
n 1的路。
证明思路：多于n-1条边的路中必有重复出现的结点，反 复删去夹在两个重复结点之间的边之后，剩余的边数不会 超过n-1条边。
v n 在一个 阶图中，若从顶点 i 到 v j 存在 推论：
通路(vi v j ) ，则从 vi 到 v j 存在长度小于等于
返回 结束
7.2.2 图的连通性
7.2.2 图的j 存在路，称 有向图中，从 vi 到 v j 存在路，称 (注意方向) 2、短程线，距离。 短程线——连通或可达的两点间长度最短的 路。 距离——短程线的长度，
12
vi 到 v j 是 连通的(双向)。 vi 可达 v j 。
1 v1e1v2e5v5e7v6 2 v1e1v2e2v3e3v4e4v2e5v5e7v6
3 v1e1v2e5v5e6v4e4v2e5v5e7v6
…………
初级通路
简单通路
复杂通路
返回 结束
7.2.1 路
例1、(2)
7
图(2)中过 v 2 的回路 (从 v 2 到 v 2 )有：
1 v2e4v4e3v3e2v2 2 v2e5v5e6v4e3v3e2v2
7.2 路与连通
内容：图的通路，回路，连通性。 重点：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
小元素是唯一的。如果<L；≤>有最大元素，则最大元 素也是唯一的。
证明 设 a 1 和 a2都是<L；≤>的最小元素，则有
a 1 ≤ a2 ，且 a2 ≤ a 1 ，得 a 1 ＝a2。
9
二、 格
1．格的定义
定义7-4 设<L；≤>是一个偏序集，如果L中
任意两个元素都存在着最大下界和最小上界，则称<L； ≤>是格。
6 4
3
1
(6∧3)∨(6∧4)= 3∨1= 3
于是 6∧(3∨4)≠(6∧3)∨(6∧4)
21
定理7-10 设<L；≤>是格，则对任意
l1,l2,l3 L ,有
(a ) l1 (l2 l3)(l1 l2) (l1 l3) (b ) l1 (l2 l3)(l1 l2) (l1 l3)
由 (54) al1,al2l3 , 且 l2l3l2 , l2l3l3 ,
由传a递 l2,性 al3 ,
又 a l 1 由 ,a l 2 和 5 － 5 ） （ a l 1 有 l 2 ,
由 a l 1 l 2 和 a l 3 和 5 5 ） ， a （ ( l 1 l 2 ) l 3 , 即 a b . 类似的方法b可 a以 。证 于明 是由反a对 b.称 17
∧都是二元运算，满足交换律，结合律和吸收律，则在L上必 存在一偏序关系，使得<L ; ≤ >是一个格。
③ => ① 设 l2 l1 ,
由自反l性 1 l1, 因此 l1l1, l1l2,
由 5 － 5 （ ） l1 l1 l2,
又7 由 4 ） l（ 1 l2l1.
故由反对 l1称 l2性 l1 .定理结论得
14
定义7-5 设<L；≤>是格，P是包含 格的元素和符号=、≤、≥，∧ ，∨的命题， 将P中的≤、≥，∧和∨分别替换成≥、 ≤、 ∨和∧所得的命题PD称为P的对偶。
是可传递的。Βιβλιοθήκη 由上证得 ~也是偏序关系。
2
例1 设 A=1,2,3,6，定义 A 上的整除关系 ：
当旦仅当 a 整除 b 时，有 a b 。
由定义 = ( 1 , 1 ) ( 1 , 2 ) ,( 1 , 3 ) , ( 1 , 6 ) ,2 , 2 ) ( ( 2 , 6 , ) ( 3 , 3 ) ,( 3 , 6 , ) ( 6 , 6 , )
第七章 格
一偏序集
1.偏序集
定义7-1 集合L和定义在 L 上的偏序关系 “≤”
一起称为偏序集，用<L；≤ >表示。
<R；≤>，<I：≤>，<2U；>和<N；|>都是偏 序集。
~
若 是集合A上的偏序关系，则 的逆关系 也必是Ａ上的偏序关系，证明如下：
1
１．对任意的 a Ａ，因为 自反，所以有
定理7-9 （格的保序性）
设＜L；≤＞是格，则对于任意 l1,l2,l3,l4L ，有
（ 1 ） l2 若 l3,则 l1 l2l1 l3,l1 l2l1 l3
（ 2 ） l1 若 l3,l2l4 ,则 l1 l2l3 l4,l1 l2l3 l4
证明 （1）
l1l3l1 l1l3l3
根据逆关系的定义
~ p= ( 1 , 1 ) ( 2 , 1 ) , ( 3 , 1 ) , ( 6 , 1 ) , 2 , 2 ) ( ( 6 , 2 , ) ( 3 , 3 ) ,( 6 , 3 , ) ( 6 , 6 , )
的次序图如下
~ p的次序图如下
6
1
2
3
1
2
3
6
3
若<L； >是一个偏序集，则对于任意元素
由 传 递 性 l1， l2 l有 3l4
20
例4 设 L = 1,3,4,6,1 2 ，L上的整除关系
与L构成一个格，记作<L；≤>，
12
3∨( 6 ∧ 4 ) = 3 ∨ 1= 3 (3∨6)∧(3∨4) = 6 ∧ 12 = 6 于是 3∨(6∧4)≠(3∨6)∧(3∨4)
6∧(3∨4) = 6∧12 = 6
1
2
两个元素，如果 1 和 有glb,则glb是唯一的，
2
如果
和 1
有l ub，则lub是唯一的。 2
证明 设 a 1 和 a2 都是 1和 2 的glb，
由定义7-1，则 a2 ≤ a1, a1 ≤ a2 ,于是有 a1= a。2
类似地可以证明, 1 和 2 若存在lub，则
由于6 12，6 18，6 6，因此，lub（2，3）=6。
6 ≤ 12，6 ≤ 18；2 ≤ 12，2 ≤ 18；3 ≤ 12，3 ≤ 18；1 ≤ 12,1 ≤ 18；
因1 ≤ 6，2 ≤ 6，3 ≤ 6，所以glb(12,18)＝6。
6
例3 设A= 1,2,3,1,1 8,2 36，整除关系是A上
证明 （a）由(5-4)有
2l3l2, 2l3l3
于是，根据定理5-19有 l1(l2l3)l1l2
又由（5-4）有
l1(l2l3)l1l3
l1 (l2 l3 ) (l1 l2 ) (l1 l3 ) 22
7．2 格是一种代数系统
定理7-10 设<L;∨,∧ >是一个代数系统，其中∨和
最小上界，简记作b=lub( 1, 2)
5
例2 设A= 1,2,3,6,9,1,1 2,2 87“整除”关系是A上
的偏序关系，其次序图如下，因此，它们构成一个
27
偏序集<A； >。
12 18
lub(2,3)=？， glb(12,18)=?， lub(18,27)=?
6
9
2
3
1
有2 6，3 6；2 12，3 12；2 18，3 18。
1, 2, 3 L，有以下六个关系式成立：
1 1
若 1 2 ，2 1，则 1= 2
（7-1） （7-2）
若 1 2 ，2 3，则 1 3 1 1
(7-3)
(7- 1 )
若 1 2 ， 2 1，则 1= 2 (7- 2 )
(7 4) (75 ) (74 ) (75 )
(71)~(75)、(71)~(75)这十个 关系式代表了格。 的定义
12
2．格的性质
定理7-3 在格<L；≤>中，对于任意 1,2L
以下三式中若任意一式成立，那么其它两式也成立.
( 1 )( l 1 l 2 l 1 )( 2 ; )( l 1 l 2 l 2 )( 3 ; ) ( l 2 l 1 )
lub也一定是唯一的。 8
3 最小元素和最大元素
定义7-3 设<L；≤>是一偏序集。
(1) 如果存在元素aL，使得对于所有的元素 L，
有a ≤ ，则称a是<L；≤>的最小元素。
(2) 如果存在元素bL，使得对于所有的元素 L，
有 ≤b，则称b是<L；≤>的最大元素。 定理7-2 如果偏序集<L；≤>有最小元素，则最
设 1和 2是偏序集<L；>中的两个元素,
元素a L，如果满足a 1,a 2 ,则称a是 1和 2的
下界。
如果元素a是 1和 2的下界。且对于任意 aL，若 a 也是 1和 2的下界，便有 a a ,则称a是 1和 2的 最大下界，简记作a=glb( 1 , 2).
证明 ① =＞ ② 设 l1l2 l1 ，
由7（ 4）l有 2l1,又由自 l2反 l2, 性
于是 75 由 ） l2 （ l1l2.
另一方面 由(7， 4) l1 l2 l2 , 故由反对称 l1 性 l2 有 l2
13
② => ③ 设 l1l2l2,
由 ( 5 4 )l 1 l2 l 1 ,即 l2 l 1
定理7-6 （吸收律）
设＜L；≤＞是格，则对任意 l1 , l2 L ，有
( a ) l 1 ( l 1 l 2 ) l 1 ; ( b ) l 1 ( l 1 l 2 ) l 1
证明 (b) 由（5-4） l1 (l1 l2 ) l1 (1 )
另一方面，由（5-1）l1l1,由 (54)l1l1l2
（a,a）,于是（a,a）~，因此 ~
也是自反的。
２．对任意 a ,b A ，若（a,b）~且（b,a）~ ，
则有（b,a） 且（a,b） ，必有a = b，
因此 ~是反对称的。
３．对任意a,b,c A,若（a,b）~,(b,c）~，
则有（c,b）且（b,a），必有 （c,a），于是（a,c）~ ，因此 ~
定义7-2 设 1和 2是偏序集<L； >中的两个元素，
元素 b L ,如果满足 1 b， 2 b，则称 b是 1 和 2的上界。
如果元素 b是 1和 2的上界，且对于任意bL，若 b
也是 1和 2的上界，便有b b，则称 b 是 1和 2的
的偏序关系，其次序图如下
36
试问 glb(18,12)=?, lub(2,3)=?
2≤18，2 ≤ 12；3 ≤ 18，3 ≤ 12，1 ≤ 18，1 ≤ 12。
18
12
2
3
1
但glb(18,12)不存在。
类似地，12，18 和 36 均是 2 和 3 的上界， 但 lub（2，3）不存在。
7
定理7-1 设 和 是偏序集<L；≤>的
若 1 2 ， 2 3，则 1 3 (7- 3)