布尔代数

东方135 2019-07-12

展开全文

折叠 编辑本段介绍

是一个集合 A，提供了两个二元运算 <math>\land</math> (逻辑与)、<math>\lor</math> (逻辑或)，一个一元运算 <math>\lnot</math> / ~ (逻辑非)和两个元素 0(逻辑假)和 1(逻辑真)，此外，对于集合 A 的所有元素 a、b 和 c，下列公理成立:

<math> a \lor (b \lor c) = (a \lor b) \lor c </math> <math> a \land (b \land c) = (a \land b) \land c </math> 结合律

<math> a \lor b = b \lor a </math> <math> a \land b = b \land a </math> 交换律

<math> a \lor (a \land b) = a </math> <math> a \land (a \lor b) = a </math> 吸收律

<math> a \lor (b \land c) = (a \lor b) \land (a \lor c) </math> <math> a \land (b \lor c) = (a \land b) \lor (a \land c) </math> 分配律

<math> a \lor \lnot a = 1 </math> <math> a \land \lnot a = 0 </math> 互补律

上面的前三对公理: 结合律、交换律和吸收律，意味着 (A, <math>\land</math>, <math>\lor</math>) 是一个格。所以布尔代数也可以定义为一个分配的有补格。

从这些公理，你可以展示出最小元素 0、最大元素 1 和任何元素 a 的补 ¬a 都是唯一确定的。对于 A 中的所有的 a 和 b，下列恒等式也成立:

<math> a \lor a = a</math> <math> a \land a = a </math> 幂等律

<math> a \lor 0 = a </math> <math> a \land 1 = a </math> 有界律

<math> \lnot 0 = 1 </math> <math> \lnot 1 = 0 </math> 0 和 1 是互补的

<math> \lnot (a \lor b) = \lnot a \land \lnot b</math> <math> \lnot (a \land b) = \lnot a \lor \lnot b</math> de Morgan 定律

<math> \lnot \lnot a = a </math> 对合律

折叠 编辑本段例子

最简单的布尔代数只有两个元素 0 和 1，并通过如下规则定义:

∧ 0 1

0 0 0

1 0 1

∨ 0 1

0 0 1

1 1 1

它应用于逻辑中，解释 0 为假，1 为真，∧ 为与，∨ 为或，¬ 为非。涉及变量和布尔运算的表达式代表了陈述形式，两个这样的表达式可以使用上面的公理证实为等价的，当且仅当对应的陈述形式是逻辑等价的。

两元素的布尔代数也是在电子工程中用于电路设计；这里的 0 和 1 代表数字电路中一个位的两种不同状态，典型的是高和低电压。电路通过包含变量的表达式来描述，两个这种表达式对这些变量的所有的值是等价的，当且仅当对应的电路有相同的输入-输出行为。此外，所有可能的输入-输出行为都可以使用合适的布尔表达式来建摸。

两元素布尔代数在布尔代数的一般理论中也是重要的，因为涉及多个变量的等式是在所有布尔代数中普遍真实的，当且仅当它在两个元素的布尔代数中是真实的(这总是可以通过平凡的蛮力算法证实)。比如证实下列定律(合意(Consensus)定理)在所有布尔代数中是普遍有效的:

(a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)

(a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)

任何给定集合 S 的幂集(子集的集合)形成有两个运算 ∨ := ∪ (并)和 ∧ := ∩ (交)的布尔代数。最小的元素 0 是空集而最大元素 1 是集合 S 自身。

有限的或者 cofinite 的集合 S 的所有子集的集合是布尔代数。

对于任何自然数 n，n 的所有正约数的集合形成一个分配格，如果我们对 a | b 写 a ≤ b。这个格是布尔代数当且仅当 n 是无平方因子的。这个布尔代数的最小的元素 0 是自然数 1；这个布尔代数的最大元素 1 是自然数 n。

布尔代数的另一个例子来自拓扑空间: 如果 X 是一个拓扑空间，它既是开放的又是闭合的，X 的所有子集的搜集形成有两个运算 ∨ := ∪ (并)和 ∧ := ∩ (交)的布尔代数。

如果 R 是一个任意的环，并且我们定义中心幂等元(central idempotent)的集合为

A = { e ∈ R : e2 = e, ex = xe, ∀x ∈ R }

则集合 A 成为有两个运算 e ∨ f := e + f + ef 和 e ∧ f := ef 的布尔代数。

首先是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，有α=α，那么R称为布尔环。令R是布尔环,若定义α∨b=α+b+α·b,α∧b=α·b,α 布尔代数布尔代数

=1+α，则R在所定义的运算下成为一个布尔代数。

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

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

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

令〈Χ,τ〉是一个拓扑空间,Χ的子集S是正规的闭集，当且仅当S的内部的闭包等于S，即布尔代数布尔代数

。若B={S⊆Χ│S是正规的闭集｝，二元运算∨是指集合的并运算，二元运算∧是指经集合的交运算后再取其内部的闭包，即布尔代数布尔代数

,S、T∈B。一元运算*是指经集合的余运算后再取闭包，即布尔代数布尔代数

，则B是一个布尔代数,也称为拓扑空间〈Χ, τ〉的正规闭集代数。类似地，当取B={S⊆Χ│S是正规的开集}。所谓正规的开集S,是指布尔代数

。再定义运算: 布尔代数布尔代数

,S∧T=S∩T；布尔代数布尔代数

，则此时 B也是一个布尔代数,也称为正规开集代数。

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

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

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

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

例如,在逻辑设计中,要考虑取值于B2中的元素的布尔变元 x1,x2,…,xn，以及函数值也在B2内的n个布尔变元的布尔函数ƒ(x1,x2,…,xn)。令x 布尔代数布尔代数

=1-x=x,x∨y=max{x, y},x∧y=min{x, y},于是任一布尔函数可表示成如下的形式: 布尔代数布尔代数

布尔代数布尔代数

或布尔代数布尔代数

, 布尔代数布尔代数

。这种形式称为ƒ的(完全的)析取范式(或完全的合取范式)。根据设计要求可先列出真值表（ƒ的列表表示），由真值表写出ƒ的析取范式（或合取范式）。化简布尔函数的表达形式在实际应用中是特别重要的，因为根据最简表达形式进行设计，不仅在功能（实际效果）上是等效的，而且更有意义的是这种设计简单、经济、可靠，因而寿命也长。化简的方法，大体上从20世纪50年代开始有所谓卡诺图的方法，奎因-麦克鲁斯基方法等等。