离散数学ch10 格与布尔代数.ppt

《离散数学ch10 格与布尔代数.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、欢迎进入第十章格与布尔代数目录引言1格2分配格3有补格4布尔代数5布尔表达式对于计算机科学来说，格与布尔代数是两个重要的代数系统。此两个系统有一个重要特点：强调次序关系。在开关理论计算机的逻辑设计，及其它一些科学领域中，都直接应用了格与布尔代数。引言返回目录§10.1格一.格的定义1.概念2.对偶原理3.基本性质二.格是代数系统1.作为代数系统的格的定义2.偏序集合的格、代数集合的格的关系三.子格1.子格2.格同态返回目录一．格的定义1．偏序集合的一些概念① 若集合A上的二元关系满足自反性、对称性、传递性，称A为偏序集合。aRb记为a≤b,它可用

2、哈斯图表示。一．格的定义(2)设〈A，≤〉是偏序集合，B是A的子集。若b∈B,b≤a,则a是子集B的上界。若a’也是B的上界，有a≤a’，称a是子集B的最小上界，记为lub(B);若b∈B,a≤b,则a是子集B的下界。若a’也是B的下界，有a≥a’，称a是子集B的最大下界，记为glb(B).一．格的定义(3)最大下界、最小上界若存在，则唯一例：则lub(a,b)=Фglb(a,b)=elub(a,e)=aglb(a,e)=elub(c,d)=fglb(c,d)=Ф一．格的定义设〈L，≤〉是偏序集合，若a，bL，都有最大下界、最小上界;则称

3、〈L，≤〉是个格，且记glb(a,b)=ab,lub(a,b)=ab,并称它们为交和并。1．定义注1:由于最大下界、最小上界若存在则唯一，所以交、并是二元运算；注2:称为由格〈L，≤〉所诱导的代数系统。一．格的定义一．格的定义格不是格的偏序集合例1:n=24Sn={1,2,3,4,6,8,12,24}2.设n是一正整数，Sn是n的所有因子的集合，D是整除关系,则是个格。n=8Sn={1,2,4,8}8244211263一．格的定义1248设S是任意集合，(S)是幂集，偏序集合是个格，其中A,B(S)

4、,A*B=A∩B,AB=A∪B.例:S={a,b}S={1,2,3}{a}{b}{1,2,3}{2,3}{3}{1,3}{2}{1,2}{a,b}一．格的定义{a}{a}{1}一．格的定义①集合S的偏序关系≤的逆关系≥也是偏序关系，若AS,其中≤的glb(A)对应于≥的lub(A),≤的lub(A)对应于≥的glb(A),所以，若是格，则也是格，称这两个格互为对偶。2.格的对偶原理①②②因为的交是的并，的并是的交，所以，关于格的一般性质的任意命题，如用≥替换≤，用替换，用替换

5、，格的一般性质的任意命题仍成立，这称为格的对偶原理。一．格的定义一．格的定义1)7)13)2)8)3)9)4)10)5)11)6)12)3.格的基本性质1)自反性a≤a对偶:a≥a2)反对称性a≤bb≥aa=b对偶:a≥bb≤aa=b3)传递性a≤bb≤ca≤c对偶:a≥bb≥ca≥c一．格的定义3.格的基本性质一．格的定义5）最大下界描述之二c≤a,c≤bc≤ab对偶c≥a,c≥bc≥ab3.格的基本性质4)最大下界描述之一ab≤a对偶ab≥aab≤b对偶ab≥b一．格的定义证：令R=a(bc),R’=(a

6、b)c则由4R≤a,R≤bcR≤a,R≤b,R≤cR≤ab,R≤cR≤(ab)cR≤R’同理可证：R≥R’所以R=R’注:格的证明思路：总是利用反对称性。3.格的基本性质6)结合律a(bc)=(ab)c对偶a(bc)=(ab)c3.格的基本性质7)等幂律aa=a对偶aa=a一．格的定义一．格的定义证：因为a≤ab,a≤a所以a≤a(ab)又a≥a(ab)所以a=a(ab)3.格的基本性质8)吸收律a(ab)=a对偶a(ab)=a一．格的定义证：a≤ba≤a,a≤ba≤ab又a≥a

7、ba=abab=a若b≤a且ba,则与ab=b矛盾若a,b不可比较，则与ab=a矛盾a≤b3.格的基本性质9)a≤bab=a（证明）ab=b一．格的定义证：ab≤a,a≤cab≤cab≤b,b≤dab≤dab≤cd3.格的基本性质10)a≤c,b≤dab≤cdab≤cd一．格的定义证：因为a≤a,b≤c由性质10)知ab≤ac即证。3.格的基本性质11）保序性（证明）b≤cab≤acab≤ac一．格的定义证:a≤ab,a≤aca≤(ab)(ac)b≤ab,c≤ac

8、bc≤(ab)(ac)（性质10)）a(bc)≤(ab)(ac)3.格的基本性质12）分配不等式（证明）a(b