离散数学-格与布尔代数省名师优质课赛课获奖课件市赛课一等奖课件

第七章格与布尔代数布尔代数是计算机逻辑设计基础，它是由格引出，格又是从偏序集引出。所以我们先回顾一下偏序集。<A,≤>是偏序集:≤是A上自反,反对称和传递关系(偏序).偏序集中元素间次序能够经过它Hasse图反应出来.比如A={1,2,3,6,12,24,36},≤是A上整除关系其Hasse图如图所表示，BAB≠Φ1.B极小元与极大元y是B极小元y∈B∧x(x∈B∧x≤y)y是B极大元y∈B∧x(x∈B∧y≤x)比如{2,3,6}极小元:2,3极大元:6６。１。３。12。２。24。36。1/872.B最小元与最大元y是B最小元y∈B∧x(x∈B

y≤x)y是B最大元y∈B∧x(x∈B

x≤y){2,3,6}最小元:无最大元:6B假如有最小元(最大元),则是唯一。3.B下界与上界y是B下界y∈A∧x(x∈B

y≤x)y是B上界y∈A∧x(x∈B

x≤y){2,3,6}下界:1上界:6,12,24,364.B最大下界(下确界)与最小上界(上确界)y是B最大下界(下确界)：B全部下界x,有x≤y。y是B最小上界(上确界)：B全部上界x,有y≤x。{2,3,6}下确界:1上确界:6(B若有下(上)确界，则唯一)６。１。３。12。２。24。36。2/877-1格(Lattice)一.基本概念1.格定义<A,≤>是偏序集，假如任何a,b∈A,使得{a,b}都有最大下界和最小上界，则称<A,≤>是格。

右图三个偏序集，<A,≤>不是格，因为{24,36}无最小上界。<B,≤><C,≤>是格。６。１。３。12。２。24。36。30。3。１。2。5。10。１5。6。<A,≤><B,≤>3。4。1。2。<C,≤>3/87这三个偏序集，也都不是格，第一个与第三个是同构。因为d和e无下界，也无最小上界；b,c虽有下界，但无最大下界。2,3无最大下界，4,5无最小上界。2.平凡格：全部全序都是格，称之为平凡格。因为全序中任何两个元素x,y，要么x≤y,要么y≤x。假如x≤y，则{x,y}最大下界为x，最小上界为y。假如y≤x，则{x,y}最大下界为y，最小上界为x。即这{x,y}最大下界为较小元素，最小上界为较大元素.d

a

b

ce

1

2

34

5

6d

a

b

c

e4/873.由格诱导代数系统设<A,≤>是格,在A上定义二元运算∨和∧为:a,b∈Aa∨b=LUB{a,b}{a,b}最小上界.LeastUpperBounda∧b=GLB{a,b}{a,b}最大下界.GreatestLowerBound称<A,∨,∧>是由格<A,≤>诱导代数系统.(∨-并,∧-交)比如右边格中a∧b=ba∨b=ab∧c=e4.子格：设<A,≤>是格,<A,∨,∧>是由<A,≤>诱导代数系统。B是A非空子集，假如∧和∨在B上封闭，则称<B,≤>是<A,≤>子格。<C,≤>是<A,≤>子格。而<B,≤>不是.b∧c=dB,(运算规则要从格<A,≤>中找)

e

ab

d

cb

a

c

fe

gb

a

c

fe

g

d<B,≤><A,≤>

a

cb

d<C,≤>5/87二.格对偶原理设<A,≤>是格，≤逆关系记作≥，≥也是偏序关系。<A,≥>也是格，<A,≥>Hasse图是将<A,≤>Hasse图颠倒180º即可。

格对偶原理：设P是对任何格都为真命题，假如将P中≤换成≥，∧换成∨，∨换成∧，就得到命题P’,

称P’为P对偶命题，则P’对任何格也是为真命题。比如：P:a∧b≤aP’:a∨b≥a{a,b}最大下界≤a{a,b}最小上界≥a6/87三.格性质

<A,∨,∧>是由格<A,≤>诱导代数系统。a,b,c,d∈A1.a≤a∨bb≤a∨ba∧b≤aa∧b≤b

此性质由运算∨和∧定义直接得证。

2.假如a≤b，c≤d，则a∨c≤b∨d，a∧c≤b∧d。证实：假如a≤b，又b≤b∨d，由传递性得a≤b∨d,

类似由c≤d，d≤b∨d，由传递性得c≤b∨d,这说明b∨d是{a,c}一个上界，而a∨c是{a,c}最小上界，所以a∨c≤b∨d。类似可证a∧c≤b∧d。推论：在一个格中，任意a,b,c∈A，假如b≤c，则a∨b≤a∨c，a∧b≤a∧c。

此性质称为格保序性。7/873.∨和∧都满足交换律。即a∨b=b∨a，a∧b=b∧a此性质由运算∨和∧定义直接得证。4.∨和∧都满足幂等律。即a∨a=aa∧a=a证实：由性质1,a≤a∨a

(再证a∨a≤a)又由≤自反有a≤a，这说明a是a上界，而a∨a是a最小上界，所以a∨a≤a。

最终由≤反对称得a∨a=a。

由对偶原理得a∧a=a8/875.∨和∧都满足结合律。即(a∨b)∨c=a∨(b∨c)，(a∧b)∧c=a∧(b∧c)

证实：⑴先证实(a∨b)∨c≤a∨(b∨c)

因a≤a∨(b∨c)，b≤b∨c≤a∨(b∨c)所以a∨b≤a∨(b∨c)又c≤b∨c≤a∨(b∨c)于是有(a∨b)∨c≤a∨(b∨c)

⑵再证a∨(b∨c)≤(a∨b)∨c

因a≤a∨b≤(a∨b)∨c；

再由b≤a∨b≤(a∨b)∨c，c≤(a∨b)∨c所以b∨c≤(a∨b)∨c于是有a∨(b∨c)≤(a∨b)∨c最终由≤反对称得

(a∨b)∨c=a∨(b∨c)

类似可证(a∧b)∧c=a∧(b∧c)。9/876.

∨和∧都满足吸收律。即a∨(a∧b)=a，a∧(a∨b)=a。证实：⑴显然有a≤a∨(a∧b)⑵再证a∨(a∧b)≤a因a≤a，a∧b≤a所以a∨(a∧b)≤a最终由≤反对称得a∨(a∧b)=a，类似可证a∧(a∨b)=a。10/877.

∨和∧不满足分配律。但有分配不等式：

a∨(b∧c)≤(a∨b)∧(a∨c)，(a∧b)∨(a∧c)≤a∧(b∨c)。我们先看右图例子：d∨(b∧e)=d∨c=d(d∨b)∧(d∨e)=a∧e=e而d≤e即d∨(b∧e)≤(d∨b)∧(d∨e)证实：⑴因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∨c)≥(a∧b)∨(a∧c)。

即(a∧b)∨(a∧c)≤a∧(b∨c)。

c

ab

e

d11/878.a≤ba∨b=ba∧b=a证实：⑴先证实a≤ba∧b=a

先证a≤b

a∧b=a由a≤b，又a≤a所以a≤a∧b又由a∧b定义有a∧b≤a由反对称得a∧b=a

再证a∧b=a

a≤b由a∧b=a则a=a∧b≤b。

综上得a≤ba∨b=b⑵下面证实a≤ba∨b=b

先证a≤b

a∨b=b由a≤b，又b≤b所以a∨b≤b又因为b≤a∨b由反对称得a∨b=b

再证a∨b=b

a≤b由a∨b=b因a≤a∨b所以a≤b。

综上得a≤ba∨b=b12/87引理：<A,∨,∧>是代数系统，假如∨和∧是满足吸收律二元运算，则∨和∧必满足幂等律。证实：任取a,b∈A因为∨和∧满足吸收律。于是有a∨(a∧b)=a------⑴a∧(a∨b)=a-------⑵。因为上式中b是任意，能够令b=a∨b并代入⑴式得a∨(a∧(a∨b))=a由⑵式得a∨a=a同理可证a∧a=a13/87定理：设<A,∨,∧>是代数系统，假如∨和∧是满足交换律，结合律，和吸收律二元运算，则A上存在偏序关系≼

，使<A,≼>是一个格，而且该格所诱导代数系统恰好是<A,∨,∧>。（由代数系统得到格）证实：设在A上定义二元关系≼为：对任意a,b∈A,a≼b当且仅当a∧b=a（1）先证二元关系≼是一个偏序关系（2）再证a∧b是{a,b}下确界（3）然后证a∨b是{a,b}上确界见书上238页14/87四.格同态与同构1.定义：设<A1,≤1>和<A2,≤2>是两个格，由它们诱导代数系统分别是<A1,∨1,∧1>和<A2,∨2,∧2>，假如存在映射f:A1A2

，使得对任何a,b∈A1，有

f(a∨1b)=f(a)∨2f(b)f(a∧1b)=f(a)∧2f(b)则称f是<A1,∨1,∧1>到<A2,∨2,∧2>同态映射。也称<f(A1),≤2>是<A1,≤1>同态像。假如f是双射，就称f是<A1,∨1,∧1>到<A2,∨2,∧2>，格同构，也称格<A1,≤1>和<A2,≤2>同构。15/87例：<A,≤>，A={1,2,3,6},≤是A上整除关系。<P(E),>，E={a,b}它们诱导代数系统分别是<A,∨,∧>和<P(E),∪,∩>其中∨和∧分别是求两个数最小公倍数和最大条约数.f(2∨3)=f(6)={a,b}f(2)∪f(3)={a}∪{b}={a,b}f(2∧3)=f(1)=Φf(2)∩f(3)={a}∩{b}=Φf(2∨6)=f(6)={a,b}f(2)∪f(6)={a}∪{a,b}={a,b}f(2∧6)=f(2)={a}f(2)∪f(6)={a}∪{a,b}={a}……可见它们同构。格同构，它们哈斯图形状一定相同。

Φ

{b}{a}

{a,b}

1

32

6f6

3

2

1

{a}

{b}

{a,b}

ΦA

P(E)16/87含有1、2、3个元素格分别同构于含有一、二、三个元素链。含有4个元素格分别同构于下面两种格形式之一：含有5个素格分别同构于下面五种格形式之一：

e

d

a

b

c

d

a

b

c

c

d

d

a

b

c

e

a

b

c

e

a

b

d

a

e

b

c

d

d

a

b

c

e

a

a

b

a

b

c17/872.格同态保序性定理：设f是格<A1,≤1>到<A2,≤2>同态映射，则对任何a,b∈A1，假如a≤1b，则f(a)≤2f(b)。证实：令<A1,∨1,∧1>和<A2,∨2,∧2>是格<A1,≤1>和<A2,≤2>诱导代数系统，任取a,b∈A1，设a≤1b，则a∧1b=af(a∧1b)=f(a)即f(a)∧2f(b)=f(a)而f(a)∧2f(b)≤2f(b)所以f(a)≤2f(b).3.格同构保序性定理：设两个格为<A1,≤1>和<A2,≤2>，f是A1到A2双射，则f是<A1,≤1>到<A2,≤2>格同构，当且仅当对任意a,b∈A1，a≤1bf(a)≤2f(b)证实：令<A1,∨1,∧1>和<A2,∨2,∧2>是格<A1,≤1>和<A2,≤2>诱导代数系统，18/871)必要性：已知f是格<A1,≤1>到<A2,≤2>同构映射，（往证：任取a,b∈A1,a≤1bf(a)≤2f(b)）a)

先证a≤1bf(a)≤2f(b)

任取a,b∈A1,设a≤1b

，由格同态保序性得f(a)≤2f(b)

b)再证f(a)≤2f(b)

a≤1b设f(a)≤2f(b)，于是有f(a)=f(a)∧2f(b)=f(a∧1b)因f是双射，所以a=a∧1b所以a≤1b最终得a≤1bf(a)≤2f(b)

。19/872)充分性：已知，对任意a,b∈A1,a≤1b

f(a)≤2f(b)(往证f(a∧1b)=f(a)∧2f(b)f(a∨1b)=f(a)∨2f(b))a)

证f(a∧1b)=f(a)∧2f(b)

令a∧1b=c所以c≤1ac≤1b，由已知得f(c)≤2f(a)和f(c)≤2f(b)，所以f(c)≤2f(a)∧2f(b)-------⑴

再证f(a)∧2f(b)≤2f(c)：因为f(a),f(b)∈A2,又∧2封闭，得f(a)∧2f(b)∈A2,又由f:A1A2是双射，必有d∈A1,使得f(a)∧2f(b)=f(d)所以f(d)≤2f(a)，f(d)≤2f(b)由已知得：d≤1a，d≤1b，于是d≤1a∧1b=c，即d≤1c，于是f(d)≤2f(c)即f(a)∧2f(b)≤2f(c)

-----⑵由⑴⑵得f(a)∧2f(b)=f(c)

，即f(a∧1b)=f(a)∧2f(b)

。b)类似可证f(a∨1b)=f(a)∨2f(b)，所以f是它们同构映射。20/877-2几个特殊格一.分配格

前面我们介绍普通格，∧和∨只满足分配不等式。a∨(b∧c)≤(a∨b)∧(a∨c)，(a∧b)∨(a∧c)≤a∧(b∨c)。下面介绍是满足分配律格----分配格。1.定义：<A,∨,∧>是由格<A,≤>诱导代数系统。假如对a,b,c∈A，有a∨(b∧c)=(a∨b)∧(a∨c)，a∧(b∨c)=(a∧b)∨(a∧c)则称<A,≤>是分配格。例：<P(E),>所诱导代数系统为<P(E),∪,∩>所以<P(E),>是分配格。21/872.二个主要五元素非分配格：2∧(3∨5)=2∧30=2(2∧3)∨(2∧5)=1∨1=1c∧(b∨d)=c∧a=c(c∧b)∨(c∧d)=e∨d=d可见它们都不是分配格。3.分配格判定：

一个格是分配格充分且必要条件是在该格中没有任何子格与上述两个五元素非分配格之一同构。用此方法能够判定下面两个格不是分配格：

3

1

30

2

5

d

e

a

b

c

4

1

6

3

5

2

f

g

a

d

c

e

b

22/874.分配格性质1.

在一个格中，假如∧对∨可分配，则∨对∧也可分配。反之亦然。证实：设<A,∨,∧>是由格<A,≤>诱导代数系统，且∧对∨可分配。则任取a,b,c∈A，(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)

即∨对∧也可分配

同理可证:假如∨对∧可分配，则∧对∨也可分配.2.全部链均为分配格。证实：显然任何链都不会含有与那两个五元素非分配格之一同构子格，所以链必是分配格。23/873.设<A,≤>是分配格，对任何a,b,c∈A，假如有a∧b=a∧c及a∨b=a∨c则必有b=c。证实：任取a,b,c∈A,设有a∧b=a∧c及a∨b=a∨cb=b∨(a∧b)(吸收律)=b∨(a∧c)(代换)=(b∨a)∧(b∨c)(分配)=(a∨b)∧(b∨c)(交换)=(a∨c)∧(b∨c)(代换)=(a∧b)∨c(分配)

=(a∧c)∨c(代换)=c(吸收律)24/87二.有界格1.格全上界与全下界1).全上界:设<A,≤>是格，假如存在元素a∈A对任何x∈A,x≤a，则称a是格全上界，记作1。(即是A最大元)定理7-2.4一个格假如有全上界，则是唯一。(我们已证实过，最大元假如有，则是唯一)2).全下界:设<A,≤>是格，假如存在元素a∈A对任何x∈A,a≤x,则称a是格全下界,记作0。(即是A最小元)定理7-2.5一个格假如有全下界，则是唯一。从格图形看：全上界1，就是图最上边元素(只一个)，全下界0，就是图最下边元素(只一个)。

b

0

1

a

c

1

c

025/872.有界格定义：假如一个格存在全上界1与全下界0，则称此格为有界格。设<A,≤>是有界格，则对任何a∈A,有因为a≤1,所以a∧1=aa∨1=10≤a所以a∧0=0a∨0=a是否全部格都是有界格？全部有限个元素格都是有界格，而无限个元素格可能是无界格。比如<I,≤>就既无全上界也无全下界。

26/87三.有补格回顾：集合补集，若A∪B=EA∩B=Φ则~A=B，~B=A如E={a,b}~E=Φ~Φ=E~{a}={b},~{b}={a}1.元素补元：

设<A,≤>是个有界格，a∈A,假如存在b∈A，使得a∨b=1且a∧b=0，则称a与b互为补元。例：右边格中a补元：c,eb补元：无c补元：a,dd补元：ce补元：a0补元：11补元：0

Φ

{a,b}

{a}

{b}

e

0

1

b

c

d

a

27/872.有补格定义：

一个有界格中，假如每个元素都有补元，则称之为有补格。上述有界格中，哪些是有补格？上述有补格中，有些元素补元不唯一，如(2)中b，那么什么样有补格元素补元唯一呢？有界分配格。请看下面定理：

Φ

{a,b}

{a}

{b}

b

0

1

a

c

e

0

1

b

c

d

a

1

c

0(1)(2)(3)(4)28/87定理7－2.6在有界分配格中，假如元素有补元，则补元是唯一。证实：设<A,≤>是有界分配格，任取a∈A，假设a有两个补元b和c，则a∧b=0a∨b=1a∧c=0a∨c=1于是有a∧b=a∧c及a∨b=a∨c由分配格性质3得b=c，所以a补元是唯一。四.布尔格

假如一个格既是分配格又是有补格，则称之为布尔格。布尔格中每个元素都有唯一补元，元素a补元记作。显然<P(E),

>是布尔格。下面介绍由布尔格诱导代数系统－－布尔代数。29/877－3布尔代数BooleanAlgebra一.定义

由布尔格<B,≤>诱导代数系统<B,∨,∧,¯>称之为布尔代数。其中¯是取补元运算。假如A是有限集合，则称它是有限布尔代数。比如：令B＝{F,T}，∧表示合取，∨表示析取，表示否定，<B,∨,∧,

>

就是个由右面格所诱导布尔代数。

E={a,b},<P(E),∪,∩,~>也是个由右面格所诱导布尔代数。

T

F

Φ

{a,b}

{a}

{b}30/87二.布尔代数性质设<B,∨,∧,¯>布尔代数,任意x,y,z∈B,有⑴交换律x∨y=y∨xx∧y=y∧x⑵结合律x∨(y∨z)=(x∨y)∨zx∧(y∧z)=(x∧y)∧z

⑶幂等律x∨x=xx∧x=x

⑷吸收律x∨(x∧y)=xx∨(x∧y)=x⑸分配律x∨(y∧z)=(x∨y)∧(x∨z)

x∧(y∨z)=(x∧y)∨(x∧z)⑹同一律x∨0=xx∧1=x

⑺零律x∨1=1x∧0=0

⑻互补律x∨=1x∧=0

⑼对合律⑽底－摩根定律31/87上述性质都能够由格，分配格，有界格，布尔格得到。下面只证实底－摩根定律。所以。类似可证另一个。32/87三.布尔代数同构1.定义：令<B1,∨1,∧1,¯>和<B2,∨2,∧2,~>是两个布尔代数，假如存在映射f:B1B2，对任何a,b∈B1，有f(a∨1b)=f(a)∨2f(b)f(a∧1b)=f(a)∧2f(b)f()=则称f是<A1,∨1,∧1>到<A2,∨2,∧2>同态映射。

与格同构比较，多了一个关于补运算同构关系等式。为了引出有限布尔代数stone定理，下面介绍原子概念。~f(a)33/872.原子

定义1:设设<B,∨,∧,¯>布尔代数,元素a∈B,a≠0,对任何元素x∈B,有x∧a=a,或x∧a=0,则称a是原子。

定义2:<A,≤>是布尔格,在<A,≤>哈斯图中称盖住全下界0元素为原子。比如：1。e。0。d。f。b。c。a。0。1。

0

1a

b34/87下面先介绍原子判定定理7-3.1设<B,∨,∧,¯>是布尔代数，a∈B,且a≠0,则a是原子充分且必要条件是对任何y∈B，假如y≤a,则y=0或y=a。证实:必要性.设a是原子,且对任何y∈B，有y≤a(往证y=0或y=a),

由原子定义得y∧a=a,或y∧a=0,而由y≤a得y∧a=y,所以有y=0或y=a.充分性.已知对任何y∈B，假如y≤a,则y=0或y=a。(往证a是原子,即证出对任何x∈B

有x∧a=a,或x∧a=0),

任取x∈B,令y=x∧a,因x∧a≤a,所以y≤a,由已知条件得y=0或y=a,所以有x∧a=a,或x∧a=0,所以a是原子.35/87定理7-3.2设a,b是布尔代数<B,∨,∧,¯>中原子，假如a≠b,则a∧b=0,(假如a∧b≠0,则a=b)即不一样两个原子下确界为0证实:设a和b是B中原子,(由原子定义得:对任何x∈B

有x∧a=a,或x∧a=0,)

因为a是原子,而b∈B,所以b∧a=a∧b=a,或b∧a=a∧b=0,于是:假如a∧b≠0,必有a∧b=a.类似地,b是原子,而a∈B,所以a∧b=b,或a∧b=0,

于是:假如a∧b≠0,必有a∧b=b,最终得a=b.所以得出,假如a∧b≠0,则a=b.等价假如a≠b,则a∧b=0.36/87定理7-3.3设a,b1,b2…bn是布尔代数<B,∨,∧,¯>中原子，则a≤b1∨b2∨…∨bn充分且必要条件为对于某个i(1≤i≤n),有a=bi.证实:充分性显然成立,因为对于某个i(1≤i≤n),有a=bi.必有a≤b1∨b2∨…∨bn必要性,已知a≤b1∨b2∨…∨bn,则a∧(b1∨b2∨…∨bn)=a(a∧b1)∨(a∧b2)∨…∨(a∧bn)=a假如每个(a∧bi)=0(1≤i≤n)则(a∧b1)∨(a∧b2)∨…∨(a∧bn)=0这与a是原子矛盾.所以最少有某个i(1≤i≤n),使得(a∧bi)≠0因为a和bi都是原子,由定理7-3.2得a=bi.37/87定理7-3.4设b是有限布尔代数<B,∨,∧,¯>中非0元素，则必存在原子a，使得a≤b.证实:1).假如b是原子,则令b=a,则a≤b.2).假如b不是原子,则必存在b1∈B使得0<b1<b,假如b1不是原子,则必存在b2∈B使得0<b2<b1<b,如此下去,因为B是有限集合,上述过程经过有限步后而最终止束,最终得到原子bk,使得0<bk<…b2<b1<b令bk=a,于是a≤b.1。e。0。d。f。b。c。a。38/87定理7-3.5有限布尔代数中，b∧=0，当且仅当b≤c。比如右图中,2∧=02≤6证实:充分性.已知b≤c又于是因为0是全下界,所以b∧=0必要性.已知b∧=0(往证b≤c,即b∨c=c)b∨c=(b∨c)∧1=(b∨c)∧(c∨)=(b∧)∨c=0∨c=c所以b∨c=c,即b≤c30。3。1。2。5。10。15。6。39/87定理7-3.6设<B,∨,∧,¯>是有限布尔代数，b非0元素，a1,a2…ak是B中满足aj≤b全部原子(j=1,2,…k),则

b＝a1∨a2∨…∨ak且除原子次序不一样外，上述表示式是唯一。

证实:(1)令a1∨a2∨…∨ak＝c(往证b=c即证b≤c且c≤b)

a).证c≤b

显然成立,因为每个ai≤b,(j=1,2,…k)所以a1∨a2∨…∨ak≤b即c≤b.

b).证b≤c.(由定理7-3.5可知,只要证出b∧=0

即可)假设b∧≠0,由定理7-3.4得,必存在原子a,使得a≤b∧,而b∧≤bb∧≤由≤传递性得a≤b,a≤.因为a是原子,且a≤b,b≠0,由题意a必是a1,a2,…,ak中之一,于是a≤a1∨a2∨…∨ak即a≤c,又a≤,得a≤c∧所以a≤0，这与a是原子矛盾.所以只有b∧=0

，

所以b≤c。综上

b=ca1

a2

bak...040/87即得b＝a1∨a2∨…∨ak…….①(2)证实上式是唯一.假设还有原子b1,b2,…,bm∈B,使得b＝b1∨b2∨…∨bm…….②

(下面证{b1,b2,…,bm}={a1,a2,...,ak})a).任取bi∈{b1,b2,…,bm},由②式得{b1,b2,…,bm}中每个bj≤b(1≤j≤m),又b＝a1∨a2∨…∨ak所以bi≤b即bi≤a1∨a2∨…∨ak,因为bi及每个aj(1≤j≤k)都是原子,由定理7-3.3得,{a1,a2,...,ak}中必存在一个aj,使得bi=aj

于是bi∈{a1,a2,…,ak}所以{b1,b2,…,bm}

{a1,a2,...,ak}类似能够证实{a1,a2,...,ak}

{b1,b2,…,bm}最终得

{b1,b2,…,bm}={a1,a2,...,ak}所以上述表示式在不考虑原子次序时,形式是唯一.41/87定理7-3.7在布尔代数<B,∨,∧,¯>中，对B中任何原子a和任何非0元素b,a≤b和a≤两式中有且仅有一个成立。证实:假设上述两个式子都成立,即a≤b和a≤,则有a≤b∧=0,这与a是原子矛盾.下面证实两个式中必有一个成立.因为a∧b≤a,而a是原子,所以只能有a∧b=a或a∧b=0假如a∧b=0,即,由定理7-3.5得,a≤,假如a∧b=a,则a≤b.于是这两个式中必有一个成立.

42/87定理7-3.8(Stone定理)设<B,∨,∧,¯>是有限布尔代数，M是B中全部原子组成集合，则<B,∨,∧,¯>与<P(M),∪,∩,~>同构。证实:结构映射f:BP(M)对于x∈B先经过下边例子了解映射f形式:

f(x)={Φx=0{a|a∈M,a≤x}x≠030。3。1。2。5。10。15。6。12356101530

Φ{2}{3}{5}{2,3}{2,5}{3,5}{2,3,5}B

P(M)f43/871).先证实f是双射.

a).证实f是入射:只有x=0时,才有f(x)=Φ.

任取x1,x2∈B,x1≠0

x1≠0且x1≠x2,由定理3-7.6得,x1,x2能够写成以下形式:x1=a1∨a2∨…∨ak其中ai≤x1(1≤i≤k)x2=b1∨b2∨…∨bm其中bj≤x2(1≤j≤m)因为每个非0元素写成上述表示式形式是唯一,又因为x1≠x2,所以{a1,a2,...,ak}≠{b1,b2,…,bm}.由f定义得f(x1)={a1,a2,...,ak}f(x2)={b1,b2,…,bm}故f(x1)≠f(x2)f入射.

b).

证实f满射:任取M1∈P(M)假如M1为Φ,则f(0)=M1

,假如M1≠Φ,令M1={a1,a2,...,ak},由∨封闭性得,必存在x∈B,使得a1∨a2∨…∨ak=x,显然每个ai≤x(1≤i≤k),故f(x)=M1,所以f是满射.最终由a)b)得f是双射.44/872).证实f满足三个同构关系式.任取x1,x2∈B,因为f是双射,必有M1,M2∈P(M),使得

f(x1)=M1,f(x2)=M2,a).证实f(x1∧x2)=f(x1)∩f(x2)=M1∩M2,

令f(x1∧x2)=M3,即证实M3=M1∩M2

先证M3M1∩M2

假如M3=Φ显然有M3M1∩M2

假如M3≠Φ,任取a∈M3,由f定义得a≤x1∧x2,又因为x1∧x2≤x1,

x1∧x2≤x2,所以a≤x1a≤x2由f定义得a∈f(x1)a∈f(x2)即a∈M1a∈M2,故a∈M1∩M2,所以M3M1∩M245/87再证M1∩M2

M3

假如M1∩M2=Φ显然有M1∩M2

M3

假如M1∩M2≠Φ,任取a∈M1∩M2a∈M1a∈M2所以a是满足a≤x1与a≤x2原子,a≤x1∧x2由f定义得,a∈f(x1∧x2),即a∈M3所以M1∩M2

M3

所以M3=M1∩M2

即f(x1∧

x2)=f(x1)∩f(x2)

46/87b).证实f(x1∨

x2)=f(x1)∪f(x2)=M1∪M2,

令f(x1∨x2)=M4,即证实M4=M1∪M2先证M4M1∪M2

假如M4=Φ显然有M4M1∪M2

假如M4≠Φ,任取a∈M4,由f定义得a≤x1∨x2,则必有a≤x1,或者a≤x2,

(因为假如a≤x1与a≤x2都不成立,由定理7-3.7得必有

与a是原子矛盾,所以a≤x1或a≤x2)由f定义得a∈f(x1)即a∈M1

或a∈f(x2)即a∈M2所以a∈M1∪

M2,所以M4M1∪M247/87再证M1∪M2

M4

假如M1∪M2

=Φ显然有M1∪M2

M4

假如M1∪M2≠Φ,任取a∈M1∪M2a∈M1或者a∈M2假如a∈M1

则a≤x1a≤x1≤x1∨x2∴a∈f(x1∨x2),a∈M4假如a∈M2

则a≤x2a≤x2≤x1∨x2∴a∈f(x1∨x2),a∈M4所以M1∪M2

M4

M4=M1∪M2与a≤x2原子,由f定义得,即所以M1∩M2

M4

所以M4=M1∩M2

即f(x1∨

x2)=f(x1)∪f(x2)48/873).证实于是有x1∨x2=1x1∧x2=0f(x1∨x2)=Mf(x1∧x2)=Φf(x1∨x2)=f(x1)∪f(x2)=M1∪M2=Mf(x1∧x2)=f(x1)∩f(x2)=M1∩M2=Φ所以M2=~M1即由1).2).3)得

f(x1∧x2)=f(x1)∩f(x2)f(x1∨x2)=f(x1)∪f(x2)所以<B,∨,∧,¯>与<P(M),∪,∩,~>同构。49/87推论1.任何有限布尔代数元素个数为2n(n=1,2,3,…)

因为|P(M)|=2n推论2.两个有限布尔代数同构充分且必要条件是其元素个数相同。1。e。0。d。f。b。c。a。0。1。

0

1a

b50/87本节重点掌握布尔代数性质，同构概念，Stone定理及其推论。作业P260（2）

Φ

{c}{b}

{d}{a}

{a,c,d}{a,b,d}

{b,c,d}{a,b,c}

{b,c}{a,d}

{b,d}{a,c}

{a,b,c,d}{c,d}

{a,b}

51/877-4.布尔表示式

一.布尔表示式概念1.定义：设<B,∨,∧,¯>是布尔代数，其上布尔表示式递归定义以下：1)B中任何元素是个布尔表示式。2)任何变元x是个布尔表示式。3)假如E1,E2是个布尔表示式,则,(E1∧E2),(E1∨E2)也是布尔表示式。4)有限次地应用规则1)2)3)得到符号串都是布尔表示式。比如令B={0,1,a,b}(a∨),((x∧y)∨),*表示式最外层括号能够省略.E1¯b¯(x1∨)———52/872.对布尔表示式赋值：设<B,∨,∧,¯>是布尔代数，含有变元x1,x2…xn

布尔表示式记作E(x1,x2,…xn),对变元x1,x2,…,xn分别用B中元素代替过程，称之为对布尔表达式赋值。比如B={0,1,a,b}E(x1,x2)=E(a,b)====b一个布尔表示式E(x1,x2,…xn),经过赋值以后，就得到一个值(即是B中一个元素)。3.两个布尔表示式相等:设<B,∨,∧,¯>是布尔代数，含有变元x1,x2,…xn

两个布尔表示式E1(x1,x2,…xn)和E2(x1,x2,…xn),假如不论对变元x1,x2…xn分别用B中任何元素赋值,都使得E1和E2值相同,则称这两个表示式相等,记作E1(x1,x2,…,xn)=E2(x1,x2,…,xn)

0

1a

b(x1∨)———(a∨)———a∨a____a¯53/87我们能够经过布尔代数性质(10个)得到很多等式.如,E1(x,y)=x∨(y∧)E2(x,y)=x∨yE1(x,y)=x∨(y∧)=(x∨y)∧(x∨)=(x∨y)∧1=x∨y=E2(x,y)二.布尔函数设<B,∨,∧,¯>是一个布尔代数，一个从Bn

B函数被称为n元布尔函数。

含有变元x1,x2,…,xn

布尔表示式E(x1,x2,…xn),能够看成是一个Bn

B布尔函数.布尔函数有两种表示方法:1.表示式方法:比如B={0,1}<B,∨,∧,¯>是布尔代数，即是表示式表示法.2.函数表法:见下面:54/87例：B={0,1,2,3}，<B,∨,∧,¯>是布尔代数在其上定义一个布尔函数f(x,y)函数表如右图所表示:<x,y>f(x,y)<x,y>f(x,y)<0,0>1<2,0>2<0,1>0<2,1>0<0,2>0<2,2>1<0,3>3<2,3>1<1,0>1<3,0>3<1,1>1<3,1>0<1,2>0<3,2>2<1,3>3<3,3>355/87三.布尔表示式范式

1.两元素布尔代数布尔表示式范式:<{0,1},∨,∧,¯>是两个元素布尔代数

1).析取范式

(1).小项:含有n个变元小项形式为:其中比如都是小项.

(2).布尔表示式析取范式:含有变元x1,x2,…,xn

布尔表示式E(x1,x2,…xn),假如写成以下形式:A1∨A2∨...∨Am(m≥1)其中每个Ai(1≤i≤m)都是有n个变元小项.则称此式是E(x1,x2,…xn)析取范式.比如:56/87

2).合取范式

(1).大项:含有n个变元大项形式为:其中比如都是大项.(2).布尔表示式合取范式:含有变元x1,x2,…,xn

布尔表示式E(x1,x2,…xn),假如写成以下形式:A1∧A2∧...∧Am(m≥1)其中每个Ai(1≤i≤m)都是有n个变元大项.则称此式是E(x1,x2,…xn)合取范式.比如:3).析取范式与合取范式写法:

方法1:列真值表

方法2:表示式等价变换.57/87方法1.用真值表求析取范式:先介绍小项性质,以两个变元x1,x2为例每一组赋值,有且仅有一个小项为1.依据一组赋值,求值为1小项:假如变元x,被赋值为0,则在此小项中,x以形式出现;假如变元x,被赋值为1,则在此小项中,x以原形x形式出现.求E(x1,x2,…xn)析取范式:先列出它真值表,找出表中每个1对应小项,然后用∨连接上述小项.00100001010010001011000158/87比如,求布尔代数<{0,1},∨,∧,¯>上布尔表示式E(x1,x2,x3)=x1∧(x2∨)析取范式.E(x1,x2,x3)=(x1∧∧)∨(x1∧x2∧)∨(x1∧x2∧x3)x3¯x1x2x3E(x1,

x2,

x3)00100100011010011010110100001111x3¯x3¯x2¯59/87方法1.用真值表求合取范式:先介绍大项性质,以两个变元x1,x2为例每一组赋值,有且仅有一个大项为0.依据一组赋值,求值为0大项:假如变元x,被赋值为1,则在此小项中,x以形式出现;假如变元x,被赋值为0,则在此小项中,x以原形x形式出现.求E(x1,x2,…xn)合取范式:先列出它真值表,找出表中每个0对应大项,然后用∧连接上述大项.00011101101110110111111060/87比如,求布尔代数<{0,1},∨,∧,¯>上布尔表示式E(x1,x2,x3)=x1∧(x2∨)合取范式.E(x1,x2,x3)=(x1∨x2∨x3)∧(x1∨x2∨)∧(x1∨∨x3)∧(x1∨∨)∧(∨x2∨)x3¯x1x2x3E(x1,

x2,

x3)00100100011010011010110100001111x3¯x2¯x3¯x1¯x2¯x3¯61/87方法2.用表示式等价变换求析取范式:E(x1,x2,x3)=x1∧(x2∨)=(x1∧x2)∨(x1∧)=(x1∧x2∧(x3∨))∨(x1∧(x2∨)∧)=(x1∧x2∧x3)∨(x1∧x2∧)∨(x1∧x2∧

)∨(x1∧∧)=(x1∧x2∧x3)∨(x1∧x2∧)∨(x1∧∧)结果与前相同.用表示式等价变换求合取范式:E(x1,x2,x3)=x1∧(x2∨)=(x1∨(x2∧)∨(x3∧))∧((x1∧)∨x2∨)=(x1∨x2∨x3)∧(x1∨x2∨)∧(x1∨∨x3)∧(x1∨∨)∧(x1∨x2∨)∧(∨x2∨)=(x1∨x2∨

x3)∧(x1∨x2∨)∧(x1∨∨x3)∧(x1∨∨)∧(∨x2∨)x3¯x3¯x2¯x2¯x3¯x3¯x3¯x3¯x3¯x3¯x2¯x3¯x3¯x3¯x2¯x1¯x3¯x3¯x2¯x1¯x3¯x3¯x2¯x3¯x3¯x2¯x1¯x3¯x3¯x2¯62/87*2.普通布尔代数布尔表示式范式:<B,∨,∧,¯>是布尔代数,含有变元x1,x2,…,xn

布尔表示式E(x1,x2,…xn),1).小项:是由n个变元和B中元素组成以下形式,，称为小项.其中Cδ1δ2...δn为B中元素,称之为小项系数.比如B={0,1,a,b},下面就是E(x1,x2,x3)中小项:

63/872).布尔表示式E(x1,x2,...xn)析取范式:E(x1,x2,…,xn)是含有变元x1,x2,…,xn

布尔表示式，假如等价写成以下形式:A1∨A2∨...∨Am(m≥1)其中每个Ai(1≤i≤m)都是有n个变元小项.则称此式是E(x1,x2,…,xn)析取范式.定理7-4.1.设<B,∨,∧,¯>是布尔代数,含有变元x1,x2,…,xn

布尔表示式为E(x1,x2,…xn),则该布尔表示式能够写成析取范式形式.64/87类似地,E(x1,x2,…xn)合取范式为:E(x1,x2,…xn)=(x1∨x2∨...∨xn∨E(0,0,…,0))∧(x1∨x2∨...∨xn-1∨∨E(0,0,…0,1))∧...∧(∨∨...∨∨xn∨E(1,1,…,1,0))∧(∨∨...∨∨E(1,1,…,1))其中E(0,0…,0),E(0,0,…0,1),…,E(1,1,…1,0)和E(1,1,…,1)就是所谓“系数”.实际上,求E(x1,x2,…xn)析取或者合取范式时,就是求这些“系数”.下面看一个例子.xn¯x1¯x2¯xn¯x1¯x2¯xn-1¯65/87已知<B,∨,∧,¯>是布尔代数,其中B={0,a,b,1}分别求出下面布尔表示式析取范式和合取范式.解.先求四个系数:析取范式为:66/87合取范式为:普通布尔函数不一定都能写成布尔表示式形式。例：设B={0,1,2,3},<B,∨,∧,¯>是布尔代数，在其上定义一个布尔函数g(x,y)，其函数表以下列图所表示:证实其不能用一个布尔表示式将其表示。67/87例：B={0,1,2,3},<B,∨,∧,¯>是布尔代数,

在其上定义一个布尔函数g(x,y),其函数表如右图所表示:<x,y>g(x,y)<x,y>g(x,y)<0,0>1<2,0>2<0,1>0<2,1>0<0,2>0<2,2>1<0,3>3<2,3>1<1,0>1<3,0>3<1,1>1<3,1>0<1,2>0<3,2>2<1,3>3<3,3>368/87证实：用反证法。若g(x,y)能被布尔表示式表示，则其必可写成析取范式形式,设其为：而g(1,1)=1,g(1,0)=1,g(0,1)=0,g(0,0)=1所以对于布尔格<{0,1,2,3},≼>，其哈斯图为考查g(3,3)=(2∧2)∨(3∧2)∨(3∧3)=2∨0∨3=1

0

1

2

369/87而在表中g(3,3)=2，矛盾，所以该函数不能用布尔表示式表示。70/87本节重点掌握内容：布尔表示式定义、析取范式和合取范式写法。本章内容小结：1.格概念、格性质.格同构.2.分配格性质、判断.有界格有补格布尔格概念性质.3.布尔代数性质,Stone定理应用.4.布尔表示式定义,范式写法.71/87

习题课———格与布尔代数72/87P242(1).(a)不是格，因为d和e没有下确界,也没有上确界.(d)不是格，5和6没有下确界,7和8既没下确界,也没上确界.深入问,假如是格,哪些是分配格?哪些是有补格?(b)不是分配格,因子集{f,g,j,k,h}组成子格如图所表示但它是有补格。(c)不是分配格,考查子集{l,n,q,r,o}组成子格；也不是有补格。1

d

a

b

ce

f

g

hi

j

k5

2

4

6l

m

no

q

r

p

3

8

7(a)(b)(c)(d)

j

k

f

h

g73/87(2).设≤是L上整除关系,下面偏序集中,哪些是格?a)L={1,2,3,4,6,12},b).L={1,2,3,4,6,8,12,14}c)L={1,2,3,4,5,6,7,8,9,10,11,12}可见只有(a)是格.

124

62

3

18

4

125

3

1

6

78

14

2

1110

92

12

4

61

3(a)(b)(c)74/87(4).设<A,≤>是一个格,任取a,b∈A,a<b(即a≤b∧a≠b),结构集合:B={x|x∈A且a≤x≤b},则<B,≤>也是格.证实:显然B是A非空子集(因为a≤a≤b,a≤b≤b,所以a,b∈B),只要证实∧和∨在B上封闭即可.任取x,y∈B,由B组成得a≤x≤b,a≤y≤b,于是由格性质得,a≤x∨y≤ba≤x∧y≤b,于是有x∨y∈Bx∧y∈B,说明∨和∧在B上封闭,所以<B,≤>也是格.75/87(7).设a,b是格<A,≤>中两个元素,证实:a).a∧b=b当且仅当a∨b=a.b).a∧b<b和a∧b<a,当且仅当a与b是不可比较.证实:a)充分性:已知a∨b=ab=b∧(b∨a)=b∧(a∨b)=b∧a=a∧b

必要性:已知a∧b=b,a=a∨(a∧b)=a∨bb)充分性:已知a与b是不可比较.因a∧b≤b,a∧b≤a,假如a∧b=b,则有b≤a,假如a∧b=a,则有a≤b,都与a与b是不可比较矛盾.所以有:a∧b≤b∧a∧b≠b,于是有a∧b<ba∧b≤a∧a∧b≠a,于是有a∧b<a