布尔代数

首先是G.布尔为了研究思维规律逻辑学、数理逻辑)于1847年和1854年提出的。它作为一种特殊的格则是J.W.R.戴德金之后的事情。所谓一个布尔代数,是指一个有序的四元组〈B,∨,∧,* 〉,其中B是一个非空的集合,∨与∧ 是定义在B上的两个二元运算,*是定义在B上的一个一元运算, 并且它们满足以下条件:A1.α∨b=b∨α,α∧b=b∧α;A2.(α∨b)∨с=α∨(b∨с), (α∧b)∧с=α∧(b∧с); A3.(α∧b)∨b=b, (α∨b)∧b=b; A4.α∧(b∨с) = (α∧b)∨(α∧с),α∨(b∧с)=(α∨b)∧(α∨с);A5.(α∧α)∨b=b,(α∨α)∧b=b,对于任意的α、b、с∈B均成立。或者,布尔代数定义为具有最大元和最小元的有余(有补)的分配格。

B2={0,1}是由两个元素0与1所组成的集合。它的两个二元运算和一个一元运算定义如下:0∨0=0,0∨1=1∨0=1∨1=1;0∧0=0∧1=1∧0=0,1∧1=1;0=1,1=0。可以验证,B2是一个布尔代数。

B={1,2,3,5,6,10,15,30}是30的正因子的集合。规定∨是取它们的最小公倍数,∧是取它们的最大公因数:*是:1=30,2=15,3=10,5=6,6=5, 10=3,15=2,30=1,容易验证B对于所定义的运算成为一布尔代数。

如果一个环R=〈R,+,·〉具有单位元1,并且对任意的α∈R,有α2=α,那么R称为布尔环。令R是布尔环,若定义α∨b=α+b+α·b,α∧b=α·b,α=1+α,则R在所定义的运算下成为一个布尔代数。

R是由所有的实数组成的集合。由单元集和区间的有限并所组成的集合B,在集合的并(∪)、交(∩)、余(C)运算之下是一个布尔代数。所谓单元集,是指仅由一个实数所组成的集合。区间可以是有界的或无界的,闭的或开的或半开(闭)的。

Χ是一个固定的集合。Χ的所有子集组成的集合称为Χ的幂集,记为P(Χ)={SSΧ}。设BP(Χ)的子集,并且{═,Χ}BP(Χ)。如果B集合论的并(∪)、交(∩)、余(C)有限次运算下是封闭的,那么这样的B在把有限次并、交、余作为∨、∧、*运算时,是一个布尔代数。这种布尔代数,常常称为集域(集场)。特殊地,取B=B2={═,Χ},B=P(Χ),B={SP(Χ)│S为有限集或有限集的余集},……,均为集域。当Χ={α1,α2,…,αn}是有限集时,则P(Χ)={SSΧ}={{αi1,αi2,…,αik}│i1,i2,…,ik是1,2,…,n中取k个的组合,0≤kn}=2X=2n也是一个集域。它是由有限个元素所组成的布尔代数(有限布尔代数)。

令〈Χ,τ〉是一个拓扑空间,τ是 X上的一个拓扑,B={SΧS 既是开集,同时又是闭集}。在集合论的并、交、余运算下B是一个布尔代数,并称之为闭开代数。若取B={SΧS的边界是无处稠密的},则此时B也是一个布尔代数。

令〈Χ,τ〉是一个拓扑空间,Χ的子集S是正规的闭集,当且仅当S的内部的闭包等于S,即。若B={SΧS是正规的闭集},二元运算∨是指集合的并运算,二元运算∧是指经集合的交运算后再取其内部的闭包,即STB。一元运算*是指经集合的余运算后再取闭包,即,则B是一个布尔代数,也称为拓扑空间 〈Χ, τ〉的正规闭集代数。类似地,当取B={SΧS是正规的开集}。所谓正规的开集S,是指。再定义运算:ST=ST,则此时 B也是一个布尔代数,也称为正规开集代数。

在概率论中,设B={SS是随机事件},即所有随机事件的全体。不可能事件及必然事件均视作随机事件。这样的B在逻辑联结词"或"(可得兼的"或")、“与”、“否定”运算之下是一个布尔代数。

在数理逻辑中,基于二值逻辑的一个形式理论的所有公式,在逻辑联结词“析取”、“合取”、“否定”运算下,是一个布尔代数,也称之为林登鲍姆-塔尔斯基代数。

布尔代数到了20世纪30~40年代才又有了新的进展,大约在1935年,M.H.斯通首先指出布尔代数与环之间有明确的联系,他还得到了现在所谓的斯通表示定理:任意一个布尔代数一定同构于某个集上的一个集域;任意一个布尔代数也一定同构于某个拓扑空间的闭开代数等,这使布尔代数在理论上有了一定的发展。布尔代数在代数学(代数结构)、逻辑演算、集合论、拓扑空间理论、测度论、概率论、泛函分析等数学分支中均有应用;1967年后,在数理逻辑的分支之一的公理化集合论以及模型论的理论研究中也起着一定的作用。

近几十年来,布尔代数在自动化技术、电子计算机的逻辑设计等等工程技术领域中有重要的应用。

例如,在逻辑设计中,要考虑取值于B2中的元素的布尔变元 x1x2,…,xn,以及函数值也在B2内的n个布尔变元的布尔函数ƒ(x1x2,…,xn)。令x=1-x=x-1xy=max{xy},xy=min{xy},于是任一布尔函数可表示成如下的形式:。这种形式称为ƒ的(完全的)析取范式(或完全的合取范式)。根据设计要求可先列出真值表(ƒ的列表表示),由真值表写出ƒ的析取范式(或合取范式)。化简布尔函数的表达形式在实际应用中是特别重要的,因为根据最简表达形式进行设计,不仅在功能(实际效果)上是等效的,而且更有意义的是这种设计简单、经济、可靠,因而寿命也长。化简的方法,大体上从20世纪50年代开始有所谓卡诺图的方法,奎因-麦克鲁斯基方法等等。

参考文章