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

离散数学第五章格与布尔代数1第1页，课件共86页，创作于2023年2月离散数学

第五章格与布尔代数

§1.格

§2.布尔代数

2第2页，课件共86页，创作于2023年2月离散数学

§2.布尔代数

布尔代数的定义

布尔代数的性质

布尔代数中的宏运算

有限布尔代数的原子表示

布尔函数与布尔表达式

布尔环与布尔代数3第3页，课件共86页，创作于2023年2月离散数学

§2.

布尔代数定义1.布尔代数(Booleanalgebra)

有补的分配格(B,≼,,,,0,1)称为布尔代数。注：布尔代数(B,≼,,,,0,1)简记为B；

若0=1，则B称为退化的布尔代数。以后，我们不讨论此种情况，因此，今后，我们假定总有|B|2；

例1.集合代数(2X,,,,,,X)

是布尔代数已知集合代数(2X,,,,,,X)

是有补的分配格(本章§1例10和例20)，因此是布尔代数。注：当X={a}时，2X={,X}，集合代数的一个特例是4第4页，课件共86页，创作于2023年2月离散数学({,X},,,,,,X)

，其运算表如下：它当然也是一个布尔代数。例2.开关代数

(switchingalgebra)(S,,,

,,0,1)

是布尔代数这里：S={0,1}，00,01,11,其运算表如下：表1AA

XXABABABXXXXXXXX5第5页，课件共86页，创作于2023年2月离散数学通过变元代换，显见表2与表1是完全相同的。即，令

h:S2X,h

(0)=,h

(1)=X

(这里：X={a})

则易证h是一个双射的同态函数。因此开关代数(S,,,

,,0,1)与集合代数(2X,,,,,,X)

是同构的(这里X={a})，所以开关代数(S,,,

,,0,1)是一个布尔代数。

xyxyxy0000010110011111

x

0110表26第6页，课件共86页，创作于2023年2月离散数学例3.命题代数(ℙ,≼,,

,,F,T)

是布尔代数这里：ℙ={F,T}，F≼

F,F

≼

T,T

≼

T,其运算表如下：通过变元代换，显见表3与表1是完全相同的。即，令

h:ℙ2X,h

(F)=,h

(T)=X

(这里X={a})

PQPQ

PQFF

F

FFT

FTTF

FTTTTTP

P

FTT

F表37第7页，课件共86页，创作于2023年2月离散数学则易证h是一个双射的同态函数。因此，命题代数(ℙ,≼,,

,,F,T)与集合代数(2X,,,,,,X)

是同构的(这里X={a})，所以命题代数(ℙ,≼,,

,,F,T)是一个布尔代数。注：利用≼，在命题逻辑中可定义逻辑推论(蕴涵)关系(⊨)。即

(或

⊨)v((v)≼(v))

有限布尔代数：对于布尔代数(B,≼,,,,0,1)，若nN，使|B|=n

，则称其为有限布尔代数；

集合代数({,X},,,,,,X)、开关代数(S,,,

,,0,1)

、命题代数(ℙ,≼,,

,,F,T)都是有限布尔代数；

例4.n元集合代数(2X,,,,,,X)

是有限布尔代数这里：X={a1,a2,,an},因此，|X|=n，

|2X|=2n

。

8第8页，课件共86页，创作于2023年2月离散数学

显然，有限集合代数是有限布尔代数。n元集合代数是有限集合代数，因此是有限布尔代数。

例5.n元(维)开关代数(Sn,,,

,,0,1)是有限布尔代数这里：Sn={(x1,x2,,xn)：xiS(1in)}=

Sn(其中S={0,1})，

0=(0,0,,0)，1=(1,1,,1)，并且

x,ySn，x

=(x1,x2,,xn)，y

=(y1,y2,,yn)xyi(1in)(xi

yi)xy=(x1y1,x2y2,,xnyn)

xy=(x1y1,x2y2,,xnyn)

=(

,

,,

)即n元开关代数的序关系、运算、最小元和最大元的定义都归结为一元开关代数(S,,,

,,0,1)

。9第9页，课件共86页，创作于2023年2月离散数学现在我们来证：

(Sn,,,

,,0,1)

≅(2X,,,,,,X)

这里：X={a1,a2,,an}，即n元开关代数与n元集合代数是同构的。从而由n元集合代数是有限布尔代数(例4)，可知n元开关代数(Sn,,,

,,0,1)也是有限布尔代数。令：h:Sn2X,xSn，x

=(x1,x2,,xn)，

h(x)=A2X(或AX)这里：A={ai：aiX

xi=1(1in)}因此aih(x)aiAxi=1(1in)

。下面我们证明h是一同构函数：为此，我们总设x,ySn，

h(x)=A，h(y)=B明显地x

=(x1,x2,,xn)，y

=(y1,y2,,yn)10第10页，课件共86页，创作于2023年2月离散数学

显然有h

(0)=,h

(1)=X；

(1)先证h是双射函数

①h是单射函数

h(x)=h(y)A=BaiAaiB(1in)xi=1

yi=1(1in)xi=

yi(1in)

x=y；

②h是满射函数

A2X

(即AX)，我们构造x

=(x1,x2,,xn)Sn，使得11第11页，课件共86页，创作于2023年2月离散数学

即

xi=1aiA(1in)

因此aih(x)

(1in)

xi=1(1in)

aiA

(1in)所以

h(x)=A；

(2)次证h满足同态公式

①h(xy)=h(x)h(y)

因为aih(xy)

(1in)

xiyi=1(1in)xi=1yi=1(1in)

aiAaiB

(1in)12第12页，课件共86页，创作于2023年2月离散数学aiAB

(1in)aih(x)h(y)

(1in)所以

h(xy)=h(x)h(y)

；

②h(xy)=h(x)h(y)仿①可证；

③h(

)=[h(x)]

因此aih(

)(1in)

=1(1in)

xi=0(1in)

aiA

(1in)

aiA

(1in)ai[h(x)]

(1in)所以

h(

)=[h(x)]

；13第13页，课件共86页，创作于2023年2月离散数学

(3)最后证h满足保序性

即xyh(x)h(y)因为aih(x)(1in)aiA(1in)

xi=1

(1in)yi=1(1in)(xyi(1in)(xi

yi))aiB(1in)aih(y)(1in)所以h(x)h(y)；例6.n元命题代数(ℙn,≼,,

,,F,T)

是有限布尔代数这里：ℙn={(P1,P2,,Pn)：Piℙ(1in)}=

ℙn14第14页，课件共86页，创作于2023年2月离散数学(其中ℙ={F,T})，

F=(F,F,,F)，T=(T,T,,T)，并且

P,Qℙn，P

=(P1,P2,,Pn)，Q

=(Q1,Q2,,Qn)

P

≼

Q

i(1in)(Pi≼

Qi)

P

Q

=(P1Q1,P2Q2,,PnQn)

P

Q

=(P1Q1,P2Q2,,PnQn)

P

=(P1

,P2

,,Pn)即n元命题代数的序关系、运算、最小元和最大元的定义都归结为一元命题代数(ℙ,≼,,

,,F,T)

。仿例5我们易证：

(ℙn,≼,,

,,F,T)≅(2X,,,,,,X)

这里：X={a1,a2,,an}，即n元命题代数与n元集合代数是同构的。从而由n元集合代数是有限布尔代数(例4)，可知n元命题代数(ℙn,≼,,

,,F,T)也是有限布尔代数。15第15页，课件共86页，创作于2023年2月离散数学定理1.(反身律)设(B,≼,,,,0,1)是布尔代数。则xB

，

(x)=x。[证].

xB

，

xx=0=(x)x(互补律)

xx=1=(x)x(互补律)x=(x)

(根据上节定理10：分配格有消去律)(x)=x

(等号的对称性)

定理2.(消去律之二)设(B,≼,,,,0,1)是布尔代数。则x,y,zB

，

xy=xz

x

y=xz。16第16页，课件共86页，创作于2023年2月离散数学[证].

x,y,zB

，

y=0y(因0≼y)=(xx)y

(互补律)

=(xy)(xy)

(分配律)=(xz)(xz)(条件xy=xz和xy=xz)

=(xx)z

(分配律)=0z

(互补律)=z(因0≼z

)所以，消去率之二在布尔代数中成立。定理3.(消去律之三)设(B,≼,,,,0,1)是布尔代数。则x,y,zB

，

xy=xz

x

y=xz。17第17页，课件共86页，创作于2023年2月离散数学[证].

仿定理2可证。对偶原理(dualityprinciple):

设(B,≼,,,,0,1)

是布尔代数，≽

是≼的逆关系。则

(1)在布尔代数(B,≼,,,,0,1)中实行：将

≼换成≽；将换成；将换成；将0换成1

；将

1

换成

0

；得到的(B,≽,,,,1,0)仍是一布尔代数；

(2)若T是原布尔代数中某个已经证明的定理，那么在定理T的条件和结论中实行：将

≼换成≽；将换成；将换成；将0换成1

；将

1

换成

0

；由此所得到的新的定理T在原布尔代数中仍然成立。18第18页，课件共86页，创作于2023年2月离散数学[证].布尔代数中的对偶原理实质上来源于两个二元运算和所具有的结合律、交换律、幂等律、吸收律、分配律的对称性，半序关系≼和其逆关系≽的对称性；最小元0和最大元1的对称性；以及任何元素x与其补元x的对称性。注：布尔代数(B,≽,,,,1,0)称为原布尔代数

(B,≼,

,,,0,1)的对偶布尔代数。实际上，它们互为对偶；定理T称为原定理T的对偶定理。实际上，它们互为对偶；定理4.(deMorgan律)设(B,≼,

,,,0,1)是布尔代数。则x,y,zB

，

(1)(xy)=xy；

(2)(xy)=xy。19第19页，课件共86页，创作于2023年2月离散数学[证].根据对偶原理的(2)，只须证(1)即可：x,y,zB

，由于(xy)(xy)

=((xy)x)((xy)y)

(分配律)=((xx)y)(x(

yy))

(结合律、交换律)=(0y)(x0)

(互补律)

=00(因0≼x及0≼y)

=0(因自反性0≼0

)

及(xy)(xy)

=(x(xy))(

y(xy))(分配律)=((xx)y)(x

(yy))(结合律、交换律)=(1y)(x1)

(互补律)

=11(因x≼1及y

≼1)

=1(因自反性1≼1

)20第20页，课件共86页，创作于2023年2月离散数学所以，(x

y)=x

y。定理5.设(B,≼,

,,,0,1)是布尔代数。则x,yB

，以下四条等价

(1)x≼y(

xy=xxy=y(§1定理4

))；

(2)y≼x(

xy

=y

x

y

=x

(§1定理4

))

；

(3)xy=0；

(4)x

y=1

。[证].采用环形证法。即(1)(2)(3)(4)(1)

(1)(2)：

xy

=(xy)

(deMorgan律)

=y(因(1)x≼y)y≼x(§1定理4

)

21第21页，课件共86页，创作于2023年2月离散数学

(2)(3)：

xy=x(xy)

(因(2)y≼x)

=(xx)y(结合律)=0y(互补律)=0(因0≼y)(3)(4)：

x

y=(x

y)

0

(因0

≼xy)=(x

y)

(xy)

(因(3)xy=0)=((xy)x)((xy)y)(分配律)=((xx)y)(x

(yy))(结合律、交换律)22第22页，课件共86页，创作于2023年2月离散数学=(1y)(x1)

(互补律)=11(因x

≼1及y

≼1)=1(因自反性1≼1

)(4)(1)：

xy=(xy)0(因0

≼xy)

=(xy)(xx)

(互补律)=x(yx)

(分配律)=x(xy)

(交换律)=x1

(因(4)x

y=1)=x(因x≼1

)x≼y

(§1定理4

)

证明完毕。23第23页，课件共86页，创作于2023年2月离散数学定义2.宏运算(macrooperation)

在布尔代数(B,≼,,,,0,1)中可定义如下的宏运算：

x,yB

(1)x＼y=xy

；(差运算)

(2)x+y=(x＼y)(y＼x

)=(xy)(yx)；(对称差)(3)xy=(xy)(yx)

；(对称积)注：这些宏运算与第一章集合代数中的宏运算是对应的概念；因而也有如下有关宏运算的定理。定理6.设(B,≼,

,,,0,1)是布尔代数。则

x,y,zB

24第24页，课件共86页，创作于2023年2月离散数学

(1)x=1＼x

；

(2)x≼yx＼

y=0；

(3)xy=(x＼y)y

；

(4)y≼x(x＼y)y=x；

(5)x＼y=xxy=0；

(6)(x＼y)z=(xz)＼(yz)。[证].只证(1),(3),(5)

(1)x=1

x(因x

≼1及定理5(1))

=1＼x

(3)xy=(xy)1

(因xy≼1及定理5(1))=(xy)(yy)(互补律)=(xy)(y

y)(交换律)25第25页，课件共86页，创作于2023年2月离散数学

=(xy)y(分配律)

=(x＼y)y

(5)x＼y=xxy

=xx

≼

y

(定理5(1))x(y)

=0(定理5(3))xy=0(反身律)定理7.设(B,≼,

,,,0,1)是布尔代数。则

x,y,zB

(1)x+y=y+x；

(2)x=yx+y=0；26第26页，课件共86页，创作于2023年2月离散数学

(3)x+y=(xy)(x

y)=(xy)＼(xy)；

(4)xy=(x+y)(xy)；

(5)(x+y)+z=x+(y+z)。[证].只证(2),(4)(2)x=y(x

≼

y)(y

≼

x)

(自反性及反对称性)(xy=0)(yx=0)(定理5(3))x+y=(xy)(yx)=0

0

=0(因自反性0≼0及定理5(1))(4)xy

=(xy)1(因xy≼1

及定理5(1))=(xy)

((xy)(xy))(互补律)27第27页，课件共86页，创作于2023年2月离散数学=((xy)

(xy))((xy)

(xy))(分配律)=((xy)＼(xy))(xy)(因xy

≼xy

及定理5(1))=(x+y)(xy)(由本定理(3))定理8.设(B,≼,

,,,0,1)是布尔代数。则

x,y,zB

(1)xy=yx；

(2)xy=x

y

；

(3)xy=(x+y)；

(4)xx=1；

(5)xy=x

+y=x+y；

(6)xy

=x

y=x+y；

(7)(xy)z=x

(yz)；28第28页，课件共86页，创作于2023年2月离散数学

(8)x

1

=x+

0=x；

(9)x0

=x+

1

=x

；

(10)x=yxy=1。[证].只证(3),(6),(9)

(3)xy=(xy)(yx)

=((xy)(yx))

(deMorgan律及反身律等)=(x+y)(6)xy

=x

(y)

(由本定理(2))=x

y(反身律)=(x+y)

(由本定理(3))29第29页，课件共86页，创作于2023年2月离散数学=((x

y)(y

(x)))=((x

y)(yx))(反身律)=((xy)(x

y))(交换律)=(x

y)(xy)(deMorgan律及反身律)=(xy)(x

y)(交换律)=x+y(定理7(3))(9)x0=x1

(1=0)=x+

1(由本定理(6))=(x＼1)(1＼x

)=(x

1)x(定理6(1))=(x0)x(1=0)30第30页，课件共86页，创作于2023年2月离散数学=0

x

(因0≼x

及定理5(1))=x(因0≼x

及定理5(1))

有限集合代数是有限布尔代数(例4)；有限布尔代数是否是有限集合代数呢？下面的斯笃(stone)定理回答了这个问题，答案是肯定的；这就为我们利用熟悉、简单的有限集合代数来研究、简化有限布尔代数奠定了理论基础。定义3.原子(atom)

设(B,≼,,,,0,1)是布尔代数。

a是B的一个原子

aBa0(xB)(ax=0ax=a)aBa0(xB)(x0ax=0a≼

x)。

31第31页，课件共86页，创作于2023年2月离散数学注：令S={a：aBa是原子}称S为B的原子集；

定义中a0

说明原子a不能是最小元；

定义中后一等价式说明：任一非零元(x0)，要么与原子不可比较(ax=0

)，要么比原子大(a≼

x)。例7.

a0a6a2a7a4a5a3a1图3图２图１a0a1a2a3a0a132第32页，课件共86页，创作于2023年2月离散数学

在图1中，a0是最小元，a1是原子，a1是最大元；在图2中，a0是最小元，a2,

a3是原子，a1是最大元；在图3中，a0是最小元，a2,

a3,a4是原子，a1是最大元；

定理9.设(B,≼,,,,0,1)是布尔代数，并且aB。

a是B的一个原子a是0的一个直接后继；即a是B的一个原子

0≼aa0(xB)(0≼x

x≼ax=0x=a)。[证].先证)：①已知a0

(原子的定义)；②显然0≼a

(0是B的最小元及aB)；③(xB)(0≼x

x≼ax=0x=a)33第33页，课件共86页，创作于2023年2月离散数学

对于任何元素xB

，

0≼x

x≼a

ax=x(本节定理5(1)及x≼a)x=0x=a(a是原子，故ax=0ax=a)

由①②③可知，a是0的直接后继；次证)：

①已知aB

；②已知a0

(a是0的直接后继)；③(xB)(ax=0ax=a)

(采用二分法)；对于任何元素xB

，分情况论证如下：

(甲)x与a可比较：

(Ⅰ)x=0，则有ax=0(本节定理5(1)及0≼a)34第34页，课件共86页，创作于2023年2月离散数学

(Ⅱ)x0

(a)x≼a0≺xx≼a(0是B的最小元及x0

)x=a

(a是0的直接后继)ax=a(幂等律)

(b)a≼x，则有ax=a(本节定理5(1))

(乙)x与a不可比较：我们可设ax=t

，于是

ax=t

t≼a

(因t是a和x

的下界，或因a

t=a(ax)=a(吸收律)

及本节定理5(1)

)

0≼tt≼a(0是B的最小元)

35第35页，课件共86页，创作于2023年2月离散数学

t=0t=a(a是0的直接后继)ax=0ax=a于是，总有ax=0ax=a；综上①②③所证，a是B的原子。注：此定理具体到集合代数，原子就是那些单元素集合。因为单元素集合在包含关系下是空集(最小元)的直接后继。即，对于一般集合代数，有原子集S={{a}:aX}；对于n元集合代数，这里X={a1,a2,,an}，有原子集

S={{a1},{a2},,{an}}。定理10.设(B,≼,,,,0,1)是布尔代数，并且a,b都是B的原子。则

(1)ab0a=b

；36第36页，课件共86页，创作于2023年2月离散数学(2)abab=0

。[证].(2)是(1)的逆否；于是只证(1)

ab0

ab=a

ab=b(a是原子

b是原子)a=b注：此定理说明两个原子，要么是同一个，要么相互不可比较。形象的，拿图论的语言来说，就是代表两个原子的结点，要么是同一个结点，要么分处在从0结点到1结点的两条不同的路上。定理11.设(B,≼,,,,0,1)是有限布尔代数，|B|=n

，

S是B的原子集。则

(xB)(x0(aS)(a≼x))37第37页，课件共86页，创作于2023年2月离散数学即，对任何B的非零元素x

，都存在着B的某一原子a

，使得a≼x

。[证].若x已是原子，则由x≼x(≼的自反性)，记a为x，就有a≼x

，定理得证；若x不是原子，则必有x1

0

，x1

x，使0≼x1

x1

≼x(否则，x是0的直接后继，因而由本节定理9，x是原子，与已设x不是原子矛盾)；若x1是原子，则由x1≼x，记a为x1

，就有a≼x

，定理得证；若x1不是原子，则必有x2

0

，x2

x1

，使0≼x2

x2

≼x1(否则，x1是0的直接后继，因而由本节定理9，x1是原子，与已设x1不是原子矛盾)；若x2是原子，则由x2≼x1

，记a为x2

，从a≼x1

x1≼x

(≼的传递性)

，就有a≼x，定理得证；若x2不是原子，则必有x30

，x3

x2

，使0≼x338第38页，课件共86页，创作于2023年2月离散数学

x3≼x2(否则，x2是0的直接后继，因而由本节定理9，x2是原子，与已设x2不是原子矛盾)；重复以上过程。从B的有限性可知，一定存在某个xk(kn)

，xk是原子，使得0≼xk

xk≼xk-1

，从而有

0≼xk≼xk-1≼≼x3≼x2≼x1≼x根据≼的传递性可知xk≼x，记a为xk

，于是a是原子,并且a≼x，定理得证。注：此定理说明在任一非零元素x的下方，一定有原子a存在；或者形象的，拿图论的语言来说，就是在结点x所处的从0结点到1结点的某条路上，在0结点上方，x结点下方，一定有原子结点a存在。定理12.(可表示性定理)

设(B,≼,,,,0,1)是有限布尔代数。

39第39页，课件共86页，创作于2023年2月离散数学

对任何元素xB，x0

，我们令

S(x)={a：aSa≼x}则一定有(元素x的原子表示式)。[证].首先，我们令，则一方面，显然有y≼x(因为对每个原子aS(x)，都有a≼x，根据上确界的最小性，就有≼x)

；另一方面，必有x≼y；为证x≼y

，根据定理5，我们只须证xy=0即可。(采用反证法)

否则，xy0,那么，根据定理11，一定有原子aS存在，使得0≼a≼xy。但是

xy≼x，xy≼y，从而由≼的传递性有a≼x，这说明aS(x)，从而a≼

y(因y是S(x)中诸原子的上确界)；同时由≼的传递性，40第40页，课件共86页，创作于2023年2月离散数学

又有a≼

y；故此a≼y

y=0(下确界的最大性及互补律)，但0≼a，于是由≼的反对称性有a=0。这就与a是原子(a0)矛盾；综合这两方面，再次由≼的反对称性可得

x=y。注：此定理说明B的任一非零元素x，都可由在它下面的(即小于它的)全部原子来表示。定理13.设(B,≼,,,,0,1)是有限布尔代数。设b,a1,a2,,anS都是原子。我们令，那么

b≼xb{a1,a2,,an}。[证].采用反证法。否则，b{a1,a2,,an}，故i(1in)，bai。由于b,ai都是原子，故根据定理10(2)可得i(1in)，bai=0。于是我们有41第41页，课件共86页，创作于2023年2月离散数学

(条件：b≼x)

(分配律)(bai=0(i(1in)))这与已知b是原子(b0)矛盾。定理14.(原子表示式的唯一性定理)

设(B,≼,,,,0,1)是有限布尔代数。则

B中任何非零元素x的原子表示式是唯一的。即42第42页，课件共86页，创作于2023年2月离散数学

对任何元素xB，x0

，那么

这里：S1,S2S[证].①先证：S1S2

aS,aS1a≼x

()aS2

(定理13及)所以S1S2；②次证：S2S1bS,bS2b≼x

()bS1

(定理13及)所以S2S1；综合①②，我们有S1=S2

。43第43页，课件共86页，创作于2023年2月离散数学注：定理12及14说明B的任一非零元素x，都可由在它下面的(即小于它的)全部原子来表示。

而所有的原子都小于最大元1

，故最大元1可由全部原子唯一的表示为：

另外，最小元0也可形式的表示为：。

定理15.(斯笃(stone)定理)

设(B,≼,,,,0,1)是一有限布尔代数，S是B的所有原子的集合。则有限布尔代数(B,≼,,,,0,1)与有限集合代数(2S,,,,,,X)同构。[证].(1)首先构造自然映射：h:B2S

使得xB，x0

，h(x)=S(x)={a：aSa≼x}2S

h(0)=2S

44第44页，课件共86页，创作于2023年2月离散数学

h是函数(后者唯一)：x,yB，

x=y

aS,a≼x

a≼y

(≼的传递性，定理13){a；aSa≼x}={a：aSa≼y}S(x)=S(y)h(x)=h(y)；

(2)h是双射函数：

①h是满射：A2S(即AS)

，令，则h(x)=S(x)={a：aSa≼x}=A(定理13)；

45第45页，课件共86页，创作于2023年2月离散数学

②h是单射：x,yB，

h(x)=h(y)S(x)=S(y)(定理12)

(S(x)=S(y))

(定理12)

；

(3)h满足同态公式：x,yB，x,y0

，①h(xy)=h(x)h(y)h(xy)=S(xy)

46第46页，课件共86页，创作于2023年2月离散数学

={a：aSa≼xy}={a：aS(a≼xa≼y)}

(见注：由a是原子易证：a≼xy

a≼xa≼y)={a：(aSaS)(a≼xa≼y)}(的幂等律)={a：(aSa≼x)(aSa≼y)}(的结合律、交换律)={a：(aSa≼x)}{a：(aSa≼y)=S(x)S(y)=h(x)h(y)当x,y至少有一为0

时，易直接验证如上的同态公式也成立；②h(xy)=h(x)h(y)47第47页，课件共86页，创作于2023年2月离散数学

h(xy)=S(xy)={a：aSa≼x

y}={a：aS(a≼xa≼y)}

(见注：由a是原子易证：a≼x

y

a≼x

a≼y)={a：(aSa≼x)(aSa≼y)}

(对的分配律)={a：(aSa≼x)}{a：(aSa≼y)=S(x)S(y)=h(x)h(y)当x,y至少有一为0

时，易直接验证如上的同态公式也成立；

48第48页，课件共86页，创作于2023年2月离散数学

③h(x)=h(x)

=S(x)={a：aSa≼x}={a：aS(a≼x)}

(见注：由a是原子易证：a≼x(a≼x))=S\{a：aSa≼x}=

=

当x为0

或1时，易直接验证如上的同态公式也成立；49第49页，课件共86页，创作于2023年2月离散数学(4)h具有保序性：x,yB，x,y0

，

x≼yh(x)h(y)x≼y{a：aSa≼x}{a：aSa≼y}(因x≼y(aS,a≼x

a≼y)(≼的传递性))S(x)S(y)h(x)h(y)(5)h具有齐性：显然h(0)=

h(1)=S最后，由同构函数的定义可知h是从(B,≼,,,,0,1)到(2S,,,,,,X)的同构函数，因而有限布尔代数(B,≼,,,,0,1)与有限集合代数(2S,,,,,,X)同构。证明完毕。50第50页，课件共86页，创作于2023年2月离散数学注：定理15证明(3)①：

a≼xy

a≼xa≼y；

先证)：(采用反证法)否则，(a≼xa≼y)，于是则有(a≼xa≼y)

(a≼x)(a≼y)(deMorgan律)a

x=0a

y=0(因a是原子)a(x

y)

=(a

x)

y

(结合律)

=0

y

(因a

x=0)

=0

(因0≼a)

(a≼xy)(因a是原子)而这与必要性条件a≼xy矛盾；次证)：

a≼xa≼y

(说明a是一下界)

a≼xy(下确界的最大性)；51第51页，课件共86页，创作于2023年2月离散数学定理15证明(3)②

：a≼x

y

a≼xa≼y

；

先证)：(采用反证法)否则，(a≼xa≼y)，于是则有(a≼xa≼y)

(a≼x)(a≼y)(deMorgan律)a

x=0a

y=0(因a是原子)a(x

y)

=(a

x)(a

y)

(分配律)

=00

(因a

x=0和

a

y=0)

=0

(幂等律)

(a≼x

y)(因a是原子)而这与必要性条件a≼x

y矛盾；次证)：

a≼xa≼y

(a≼x

≼x

y)(a≼yy≼x

y)(上确界是上界)a≼x

ya≼x

y

(≼的传递性)a≼x

y

(的幂等律)；52第52页，课件共86页，创作于2023年2月离散数学定理15证明(3)③

：a≼x(a≼x)

；

a≼x

a

x=a(x)

(反身律)

=0

(定理5(3)及a≼x)(a≼x)

(因a是原子)。注：由Stone定理知每一个布尔代数都和某一个集合代数同构。前