《离散数学讲义(第6章)》由会员分享，可在线阅读，更多相关《离散数学讲义(第6章)（37页珍藏版）》请在金锄头文库上搜索。
1、1,Discrete Mathematics,离散数学讲义（电子版）,天津财经大学 信息科学与技术系 王宁,2,第六章 格与布尔代数,3,第六章 格和布尔代数,本章包括以下内容：,6-1 格的概念6-2 分配格6-3 有补格6-4 布尔代数6-5 布尔表达式,4,在第三章曾讨论过偏序集合,定义了有关的术语。并曾证明过:(1)一个偏序集合的子集,如果存在最小上界(lub),则它是唯一的,如果存在最大下界(glb),则它也是唯一的;(2)如果偏序集合拥有最小元素,则它是唯一的,如果偏序集合拥有最大元素,则它也是唯一的。我们就以这些知识为基础介绍格的概念和有关性质。,6-1 格的概念,5,6-1 格
2、的概念（续）,偏序集,由一个集合A以及A上的一个偏序关系 所组成的一个序偶A， 称为偏序集。,定义：设A， 为一个偏序集，如果A中任意两个元素都有最小上界和最大下界，则称A， 为格。,注意：偏序集的任意子集不是必定存在最小上界或最大下界的。,例如：正整数集合I+与其上的整除关系 | 组成一个偏序集 I+ ，|，并且为格。例如：集合S的幂集P(S)与其上的包含关系 组成一个偏序集 P(S) ， ，并且是格。,6,6-1 格的概念（续）,偏序集但不是格 格,a,f,e,d,c,b,7,6-1 格的概念（续）,代数系统,设A， 是一个格，如果在A上定义两个二元运算和，使得对于任意的a，bA，ab等于
3、a和b的最小上界，ab等于a和b的最大下界，那么就称A， ， 为由格A， 所诱导的代数系统。二元运算， 分别称为并运算和交运算。,例如：S=a, b，P(S)=，a，b，a，b ，则由格 P(S) ， 所诱导的代数系统为 P(S)， ， ，其中是集合的并， 是集合的交。,a,b,a，b,8,定义：设A，是一个格，由A，诱导的代数系统为A， ， ，设B A且B ，如果A中的这两个运算， 关于B是封闭的， 那么称B，是A，的子格。 可以证明子格本身是一个格，因为交换律，结合律，吸收律都是继承的。显然，对于A的任意非空子集B，B，是偏序集，但不是一定是格，并且即使是格，也不一定是A的子格。例如右图所
4、示的格中，a,b,d，是子格，b,c，不是子格，因为b,c对运算不封闭。,6-1 格的概念（续）,9,例如：S=a,b,c,d,e,f,g,h，取 S1=a,b,d,f，S2=c,e,g,h，S3=a,b,c,d,e,g,h，则S1，S2 ，都是S，的子格。而 S3，是格，但不是S，的子格，因为b d = f S3 。,例1 设S， 为格，任取a S，构造S的子集T=x|x S且x A，则T，为S，的子格。解： x，y T，必有x a， y a，故xy a，xy a，故xy T ，xy T 因此，T，为S，的子格。,6-1 格的概念（续）,10,给定一个偏序集合A，的逆关系R或记作，表示对于A
5、中的元素a，b，aRb当且仅当ba。 显然A，R（或记作A， ）也是一个偏序集，我们称偏序集合A，和A，互为对偶。从图形上看，后者的哈斯图就是前者哈斯图的上下颠倒。,格的对偶,设对任意格都为真的命题P，在命题P中将“”换成“”，“”换成“”， “”换成 “”，得到新的命题P，称为P的对偶命题。 P对任意格也是真命题。,格的对偶原理,6-1 格的概念（续）,11,格的性质,1a a b b a b a b a a b b,2若a b，c d，则 a c b d a c b d,3若b c，则 a b a c a b a c,设A， 为格，其所诱导的代数系统为A， ，对任意的a，b，c，d A，有
6、下列性质成立。,6-1 格的概念（续）,12,4a b = b a a b = b a,5a (b c) = (a b) c a (b c) = (a b) c,6a a = a a a = a,7a (a b) = a a (a b) = a,交换律,结合律,幂等律,吸收律,6-1 格的概念（续）,13,引理：设A， ， 是一个代数系统，其中，和都是二元运算且满足吸收律，则， 都满足幂等性。,定理：设A， ， 是一个代数系统，其中，和都是二元运算且满足交换性、结合性和吸收性，则A上存在偏序关系，使A， 为一个格。,定理：在格A， 中，对任意的a，b，c A，都有a (b c) (a b) (
7、a c) a (b c) (a b) (a c),6-1 格的概念（续）,14,定理：设A， 为一个格，对任意的a，b A，有 a b a b = a a b = b,定理：设A， 为一个格，对任意的a，b，c A，有 a c a (b c) (a b) c,推论：在格A， 中，对任意的a，b，c A，必有(a b) (a c) a (b (a c) ) (a b) (a c) a (b (a c) ),6-1 格的概念（续）,15,格同态，格同构,设A1 ，1，A2 ，2是两个格，由它们诱导的代数系统分别为A， 1 ， 1 ，A， 2 ，2 ，如果存在着一个从A1到A2的映射f，使得对任意的
8、a，b A1 ，有f(a 1 b)=f(a) 2 f(b)f(a 1 b)=f(a) 2 f(b)则称f为从A1， 1 ， 1 到A2， 2 ，2 的格同态，也称f(A1) ，2是A1 ，1的格同态。 当f为双射时，则称f为从A1， 1 ， 1 到A2， 2 ，2 的格同构，也称A1 ，1和A2 ，2是格同构。,6-1 格的概念（续）,16,定理：设f为从A1 ，1到A2 ，2的格同态，则对任意的x,y A1，如果x 1 y，则 f(x) 2 f(y)。,定理：设A1 ，1，A2 ，2是两个格，f是从A1到A2的双射，则f是A1 ，1到A2 ，2的格同构当且仅当对任意的a，b A1，有 a 1
9、 b f(a) 2 f(b),6-1 格的概念（续）,17,6-2 分配格,定义：设A,是由格A， 所诱导的代数系统。如果对任意的a,b,cA，满足：a (b c) = (a b) (a c)及 a (b c) = (a b) (a c)则称A， 是分配格。,讨论定义：(1) 定义中的两式互为对偶式。(2) 必须对任意的a,b,cA，都要同时满足交运算对并运算的分配律以及并运算对交运算的分配律。,18,6-2 分配格（续）,例如右图：设S=a,b,c，则P(S),是由格P(S), 诱导的代数系统。则P(S), 是一个分配格。,例如：右图所示的两个五元素格都不是分配格。定理：一个格是分配格的充要
10、条件是在该格中没有任何子格与这两个五元格同构。（了解）,19,定理：如果在一个格中交运算对并运算可分配，则并运算对交运算一定可分配。反之亦然。,定理：每个链是分配格。,定理：设A， 为一个分配格，则对任意的a，b，c A，如果有a b = a c且a b = a c，则b=c。,6-2 分配格（续）,20,定义：设A,是由格A， 所诱导的代数系统。如果对任意的a,b,cA，当b a时，有：a (b c) = b (a c)则称A， 是模格。,定理：设A， 为在模格，当且仅当在A中不含有适合下属条件的元素a，b，ca b 且 a c = b c， a c = b c,6-2 分配格（续）,21,
11、定理：对于模格，若有三个元素a，b，c使得下述三个式子的任何一个式子中把换成=成立，则另外两个式子中把换成=也成立。a (b c) (a b) (a c)(a b) (a c) a (b c) (a b) (b c) (c a) (a b) (b c) (c a),定理：分配格一定是模格。,6-2 分配格（续）,22,6-3 有补格,定义：设A， 是一个格，如果存在元素aA，对任意的xA，都有a x，则称a为格A， 的全下界。记作 0。,定理：格A， 若有全下界或全上界，则必唯一。,定义：设A， 是一个格，如果存在元素bA，对任意的xA，都有x b，则称b为格A， 的全上界。记作 1。,23,
12、6-3 有补格（续）,定义：如果一个格中存在全上界和全下界，则称这个格为有界格。,定理：设A， 为一个有界格，则对任意的a A，必有a 1 = 1， a 1 = aa 0 = a， a 0 = 0,24,6-3 有补格（续）,定义：设A， 为一个有界格，对于A中的一个元素a，如果存在b A，使得a b = 1，a b = 0，则称元素b是元素a的补元。或称a与b互为补元（由对称性）。注意：对于元素a可以存在多个补元，也可以不存在补元。,定义：在一个有界格中，如果每个元素都至少有一个补元，则称此格为有补格。,定理：在有界分配格中，若有一个元素有补元，则必是唯一的。,25,6-4 布尔代数,定义：
13、一个有补分配格称为布尔格。,定义：由布尔格A， 可以诱导一个代数系统A, ，称为布尔代数。,-,例如：S=a, b，P(S)=，a，b，a，b ，则 P(S) ， 为布尔格。所诱导的代数系统为 P(S)， ，其运算表为,26,6-4 布尔代数（续）,定理：对布尔代数中的任意两个元素a，b，有,定义：具有有限个元素的布尔代数称为有限布尔代数。,27,6-4 布尔代数（续）,结论：（1）对于每一个正整数n，必存在含有2n各元素的布尔代数；反之，任一有限的布尔代数，其元素个数必为2的幂次。（2）元素个数相同的布尔代数都是同构的。,定义：设两个布尔代数A， 和 B， ，如果存在A到B的双射f，对于任意的a,b A，都有则称这两个布尔代数同构。,
