离散数学第六章格与布尔代数

离散数学第六章格与布尔代数1第1页，课件共47页，创作于2023年2月§6.1 格的概念本章将介绍其他的代数系统——格和布尔代数，格论是数学的一个分支，不仅在近代解析集合有重要的作用，而且在计算机领域也有一定的用途；布尔代数形成比较早，在19世纪，就已经有了相当的发展，布尔代数是研究和逻辑、集合等运算有关的知识。2第2页，课件共47页，创作于2023年2月定义设<A,

>为偏序集,B

A,y

A.(1)若

x(x

B→x

y)成立,则称y为B的上界;(2)若

x(x

B→y

x)成立,则称y为B的下界;(3)令C={y|y为B的上界},若C有最小元素，则称该最小元素为B的最小上界或上确界,记为LUB(上确界)(4)令D={y|y为B的下界},若D有最大元素，则称该最大元素为为B的最大下界或下确界,记为GLB(下确界)复习偏序关系中的上界，下界，上确界与下确界3第3页，课件共47页，创作于2023年2月§6.1 格的概念例：偏序集(｛2,3,5,7,14,15,21｝,/)，“/”为整除关系。其hasze图如下：｛2,7｝的最小上界、最大下界各为什么？｛2,3｝呢？｛5,14｝呢？｛2,7｝的最小上界为14。最大下界无。｛2,3｝的最小上界无，最大下界无。｛5,14｝的最小上界无，最大下界无。4第4页，课件共47页，创作于2023年2月然而也存在这样一类偏序集，它的每一对元素都有最小上界和最大下界，如：偏序集(｛1,2,3,4,6,8,12,24｝,/)：其Hasze图如下：

§6.1 格的概念5第5页，课件共47页，创作于2023年2月一、格1．定义：设<A,≤>是一个偏序集，若对A中的任两个元素a、b，都有最小上界和最大下界，则称 <A,≤>为格。其中上确界lub{a,b}，记为a∨b,称为a和b的并。下确界glb{a,b}，记为a∧b,称为a和b的交。将∨、∧，看作集合上的两个二元运算，故格<A,≤>所诱导的代数系统记作<A，∨，∧>。6第6页，课件共47页，创作于2023年2月一、格下述偏序集能构成格的是（？）(a)(b)(c)(d)bbcdefacdfabcdefghabcdef√ac7第7页，课件共47页，创作于2023年2月一、格2、对偶格：若<A,≤>是一个偏序集，则<A,≥>也是一个偏序集，其中“≥”是“≤”的逆关系。若<A,≤>是一个格，则<A,≥>也是一个格，称这两个格互为对偶。若将关于格<A,≤>的命题中符号≤，≥，∨、∧，分别用≥，≤，∧、∨，代替，则得到一个新的命题，称这个新命题为原命题的对偶命题。定理：对于格中的一个真命题，其对偶命题亦真。

8第8页，课件共47页，创作于2023年2月二、格的性质定理1：若<A，≤>是一个格，则对任意a、b

、c

A，有（1）a≤a∨b，b≤a∨b

（2）a∧b≤a，a∧b≤b（3）若a≤c且b≤c，则a∨b≤c（4）若c≤a且c≤b，则c≤a∧b9第9页，课件共47页，创作于2023年2月二、格的性质（1）a≤a∨b，b≤a∨b

证明：因a∨b=lub{a，b}，它显然是a的一个上界，∴a≤a∨b

，同理：b≤a∨b。（2）a∧b≤a，a∧b≤b证明：因a∧b=glb{a，b}，它显然是a的一个下界，∴a∧b≤a

，同理：a∧b≤b。10第10页，课件共47页，创作于2023年2月二、格的性质（3）若a≤c且b≤c，则a∨b≤c

证明：∵a≤c且b≤c，由上界的定义知，c是{a，b}的一个上界，而a∨b是{a，b}的最小上界，∴a∨b≤c。（4）若c≤a且c≤b，则c≤a∧b证明：∵c≤a且c≤b，由下界的定义知，c是{a，b}的一个下界，而a∧b是{a，b}的最大下界，∴c≤a∧b。

11第11页，课件共47页，创作于2023年2月二、格的性质推论：在<A，≤>中，对于任意a，b

，c

A，如果b≤c，则a∨b≤a∨c，a∧b≤a∧c。定理2：若<A，≤>是一个格，则对于任意a，b

A，以下三个公式等价；（1）a≤b

（2）a∨b=b

（3）a∧b=a12第12页，课件共47页，创作于2023年2月二、格的性质（1）a≤b

（2）a∨b=b

（3）a∧b=a证明：（1）（2）∵a≤b且偏序关系是自反的。∴b≤b，∴a∨b≤b 又b≤a∨b成立∴a∨b=b（偏序关系是反对称的）

设a∨b=b

∵a≤a∨b成立，将a∨b=b代入a≤a∨b得：a≤b

类似可证（1）

（3）13第13页，课件共47页，创作于2023年2月二、格的性质定理3：<A，≤>是一个格，则对于任意a，b，c

A，满足以下四个定律：（1）交换律：a∨b=b∨a

a∧b=b∧a（2）吸收律：a∨（a∧b）=aa∧（a∨b

）=a（3）结合律：a∨（b∨c）=（a∨b）∨c，

a∧（b∧c）=（a∧b

）∧c（4）等幂律：a∨a=a

a∧a=a14第14页，课件共47页，创作于2023年2月二、格的性质定理4：设有格<A，≤>，对于任意a，b，c，d

A，如果a≤b和c≤d，则（1）a∨c≤b∨d，（2）a∧c≤b∧d证：∵b≤b∨d，d≤b∨d

，而a≤b，c≤d，∴由传递性可得：a≤b∨d

，c≤b∨d，这就表明b∨d是a和c的一个上界，而a∨c是a和c的最小上界，∴必有a∨c≤b∨d。类似地可以证明：a∧c≤b∧d

15第15页，课件共47页，创作于2023年2月二、格的性质定理5：在一个格<A，≤>中，对于任意a，b，c

A，有下列分配不等式成立：（1）a∨（b∧c）≤（a∨b）∧（a∨c）（2）a∧（b∨c）≥（a∧b）∨（a∧c）证：由定理1，（1）（2）知：a≤a∨b和a≤a∨c，可得：

a≤（a∨b）∧（a∨c），①又∵b∧c≤b≤a∨b和b∧c≤c≤a∨c∴b∧c≤（a∨b）∧（a∨c）②对于①和②，有：a∨（b∧c）≤（a∨b）∧（a∨c）利用对偶原理，即得：（a∧b）∨（a∧c）≤a∧（b∨c）

16第16页，课件共47页，创作于2023年2月定义设<A，≤>是一个格，设非空集合S且S

A,若对任意的a,b∈S,有a∧b∈S,a∨b∈S,则称〈S,≤〉是<A，≤>的子格。显然，子格必是格。而格的某个子集构成格，却不一定是子格。三、子格17第17页，课件共47页，创作于2023年2月【例】设〈A,≤〉是一个格，其中A={a,b,c,d,e},其哈斯图如图所示。S1={a,b,c,d}，S2={a,b,c,e},则〈S1,≤〉是〈A,≤〉是一个子格，〈S2,≤〉不是〈A,≤〉是一个子格，因为b∧c=d∈S2，〈S2,≤〉不是子格。三、子格18第18页，课件共47页，创作于2023年2月定义：设〈A1,≤〉,〈A2,≤〉是两个格,由它们所诱导的代数系统为〈A1,∨1,∧1〉,〈A2,∨2,∧2〉，如果存在映射f:A1

→A2,任意a,b∈A1，满足：f(a∨1

b)=f(a)∨2

f(b),f(a∧1

b)=f(a)∧2

f(b)称f为<A1,∨1,∧1〉到〈A2,∨2,∧2〉的格同态。若f是双射，则称f为格同构，亦称〈A1,≤〉,〈A2,≤〉这两个格是同构。

四、格同态与格同构类似群的同态，也可以定义格的同态。19第19页，课件共47页，创作于2023年2月定理：设f是格〈A1,≤1〉到〈A2,≤2〉的格同态，则对任意的x,y∈A1

，如果x≤1y，必有f(x)≤2

f(y)。这说明格的同态是保序的。定理：设两个格为〈A1,≤1〉，〈A2,≤2〉，f是从

A1到A2的的双射，则f是〈A1,≤1〉到〈A2,≤2〉是格同构，当且仅当对任意的x,y∈A1

，如果x≤1y

f(x)≤2

f(y)。四、格同态与格同构20第20页，课件共47页，创作于2023年2月§6.2分配格

对格<A,≤>中的任意元素a,b,cA，必有a

(b

c)≤(a

b)

(a

c)(a

b)

(a

c)≤a

(b

c）当上述两式中等号成立的时候，就得到一类特殊的格。《定义》设<A,

,

>是由格<A,≤>所诱导的代数系统。如果对任意的a,b,cA，满足：

a

(b

c)=(a

b)

(a

c)a

(b

c)=(a

b)

(a

c)

则称<A,≤>是分配格。21第21页，课件共47页，创作于2023年2月例：判断图示的格是否是分配格

∵a3∧（a4∨a5）=a3∧a1=a3

（a3∧a4）∨（a3∧a5）=a4∨a6=a4

∴所示的格不是分配格。

§6.2分配格

22第22页，课件共47页，创作于2023年2月§6.2分配格《定理》如果格中交对并是分配的，那么并对交也是分配的，反之亦然。证明：已知a

(b

c)＝(a

b)

(a

c)

(a

b)

(a

c)=((a

b)

a)

((a

b)

c) =a

((a

b)

c) =a

((a

c)

(b

c)) =(a

(a

c))

(b

c) =a

(b

c)即：并对交也是分配的。23第23页，课件共47页，创作于2023年2月§6.2分配格《定理》每个链均是分配格。证明：设<A,≤>是链。对任意a，b，cA(1)若a≤b或a≤c，则a

(b

c)＝a，

(a

b)

(a

c)＝a即：a

(b

c)＝(a

b)

(a

c)(2)若a≥b且a≥c，则

a

(b

c)＝b

c，

(a

b)

(a

c)＝b

c即：a

(b

c)＝(a

b)

(a

c)。得证。24第24页，课件共47页，创作于2023年2月定理：设<A，≤

>是一个分配格，则对于任意a，b，c

A，如果有a∧b=a∧c和a∨b=a∨c成立，则必有b=c。§6.2分配格

证：∵（a∧b）∨c=（a∧c）∨c=c（a∧b）∨c=（a∨c）∧（b∨c）=（a∨b）∧（b∨c）=（b∨a）∧（b∨c）=b∨（a∧c）=b∨(a∧b)=b∴b=c

25第25页，课件共47页，创作于2023年2月§6.2分配格《定义》设<A,

,

>是由格<A,≤>所诱导的代数系统。如对A中任意a，b，c有：

b≤aa

(b

c)＝b

(a

c)则称<A,≤>为模格。26第26页，课件共47页，创作于2023年2月§6.2分配格《定理》分配格是模格。证明：由于a

(b

c)＝(a

b)

(a

c)若b≤a，则a

b=b，代入上式得

a

(b

c)＝b

(a

c)

∴分配格是模格27第27页，课件共47页，创作于2023年2月§6.3有补格《定义》设<A,≤>是一个格，如果存在元素aA，对于任意的xA，都有：a≤x

则称a为格<A,≤>的全下界，记格的全下界为0。《定义》设<A,≤>是一个格，如果存在元素bA，对于任意的xA，都有：x≤b

则称b为格<A,≤>的全上界，记格的全上界为1。28第28页，课件共47页，创作于2023年2月§6.3有补格《定理》如果格<A,≤>有全上界（全下界），那么它是唯一的。证明：（反证法）设有两个全上界a和b，则由定义

a≤b，且b≤a，由“≤”的反对称性，a＝b。《定义》设<A,≤>是一个格，如果格中存在全上界和全下界，则称该格为有界格。29第29页，课件共47页，创作于2023年2月§6.3有补格《定理》如果<A,≤>是有界格，全上界和全下界分别是1和0，则对任意元素aA，有：

a

1=1

a=1，a

1=1

a=a，

a

0=0

a=a，a

0=0

a=0。证明：因为1≤a

1， 又因(a

1)A且1是全上界，∴a

1≤1，

∴a

1=1。由交换律：1

a＝a

1=1。 因为a≤a，a≤1，∴a

a≤a

1，即：a≤a

1，又a

1≤a，∴a

1=a。仿此可得另两式。30第30页，课件共47页，创作于2023年2月§6.3有补格《定义》设<A,≤>是一个有界格，对于A中的一个元素a，如果存在bA，使得a

b=1和a

b=0，则称元素b是元素a的补元。讨论定义：（1）∵

和

是可交换的，∴补元是相互的。

（2）

，即在有界格中，1和0互为补元；

（3）由定义可知A中一个元素的补元不一定是唯一的；可能存在多个补元，也可能不存在补元。31第31页，课件共47页，创作于2023年2月§6.3有补格《定义》在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。讨论定义：（1）在有补格中，每一个元素一定存在补元（不一定是一个补元）；（2）有补格一定是有界格，而有界格不一定是有补格。32第32页，课件共47页，创作于2023年2月如图所示的格，是有补格吗？该格是有界格，却不是有补格。§6.3有补格33第33页，课件共47页，创作于2023年2月§6.3有补格《定理》在有界分配格中，若有一个元素有补元，则必是唯一的。证明：设a有两个补元素b和c,则有：

a

b=1,a

b=0a

c=1,a

c=0所以a

b=a

c，a

b=a

c由定理知：b=c34第34页，课件共47页，创作于2023年2月有补分配格定义：一个格如果既是有补格，又是分配格，则称该格为有补分配格，可以证明：在有补分配格中，任一元素的补元都是唯一的。将有补分配格中任一元素a的唯一补元记为a§6.3有补格35第35页，课件共47页，创作于2023年2月§6.4布尔代数《定义》一个格<A,≤>如果它既是有补格，又是分配格，则它为有补分配格。我们把有补分配格中任一元素a的唯一补元记为a。《定义》一个有补分配格称为布尔格。讨论定义：(1)布尔格中，每个元素有唯一的补元。(2)我们可以定义A上的一个一元运算，称为补运算，记为“-”。-36第36页，课件共47页，创作于2023年2月§6.4布尔代数《定义》由布尔格<A,≤>，可以诱导一个包括交，并和补运算的代数系统<A,

,

,->，称此代数系统为布尔代数。例：设S是一个非空有限集，<(S),>是一个格，且是一个布尔格。由<(S),>所诱导的代数系统为

<(S),

,

,->是一个布尔代数。其中“

,

,-”分别是集合的交、并、补运算。37第37页，课件共47页，创作于2023年2月§6.4布尔代数例：设A是一非空集合,

(A)是A的幂集,可以验

证,<

(A),∪,∩,~,

,A>是个布尔代数,称此为集合代数,其中运算为∪,∩,~,全下界

,全上界A。S是命题公式的全体,则<S,∨,∧,

,0,1>是一个布尔代数,称之为命题代数。其中运算为∨,∧,

,全下界是恒假公式0,全上界是恒真公式1。38第38页，课件共47页，创作于2023年2月§6.4布尔代数《定理》对于布尔代数中任意两个元素a,b，必定有39第39页，课件共47页，创作于2023年2月定义：当布尔代数<A,,,->的载体A的基数|A|是有限数时,则称之为有限布尔代数。定义：设<A,,,->是一个布尔代数，a∈A,如果a盖住0，则称元素a是该布尔代数的一个原子。§6.4布尔代数定义：布尔代数<A,,,->中除0外的每个元素，都可以唯一地表示成原子的并。例如：40第40页，课件共47页，创作于2023年2月§6.4布尔代数例：<(S),

,

,~,

,S>，其中S={a,b,c}，在这个布尔代数中的元素分三种情况：（ⅰ）界：全上界S，全下界

；（ⅱ）{a},{b},{c}单个元素集合的元素；（ⅲ）二，三个元素作为集合的元素，但它们均可用单个元素的集合的元素来表述：{a,b}={a}

{b},{a,c}={a}

{c},{b,c}={b}

{c},{a,b,c}={a}

{b}

{c}。

{a,c}{a,b,c}{a,b}{b,c}{a}{c}{b}Ø41第41页，课件共47页，创作于2023年2月§6.4布尔代数《定理》设<A,,,->是由有限布尔格<A,≤>所诱导的一个有限布尔代数，S是布尔格<A,≤>中的所有原子的集合，则<A,

,

,->和<(S),,,~>同构。42第42页，课件共47页，创作于2023年2月§6.4布尔代数该定理可得以下两个推论：a)<B,*,

,’,0,1>与<p(S),∪,∩,~,Ø,S>同构，|p(S)|=2|s|所以，|B|=2|s|

，故任一有限布尔代数载体的基数是2的幂。b)任一有限布尔代数和它