离散数学课件

格与布尔代数第七章§7.1

格的基本概念及性质如果x,y

S,{x,y}都有最小上界和最大下界,则称<S,>是一个格,通常记：{x,y}的最大下界为x

y{x,y}的最小上界为x

y格：设<S,>是偏序集.例7.1设n为正整数,Sn是n的正因子的集合,D为整除关系,验证<Sn,D>是格,并举例说明：解：首先<Sn,D>显然是自反的,反对称的,传递的,从而是偏序集；其次

x,y

Sn,由于x与y的最小公倍数[x,y]仍属于Sn,x与y的最大公约数(x,y)仍属于Sn,且x

y=[x,y]x

y=(x,y)所以<Sn,D>是一个格,如n=8,6,30时,分别有下图：<S8,D>8421<S6,D>6231<S30,D>7.2判断下列偏序集是否构成格,说明为什么？efdcab(1)解:

不是格,e

f

不存在；解:是格(任何两个元素都有最小上界和最大下界)；ebcda(2)解:不是格,d

e

不存在,d,e有三个下界a,b,c,但没有最大的；fdbcea(3)51234(4)解:

不是格,3

2不存在.格的性质：(1)设f为含有格中的元素及符号,,,

,

的关系式.f

是将f中的“”改成“”,“”改成“”,“

”改成“

”,“

”改成“

”后所得的关系式,称之为f的对偶式.如果f为真,则f

也为真命题–––格的对偶原理.

(2)设<A,>是格,a,b,c是A中任意元素,则有：幂等律：

a

a=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保序性：

b

c,则a

b

a

c,a

b

a

c分配不等式：a

(b

c)(a

b)

(a

c),a

(b

c)(a

b)

(a

c)(3)a

b

a

b=a,a

b=b(4)A的任意有限子集S均有最大下界和最小上界,我们只证明结合律、等幂律、吸收律,其他证明可参看教材.证明：(a

b)

c=a

(b

c)由最小上界的定义：(a

b)

c(a

b)a(1)(a

b)

c(a

b)b(2)(a

b)

c

c(3)由(2)(3)可得：(a

b)

c

b

c(4)再由(1)(4)可得：(a

b)

c

a

(b

c)仿照上述过程,再证：a

(b

c)(a

b)

c从而：(a

b)

c=a

(b

c)类似地,不难证明：(a

b)

c=a

(b

c)证明：a

a=a

a

a=a由最小上界的定义：a

a

a(1)又因为a

a

所以a

a

a(2)综合(1)(2),根据偏序的反对称性知：a

a=a同理可得：a

a=a证明：a

(a

b)=a

a

(a

b)=a首先：a

(a

b)a

显然成立又由于a

a,a

b

a

所以有a

(a

b)a这样a

(a

b)

=a同理可证：a

(a

b)=a§7.2特殊格完全格：格<A,>中A的任意子集(不要求有限)均有最大下界和最小上界,则称<A,>是完全格.如：(1)<S8,D>,其中D为整除关系,S8为8的所有正因子构成的集合.8421<S8,D>6123<S6,D>完全格的性质：完全格中,存在唯一最大元和最小元,分别记作1和0.有界格：在格<A,>中,如果存在最大元1和最小元0,则称之为有界格,并记之为<A,,0,1>.分配格：设<A,>是格,如果a,b,c

A

有a

(b

c)=(a

b)

(a

c)a

(b

c)=(a

b)

(a

c)则称<A,>为分配格.如：<P(s),>是分配格.例7.3试判断下列图对应的格是否为分配格：fdbce(2)(3)(4)ahgabcdeabdceba(1)c解：(1)a

b=b,b

c=c,a

c=c；a

b=a,b

c=b；a

c=a

从而可以验证：a

(b

c)=(a

b)

(a

c)a

(b

c)=(a

b)

(a

c)改变a,b,c的位置同样成立.所以(1)是分配格.(2)同(1)可以验证(2)是分配格.ba(1)cfdbce(2)ahg(3)由于(3)中a

(b

c)=a

e=a

(a

b)

(a

c)=d

d=d

所以(3)不是分配格.(4)由于(4)中b

(a

c)=b

e=b

(b

a)

(b

c)=d

c=c所以(4)也不是分配格.(3)abcde(4)abdce分配格的判定：设<A,>是一个有界格,对于a

A,如果存在b

A使a

b=1和a

b=0,则称b是a的补元,显然b是a的补元时,a也是b的补元.任何全序集(或称线序集)一定是分配格.补元：例7.4

在下图对应的格中,哪些元素有补元,哪些元素没有补元？gabcdef解：由图可知,它所对应的格为有界格,b

f=g=1,b

f=a=0所以b与f互补；c

e=g=1,c

e=a=0所以c与e互补；d

e=g=1,d

e=a=0所以d与e互补；b没有补元.最大元为g,最小元为a,因此,a,g互为补元,此外：例7.5指出下列有界格中,哪些元有补元？哪些元无补元？(1)11a1a2a3a3a2a100(2)解：(1)a1,a2,a3都没有补元,0与1互补；(2)a1,a2,a3为补元,0与1互补.有补格：设<A,,0,1>是有界格,如果A的每个元素都至少有一个补元素,则称该格为有补格.例如：下面三个格都是有补格.ab10(1)abcd10(2)10adcb(3)布尔格：如果<A,>既是分配格又是有补格,布尔格的性质：<A,

>是布尔格,则：

例如：幂集格<P(A),

>是布尔格.证明：设a1,a2是a在A中的两个补元,则a

a1=1

a

a1=0因而a

a1=a

a2

a

a1=a

a2由于a1=a1

(a

a1)=(a

a2)

(a1

a2)=(a

a2)

a2=a2

所以矛盾.(上述证明过程说明“消去律”成立)a

a2=1

a

a2=0=a1

(a

a2)=(a1

a)

(a1

a2)=(a

a1)

a2

证明：

a

A,由于a与互补,所以

证明：只要证：只要利用格的性质即可.

证明:

(i)(ii)从而

(ii)(iii)(iii)(i)

§7.3布尔代数

与

是A上的两个二元运算,对于任意的a,b,c

A,如果：(1)交换律：a

b=b

a,a

b=b

a(2)分配律：a

(b

c)=(a

b)

(a

c)a

(b

c)=(a

b)

(a

c)布尔代数：设A是一个集合,|A|2,(3)同一律：0,1

A,对于A中任意元素aa

1=a,a

0=a(4)互补律：对于A中任意元素a,存在,使成立,则称<A,

,

,,,>为布尔代数,具有有限个元素的布尔代数叫做有限布尔代数.

布尔格与布尔代数：布尔格就是布尔代数.布尔常元：设<A,

,

,,,>是布尔代数,A中的元素称为布尔常元.布尔变元：设<A,

,

,,,>是布尔代数,在A中取值的变元称为布尔变元.布尔表达式：设<A,

,

,,,>是布尔代数,在这个布尔代数上可定义布尔表达式：(1)A中任何布尔常元是布尔表达式(2)任何布尔变元是一个布尔表达式(4)只有有限次地使用规则(1),(2),(3)构造的符号串都是布尔表达式.(3)如果e1和e2是布尔表达式,则,(e1

e2),(e1

e2)也是布尔表达式.n元布尔表达式：一个含有n个相异布尔变元的布尔表达式,称为n元布尔表达式,记作：E(x1,x2,…,xn),其中,x1,x2,…,xn是相异布尔变元.布尔表达式赋值：用A中的元素作为n元布尔表达式中变元xi(i