电子工业出版社：计算机类本科规划教材《离散数学》课程教学资源（PPT课件讲稿）第8章 格与布尔代数

第障格与布尔代数 (2)证明vab∈X,a∧b是集合a,b}的最大下界。因为 (a∧b)c=a∧b和(a∧b)∧b=a∧b 所以a∧b≤组且a∧b≤b,即a∧b是ab}的下界。 下证a∧b是ab}的最大下界 设c是{ab}的任一下界,即c≤a,c≤b,那么有 c∧a=c,c∧b=c 而c∧(a∧b)=CAa)∧b=c∧b=c 所以c≤a∧b,即a∧b是1ab}的最大下界 (3)证明a∧b=a的充分必要条件是a∨b=b 设a∧b=a,由吸收率可得 a∨b=(a∧b)∨b=bV(b∧a)=b,即aVb=b 设a∨b=b,由吸收率可得 a∧b=a∧(aVb)=a,即a∧b=a

第8章 格与布尔代数 ⑵证明a,bX，a∧b是集合a,b的最大下界。因为 (a∧b)∧a=a∧b和(a∧b)∧b=a∧b 所以a∧b≼a且a∧b≼b，即a∧b是a,b的下界。 下证a∧b是a,b的最大下界。 设c是a,b的任一下界，即c≼a，c≼b，那么有 c∧a=c，c∧b=c 而 c∧(a∧b)=(c∧a)∧b=c∧b=c 所以 c≼a∧b，即a∧b是a,b的最大下界。 ⑶ 证明a∧b=a的充分必要条件是a∨b= b 设a∧b=a，由吸收率可得 a∨b=(a∧b)∨b=b∨(b∧a)=b，即a∨b= b 设a∨b=b，由吸收率可得 a∧b=a∧(a∨b)=a，即a∧b=a

第障格与布尔代数 (4)证明∨abeX,aVb是集合1a,b}的最小上界。 根据(3,偏序关系≤可以等价的定义为: ≤<ab>a,b∈X且a∨b=b}, 用这个定义和类似于(2)的方法可以证明a∨b是集合{ab}的 最小上界 因此,<X,令>构成一个格 根据定理81.3,可以给出格的另一个等价定义 定义8.1.4设<X米∞是代数系统,其中*和。都是二元运 算,如果*和。在上封闭且满足交换律、结合律和吸收律 则称<X*。>为格。 根据定义81.4和定理81.1,格<X≤>导出的代数系统 <X∨,∧>是格,以后不再区分偏序集定义的格和代数系统 定义的格,统称为格

第8章 格与布尔代数 ⑷ 证明a,bX，a∨b是集合a,b的最小上界。 根据⑶，偏序关系≼可以等价的定义为： ≼=a,b|a,bX且a∨b=b， 用这个定义和类似于⑵的方法可以证明a∨b是集合a,b的 最小上界。 因此，X,≼构成一个格。 根据定理8.1.3，可以给出格的另一个等价定义。 定义8.1.4 设X, * , ∘是代数系统，其中*和∘都是二元运 算，如果*和∘在X上封闭且满足交换律、结合律和吸收律， 则称X, * , ∘为格。 根据定义8.1.4和定理8.1.1，格X,≼导出的代数系统 X,∨,∧是格，以后不再区分偏序集定义的格和代数系统 定义的格，统称为格

第障格与布尔代数 定理8.1.4设<X,≤>是格,∨是X上的并运算,∧是X上 的交运算。则∨a,beX有 (1)a≤b当且仅当a∧b=a (2)a≤b当且仅当a∨b=b 证明:(1)设a≤b,下证a∧b=a 由a≤a且a≤b知a是集合ab}的下界,故有a≤a∧b;另 一方面,由于a∧b是{ab}的最大下界,所以是ab}的下界, 即a∧b≤a。根据偏序关系的反对称性得a∧b=a 设a∧b=a,下证a≤b a=a∧b≤b,即a≤b (2)可类似(1)进行证明

第8章 格与布尔代数 定理8.1.4 设X,≼是格，∨是X上的并运算，∧是X上 的交运算。则a,bX有 ⑴ a≼b当且仅当a∧b=a ⑵ a≼b当且仅当a∨b=b 证明：⑴ 设a≼b，下证a∧b=a 由a≼a且a≼b知a是集合a,b的下界，故有a≼a∧b；另 一方面，由于a∧b是a,b的最大下界，所以是a,b的下界， 即a∧b≼a。根据偏序关系的反对称性得a∧b=a 设a∧b=a，下证a≼b a=a∧b≼b，即a≼b ⑵ 可类似⑴进行证明

第降格与布尔代数 定理8.1.5设<X,令>是格,∨是X上的并运算,∧是X上 的交运算。∨a,b,c,d∈X,若a≤b且c≤d,则a∨c≤b√d, a∧c≤b∧d 证明:a≤b≤b∨d,C≤4b∨d,因此a∨c≤b√d 类似的可以证明a∧c≤b∧d 定理81.6设<X>是格,∨是X上的并运算,∧是X上 的交运算。则∨a,b,c∈eX有 (1)aV(b∧c)≤(aVb)∧(aVc) (2)(a∧b)(a∧c)≤a∧(bVc) 证明:(1)根据定理8.1.5,由a≤a和b∧c≤b得 aV(b∧c)≤a∨b 又由a≤a且b∧c≤c得 aV(b∧c)≤aVc 从而得到aV(b∧c)≤(aVb)∧(aVc) 利用对偶原理,即得(2)。 般地说,格中的∨和∧并不满足分配律

第8章 格与布尔代数 定理8.1.5 设X,≼是格，∨是X上的并运算，∧是X上 的交运算。a,b,c,dX，若a≼b且c≼d，则a∨c≼b∨d， a∧c≼b∧d 证明： a≼b≼b∨d ，c≼d≼b∨d，因此a∨c≼b∨d 类似的可以证明a∧c≼b∧d 定理8.1.6 设X,≼是格，∨是X上的并运算，∧是X上 的交运算。则a,b,cX有 ⑴ a∨(b∧c) ≼ (a∨b)∧(a∨c) ⑵ (a∧b)∨(a∧c) ≼ a∧(b∨c) 证明：⑴ 根据定理8.1.5，由a≼a和b∧c≼b得 a∨(b∧c)≼a∨b 又由a≼a且b∧c≼c得 a∨(b∧c)≼a∨c 从而得到 a∨(b∧c)≼(a∨b)∧(a∨c) 利用对偶原理，即得⑵。 一般地说，格中的∨和∧并不满足分配律

第障格与布尔代数 8.1.2子格和格的同态 定义8.1.5设<X,∨,∧>是格,B是X的非空子集,如果B 关于运算∨和∧也构成格,则称<B,∨,∧>是<X,∨,∧>的子 格 在例81中,令B1=12,3,6},B2=124,6,12},则 <B1∨V,∧>和<B2∨,∧>是格<S12V,∧>的子格 令B3=1,2,3,12},由于2V3=6,而6∈B3,所以 <B3∨,∧>不是格<S12,∨,∧>的子格 以下定义格的同态。 定义8.6设<H1,V1∧1>和<k2,V22>是格,其中∨1 ∧1,V2和∧2都是二元运算。/是从X到H2的一个映射,对任 意的ab∈X1有aVb)=a)∨2b), f(a∧1b)f(a)∧2f(b) 则称是格<X12V1∧p到格<H2V2,2>的格同态。如果是 单射、满射和双射,分别称禔是格单同态、格满同态和格同 构。称<八X1)V22>是<X1∨1,∧1>的格同态像

第8章 格与布尔代数 8.1.2子格和格的同态 定义8.1.5 设X,∨,∧是格，B是X的非空子集，如果B 关于运算∨和∧也构成格，则称B,∨,∧是X,∨,∧的子 格。 在例8.1中，令B1 ＝1,2,3,6，B2 ＝2,4,6,12，则 B1 ,∨,∧和B2 ,∨,∧是格S12,∨,∧的子格。 令B3 ＝1,2,3,12，由于2∨3=6，而6B3，所以 B3 ,∨,∧不是格S12,∨,∧的子格。 以下定义格的同态。 定义8.1.6 设X1 ,∨1 ,∧1 和X2 ,∨2 ,∧2 是格，其中∨1 , ∧1 ,∨2和∧2都是二元运算。f是从X1到X2的一个映射，对任 意的a,bX1有f(a∨1 b)=f(a)∨2 f(b)， f(a∧1 b)=f(a)∧2 f(b) 则称f是格X1 ,∨1 ,∧1 到格X2 ,∨2 ,∧2 的格同态。如果f是 单射、满射和双射，分别称f是格单同态、格满同态和格同 构。称f(X1 ),∨2 ,∧2 是X1 ,∨1 ,∧1 的格同态像