布尔代数

第五章 布尔代数

布尔代数最初是作为对逻辑思维法则的研究出现的。英国哲学家George Boole于1847年的论文“逻辑之数学分析”及“思维法则之研究”中引入了布尔代数。 本世纪30年代C.E. Shannon发表了“继电器和开关电路的符号分析”一文，为布尔代数在工艺技术中的应用开创了道路。 50年代苏联科学家把布尔代数发展成为接点网络实用中的通用理论，从而使布尔代数成为计算机科学中的重要基础理论。

从逻辑上讲，布尔代数是一个命题演算系统; 从抽象代数观点讲，布尔代数是一个代数系统; 从集合的观点讲，它是一个集合代数;

从工程技术的观点讲，布尔代数是电路代数，电子线路的设计离不开它;

5.1 布尔代数的基本定义和性质

定义5.1.1 给定一个具有三个运算的代数结构，其中，⊕，⊙是S上的二元运算，′是S上的一元运算，0，1∈S。 若对于?x，y，z∈S

(1) x⊕y=y⊕x，x⊙y=y⊙x (交换律) (2) (3) (4) (5)

x⊕(y⊕z)=(x⊕y)⊕z，x⊙(y⊙z)=(x⊙y)⊙z(结合律) x⊕(y⊙z)=(x⊕y)⊙(x⊕z)， x⊕0=x，x⊙1=x (同一律) x⊕x′=1，x⊙x′=0(有补律)

x⊙(y⊕z)=(x⊙y)⊕(x⊙z)(分配律)

则称称为布尔代数(Boolean Algebra)，⊕，⊙，′分别称为它的并(布尔和)，交(布尔积)和补运算，0和1分别称为它的零

1

元和么元。一个布尔代数通常记为。 例5.1.1 二值（元）布尔代数，其中B={0，1}

1⊕1=1⊕0=0⊕1=1，0⊕0=0，1=0′ 1⊙1=1，1⊙0=0⊙1=0⊙0=0，0=1′ 例5.1.2 集合代数 例5.1.3* 命题代数

定理5.1.1 在一个布尔代数中，0和1 都是唯一的; 定理5.1.2 在一个布尔代数中，任一元素的补元是唯一的; 证明(利用同一律，有补律和分配律)

定理5.1.3 在一个布尔代数中中，则

对?x∈S，(x′) ′=x

定理5.1.4 条件同上，则0′=1，1′=0;

定理5.1.5 条件同上，则对?x∈S，x⊕x=x，x⊙x=x(幂等律) 证明(利用同一律，有补律和分配律)

定理5.1.6 条件同上，则对?x∈S，x⊕1=1，x⊙0=0(零一律) 证明(同定理5.1.5)

定理5.1.7 条件同上，则对?x，y∈S，x⊕(x⊙y)=x， x⊙(x⊕y)=x(吸收律) 证明(同定理5.1.5)

定理5.1.8 条件同上，则对?x，y∈S，(x⊙y)′=x′⊕y′， (x⊕y) ′=x′⊙y′(De morgan律) 证明(同定理5.1.5)

2

定理5.1.9 条件同上，若对x，y，z∈S，x⊙y=x⊙z，x⊕y=x⊕z， 则y=z (消去律)

证明(利用集合中类似证明方法)

定理5.1.10 条件同上，则对?x，y∈S，x⊙y=x?x⊕y=y 证明(利用吸收律)

对偶原理: 在布尔代数中，若P是某个已经得到证明的定理，将定理中的条件和结论 (1) 5.2 格

定理5.2.1 设为一个布尔代数，则集合

≤={| x⊙y=x∧x∈S∧y∈S} 称为S上的偏序关系。 注 x≤y? x⊕y=y? x⊙y=x

定理5.2.2 设为一个布尔代数，以及S上的偏序关系 ≤，则对? x，y，z∈S (1) (2) (3) (4) (5)

x⊙y≤x，x⊙y≤y; x≤x⊕y，y≤x⊕y;

x≤z∧y≤z => x⊕y≤z; x≤y∧x≤z => x≤y⊙z; x≤y ? x⊙y′=0; 0≤x，x≤1;

⊕与⊙互换; (2) 0与1 互换

则由此而得的新定理仍然成立;

3

证明(利用≤定义及吸收律)

定义5.2.2 给定偏序集，若其中S的任两个元素组成的集合均有上确界(最小上界)和下确界(最大下界)，则称此偏序集为一个格(Lattice)。

有一些偏序集不是格:

例5.2.1 设S={0，1，a，，b，c，d}， ≤={<0，0>，<1，1>，，，，，<0，a>，<0，b>，<0，c>， <0，d>，<0，1>，，，，，，，，}则{a，b}无上确界，{c，d}无下确界;

定义5.2.3 设是一个格，在S上定义两个二元运算: 对?x，y∈S， x⊙y=GLB(x，y)， x⊕y=LUB(x，y)

(其中GLB(x，y)和LUB(x，y)分别为集合{x，y}在偏序集中的下确界和上确界)。格记为; 推论 运算⊕，⊙分别满足交换律和结合律;

定义5.2.4 设是一个格，若⊕，⊙相互满足分配律，则称之为一个分配格(Distributive Lattice)。

定义5.2.5 设是一个格，若S中有最大元和最小元，则称之为有界格(Bounded Lattice)。且分别用0和1表示一个有界格中的最小元和最大元;

注 在一个有界格中，对?x∈S，0≤x≤1;

定义5.2.6 设是一个有界格，x∈S，存在y∈S

使 x⊕y=1， x⊙y=0

4

则称x和y互为补元(Complement)

显然0和1互为补元;

定义5.2.7 每个元素都有补元的有界格称为有补格(Complemented Lattice)。

定义5.2.8 任一个有补分配格是一个布尔代数;

将x的补元记为x′， ′称为有补格的补运算;

5.4 布尔代数的原子表示

定义5.4.1 设为布尔代数，a是S中的一个非零元。若对?x∈S，有a⊙x=a或a⊙x=0，则称a是此布尔代数的一个原子(Atom);

注 1) 若a是布尔代数的一个原子，则对?x∈S，有a≤x或a⊙x=0;

2)若a为的原子且x≤a，则x=a或x=0; 例5.4.1 1)设S={a，b，…，c}，则{a}，{b}，…，{c}是布尔代数的所有原子;

2)设S是一个无限集，则对?a∈S，{a}是此布尔代数的一个原子; 定理5.4.1 若a和b为布尔代数的两个原子，且a⊙b≠0，则a=b;

(其逆否命题:若a，b为布尔代数的两个不同原子，则a⊙b=0)

定理5.4.2 若为有限布尔代数，x∈S，x≠0，则存在原子a∈S，使a≤x。

5