离散数学第七章2014.pptVIP

2. 试证明在格中对于任意元素a,b,c,d, 有 (a?b) ?(c?d)? (a?c) ?(b?d) 证明 由(7-4) a ? b ? a ； 由(7-4?)，a ?a ? c，因此a ? b ?a?c， 同理，c?d?c，c?a?c，因此有c?d?a?c， 故由（7-5′）a?c?(a?b) ?(c?d) 类似地，a?b ?b ?b?d，c?d ?d ?b?d 故由（7-5′）b?d?（a?b）?(c?d) 又由（7-5）(a ? b)?(c?d) ?( a ?c)?( b?d ) * * 作业 P173 1 (2) 4 P174 16 18 * * 令 S1={{b},{a,b}{b,c},{a,b,c}} S2={?,{a},{ c},{a, c}} S3={?,{a},{c},{a,b},{a,c},{b,c},{a,b,c}} S1;?,?是2U;?,?的子格。 S2;?,?也是2U;?,?的子格。 S3不能与这两个运算构成2U;?,?的子格。 ? {a,b,c} {a,c} {b,c} {a,b} {a} {c} {b} * * 2 6 1 12 练习 12 6 4 3 2 1 1． 设 L = {1，2，3，4，6，12}，在L上定义 整除关系，构成偏序集L; ?。 （1） glb(6,4)= ; lub(2,3)= ； （2） 该偏序集的最小元素是 ， 最大元素是 。 * * 3 4 1 10 （1） glb(6,9) = ; glb(8,12) = .； （2） glb(9,7) = ; lub(5,10) = .。 2．设L={1，2，3，…，11，12}，在L上定义整除关 系，构成偏序集. 12 8 4 2 1 10 5 6 3 9 7 11 * * 下面给出的三个次序图，其中哪些是格？在图 下方相应的括号内键入“Y”或“N”表示肯定或否定。 ( ) ( ) ( ) N Y Y * * Y Y N N 4．对下图所给出的格判断以下子集是否能构成它的 子格。在相应的括号内键入“Y”或“N”来回答 （1）S1={e,c,b} ( ) （2）S2={d,b,a} ( ) （3）S3={c,d,b} ( ) （4）S4={e,c,d,a} ( ) e d c b a * * 定义7-9 设L;?,?是一个格, 若对于任意的l1, l2, l3 ? L,有 则称 L;?,? 是分配格。 7．2 分配格和有补格 d c b a e c d b a d b c a 一、分配格 1．分配格的定义 * * 例1 对任意的集合A，2A ;?,?是一个分配格， = a?a =a 因此 b?(c?d)≠(b?c)?(b?d) 而(b?c)?(b?d) 例2???? b?(c?d) = b?e = b e b c d a * * 2． 分配格的判别 定理7-11 在格L;?,?中, 如果交运算对并运算是可分配的, 则并运算对交运算也是可分配的;如果并运算对交 运算是可分配的,则交运算对并运算也是可分配的。 证明 设在格L;?,?中, 对任意l1, l2, l 3?L,有l1 ?(l2 ?l3) =(l1?l2)?( l1? l3 ) * * 例如 设 L ={1,2,4,16,32,64}, 定义在L上的整除关系?与L构成一个链L;?。 设L;? 是一个偏序集，若对于任意的l1, l2?L，或者l1?l2，或者l2?l1，则称L; ?是一个链。 6