文档介绍：离散数学课件第六章序关系和结构
2
———————————————————————————————— 作者：
———————————————————————————————— 日期：
个人收集 仅供参考学****勿做商业用途
第六章序关系和构造Order Relations and Structures
§ 偏序集Partial Ordered Sets
关系 Relation
定义
A Relation R From A to B is a subset of A´B
A relation on A is a subset of A´A
矩阵表示，图表示。
性质
自反 reflextive
DÍR
对称 symmetric, asymmetric, antisymmetric
R-1=R, R-1ÇRÍD, R-1ÇR=Æ
传递 transive
R2ÍR or R¥=R
3
个人收集 仅供参考学****勿做商业用途
传递闭包 Wallshall算法O(n3)
等价关系 =
偏序关系Partial Order £
Definition
1. 自反 Reflexive
"aÎA, (a,a)ÎR
2．反对称antisymmetric
"a,bÎA (a,b)∈R∧(b,a)∈R Þ a=b
3．传递Transitive
"a,b,cÎA (a,b)∈R ∧ (b,c)∈R Þ (a,c)∈R.
Examples
<N, £>, <Q, £>, <N, |>, <D12,|>, <P(A),Í>
4
个人收集 仅供参考学****勿做商业用途
例4． R，S都是A上等价关系, RÍSÛxRy→xSy, R：A上全体等价关系， (R ，Í)构成偏序。
对偶偏序集：
如果R是A上偏序，那么R－1也是A上偏序。〔A，R－1〕称为〔A，R〕的对偶偏序集。 〔A，≥〕是〔A，≤〕的对偶偏序。
全序关系，线性序关系linear order，链chain
偏序.＋4
4． "a,bÎA,(a,b)ÎR∨(b,a)∈R.
字典序
偏序乘积
定理1如果(A,≤)，(B,≤)是偏序，那么(A×B，≤)是乘积偏序product partial order，其中≤定义为： (a,b)≤(a’,b’)Ûa≤a’Ùb≤b’
偏序与严格序
设〔A，≤〕是偏序， 令a<bÛa≤b，a
5
个人收集 仅供参考学****勿做商业用途
≠b， 称〔A，<〕严格序， 大于，小于都是严格线性序。
反之假设〔A，<〕是严格序， 令a≤bÛa<bÚa=b, 那么(A,≤)是偏序。
字典序
二元
(A×B，≤)中，令(a,b)<(a’,b’)Ûa<a’or a=a’,b<b’ <是字典序lexicographic
n元(A，≤〕是偏序，
An＝A×A×……×A
(a1,a2,……,an)<(b1,b2,……,bn)
Û a1<b1∨a1=b1∧a2<b2∨……
∨a1=b1∧……∧an<bn
不等长
(a1,a2,……,an)<(b1,b2,……,bm)
6
个人收集 仅供参考学****勿做商业用途
If n=m
If n<m (a1,a2,……,an)£(b