人民邮电出版社：高等学校21世纪教材《离散数学》电子教案（PPT课件）第九章 格与布尔代数

高等学校21卌纪教材 第九章格与布尔代数 91橙 9.2布尔代数 9.3子布尔代数、积布尔代数 初布尔代数同态 9.4布尔代数的原子表示 9.5布尔代数B2 9.6布尔表达式及其范式定理 PT PRESS 人民邮电出版社 退出

第九章 格与布尔代数 9.1 格 9.2 布尔代数 9.3 子布尔代数、积布尔代数 和布尔代数同态 9.4 布尔代数的原子表示 9.5 布尔代数Br 2 9.6 布尔表达式及其范式定理 退出

高等学校21卌纪教材 91格 1.格作为偏序集 定义9..1设是一个偏序集,若对任 意a,b,∈L,存在gb{a,b}和lub{a,b},则称为<L,所诱导的代数结构的格 若L是有限集合,称<L,☆为有限格 PT PRESS 人民邮电出版社

9.1 格 1．格作为偏序集 定义9.1.1 设是一个偏序集，若对任 意a,b,L，存在glb{a,b}和lub{a,b}，则称 为格，并记为a*b=glb{a,b}，ab=lub{a,b}，称 和分别为L上的交（或积）和并（或和）运 算。称为所诱导的代数结构的格。 若L是有限集合，称为有限格

高等学校21卌纪教材 格的对偶性原理是成立的: 令是偏序集,且中 lub{a,b}等同于中gIb{a,b},<L,中 glb{a,b}等同于<L,≥中的lb{a,b}。若L是有限 集,这些性质易从偏序集及其对偶的哈斯图得 到验证 PT PRESS 人民邮电出版社

格的对偶性原理是成立的： 令是偏序集，且是其对偶的偏 序集。若是格，则也是格，反之亦 然。这是因为，对于L中任意a和b，中 lub{a,b}等同于中glb {a,b}，中 glb{a,b}等同于中的lub{a,b}。若L是有限 集，这些性质易从偏序集及其对偶的哈斯图得 到验证

高等学校21卌纪教材 从上讨论中,可知两格互为对偶。互为对 偶的两个有着密切关系,即格 中的并运算v正是格中的交运算入 因此,给出关于格一般性质的任何有效命题 把关系的子擦。 PT PRESS 人民邮电出版社

从上讨论中，可知两格互为对偶。互为对 偶的两个和有着密切关系，即格 中交运算正是格中的并运算，而 格中的并运算正是格中的交运算。 因此，给出关于格一般性质的任何有效命题， 把关系≤换成≥（或者≥换成≤），交换成并，并 换成交，可得到另一个有效命题，这就是关于 格的对偶性原理。 定义9.1.2 设是格，且SL。若对任 意a,bS，有a*bS和abS，则称是格 的子格

高等学校21卌纪教材 2.格的基本性质 在证明格的性质前,回忆一下a为b和ab的 真正含义是有好处的 ①a*b≤a和a入b≤b,则表明a*b是a和b的下 界 ②若ca和cb,则∝a*b,这表明a为b是a 和b的最大下界。 ①’a≤ab和b≤ab,则表明ab是a和b 的上界。 49b是a和b的最小上免e,则ab≤c,这表明 ②’若a≤c,且b PT PRESS 人民邮电出版社

2．格的基本性质 在证明格的性质前，回忆一下a*b和ab的 真正含义是有好处的。 ①a*b≤a和ab≤b，则表明a*b是a和b的下 界。 ②若c≤a和c≤b，则c≤a*b，这表明a*b是a 和b的最大下界。 ①’a≤ab和b≤ab，则表明ab是a和b 的上界。 ②’若a≤c，且b≤c，则ab≤c，这表明 ab是a和b的最小上界

高等学校21卌纪教材 定理9.1.1设是格,对任意a,b∈L, 有 ①ab=b分→a≤b ②a“b=a冷ab ③a*b=a分→ab=b 亦即 a<b令→ab=b今a"b=a PT PRESS 人民邮电出版社

定理9.1.1 设是格，对任意a,bL， 有 ① ab=ba≤b ② a*b=aa≤b ③ a*b=aab=b 亦即 a≤bab=ba*b=a

高等学校21卌纪教材 定理91.2设<L,是格,对任意a,b∈L: 有 ①a*b=a,a④a=a (幂等律) ②a*b=b*a,ab=bGa。(交换律) ③a(b*c)=(a*b)c a0(bec=(aeb)ec (结合律) ④a(aGb)=a a(a b=a (吸收律) PT PRESS 人民邮电出版社

定理9.1.2 设是格，对任意a,bL， 有 ① a*b=a, aa=a。 （幂等律） ② a*b=b*a, ab=ba。 （交换律） ③ a*(b*c)=(a*b)*c a(bc)=(ab)c （结合律） ④ a*(ab)=a a(a*b)=a （吸收律）

高等学校21卌纪教材 定理9.13设<L,是格,对任意a,b,c∈L, 有 ①若a≤b和c≤d,则a*c≤b*d,ac≤bd。 ②若a≤b,则a*c≤b*c,aEc≤bEc ③c和c<bc≤a*b ④a≤c和b≤caGb<c PT PRESS 人民邮电出版社

定理9.1.3 设是格，对任意a,b,cL， 有 ①若a≤b和c≤d，则a*c≤b*d，ac≤bd。 ②若a≤b，则a*c≤b*c，ac≤bc。 ③c≤a和c≤b c≤a*b ④a≤c和b≤c ab≤c

高等学校21卌纪教材 定理9.1.4设是格,对任意的a,b,c∈L, 有 a(b*cs(ab) *(aec (a2b)H(a2C)≤a“(bc) 通常称上二式为格中分配不等式。 PT PRESS 人民邮电出版社

定理9.1.4 设是格，对任意的a,b,cL， 有 a(b*c)≤(ab)*(ac) (a*b)(a*c)≤a*(bc) 通常称上二式为格中分配不等式

高等学校21卌纪教材 定理91.5设是格,对任意的a,b,c∈L, 有 as÷≥a(bc)≤(ab)*c 推论:在格中,对任意的a,b,c∈L, 有 (a2b)H(a2C)≤a“(bac)) a(b(adc)≤(ab)*(ac) PT PRESS 人民邮电出版社

定理9.1.5 设是格，对任意的a,b,cL， 有 a≤ca(b*c) ≤(ab)*c 推论：在格中，对任意的a,b,cL， 有 (a*b)(a*c)≤a*(b(a*c)) a(b*(ac))≤(ab)*(ac)