离散数学课件第六章序关系和结构.doc

第六章序关系和结构 Order Relations and Structures§6.1 偏序集 Partial Ordered Sets关系 Relation定义A Relation R From A to B is a subset of ABA relation on A is a subset of AA矩阵表示，图表示性质自反 reflextiveR对称 symmetric, asymmetric, antisymmetricR-1=R, R-1R, R-1R=传递 transiveR2R or R=R传递闭包 Wallshall 算法 O(n3)等价关系 =偏序关系 Partial Order Definition1. 自反 ReflexiveaA, (a,a)R2．反对称 antisymmetrica,bA (a,b)∈R∧(b,a)∈R  a=b3．传递 Transitivea,b,cA (a,b)∈R ∧ (b,c)∈R  (a,c)∈R.Examples, , , , 例 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偏序 1.2.3.＋44． 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，≤）是偏序， 令am (a1,a2,……,am)a’.定理 3. 偏序集 A 中，BA，B 至多一个上确界，至多一个下确界定理 4. 设 f：（A，≤）→（A’,≤’ ）是偏序同构，（a） a 是 A 的极大（极小）元，则 f(a)是 A’的极大（极小）元b） a 是 A 的最大（最小）元，则 f(a)是 A’的最大（最小）元c） BA， a 是 B 的上（下）界，则 f(a)是f(B)的上（下）界（d） BA， a 是 B 的上确（下）界，则f(a)是 f(B)的上（下）确界Homework P206－20716，26，33§6.3 格 Lattices定义 格是一个偏序集（L，≤） ，任意a，b∈L，a，b 有上下确界。

令 a∨b＝LUB(a,b), a∧b＝GLB(a,b).格 (L,≤，∨，∧)例 1． （P(S), ）是格，A∨B＝A∪B，A∧B＝A∩B记做（P(S), ,∪,∩）例 2． （Z ＋ ，| ）是格，a∨b＝LCM(a,b),a∧b＝GCD(a,b).例 3．令 Dn是 n 的所有正因子的集合，（D n，|）是格D20＝{1,2,4,5,10,20}, D30={1,2,3,5,6,10,15,20}线性序是格例 4． Hasse 图是否格的判断abcdab cdab cdeab cde eab cdab cdef g例 5． R：A 上全体等价关系，偏序（R ，）是格R∧S＝R∩SR∨S＝(R∪S) ∞设（L，≤）是格，则对偶（L，≥）也是格问题 6.3.1 1)格的判定算法？2)格的运算表生成？定理 1.乘积格设（L 1,≤,∨,∧） ，（L 2,≤,∨,∧）都是格则（L 1×L2，≤,∨,∧）也是格a,b)∨(c,d)=(a∨c, b∨d)(a,b)∧(c,d)=(a∧c, b∧d)子格 sublattice设（L，≤）是格，SL，S 对∨，∧封闭，即 a，b∈Sa∨b ，a∧b∈S 。

记做(S，≤,∨,∧)  (L，≤,∨,∧)或 格 S  L例如(Dn，|, LCM, GCD) (Z+, |, LCM,GCD)例 9egab cdfegb cfegab cdfab cd格的同构 Isomorphic Latticesf：(L 1,≤,∨,∧)→(L 2,≤,∨,∧)，f 是 L1 到 L2 的序同构，则 f 保持∨，∧运算，f(a∨b)=f(a)∨f(b)f(a∧b)=f(a)∧f(b)格同构也记做 L1L2D6P({a,b}).问题 （6.3.2） 1） D n 同构与 (P(S), ≤)的充分必要条件？ 2）D n 同构与 Dm的充分必要条件是什么？格的性质 Properties of Lattices定理 2 设 L 是格，则 a≤b  a∨b ＝b  a∧b ＝a.定理 3.设 L 是格，则 L 具有如下性质：幂等律 a∨a＝a， a∧a＝a交换律a∨b＝b∨a，a∧b＝b∧a结合律a∨(b∨c)=(a∨b)∨c,a∧ (b∧c)=(a∧b)∧c吸收律a∨(a∧b)=a, a∧(a∨b)=a定理 3’ 设集合 L 上有运算∨，∧， （L,∨,∧）满足幂等律，交换律，结合律，吸收律，则L 是格。

证明.1）a∨b＝b iff a∧b＝a a∧b＝a∧(a∨b)=a. a∨b＝a∨(a∧b)=a.2）定义 L 上≤关系：a≤b iff a∨b＝b iff a∧b＝a3）≤是 L 上偏序：1）自反性：由 a∨a＝a，得 a≤a 2）反对称性：设 a≤b，b≤a，a＝a∧b＝b∧a＝b，3）传递性设 a≤b，b≤c，a∨c＝a∨(b∨c)＝(a∨b)∨c＝b∨c＝ca≤c4）a∨b，a∧b 分别是上下确界a∨b 上界：a∧(a∨b)=a, a≤a∨bb∧(a∨b)=b, b≤a∨ba∨b 上确界设 a≤c，b≤c，(a∨b)∨c=a∨(b∨c)=a∨c＝ca∨b≤ca∨b 是 a，b 的最小上界定理 4. 设 L 是格，1）如果 a≤b，则（a）a∨c≤b∨c（b）a∧c≤b∧c2）a≤c，b≤c iff a∨b≤c3）c≤a，c≤b iff c≤a∧b4）如果 a≤b，c≤d 则a∨c≤b∨d 且 a∧c≤b∧d有界格有界格 Bounded lattice：有最大元 1，最小元 0 的格叫有界格L 是有界格，则对任意 a∈L，有 0，1 律成立1）0≤a≤12）a∨0＝a，a∧0＝03）a∨1＝1，a∧1＝a定理 5. L 是有限格，则 L 有界。

分配格 Distributive Lattice：1. a∧(b∨c)＝(a∧b)∨(a∧c)2. a∨(b∧c)＝(a∨b)∧(a∨c)12(a∨b)∧(a∨c)=((a∨b)∧a)∨((a∨b)∧c)=a∨((a∨b)∧c)=a∨((a∧c)∨(b∧c))=a∨(b∧c)例 16．格(P(S),∪,∩)是分配格例 18．下列格ab cdeab cde定理 6 格 L 不是分配格当且仅当 L 含有例18 中的子格可补格 Complement Lattice.有界格 L 是可补格，如果任意 a∈L，有a’∈L，使a∨a’=1，a∧a’=0.称 a’为 a 的补元cba101a b c0例 19．格(P(S),∪,∩)是可补格例 21．D 20，D 30都是可补格定理 7. 设 L 是有界格，a∈L，如果 a 有补元，则其补元唯一证明. 设 a’,a”都是 a 的补元则 a’=a’∨0＝a’∨(a∧a”)＝(a’∨a)∧(a’∨a”)= a’∨a”a”=a”∨0＝a”∨(a∧a’)＝(a”∨a)∧(a”∨a’)= a’∨a”因此 a’=a”.Homework P216－21712，14，18，21，23，24，27，31，33§6.4 有限布尔代数Finite Boolean Algeblas0定理 1 设 S1＝{x 1,x2,……,xn},S2＝{y 1,y2,……,yn}，则格（P(S 1), ）（P(S 2),）.证明. 令 f：S 1→S 2，f(xi)=yi , i=1,2,……,n.则 f： P(S1)→P(S 2)是格同构。

1. 任意 A∈P(S 1), AS1,f(A)  S2,是一一对应2. 任意 A，B∈P(S 1), AB,f(A)  f(B). f 保序定义：|S|=n, 格（ P(S1), ）记做 BnBn 是布尔代数定理 2. n=p1p2……pk时，D n是布尔代数证明. 令 S＝{p 1,p2,……,pk}Dn 中的元素 m=pk1*,...,pkmP(S)中的元素 T={pk1,…,pkm}f: P(S)→ Dnf(T)=pk1*…*pkm 只需证明 f 是同构对应1） f 是一一映射2） T1T2→f(T 1)|f(T2)显然成立例 D1001 是布尔代数定理 3. 设 B 是布尔代数，x，y∈B ，1．(x’)’=x,2. (x∧ y)’=x’∨y’. De. Morgan 律3. (x∨ y)’=x’∧y’布尔代数的性质：交换律 commutativepropertiesx∧y y∧xx∨y y∨x结合律 associative properties(x∧y) ∧rx∧(y∧r).(x∨y)∨rx∨(y∨r).分配律 distributive propertiesx∧ (y∨ r) x∧y∨x∧r.x∨(y∧ r)  (x∨y) ∧(x∨r).幂等律 idempotent propertiesx∨x x.x∧x x.双重否定 property of negation9． x’’xDe Morgan’s law10. (x∨y)’ x’∧y’11. (x∧y)’ x’∨y’吸收律12 x∨(x ∧y) ＝ x13 x∧(x ∨y) ＝ x01 律14．x∨0＝x，x∧0＝015．x∨1＝1，x∧1＝x16. x∨x’=1, x∧x’=017. 1’=0, 0’=1 例 7．P230 图 6.62 不是布尔代数。

例 8．p 2|n, p 是素数，则 Dn 不是布尔代数证明.设 Dn 是布尔代数p2|n, n=p2k. p∈D n，p’ ∈D np∧p’＝ 0，GCD(p,p’)=1,p∨p’＝ 1，LCM(p,p’)=n.GCD(p,p’)＝1 ～p|p’.LCM(p,p’)=n=p2kp|p’.矛盾例 9．D 12 不是布尔代数定理 4. BnB×B×……×BBnB×B×……×B， n 个B 的卡氏积证明.令 f：B n→B ×B×……×BS＝{ x1x2……xn}, Bn＝P(S).Bn 中任意元素 A ={xk1,…,xkm}B×B×……×B 中的任意元素 a=(a1,…,an), ai{0,1}令 f(A)= (a1,…,an) If xiA then ai=1 If xiA then ai=0其中 只需证明 f 是同构对应1) f 是一一映射2) AB iff (a1,…,an)≤(b 1,…,bn)，显然成立Bn= B×B×……×B设 x＝a 1a2……ak， y＝b 1b2……bk∈B n1．x≤y iff a k≤b k，k＝1,2,……,n2. x∧y＝c 1c2……ck， ck＝min{ a k， bk}3. x∨y＝d 1d2……dk， dk＝max{ a k， bk}4．x’= z 1z2……zk， zk＝a k’.Homework P224－22516，18，20，22，。