格与布尔代数课件

1、第六章 格与布尔代数1、格的基本概念2、分配格3、有补格非本次期末考试内容4、布尔代数5、布尔表达式第1页，共28页。1 格的基本概念 图、三个偏序集哈斯图1262324361246231123定义1：设是一个偏序集，若A中任意两个 元素都有最大下界和最小上界，则称 为格。格格不是格第2页，共28页。例：判断、 是否是格。其中:I+ 是正整数，D是整除关系，Sn =n的所有因子 如：S6=1,2,3,6、S8=1,2,4,8、S12=1,2,3,4,6,12、 S30=1,2,3,5,6,10,15,30解：是格 整除关系是偏序关系，对a,bI， a、b的最小上界等于a、b的最小公倍数， a、

2、b的最大上界等于a、b的最大公约数。第3页，共28页。 是格 子集关系是偏序关系，对a,b P(S)， a、b的最小上界等于ab， a、b的最大上界等于ab。是格，偏序关系的哈斯图如下：12368421312641212351563010=,第4页，共28页。45312671234576这两个图是偏序关系，但不是格。第5页，共28页。定义2：格代数设是一个格，若在A上定义两个二元运算和,使得对于a,bA,ab等于a和b的最小上界,ab等于a和b的最大下界,则称为由格所诱导的代数系统。二元运算和分别称为并运算和交运算。显然， 所诱导的代数系统为 第6页，共28页。 1 2 3 6 1 2 3 6

3、 1 1 2 3 6 1 1 1 1 1 2 2 2 6 6 2 1 2 1 2 3 3 6 3 6 3 1 1 3 3 6 6 6 6 6 6 1 2 3 6S6= 1,2,3,6，则是一个格1236下面的运算表表示的系统就是由格所诱导的代数系统第7页，共28页。定义3：设是一个格，由格所诱导的代数系统为。设BA且B ，如果运算和在B上封闭，则称 是的子格。注： (1) 可以证明子格必是格（证明略） (2) 不能理解为： BA且 是格，则 是 的子格。应特别注意条件: “运算和在B上封闭”。 (3) 对于格， BA且B，则 一定是 偏序集，但不一定是格。第8页，共28页。例：B1 = 1,2

4、,3,6 ， B2 = 5,10,15,30 ， 和都是 的子格。 1 2 3 6 1 2 3 6 1 1 2 3 6 1 1 1 1 1 2 2 2 6 6 2 1 2 1 2 3 3 6 3 6 3 1 1 3 3 6 6 6 6 6 6 1 2 3 6可见运算和在B1上封闭，B1 S30 且B1 是 的子格，同理可证是 的子格2315156301012365153010第9页，共28页。2315163010例：B3 = 1,2,3,6,10,15,30 ，显然 是格。但1015 = 5 B3，即运算在B3上不封闭， 不是 的子格。23151563010例：B4 = 2,3,6 ，则 是偏

5、序集， 不是格，更不是的子格。236第10页，共28页。对偶原理：设P是对任意格都为真的命题，如果在命题P中把换成，换成，换成，就得到另一个命题P，把P称为P的对偶命题。则P对任意格也是真命题。（其中“”是“”的逆关系）若是格，可证明也是一个格，且它们的哈斯图是上下颠倒的。2315156301030101562351的逆关系在中任何两个元素的的结果值必然等于这两个元素在中的结果值；任何两个元素的的结果值必然等于这两个元素在中的结果值；反之亦然。第11页，共28页。格的基本性质：(除自反性、反对称性和传递性之外)设格，对A中的任意元素 a,b,c，有：(1) aab、bab、aba、abb(2)

6、 如果ab且cd，则acbd，acbd(3) 若bc，则aA，有abac，abac （保序性）(4) 交换律：ab = ba、ab = ba 结合律：a(bc) = (ab)c、 a(bc) = (ab)c 幂等律：aa = a、aa = a 吸收律：a(ab) = a、a(ab) = a第12页，共28页。(5) ab ab=a ab = b(6) 分配不等式： a(bc)(ab)(ac)、 (ab)(ac)a(bc)格的基本性质：(除自反性、反对称性和传递性之外)第13页，共28页。(1) aab、bab、aba、abb证明： ab是a和b的最小上界 aab、bab， 由对偶原理，有aba

7、、abb (2) 如果ab且cd，则acbd，acbd证明： ab，由(1)得bbd，由传递性得：abd cd，由(1)得dbd，由传递性得： cbd bd是a和c的一个上界，而ac是a和c的最小上界， acbd 同理可证：acbd第14页，共28页。(3) 若bc，则aA，有abac，abac证明: bc，aa，由性质(2)得：abac，abac(4) 交换律：ab = ba、ab = ba 结合律：a(bc) = (ab)c、 a(bc) = (ab)c 幂等律：aa = a、aa = a 吸收律：a(ab) = a、a(ab) = a证明：幂等律 aa， a是a的上界，而aa是a的最小上

8、界， aaa ，又 aa a， 由反对称性得：aa = a 由对偶原理得，aa = a第15页，共28页。证明：吸收律 a a a b a a(a b)aa， a(a b)a 又aa (a b), a(a b) = a由对偶原理得， a(ab) = a证明：结合律 b (a b) c, c (a b) c bc(a b) c，又aa b (a b) c, a( bc)(a b) c同理可证(a b)ca(bc) ， a(bc) = (ab)c由对偶原理得，a(bc) = (ab)c第16页，共28页。(5) ab ab=a ab = b证明：ab ab=a ab = b ab (1) ab,

9、aa a ab，又aba ab=a (2) ab = (ab)b = b (3) aab a b 第17页，共28页。引理：设是代数系统，其中,都是二元运算且满足吸收律，则和都满足幂等律.证明： a,bA, ,满足吸收律，则有 (1) a (ab) = a, (2) a (ab) = a 由 b 的任意性，在(1)式中令 b = ab ，代入(2)得 aa = a 同理可证： aa = a第18页，共28页。定理1：设是代数系统，其中,都是二元运算且满足交换律、结合律和吸收律，则A上存在偏序关系，使是一个格。证明：在A上定义一个二元关系为： 对于a,bA,ab当且仅当 ab = a 首先证明是

10、偏序关系 (1) a,b,cA， ,满足吸收律 ,满足幂等律 即对aA，有a a = a a a 自反 (2) 若a b且b a，则ab=a且ba=b， 即有a=ab，b=ab，a=b， 反对称 (3) 若a b且bc，则ab=a且bc=b， ac= (ab)c=a(bc)=ab=a ac 传递 是偏序关系第19页，共28页。其次证明A中任意两个元素a,b都有最小上界和最大下界。 先证ab是a和b的最大下界 由 的定义知：(ab)a=ab，(ab)b=ab ab a,ab b，即ab是a和b的下界 设c是a和b的任一下界，即c a，c b，于是有 ca=c，cb=c，而c(ab)=(ca)b=

11、cb=c c ab，即证明了ab是a和b的最大下界 再证ab 是a和b的最小上界 a,bA，a(ab)=(aa)b=ab aab b(ab)=a(bb)=ab bab ab 是a和b的上界 设c是a和b的任一上界，即ac，bc，于是有 ac=c，bc=c，而(ab)c=a(bc)=ac=c abc，即证明了ab是a和b的最小上界 是格第20页，共28页。说明：该定理可以作为格的另一个定义，即设是代数系统，其中,都是二元运算且满足交换律、结合律和吸收律，则是一个格。第21页，共28页。定义：和是两个格，由它们诱导的代数系统分别是 ，如果存在一个从A1到A2的映射f，使得对a,bA，有f(a1b)

12、=f(a)2f(b)，f(a1b)=f(a)2f(b)，则称f为由到的一个格同态；称是的格同态象；当f是双射时，称和是同构的。注：同构的两个格的哈斯图是一样的，只是各结点的标记不同而已。第22页，共28页。例：设A1=a,b,c, A2=P(A1), (是小于等于)和(是子集关系)都是格，如下图所示。定义 f:A1A2，f(x)=y | yx,yA，证明f是格同态。其中c b a， A2=P(A1)=,a,b,c,a,b,a,c,b,c,a,b,cacb,cba,ca,b,ca,babc第23页，共28页。证明： 诱导的代数系统是 诱导的代数系统是x1,x2A1f (x11x2) = f (m

13、inx1,x2) = y | yminx1,x2 = y | yx1 y | yx2 = f(x1) 2 f(x2)f (x11x2) = f (maxx1,x2) = y | ymaxx1,x2 = y | yx1 y | yx2 = f(x1) 2 f(x2)存在一个从A1到A2的映射f，使得对 x1,x2 A，有f(x11x2)=f(x1)2f(x2)，f(x11x2)=f(x1)2f(x2)f 是 A1 到 A2 的格同态。第24页，共28页。定理2：设f是由格到格的格同态，则对x,yA1，如果x 1 y，必有f(x) 2 f(y)。证明： x 1 y 由公式(5) ab ab=a x

14、1y=x f (x) = f (x1y) = f (x)2f (y) f (x) 2 f (y)注：该定理说明 格同态保序，但反之不一定成立，即保序不一定能推出格同态。第25页，共28页。例：S12=1,2,3,4,6,12，和都是格3126412 3211264定义双射函数f: S12S12，f(x)=x，a,bS12，若 a / b ，则有 a(小于等于)b，即 f(a) (小于等于)f(b) 到是保序的。 但 213 = 1, f (213) = f (1) = 1 而 f (2)2 f (3) = 223 = 2 f (213) f (2) 2f (3) f 不是格同态（即保序不一定能

15、推出格同态）格同态保序，但反之不一定成立，即保序不一定能推出格同态。第26页，共28页。定理3：设f是由格到格的格同构，当且仅当对a,bA1，有a1b f(a)2f(b)。证明： (1) 设f是到的格同构 由定理2， a,bA1，有 a 1 b f (a) 2 f (b) 反之，若f (a) 2 f (b)，则f (a) 2 f (b) = f (a)， 于是有 f (a 1 b) = f (a)，由于 f 是双射 a1 b = a ， a 1 b a 1 b f (a) 2 f (b)。第27页，共28页。证明： (2) 设 a,bA1，有 a 1 b f (a) 2 f (b) a 1 b 1 a， a 1 b 1 b，由已知有f (a 1 b) 2 f (a)， f (a 1 b) 2 f (b)f (a 1