《格与布尔代数》PPT课件.ppt

1、离散数学，中北大学，电子与校正机科学技术学院，2020年8月6日星期四，2020/8/6，第6章格与布尔代数，2020/8/6，偏差格，右边两个哈斯图的区别是什么？2020/8/6、定义6.2.1作为偏置，对于任意的a、bL、a、b，如果存在最大下界和最小上界，则称为格，简称为l。 如果l是有限集合，则称格为有限格。 一旦偏置关系定义的格称为偏置格，2020/8/6，保交和保连，格中任意取a、bG，a、b的最大下界和最小上界唯一存在，都属于l。 a、b的最大下界用a*b表示，a与b的保持交叉点，a、b的最小上界用ab表示，a与b的保持交叉点，即，a*b=GLBa、b，ab=LUBa、b，也可分

2、别称为和、和、和，(2)a为一个集合，P(A )为应该a的集合， 2020/8/6以及6.2.1 (继续)分析一个偏置是否等级并且确定对于l的所有两个元素子集是否存在最大和最小上界解(1)对于a，bZ，其中a*b=GLBa，b 有2020/8/6、例子6.2.1解(继续)、(2)对S1、S2P(S )、S1*S2=GLBS1、S2=S1S2P(S )。2020/8/6、例6.2.1解(续)、(4)由于全顺序集中，对于任意a、bL，a b或b a成立。 如果a-b成立，则a、b将最大下界设为a，将最小上界设为b。 如果b-a成立，则a、b将最大下界设为b，将最小上界设为a。 所以是一个价格。 定

3、义2020/8/6、6.2.2，作为具有两个二元运算的代数系统，如果满足交换律、结合律和吸收律则称为格。 代数系统中定义的格叫代数格。 2020/8/6，例6.2.3，设a为一个集合，设P(A )为a的幂集合，分别为集合的正交和并行运算，试图证明代数系统是一个格。 从集合的演算性质可知，因为正交和并演算满足交换律、结合律、吸收律，所以从定义可知，是格。2020/8/6、定义6.2.3、代数系统为一个格，如果s满足： (1)S； (2)运算和子集s被称为闭合的是子集，简称s被称为l的子集。 另外，在2020/8/6、例子6.2.4、正整数集合z中，对于任意的a、bP、ab=a、b进行了规定。 其

4、中，a和b是表示a和b的最小公倍数ab=(a )的S=3k | kZ，测试证明是子网格。 2020/8/6，例6.2.4证明，显然是s。 对于任意的3m、3nS，因为有3m3n=3m、3n=3m、nS、3m3n=(3m、3n)=3(m、n)S，所以是子格式。 2020/8/6、子网格、定义6.2.4为1网格、S L、如果满足s:(1) s； (2)对任何a、bS的保持正交性和保持连接运算均有ab=GLBa、bS、ab=LUBa、bS，将其称为一个子小区，简称s为l的子小区。 如果设定为2020/8/6、例6.2.5、一个格式，且设定为aL、S=x|xL、x a，则s为l的格式。 为了证明a a

5、，aS，即s是非空子集。 从x a和y a可以看出，对于任何x和y，xy=GLBx、y a，即xy=GLBx、yS xy=LUBx、y a，即xy=LUBx，yS是l个子单元。 将2020/8/6、定义6.2.5、和作为2个格，将f作为从l到s的映射。 对于任意的x、yL，如果有f(xy)=f(x)* f(y )、f(xy)=f(x) f(y )，则将f称为格到格的格同态映射，简称为格同态的f为格同态，在f分别为单射、全射、双射的情况下，f分别为单一格同态、满射2020/8/6、定义6.2.6作为一个格式，对于任意的a、b、cL，有a(bc)=(ab) (ac )、a(bc )。将2020/8

6、/6、例6.2.7、(1)a作为任意的集合，价格是否分配价格？ (2)把p作为命题式集合，分别是命题式的合计，和格是分配格还是解(1)集合的交叉，并列演算满足分配律，所以格是一个分配格。 (2)命题式的提取、共现演算因为满足分配律，所以格为分配格。 2020/8/6，定理6.2.4，所有的链都是分配价格。 证明是链，因此是格，任意取a、b、cL，(1)a是三者中最大的，即b a、c a； (2)a是三者中最大的，即不是a b或a c。 在情况(1)中，因为bc a，所以a(bc)=bc。 显然，ab=b，ac=c。 a(bc)=bc=(ab)(ac )。 2020/8/6、定理6.2.4 (继

7、续)、在情况(2)下abc、ab=a或ac=a到(ab)(ac )、2020/8/6、例6.2.8、右图所示的两个格式都不是分配格式。 由于分析是链为分配格，所以同一链上的要素都满足分配方程式，不满足分配方程式的可能性最大的要素不在同一链上。 要验证，请选择b、c和d。2020/8/6、例6.2.8 (继续)、图中的b、c、d这三个要素的验证取消。 在图中，b(cd)=be=b，(bc)(bd)=aa=a。 在图中，b(cd)=be=b，而bc)(bd)=aa=a。 因此，在图(a )和(b )两者中，b (CD )、(BC )、(BD )并不是它们的分配价格。2020/8/6、定理6.2.5

8、、一个格为分配格的足够的必要条件是，该格与6例15.2.86这两个五要素格中的任一个都不具有相同的构造。2020/8/6、性质6.2.2、(1)4个要素以下的价格均为分配价格。 (2)5个要素的格只有2个格是非分配格(图6.2.8(a )和(b ) )，其馀3个格(右图(a )、(b )和(c ) )都是分配格。 设定为2020/8/6、定理6.2.6、分配价格，对于任意的a、x、yL，如果ax=ay且ax=ay，则设定为x=y。 证明x=x (ax ) (吸收律)=x (ay ) (已知ax=ay )=(xa ) (分配律)=x (ay ) (已知ay )对于任何a、b、cL，如果存在ab

9、a(bc)=b(ac )或者(模型) ab a(bc)=b(ac )，那么证明作为分配价格，对于任意a、b、cL，如果是a b，则ab=b，从分配规则中得到的a (bc)=(ab)(ac)=b(ac )是模块。2020/8/6、性质6.2.3、(1)各链接为模块。 (2)4个要素以下的格全部为模块，将2020/8/6、定义6.2.8设为一个格，如果存在要素aL，则对于任意的xL，如果存在a x (或x a )，则将a称为格的全下界(或全上界)，分别记为当存在(a1a2) an )=a1a-2 an (a1a2) an )=a1a-2 an时，a1a-2 an和a1a-2 an分别为格子l的全下

10、界和全上界，即，a1a-2 an=0a-1 a-2 an=1。2020/8/6、定理6.2.8、格中，全下界和全上界分别为集合l的最小元和最大元，根据最大元和最小元的唯一性，定理6.2.8为一个格、若格的全上，为2020/8/6、定义6.2.9、有界格，1和0分别为存在bL，设ab=0，ab=1，则b被称为a的补正源，表示为a。 如果有界格内的所有元素都存在补丁，则称为有补丁。 2020/8/6、例6.2.9、下图有边界格，求其所有要素的补元(如果有)。2020/8/6、例6.2.9 (续)，解与图a中d和c互补，其中a、d都是e的补偿源，c和e都是d的补偿源，b不是补偿源。 图b3360=1

11、、1=0、a=b、a=d、b=a、b=c、c=d、c=b、d=a、d=c的情况下的图a在2020/8/6、定理6.2.9、有界分配格(既是有界格也是分配格，简称有界分配格)中，如果元素aL中存在补元，则该元素的补元必须是唯一的。 证明a有两个校正元b和c。根据校正元的定义，ab=0=ac，ab=1=ac是根据定理获知的，并且b=c。 推论6.2.1补充分配格(既有补充格又有分配格，简称补充分配格)中，各要素都存在唯一的补充要素。 假设有2020/8/6、定理6.2.10、候补分配价格，“ ”是该价格的偏置顺序，对于任意的a、bL，(1)(a)=a； (适用律) (2)(ab )=a b，(ab

12、)=ab； (3)a b b a。 (4)a b ab=0 ab=1。 2020/8/6，定理6.2.10 (继续)，(1)a是a的补偿元，相反，a也是a的补偿元，证明是从推论15.2.1得到的，(a) (2)(ab)(ab)=(ab)a)(ab)b ) (分配律)=(aa ) b ) 可以证明是一样的，(ab)=ab。 如果得到2020/8/6、定理6.2.10 (继续)、(3)、a b、ab=a，那么(ab)=a有De Morgan法则(4)，根据a b，如果有b a，那么ab aa=0，即2020/8/6、定理另外，0是全下界的定理6.2.10 (继续)、“ab=1，De Morgan律

13、，如果有ab=0，则a(ab)=a0=a在上式的左边使用分配律，如果得到a (，则将2020/8/6，定义6.3.1，补充分配格称为布尔格。 定义6.3.2由布尔引导的代数系统称为布尔代数。 如果布尔代数的元素数是有限的，则此布尔代数称为有限布尔代数，否则称为无限布尔代数。2020/8/6、布尔代数、布尔代数有补分配格，补分配格必须满足它有格、全上界和全下界，分配律成立，各要素中存在补要素。 显然，全上边界1与全下边界0可用下面的公式描绘，使得l中存在两个元素0与1，对于任何aL存在a1=a，a0=a。2020/8/6、布尔代数、候补元的存在可以用以下互补律来记述。 对于任意aL，存在aL，使

14、得aa=0，aa=1。 格可以用交换律、结合律、吸收律来记述。 因此，有补分配价格必须满足交换律、结合律、吸收律、分配律、同一律、互补律。 另外，可以证明交换律、分配律、一律、从互补律中得到结合律、吸收律。 因此，布尔代数有以下等价定义： 2020/8/6、定义6.2.3、代数系统。 其中，在b中的二元运算中，对于任意的a、b、cB，满足(1)交换律： ab的(2)分配律： a (bc)=(ab) (ac )，a (bc)=(ab) (ac )； (3)同样： b中存在2个元素0和1，对于任意的aB，a1=a，a0=a。 (4)互补律：对于任意的aB，存在aB，使aa=0，aa=1。 称为布尔代数，2020/8/6，定义6.2.3 (续)，通常将布尔代数标记为。 为方便起见，也简称为b的是布尔代数。2020/8/6、定义6.2.4、布尔代数、s为b的非空子集合，如果运算、和都关闭了s，则称为的子布尔代数，s简称为b的子布尔代数。 很明显，对于任何布尔代数，子集0、1、b总是构成b的子布尔代数，这两个子布尔代数称为平凡的子布尔代数。 考察2020/8/6、例6.3.1、下图所示的布尔代数。 S1=a、a、0、1、S2=