CHAPT19格与布尔代数

《CHAPT19格与布尔代数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十九章格与布尔代数9/25/20211离散数学目录本章介绍另外一类具有两种二元运算的代数系统——格，以及特殊的格——布尔代数：格是描述集合或命题的代数系统，称为集合代数或命题代数§19.1格的定义§19.2格的性质§193几种特殊的格§19.4布尔代数§19.5有限布尔代数的结构9/25/20212离散数学§19.1格的定义9/25/20213离散数学格的定义定义19.1.1：设L,≤是一个偏序集。如果对任意a，b∈L，{a，b}在L中都有最大下界和最小上界，则称L,≤是一个格。常将{a，b}的最大

2、下界记为inf{a,b}，最小上界记为sup{a,b}。9/25/20214离散数学复习定义2.4.5和定义2.4.6上(下)界：设是一个偏序集,BA,若存在a∈A,使得对任何x∈B都有xa(或ax),则称a为B的上(下)界。（如果存在，上(下)界可在A中，也可在B中）上(下)确界：设是一个偏序集，BA，若a是B的一个上(下)界，且对B的任何一个上(下)界x，均有ax(或xa),则称a为B的上(下)确界，也可称为最小上界（或最大下界）。记为a=sup(B)(a=inf(B))。

3、9/25/20215离散数学几个是格的偏序集(a)(b)(c)图(a)中是一个全序集(链)，自然是一个格。不难验证，图(b)和图(c)中的偏序集中任意两个元素都有最小上界和最大下界，因而都是格。9/25/20216离散数学并非所有偏序集都是格不是所有的偏序集都是格。图(d),(e),(f)所表示的偏序集都不是格。不难找出它们之中存在着两个元素，或没有最小上界，或没有最大下界。(d)(e)(f)9/25/20217离散数学子集格例1：设S是集合，ρ(S)是S的幂集。于是ρ(S),是一个格，称为S的子集格。

4、因为：首先，ρ(S),是一个偏序集；其次，对任意的A,B∈ρ(S)，有sup{A,B}=A∪B；inf{A,B}=A∩B。9/25/20218离散数学整除格例2：设Z+是所有自然数的集合。

5、是Z+上的整除关系。于是Z+,

6、是一个格，称为整除格。因为首先，Z+,

7、是一个偏序集；其次，对任意的m,n∈Z+，有sup{m,n}=[m,n](最小公倍数)；inf{m,n}=(m,n)(最大公约数)。9/25/20219离散数学子群格例3：设G是群，S(G)表示G的所有子群组成的集合。于是S(G),

8、是一个格，称为G的子群格。因为首先，S(G),是一个偏序集；其次，对任意的H,K∈S(G)，有sup{H,K}是包含H∪K的最小子群；inf{H,K}=H∩K。9/25/202110离散数学子格定义19.1.2：设L,≤是格，SL，如果S,≤也是格，则称S,≤是L,≤的子格。偏序集的任何子集仍是偏序集。但是格L,≤中的偏序集L的子集S却不一定能够构成格S,≤。例如，在整除格中，取S={1，2，3}，则S,

9、不是格。因为按整除关系[2,3]=6,而6S，即sup{2,3}不

10、存在。9/25/202111离散数学整除格的子格例4：设n是正整数，Sn={k

11、k＞0且k

12、n}。比如：S6={1,2,3,6}，S8={1,2,4,8}，S24={1,2,3,4,6,8,12,24}，…容易验证，Sn,

13、是格，且m

14、n当且仅当SmSn。因此对任意的m，n，若m

15、n，则Sm,

16、是Sn,

17、的子格。当然Sn,

18、的子格还有其它形式，比如{a},

19、也是Sn,

20、的子格，其中a∈Sn。9/25/202112离散数学格中的运算格中的inf和sup实际上是两个二元运算。用算符×和

21、分别表示inf和sup，即a×b=inf{a,b}，ab=sup{a,b}。这两种运算满足如下的性质：(1)交换律：a×b=b×a，ab=ba；(2)结合律：a×(b×c)=(a×b)×c,a(bc)=(ab)c(3)吸收律：a×(ab)=a,a(a×b)=a。？因为a×(ab)=inf{a,sup{a,b}}，所以a×(ab)≤a，即inf{a,sup{a,b}}≤a又因为，a≤a且a≤sup{a,b}，所以a是a与sup{a,b}的下界，即a≤inf{a,sup{a,b}}于是inf

22、{a,sup{a,b}}≤a≤inf{a,sup{a,b}}即a×(ab)=a。同理可证a(a×b)=a。格就是具有以上性质的二元运算的代数系统。9/25/202113离散数学从代数系统来定义格定义19.1.3：设L是一个集合，×和是L上的两个二元封闭运算，若×和对a,b,c∈L，满足：(1)交换律：a×b=b×a，ab=ba；(2)结合律：a×(b×c)=(a×b)×c,a(bc