文档介绍：该【离散数学-第五章-格与布尔代数(2) 】是由【350678539】上传分享，文档一共【85】页，该文档可以免费在线阅读，需要了解更多关于【离散数学-第五章-格与布尔代数(2) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。离散数学-第五章-格与布尔代数(2)
第一页,共85页。
离散数学
§
布尔代数的定义
布尔代数的性质
布尔代数中的宏运算
有限布尔代数的原子表示
布尔函数与布尔表达式
布尔环与布尔代数
2
第二页,共85页。
离散数学
§
(Booleanalgebra)
有补的分配格(B,≼,,,,0,1)称为布尔代数。
注:布尔代数(B,≼,,,,0,1)简记为B;
若0=1,则B称为退化的布尔代数。以后,我们不讨论此种情况,因此,今后,我们假定总有|B|2;
(2X,,,,,,X)是布尔代数
已知集合代数(2X,,,,,,X)是有补的分配格(本章§1例10和例20),因此是布尔代数。
注:当X={a}时,2X={,X},集合代数的一个特例是
3
第三页,共85页。
离散数学
({,X},,,,,,X),其运算表如下:
它当然也是一个布尔代数。
(switchingalgebra)
(S,,,,,0,1)是布尔代数
这里:S={0,1},00,01,11,其运算表如下:
表1
A
A

X
X

A
B
AB
AB





X

X
X


X
X
X
X
X
4
第四页,共85页。
离散数学
通过变元代换,显见表2与表1是完全相同的。即,令
h:S2X,h(0)=,h(1)=X (这里:X={a})
则易证h是一个双射的同态函数。
因此开关代数(S,,,,,0,1)与集合代数(2X,,,,,,X)是同构的(这里X={a}),所以开关代数(S,,,,,0,1)是一个布尔代数。
x
y
xy
xy
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
1
x
0
1
1
0
表2
5
第五页,共85页。
离散数学
(ℙ,≼,,,,F,T)是布尔代数
这里:ℙ={F,T},F≼F,F≼T,T≼T,其运算表如下:
通过变元代换,显见表3与表1是完全相同的。即,令
h:ℙ2X,h(F)=,h(T)=X (这里X={a})
P
Q
PQ
PQ
F
F
F
F
F
T
F
T
T
F
F
T
T
T
T
T
P
P
F
T
T
F
表3
6
第六页,共85页。
离散数学
则易证h是一个双射的同态函数。
因此,命题代数(ℙ,≼,,,,F,T)与集合代数(2X,,,,,,X)是同构的(这里X={a}),所以命题代数(ℙ,≼,,,,F,T)是一个布尔代数。
注:利用≼,在命题逻辑中可定义逻辑推论(蕴涵)关系(⊨)。即
(或⊨)v((v)≼(v))
有限布尔代数:对于布尔代数(B,≼,,,,0,1),若nN,使|B|=n,则称其为有限布尔代数;
集合代数({,X},,,,,,X)、开关代数(S,,,,,0,1)、命题代数(ℙ,≼,,,,F,T)都是有限布尔代数;

(2X,,,,,,X)是有限布尔代数
这里:X={a1,a2,,an},因此,|X|=n,|2X|=2n。
7
第七页,共85页。
离散数学
显然,有限集合代数是有限布尔代数。n元集合代数
是有限集合代数,因此是有限布尔代数。
(维)开关代数(Sn,,,,,0,1)是有限布尔代数
这里:Sn={(x1,x2,,xn):xiS(1in)}=Sn
(其中S={0,1}),0=(0,0,,0),1=(1,1,,1),并且
x,ySn,x=(x1,x2,,xn),y=(y1,y2,,yn)
xyi(1in)(xiyi)
xy=(x1y1,x2y2,,xnyn)
xy=(x1y1,x2y2,,xnyn)
=(,,,)
即n元开关代数的序关系、运算、最小元和最大元的定义都归结为一元开关代数(S,,,,,0,1)。
8
第八页,共85页。
离散数学
现在我们来证:
(Sn,,,,,0,1)≅(2X,,,,,,X)
这里:X={a1,a2,,an},即
n元开关代数与n元集合代数是同构的。
从而由n元集合代数是有限布尔代数(例4),可知n元开关代数(Sn,,,,,0,1)也是有限布尔代数。
令:h:Sn2X,xSn,x=(x1,x2,,xn),
h(x)=A2X(或AX)
这里:A={ai:aiXxi=1(1in)}
因此aih(x)aiAxi=1(1in)。
下面我们证明h是一同构函数:
为此,我们总设x,ySn,h(x)=A,h(y)=B
明显地 x=(x1,x2,,xn),y=(y1,y2,,yn)
9
第九页,共85页。
离散数学
显然有 h(0)=,h(1)=X;
(1)先证h是双射函数
①h是单射函数
h(x)=h(y)
A=B
aiAaiB(1in)
xi=1yi=1(1in)
xi=yi(1in)
x=y;
②h是满射函数
A2X(即AX),我们构造x=(x1,x2,,xn)Sn,使得
10
第十页,共85页。