格和布尔代数精简.ppt

****偏序关系：自反、反对称、传递，上界：集合B是A的子集，如果对于B中的任意一个元素都有b=a，则a属于A称为B的上界，反之(b=a)称为B的下届。最大上界：a是B的一个上界，对于B中的任意一个上界a’，都有a’=a,则a属于A称为B的最大上界。反之称为B的最小上界。最大、最小元素，极大、极小元素，上界、下界，最小上界、最大下界偏序关系一般用哈斯图来表示：不存在自反特性的自回路，不表示包含传递关系的边，即仅当没有元素使得a＝c且c＝b时，才有一条由a到b的边，没有有向回路（反对称）**任意两个元素之间都有最大下界、最小上界，格一定要上下封口。(c)布尔格(d)钻石格(e)五角格；(a)(b)(c)不是格**任何两个元素之间都会有最小公倍数和最大公约数**命题：是一个或真或假而不能两者都是的断言。**L满足格的定义**(5)c是a,b的下界，而a∧b是a和b的最大下界，因此c=a∧b.最大下界、最小上界**遇到括号的证明，一般从括号里面开始，口朝谁，把谁分解开**a∨a是a的最小上界，而a=a,a是a的上界，利用的是具体的∨与∧的含义****替换不影响原式的值**找到这个关系，然后证明它是一个偏序、任两个元素都有最大下界，最小上界。利用运算来定义二元关系，利用前面学过的一个性质。而且满足吸收律一定满足等幂律**在偏序集合中，如果每一个a,b属于A，a,b之间都有关系，即可比较，则称关系为集合上的线序，这时的序偶叫做线序集合或链。**因为是链可以考虑其相对位置，考虑六种情况(i)考虑了四种情况(ii)考虑了两种情况7.3分配格【例题】图(a)、(b)所示的格是分配格吗？为什么？分析：均不是分配格。考虑b∧(c∨d)与(b∧c)∨(b∧d)；考虑c∧(b∨d)与(c∧b)∨(c∧d)cabde(a)钻石格abcde(b)五角格第38页,共69页，星期六，2024年，5月7.3分配格『定理』设L,≤是一个格，若∧运算对∨运算可分配，则∨对∧也可分配，反之亦然。证明：设∧运算对∨运算可分配，即任取a,b,c∈L,满足a∧(b∨c)=(a∧b)∨(a∧c)现要证a∨(b∧c)=(a∨b)∧(a∨c)(a∨b)∧(a∨c)=((a∨b)∧a)∨((a∨b)∧c)=a∨((a∨b)∧c)第39页,共69页，星期六，2024年，5月7.3分配格=a∨((a∧c)∨(b∧c))=a∨(a∧c)∨(b∧c)=a∨(b∧c)由此可知，∨运算对∧运算也可分配。同理可证，若∨运算对∧运算可分配，则∧运算对∨运算也可分配。第40页,共69页，星期六，2024年，5月7.3分配格『定理』每个链都是分配格。证明：设L,≤是一个链，则L,≤必是一个格。任取a,b,c∈L,讨论以下两种情况：(i)a≤b或a≤c无论是a≤b或a≤c都有a∧(b∨c)=a(a∧b)∨(a∧c)=a即a∧(b∨c)=(a∧b)∨(a∧c)第41页,共69页，星期六，2024年，5月7.3分配格(ii)b≤a且c≤a:由b≤a,c≤a知b∨c≤a，可得a∧(b∨c)=b∨c又因为(a∧b)∨(a∧c)=b∨c,所以有a∧(b∨c)=(a∧b)∨(a∧c)由(i)、(ii)可知∧运算对∨运算可分配，于是∨运算对∧运算也可分配。故每个链都是分配格。第42页,共69页，星期六，2024年，5月7.3分配格『定理』设L,≤是一个分配格，那么对于任意a,b,c∈L,如果有a∧b=a∧c和a∨b=a∨c成立，则必有b=c。证明：b=b∨(a∧b)=b∨(a∧c)=(b∨a)∧(b∨c)=(a∨c)∧(b∨c)=(a∧b)∨c=(a∧c)∨c=c第43页,共69页，星期六，2024年，5月7.3分配格『定理』一个格是分配格，当且仅当它不存在与钻石格和五角格同构的子格。