定义设L,≤是格，对任意的a,b,c?L，有①a?(b?c)=(a?b)?(a?c)②(a?b)?(a?c)=a?(b?c)则称L,≤为分配格，称①和②为格中分配律。第31页，共52页，星期日，2025年，2月5日分配格的性质性质1：如果①交对并可分配，则②并对交也一定是可分配的，反之亦然。只证前半部分，即由①推②：(a?b)?(a?c)＝((a?b)?a)?((a?b)?c)（由①）＝(a?a)?(a?b)?(c?a)?(c?b)（由①,交换律）＝a?(a?b)?(a?c)?(b?c)＝a?(b?c)（吸收律）注：此性质说明，分配格的定义可以简化成只需满足①或②其中之一即可。第32页，共52页，星期日，2025年，2月5日性质2：每个链L,≤都是分配格。（|L|≥3）链链第33页，共52页，星期日，2025年，2月5日例：试判断下面两个哈斯图是否表示的是分配格？显然(1)是格，但因为b?(c?d)=b?a=b，而(b?c)?(b?d)=e?e=e，故它不是分配格；显然(2)也是格，但因为c?(b?d)=c?a=c，而(c?b)?(c?d)=e?d=d，故它也不是分配格，注：上面两个具有五个元素的格是很重要的，因为有这样的定理：一个格是分配格的充要条件是，在该格中没有任何子格与这两个五元素格中的任何一个同构。bcdae(1)bcdea(2)第34页，共52页，星期日，2025年，2月5日我们知道，验证一个格是不是分配格是很复杂的，可以利用上面这个定理判断一个格不是分配格。如(3)中，容易验证{a,b,c,e,g},≤是{a,b,c,d,e,f,g},≤的子格，且与(1)同构，或者容易验证{a,b,c,f,g},≤是{a,b,c,d,e,f,g},≤的子格，且与(2)同构，故不是分配格。从而判断它不是分配格。bcdae(1)bcdea(2)abcfgde(3)第35页，共52页，星期日，2025年，2月5日例：证明Sn,≤是一个分配格。证：设∧和∨分别为Sn上的交（或积）和并（或和）运算，对于任意a，b，c∈Sn，有a∨(b∧c)=lcm(a,gcd(b,c))=gcd(lcm(a,b),lcm(a,c))=(a∨b∧(a∨c)a∧(b∨c)=gcd(a,lcm(b,c))=lcm(gcd(a,b),gcd(a,c))=(a∧b)∨(a∧c)（事实上，上面是利用“最大公约数对最小公倍数是分配的，最小公倍数对最大公约数也是分配的”这个性质）故Sn，|是一个分配格。第36页，共52页，星期日，2025年，2月5日在介绍有补格之前，先介绍补元的定义。定义设L,≤是有界格，对于a?L，存在b?L，使得a?b=0，a?b=1称b为a的补元，记为a。由定义可知，若b是a的补元，则a也是b的补元，即a与b互为补元。显然，0=1和1=0。一般说来，一个元素可以有其补元，未必唯一，也可能无补元。第37页，共52页，星期日，2025年，2月5日第1页，共52页，星期日，2025年，2月5日在介绍格之前，对于我们在前面学过的偏序，我们要补充两个内容：1.哈斯图2.最小上界与最大下界第2页，共52页，星期日，2025年，2月5日1.哈斯图为了更清楚地描述偏序集合中元素间的层次关系,也为了更快、更有效地画出偏序关系的简化图,下面介绍“盖住”的概念。定义在偏序集A,≤中,对x,y?A,x≤y且x?y,且A中无任何其它元素z,满足x≤z且z≤y,称y盖住x,或称x是y的直接前趋,y是x的直接后继。盖住关系记作cov(A)={(x,y)|x,y?A且y盖住x}。第3页，共52页，星期日，2025年，2月5日显然盖住关系是唯一确定的,盖住关系是“≤”的子集。盖住关系的关系图称哈斯(Hasse)图,它实际上偏序关系是经过如下简化的关系图:1.省略关系图中的每个结点处的自环,这是因为偏序关系“≤”是自反的。2.若xy且y盖住x,将代表y的结点放在代表x的结点之上,并在x与y之间连线,省去有向边的箭头,使其成为无向边。 若xy但y不盖住x,则省去x与y之间的连线。第4页，共52页，星期日，2025年，2月5日例A={1,2,3,4,5,6,8,10,12,16,24},偏序关系是A上的整除关系“≤”,画出偏序集A,≤的哈斯图。我们先画出关系图。注意图中，并没有画出所有关系，否则画面更显凌乱。按照哈斯图的画法，去掉一部分，结果如左图。