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

第六章序关系和结构Order Relations and Structures6.1 偏序集Partial Ordered Sets关系 Relation定义A Relation R From A to B is a subset of ABA relation on A is a subset of AA矩阵表示，图表示。性质自反 reflextiveDR对称 symmetric, asymmetric, antisymmetricR-1=R, R-1RD, R-1R=传递 transiveR2R or R=R传递闭包 Wallshall算法O(n3)等价关系 =偏序关系Partial Order Definition1. 自反 Reflexive aA, (a,a)R2反对称antisymmetric a,bA (a,b)R(b,a)R a=b3传递Transitivea,b,cA (a,b)R (b,c)R (a,c)R.Examples, , , , 例4 R，S都是A上等价关系, RSxRyxSy, R：A上全体等价关系， (R ，)构成偏序。对偶偏序集：如果R是A上偏序，则R1也是A上偏序。（A，R1）称为（A，R）的对偶偏序集。 （A，）是（A，）的对偶偏序。全序关系，线性序关系linear order，链chain偏序1.2.3.44 a,bA,(a,b)R(b,a)R.字典序偏序乘积定理1如果(A,)，(B,)是偏序，则(AB，)是乘积偏序product partial order，其中定义为： (a,b)(a,b)aabb偏序与严格序设（A，）是偏序， 令abab，ab， 称（A，）严格序， 大于，小于都是严格线性序。反之若（A，）是严格序， 令ababa=b, 则(A,)是偏序。字典序二元(AB，)中，令(a,b)(a,b)aaor a=a,bb 是字典序lexicographicn元(A，）是偏序，AnAAA(a1,a2,an)(b1,b2,bn) a1b1a1=b1a2b2a1=b1anbn 不等长(a1,a2,an)(b1,b2,bm)If n=mIf nm (a1,a2,am)(b1,b2,bm)12定理2. 偏序集的有向图中没有长度大于1的圈。423哈斯图Hasse Diagram1parital order，digraph and the matrix of D6？从关系图到哈斯图Deleting all the self-circlesDeleting all the edges which can be induced by transive propertyReplacing vertices by dotsMake sure the greater elements are located at higher place.例11D12 的哈斯图？0例12Sa,b,c, A=P(S).问题（6.1.1）给定偏序关系R，哈斯图是否唯一？计算哈斯图的算法？传递闭包逆运算？拓扑排序（A，）是偏序集，构造一个线性序（A，）使 abab，算法原理： 1. 选择一个没有前驱的顶点输出， 2. 去掉这个顶点以及从这点出发的所有边。 重复1.2.直到所有顶点都输出完毕时间复杂性？O(n3)同构Isomorphic定义f：（A, ）（A, ）f是AA的一一对应，ab iff f(a)f(b)。例15（Z，）（2Z，）f：（Z，）（2Z，）是同构。f(a)=2aab iff 2a2b定理3. 设f：(A,) (A,)。则A, A对应的性质都相同。序同构与哈斯图的关系1 如果f是同构，则A的哈斯图中所有标记a换成对应的标记f(a), 得到A的哈斯图。2 如果A的哈斯图中所有标记a换成对应的标记f(a), 得到A的哈斯图，则f是同构。 例17A1,2,3,6, A=P(a,b)= ,a,b,a,bHomework P2002015，6，14，16，24，28，35，366.2偏序集的极大极小元 Extremal elements of Partial Ordered Sets极大元maximal element：aA，$bA，ab.极小元minimal element：aA，$bA，ba.定理3. 偏序集A中，BA，B至多一个上确界，至多一个下确界。定理4. 设f：（A，）（A,）是偏序同构，（a） a是A的极大（极小）元，则f(a)是A的极大（极小）元。（b） a是A的最大（最小）元，则f(a)是A的最大（最小）元。（c） BA，a是B的上（下）界，则f(a)是f(B)的上（下）界（d） BA，a是B的上确（下）界，则f(a)是f(B)的上（下）确界Homework P20620716，26，336.3 格 Lattices定义 格是一个偏序集（L，），任意a，bL，a，b有上下确界。令abLUB(a,b), abGLB(a,b).格 (L,，)例1（P(S), ）是格，ABAB，ABAB。记做（P(S), ,）例2（Z，| ）是格，abLCM(a,b),abGCD(a,b).例3令Dn是n的所有正因子的集合，（Dn，|）是格。D201,2,4,5,10,20, D30=1,2,3,5,6,10,15,20线性序是格例4 Hasse图是否格的判断。 例5 R：A上全体等价关系，偏序（R ，）是格。 RSRS RS(RS)设（L，）是格，则对偶（L，）也是格。问题6.3.1 1)格的判定算法？2)格的运算表生成？定理1.乘积格设（L1,），（L2,）都是格。则（L1L2，,）也是格。(a,b)(c,d)=(ac, bd)(a,b)(c,d)=(ac, bd)子格sublattice设（L，）是格，SL，S对，封闭，即a，bSab，abS。记做(S，,) (L，,)或 格S L。例如(Dn，|, LCM, GCD) (Z+, |, LCM,GCD)例9 格的同构Isomorphic Latticesf：(L1,)(L2,)，f是L1到L2的序同构，则f保持，运算，f(ab)=f(a)f(b)f(ab)=f(a)f(b)格同构也记做L1L2。D6P(a,b).问题 （6.3.2） 1） Dn 同构与 (P(S), )的充分必要条件？ 2）Dn 同构与Dm的充分必要条件是什么？格的性质Properties of Lattices定理2 设L是格，则ab abb aba.定理3.设L是格，则L具有如下性质：幂等律 aaa， aaa交换律 abba，abba结合律 a(bc)=(ab)c, a (bc)=(ab)c吸收律 a(ab)=a, a(ab)=a定理3 设集合L上有运算，（L,）满足幂等律，交换律，结合律，吸收律，则L是格。证明.1）abb iff aba。 aba(ab)=a. aba(ab)=a.2）定义L上关系：ab iff abb iff aba。3）是L上偏序： 1）自反性：由aaa，得aa 2）反对称性：设ab，ba，aabbab， 3）传递性设ab，bc，aca(bc)(ab)cbccac4）ab，ab分别是上下确界ab上界：a(ab)=a, aabb(ab)=b, babab上确界设ac，bc，(ab)c=a(bc)=accabcab是a，b的最小上界。定理4. 设L是格，1）如果ab，则（a）acbc（b）acbc2）ac，bc iff abc3）ca，cb iff cab4）如果ab，cd则 acbd 且acbd有界格有界格Bounded lattice：有最大元1，最小元0的格叫有界格。L是有界格，则对任意aL，有0，1律成立。1）0a12）a0a，a003）a11，a1a定理5. L是有限格，则L有界。分配格Distributive Lattice：1. a(bc)(ab)(ac)2. a(bc)(ab)(ac)12(ab)(ac)=(ab)a)(ab)c)=a(ab)c)=a(ac)(bc)=a(bc)例16格(P(S),)是分配格。11例18下列格 bcaabc00定理6格L不是分配格当且仅当L含有例18中的子格。可补格Complement Lattice.有界格L是可补格，如果任意aL，有aL，使 aa=1，aa=0.称a为a的补元。0例19格(P(S),)是可补格。例21D20，D30都是可补格。定理7. 设L是有界格，aL，如果a有补元，则其补元唯一。证明. 设a,a”都是a的补元。则a=a0a(aa”) (aa)(aa”) = aa” a”=a”0a”(aa) (a”a)(a”a) = aa”因此 a=a”.Homework P21621712，14，18，21，23，24，27，31，336.4 有限布尔代数Finite Boolean Algeblas定理1 设S1x1,x2,xn,S2y1,y2,yn，则格（P(S1), ）（P(S2),）.证明. 令f：S1S2， f(xi)=yi , i=1,2,n.则 f：P(S1)P(S2)是格同构。 1. 任意AP(S1), AS1, f(A) S2,是一一对应。 2. 任意A，BP(S1), AB, f(A) f(B). f保序。定义：|S|=n, 格（P(S1), ）记做BnBn是布尔代数。定理2. n=p1p2pk时，Dn是布尔代数。证明. 令Sp1,p2,pkDn中的元素m=pk1*,.,pkmP(S)中的元素 T=pk1,pkmf: P(S)Dn f(T)=pk1*pkm 只需证明f是同构对应。1） f是一一映射2） T1T2f(T1)|f(T2)显然成立例D1001是布尔代数。定理3. 设B是布尔代数，x，yB，1(x)=x,2. (xy)=xy. De. Morgan律3. (xy)=xy布尔代数的性质：交换律commutativepropertiesxyyxxyyx结合律associative properties(xy) rx(yr).(xy)rx(yr).分配律distributive propertiesx (yr) xyxr.x(yr) (xy) (xr).幂等律idempotent propertiesxxx.xxx.双重否定property of negation9 xxDe Morgans law10. (xy) xy11. (xy) xy吸收律12 x(xy)x13 x(xy)x01律14x0x，x0015x11，x1x16. xx=1, xx=017. 1=0, 0=1 例7P230图6.62不是布尔代数。例8p2|n, p是素数，则Dn不是布尔代数。证明.设Dn是布尔代数。p2|n, n=p2k. pDn，pDn。pp0，GCD(p,p)=1,pp1，LCM(p,p)=n.GCD(p,p)1p|p.LCM(p,p)=n=p2kp|p.矛盾。例9D12不是布尔代数。定理4. BnBBBBnBBB， n个B的卡氏积。 证明.令f：BnBBBS x1x2xn, BnP(S).Bn中任意元素A =xk1,xkmBBB 中的任意元素a=(a1,an), ai0,1令f(A)= (a1,an) If xiA then ai=1 If xiA then ai=0其中 只需证明f是同构对应。1) f是一一映射2) AB iff (a1,an)(b1,bn)，显然成立Bn= BBB设xa1a2ak，yb1b2bkBn1xy iff akbk，k1,2,n2. xyc1c2ck，ckmin ak，bk3. xyd1d2dk，dkmax ak，bk4x= z1z2zk，zkak.Homework P22422516，18，20，22，24，266.5 布尔函数Function on Boolean Algebra布尔函数定义f:BnB，0元的布尔函数0,11元的布尔函数XF0F1F2F300011101012元的布尔函数X1X2F0F1F2F3F4F5F6F7F8F9F10F11F12F13F14F15000000000011111111010000111100001111100011001100110011110101010101010101名称0*多元的布尔函数f(x1,x2,xn)x1x2x3f(x1,x2,x3)00010010010001101001101011001111布尔函数的公式表示：布尔多项式Boolean Polynomials布尔表达式Boolean expressionp(x1,x2,xn):1. 单个变元xi，1in，是布尔多项式。2. 0，1是布尔多项式。3. 若p(x1,x2,xn)， q(x1,x2,xn)是布尔多项式，则p(x1,x2,xn)q(x1,x2,xn)，p(x1,x2,xn)q(x1,x2,xn)，（p(x1,x2,xn)），也是布尔多项式。(xy)z, (xy)(y1)，(x(yz)(x(y1)，都是布尔多项式。范式normal formulas析取范式极小项命题变元p1,p2,pn的极小项minimal terms Q1Q2Qn其中每个 Qi =pi 或 pi 1in.p1p2pn有2n个极小项。p1p2p3的8个极小项为p1p2p3， p1p2p3，p1p2p3， p1p2p3，p1p2p3， p1p2p3，p1p2p3， p1p2p3。每个极小相，只有一个对应的成真赋值。p, q, r的8个极小项对应的赋值:若干极小项的析取叫析取范式normal disjunction formulas定理 每个可满足的命题公式都等价于唯一一个析取范式。 先给出命题公式的真值表，找出取值为1的所有赋值，这些赋值对应的基本合取项的析取就是所求的析取范式。也可以通过等价变换得到析取范式：p(qr) pqr p(qq) (rr)(pp) q (rr)(pp) (qq)rpqrpq rpqrpqrp q rpqrpqrpqrpqrpqrpqrpqrpqrpqrpqrp q rpqrpqrpqrpqr合取范式命题变元p1,p2,pn的基本析取项basic disjunction terms Q1Q2Qn其中每个 Qi =pi 或 pi 1in.p1p2pn有2n个基本合取项。p1p2p3的8个基本合取项为p1p2p3，p1p2p3，p1p2p3，p1p2p3，p1p2p3，p1pp3，p1p2p3，p1p2p3。命题变元p1,p2,pn的赋值(p1,p2,pn)对应的基本析取项： Q1Q2Qn其中每个 Qi =pi if pi=0 Qi=pi if pi=1.设Q1Q2Qn是命题变元p1,p2,pn的一个基本析取项，是p1,p2,pn的一个赋值， (Q1Q2Qn) =0 当且仅当 Q1Q2Qn是对应的基本析取项。若干基本析取项的合取叫合取范式Normal conjunction formulas 定理 每个不恒真的命题公式都等价于唯一一个合取范式。 先给出命题公式A的真值表，找出取值为0的所有赋值，这些赋值对应的基本析取项的合取就是A的合取范式。也可以先给出A的析取范式，再用De Morgan律算出A的合取范式。布尔函数的门电路表示：联结词的全功能集functional complete set of logical connectives定义F=f1,fm为m个真值函数的集合， 若任意的n元真值函数h(x1,xn) 都可以由f1,fm来构造，就说F是一个全功能集常见全功能集， 是一个全功能集。每个命题公式都能表示为析取范式，可以只用，做联结词。, , 也是全功能集。由pq (pq) pq (pq)，也是全功能集由pq pq知, 也是全功能集。与非 pq ( pq) 或非 pq (pq) pqpqpq0011011010101100p pp pppq (pq) (pq)(pq)pq ( pq) ( pq)( pq)如何证明一组函数是全功能集？常见的非全功能集， 都不是全功能集。如何证明一组函数不是全功能集？真值函数的性质1) 1保持的 f(1,1,1)=1;2) 0保持的 f(0,0,0)=0;3) 单调的. 任意(x1,.,xn)(y1,yn)有f(x1,.,xn)f(y1,yn)4) 自对偶的。f(x1,.,xn)= f(x1,., xn)5) 计数的。每个变量要么是哑变量，要么是计数变量。Post 定理Homework P2294，6，8，11，14，15，16，17，186.6 线路设计Circuit Designs定义设f：BnB是一个布尔函数，令S(f)=bBn | f (b)=1定理1. 令f，f1, f2都是Bn到B的布尔函数。（a） 如果S(f)=S( f1)S(f2), 则对任意bBn，f(b)= f 1(b)f2 (b)（b） 如果S(f)=S( f1)S(f2), 则对任意bBn，f(b)= f 1(b)f2 (b)例f：B2B。f(x,y)=x, S(f)=(1,0),(1,1)f(x,y)=y, S(f)=(0,1),(1,1)f(x,y)=x, S(f)=(0,0),(0,1)f(x,y)=y, S(f)=(0,0),(1,0)f(x,y)=xy, S(f)=(1,1)f(x,y)=xy, S(f)=(0,1)f(x,y)=xy, S(f)=(1,0)f(x,y)=xy, S(f)=(0,0)S(xyz)=(0,0,1) 极小项minterm：使S(f)是单元集的布尔函数f(x1,，xn)叫极小项。极小项相当于基本合取范式。x1x2x3x4，S(x1x2x3