第六章格和布尔代数

1、第六章 格和布尔代数2014-2015 学年第二学期陈磊6.1 格的概念 对于偏序集来说,它的任一子集不是必定存在最小上界或最大下界的.【例】由右图所示的偏序集中, 2,3的最小上界是6, 但没有最大下界 24,36的最大下界是12,但没有最小上界 约定 把a,b的最小上界(最大下界)称为 元素a,b的最小上界(最大下界). 有没有一种偏序集使得任何两个元素都有最小上界和最大下界? 定义6-1.1 设A, 是一个偏序集，如果A中任意两个元素都有最小上界和最大下界，则称A, 是格。【例】1.设I+表示所有的正整数,定义I+上的二元关系为整除关系|,则是一个偏序关系.进一步,任意两个元素的最大下界

2、就是两个数的最大公约数,而最小上界为两个数的最小公倍数,因此是格 2.也是格,任意两个元素S1,S2,最大下界为S1S2,最小上界为S1S2【例】下图中给出了一些偏序集的哈斯图，判断它们是否构成格。 定义6-1.2 设A, 是一个格, 如果在A上定义两个二元运算和,使得对于任意的a,b A, ab等于a和b的最小上界, ab等于a和b的最大下界,那么就称 为由格所诱导的代数系统, 二元运算和称为并运算和交运算.【例】S=a,b, P(S)=?,a,b,a,b, 那么是一个格由这个格所诱导的代数系统为, 其中是集合的并, 是集合的交, 这两个运算的运算表见下表 aabba,baaaa,ba,ba

3、,bbba,ba,ba,ba,ba,bba,ba,baba,baaabbba,baba,b 定义6-1.3 设A, 是一个格，由A, 诱导的代数系统A,设 BA且B?, 如果A中两个运算和关于B是封闭的，则称B, 是A, 的子格。 子格一定是格【例】 是一个格,E+是正偶数的全体,则是的一个子格 注 对于格,B是A的非空子集, 也是一个偏序集 不一定是格 即使是格,也不一定是的子格【例】设是一个格,其中S=a,b,c,d,e,f,g,h,哈斯图如下所示S1=a,b,d,fS2=c,e,g,hS3=a,b,c,d,e,g,h, ,都是格,其中和是的子格,而,不是的子格. 设A, 是一个偏序集,

4、在A上定义一个新的二元关系R, 使得对于A中两个元素a,b, 有关系a Rb当且仅当b a 也是一个偏序集 A, 和称为是彼此对偶的 若A, 是一个格,则也是一个格 R一般用 表示 设P是对任意格都为真的命题, 如果在命题P中把 换成 , 换成，换成, 就得到另一个命题P1, 称P1为P的对偶命题. 同时P1对任意格也是真命题 定理6-1.1在一个格A, 中,对任意的a,b A, 都有 a ab, b ab ab a, ab b 定理6-1.2在一个格A, 中,对于a,b,c,d A, 如果a b和c d,则 ac bd, ac bd 推论 在一个格A, 中, 对于a,b,c A, 如果b c

5、, 则ab ac, ab ac. 这个性质称为格的保序性 定理6-1.3 设A, 是一个格，由格A, 所诱导的代数系统为A, 则对任意的a,b,c,dA有 ab=ba， ab=ba (交换律) (ab)c=a(bc) (ab)c=a(bc) (结合律) aa= a， aa= a (幂等律) a(ab)=a a(ab)=a (吸收律) 引理6-1.1 设A,是一个代数系统，其中,都是二元运算且满足吸收性，则和满足幂等性。 定理6-1.4 设A,是一个代数系统，其中,都是二元运算且满足交换性、结合性和吸收性，则A上存在偏序关系 ，使A, 是一个格。 定理6-1.5 在一个格A, 中，对任意的a,b

6、,cA, 都有 a(bc) (ab)(ac) (ab)(ac) a(bc) 定理6-1.6 设A, 是一个格，那么对于任意的a,bA, 有 a b ab=a ab=b 定理6-1.7设A, 是一个格，那么对于任意的a,b,cA, 有 a c a(bc) (ab)c 推论 在一个格A, 中，对于任意的a,b,cA，必有 (ab) (ac) a (b(ac) a(b (ac) (ab)(ac) 定义6-1.4 设A1, 1和A2,2是两个格，由它们诱导的代数系统为A1,1,1和A2,2,2，如果存在着一个从A1到A2的映射，使得对任意的a,bA1,有 f(a1b)=f(a)2 f(b) f(a1b

7、)=f(a)2 f(b) 则称f是从A1,1,1到A2,2,2的格同态，亦可称是A1, 1的格同态象。 当f是双射时，则称为从A1,1,1到A2,2,2的格同构，亦称A1, 1和A2,2这两个格同构 定理6-1.8 设f是格A1,1到A2,2的格同态，则对任意的x,yA1，如果x1y，必有f(x)2f(y) 定理6-1.8说明格同态是保序的。一般地，定理6-1.8的逆并不成立【例】设A=a,b,c,d,e，A, 是格，其哈斯图如下图所示，P(A)是A的幂集合，R=x,y|xP(A)yP (A)xy是P(A)上的偏序关系。P(A), R也是格。作映射f：AP (A)，定义为：xA，f(x)= y

8、|yA且y x，即f(a)=a,b,c,d,e=A，f(b)=b,e，f(c)=c,e，f(d)=d,e，f(e)=e。证明f是保序的，但不是格同态。 f(bd)=f(a)=a,b,c,d,e f(b)f(d)=b, ed,e=b, d, e f(bd) f(b)f(d) 定理6-1.9 设A1,1和A2,2是两个格，f 是A1到A2的双射，则 f 是A1, 1 到 A2,2的格同构 ， 当 且 仅 当 对 于 任 意 的 a , b A1，a1bf(a)2f(b)。 作业 (1) (4) (8) 6.2 分配格 由定理6-1.5 可知在一个格A, 中，对任意的a,b,c A, 都有 a(bc

9、) (ab)(ac) (ab)(ac) a(bc) 当上述两个式子中的等号都成立时, 即 a(bc) = (ab)(ac) (ab)(ac) = a(bc) 定义一类特殊的格 定义6-2.1 设A,是由格A,所诱导的代数系统，如果对任意的a,b,cA满足 a(bc)=(ab)(ac) (并运算对交运算可分配) a ( b c ) = ( a b ) ( a c ) (交运算对并运算可分配) 则称A, 为分配格。【例】 设A=a,b,c，P (A)=,a,b,c,a,b,a,c,b,c,a,b,c是A的幂集合，是一个格. 则它诱导的代数系统P (A), , , 其中是集合的并运算，是集合的交运算

10、. 因为集合的并、交运算满足分配律： 任意的P,Q,RP (A) ,有 P(QR)=(PQ)(PR) P(QR)=(PQ)(PR) 所以，P (A), , 是一个分配格。【例】A=a,b,c,d,e，A, 是格，其哈斯图如下左图所示，证明A, 不是分配格。【例】设A=a,b,c,d,e，A, 是格，其哈斯图如上右图所示，证明A, 不是分配格。 注:一个格是分配格的充分必要条件是该格中不含有与钻石格或五角格同构的子格。钻石格五角格计算b(cd)和(bc)(bd)计算c(bd)和(cb)(cd)【例】下图给出了两个格的哈斯图。试证明它们都不是分配格。 注: 设A, 是格，如果|A|5，则A, 一定

11、是分配格。 定理6-2.1 如果在一个格中交运算对于并运算可分配, 则并运算对交运算一定是可分配的. 反之亦然. 定理6-2.2 每个链是分配格 定理6-2.3 设A, 是一个分配格, 那么对于任意的a,b,cA，如果有 ab=ac和ab=ac 成立, 则必有b= c 定义6-2.2 设A,是一个格, 由它诱导的代数系统为A, 如果对于任意的a,b,cA, 当ba时, 有 a(bc)=b(ac) 则称A,为模格 定理6-2.4 格A,是模格, 当且仅当在A中不含有适合下述条件的元素u,v,w v u 且 uw=vw, uw=vw 在一般格中,对于任意的a,b,c, 有以下三个式子成立 a(bc

12、) (ab)(ac) (ab)(ac) a(bc) (ab)(bc)(ca) (ab)(bc) (ca) 定理6-2.5 对于模格,若有三个元素a,b,c, 使得上述三个式子中任何一个式子中把“ ”换成“=”成立, 则另外两个式子把“ ”换成“=”也必成立. 定理6-2.6 分配格必定是模格. 作业 (2) (5) 6.3 有补格 定义6-3.1 设A, 是一个格，如果存在元素aA，对于任意的xA, 都有 a x 则称a为格A, 的全下界，记格的全下界为0。 定理6-3.1 一个格A, ，若有全下界，则是惟一的。 定义6-3.2 设A, 是一个格，如果存在元素bA，对于任意的xA, 都有 x

13、b 则称b为格A, 的全上界，记格的全上界为1。 定理6-3.2 一个格A, ，若有全上界，则是惟一的。【例】 1. 在格中, 空集?是全下界, 而A是全上界 2. 如下图所示的格中, e是全下界, 而a是全上界 定义6-3.3 如果一个格中存在全下界和全上界, 则称该格为有界格 定理6-3.3 设A, 为一个有界格，则对任意的aA,必有a1=1, a1=a a0=a, a0=0 设A,是由有界格A, 所诱导的代数系统 ，aA有a0=0，因为格满足交换律，所以0a=0，这说明0是交运算的零元；同样的道理，0是并运算的幺元，而1是交运算的幺元和并运算的零元 定义6-3.4 设A, 是一个有界格，

14、对于A中的一个元素a，如果存在bA，使得ab=1且ab=0，则称b是a的补元。 如果b是a的补元，从上述定义可以看出，a也是b的补元。因此，可以说a和b是互补的，或者说a和b互为补元。【例】如下图所示的格中, b和c互为补元，b和d也互为补元，b有两个补元c和d。 注: 格中元素的补元并不惟一, 也可能不存在【例】下图是一个有界格的哈斯图。找出a,b,c,d,e的补元。 a的补元: ec的补元: dd的补元: c,ee的补元: a,db没有补元 注: 在有界格中，全上界1的惟一补元是全下界0，而全下界0的惟一补元是全上界1。 定义6-3.5 在一个有界格中，如果每个元素都至少有一个补元, 则称

15、此格为有补格【例】如下图所示三个格均为有补格 定理6-3.4 在有界分配格中,若有一个元素有补元,则必是唯一的 定义定义6-3.66-3.6 一个格如果它既是有补格又是分配格, 则称为有补分配格.并记格中任一元素a的唯一补元为 作业 (1) (4) (6) 6.4 布尔代数 定义6-4.1 有补分配格称为布尔格。 在布尔格中每一个元素a都有补元, 并且是唯一的, 这唯一的补元记为 对于一个有补分配格, 计算一个元素的补元可以确定一个一元运算, 记为 “-”, 称为补运算 定义6-4.2 由布尔格A, ，可以诱导一个代数系统A, -, 这个代数系统称为布尔代数。【例】S是一个非空有限集合, P

16、(S), 是一个格, P (S),是由P (S),导出的代数系统. 集合的并(交)对于交(并)是可分配的, 而且其全上界为S, 全下界为?. 因此P(S),是有界分配格. 对任意TP (S)，都有一个补元ST. P (S), 是一个布尔代数. 定理6-4.1 对于布尔代数中任意两个元素a,b, 必定有 定义 6-4.3 具有有限个元素的布尔代数称为有限布尔代数babababaaa)( 定义 6-4.4 设A, -和B, -是两个布尔代数, 如果存在着A到B的双射f, 对于任意的a,bA, 都有 f(ab)=f(a)f(b) f(ab)=f(a)f(b) 则称A, -和B, -同构)()(afa

17、f 接下来用同构的观点来讨论有限布尔代数的结构 定义6-4.5 设A, 是一个格，具有全下界0，如果有元素a盖住0，则称元素a为原子。【例】如下图所示是三个格的哈斯图, 试找出每个格的原子 注: 若a,b是原子, 且ab, 则ab=0 定理6-4.2 设A, 是一个具有全下界0的有限格，则对于任何一个非零元素b(即b0)，至少存在一个原子a，使得a b。 注: 上述定理中的原子a不一定惟一 引理6-4.1 在一个布尔格中, 当且仅当b c。 引理6-4.2 设A,-是一个有限布尔代数，若b是A中任意非零元素, a1,a2,ak是A中满足aj b的所有原子，则 b=a1a2ak 引理6-4.3

18、设A, -是一个有限布尔代数, bA且b0，a1,a2,ak是满足ai b(i=1,k)的A中的所有原子, 则b=a1a2ak是将b表示为原子的并的惟一形式。0cb 引理 6-4.4 在一个布尔代数A, 中, 对A中任意一个原子a和另一个非零元素b, a b和a 两式中有且仅有一式成立. 定理6-4.3 (Stone表示定理) 设A, -是由有限布尔格A, 所诱导的一个有限布尔代数，S是布尔格A, 中所有原子的集合，则A,- 和P (S), 同构。 推论6-4.1 有限布尔格的元素个数必定等于2n，其中n是该布尔格中所有原子的个数。 推论6-4.2 任何一个具有2n个元素的有限布尔代数都是同构

19、的.b 定理6-4.3 (Stone表示定理) 设A, -是由有限布尔格A, 所诱导的一个有限布尔代数，S是布尔格A, 中所有原子的集合，则A,- 和P (S), 同构。 推论6-4.1 有限布尔格的元素个数必定等于2n，其中n是该布尔格中所有原子的个数。 推论6-4.2 任何一个具有2n个元素的有限布尔代数都是同构的. 作业 (2) (3) (6) 6.5 布尔表达式 设A, -是一个布尔代数, 考虑一个从An到A的函数【例】1. A=0,1, 下表给出了一个从A3到A的一个函数 2. B=0,1,2,3,下表给出了一个从B2到B的一个函数001011011200013113100232 定

20、义6-5.1 设A, -是一个布尔代数, 并在这个布尔代数上定义布尔表达式如下: (1) A中任何元素是一个布尔表达式 (2) 任何变元是一个布尔表达式 (3) 如果e1和e2是布尔表达式, 那么 ,(e1e2)和 (e1e2)也是布尔表达式 (4) 只有通过有限次运用规则(2)和(3)所构造的符号串是布尔表达式【例】 0,1,2,3, -是一个布尔代数, 下列三个符号串都是布尔表达式 0 x1, , 1e21)1 (xx )()()32(3121xxxx 定义6-5.2 一个含有n个变元的布尔表达式, 称为含有n元的布尔表达式. 记为E(x1,x2,xn), 其中x1,x2,xn为变元 定义

21、6-5.3 布尔代数A, -上的一个含有n元的布尔表达式E(x1,x2,xn)的值是指: 将A中元素作为变元xi的值来代替表达式中相应的变元(即对变元赋值), 从而计算出表达式的值.【例】 设布尔代数0,1, -上的布尔表达式为: )()()(),(322121321xxxxxxxxxE 定义6-5.4 设布尔代数A, -上两个n元的布尔代数为E1(x1,x2,xn)和E2(x1,x2,xn), 如果对于n个变元的任意赋值 , 时, 均有 则称这两个布尔表达式是等价的.【例】在布尔代数上定义: 一个n元布尔表达式确定一个从An到A的函数。【例】 A=0,1, 右表给出了一个从A3到A的一个函数

22、 iixxAxi),(),(212211nnxxxExxxE)()()(),(3121321321xxxxxxxxxxE00101101)()(31211xxxxE)(3212xxxE 定义 6-5.5 设 为布尔代数,一个从An到 A的函数，如果它能够用 上的n元布尔表达式表示，那么，这个函数就称为布尔函数。 定理 6-5.1 对于两个元素的布尔代数,任何一个从 0,1n到 0,1的函数,都是布尔函数. 布尔小项 形如 , 其中 是xi或 中的任一个 析取范式 一个在 上的布尔表达式, 如果它能表示成小项的并, 我们称为这个布尔表达式为析取范式. nxxx21ixix 求函数的析取范式 (1) 取使函数值为1的有序n元组分别构造小项 其中 (2) 将这些小项做并运算【例】求由右表定义的函数的析取范式0 1 个分量为元组中第若个分量为元组中第若inxinxxiiinxxx2110100001 布尔大项 形如 , 其中 是xi或 中的任一个 合取范式 一个在 上的布尔表达式, 如果它能表示成大项的交, 我们称为这个布尔表达式为合取范式. 求函数的合取范式 (1) 取使函数值为0的有序n元组分别构