布尔代数

布尔代数（英文：Boolean algebra^[1]）是一种类似于布尔环的代数结构，但它是使用与（∧）、或（∨）、非（¬）运算符来定义的。^[14]亨廷顿公理给出了布尔代数的明确定义，同时，它具有等价定义，即由布尔格诱导生成的代数系统。^[9][15]

布尔代数起源于逻辑学的兴起，古希腊逻辑学发展成为了西方传统形式逻辑，为人们提供了认识科学的有效工具。^[16]近代以来，随着自然科学的发展，人们试图将数学方法推广到其他领域。莱布尼茨（Leibniz,G.W.）曾设想创造一种通用语言来表示逻辑学中的一切概念，但是在构设符号逻辑体系方面没有取得成功。^[3]1830年，英国数学家皮考克（G.Peacock）在《代数学》一书中对代数运算的基本法则做了探索，并试图建立一门更普遍的代数。在前人工作的基础上，1847年，英国数学家乔治·布尔（George Boole）出版了著作《逻辑的数学分析，论演绎推理的演算法》，书中他把数学演算应用于逻辑推理，使得逻辑学从传统逻辑发展成为了现代逻辑学。^[4][17]1854年，布尔又出版了书籍，进一步完善了数理逻辑的理论，为布尔代数系统的创立奠定了基础。^[2]1904年，美国数学家亨廷顿（Huntington）在布尔工作的基础上研究了布尔代数的代数结构，并给出了布尔代数的公理化系统。^[3][18]20世纪以来，布尔代数与拓扑学、集合论、环论等分支的联系越来越紧密，理论进一步得到了发展与完善。^[3]

布尔代数有一些经典的模型实例，如命题代数、开关代数和集合代数等。^[12][13]或、与、非为布尔代数系统的三种基本运算，它们满足单调定律^[9]、非单调定律、完备性定理^[8]和对偶原理^[9]等规律。^[7]布尔代数上的关系包括顺序关系、同态与同构、合同关系等。^[10][11]与布尔代数类似的理论是布尔函数，应用布尔代数运算公式可使布尔函数的化简运算更加方便快捷。^[19][20]如果放弃交换性和结合性公理，可得到布尔代数的推广形式——纽曼代数。^[3]此外，在现实世界中，布尔代数具有广泛的应用价值，如在密码学中，基于布尔代数的合式基概念的与或逻辑，可构造一种秘密共享方案，能有效提高秘密信息的安全性。^[5]

布尔代数起源于逻辑学的兴起，公元前5世纪前后，古代中国、古印度和古希腊产生了各具特色的逻辑学说，三大逻辑流派自成体系。后来，古希腊逻辑学发展成为了西方传统形式逻辑，并以正确思维形式及其规律为对象和有效推理的规则为核心内容，为人们提供了认识的有效工具。^[16]近代以来，随着自然科学的发展，人们试图将数学方法推广到其他领域。莱布尼茨（Leibniz,G.W.）曾设想创造一种通用语言，用它能将逻辑学中的一切概念表达出来，但是在构设具有“通用语言”和“通用数学”功能的符号逻辑体系方面没有取得成功。^[3]

数理逻辑的初创时期，代数学的发展为逻辑代数提供了理论基础。1830年，英国数学家皮考克（G.Peacock）在《代数学》一书中对代数运算的基本法则做了探索，并试图建立一门更普遍的代数。随后，格雷戈里（G.F.Gregory）发展了皮考克的代数思想，认为符号规则应该扩展到数和量的领域之外，并且认为符号可以允许非数的解释。后来，德·摩根（De Morgan）在对符号代数和逻辑之间关系的研究工作中指出，需从代数那里去寻找逻辑形式的最寻常用方法。在前人的工作基础上，1847年，英国数学家乔治·布尔（George Boole）出版了著作《逻辑的数学分析，论演绎推理的演算法》，书中他把数学演算应用于逻辑推理，使得逻辑学从传统逻辑发展成为了现代逻辑学。^[4][17]1854年，布尔又出版了书籍，进一步完善了数理逻辑的理论，为布尔代数系统的创立奠定了基础。^[2]

1904年，美国数学家亨廷顿（Huntington）在布尔工作的基础上研究了布尔代数的代数结构，并给出了布尔代数的公理化系统。^[18]1921年，波斯特（Post,E.L.）证明了命题逻辑的完备性定理：每一个二元布尔代数上的恒等式可以由布尔代数的公理导出。在亨廷顿等人的基础上，1938年，克劳德·香农（Claude Shannon）在做电路优化时，把布尔代数应用到电路设计上来，并在论文《继电器与开关电路的符号分析》中证明了可以通过继电器电路来实现布尔代数的逻辑运算，为布尔代数的应用提供了理论基础。^[3][21][22]

20世纪以来，布尔代数与数学其他分支的联系越来越紧密。1936年，斯通（Stone,M.H.）证明了每一个布尔代数同构于一个集合代数，并且若在布尔代数中引入对称差运算，则布尔代数可看做一个环，布尔代数的理论与一种特殊类型的环理论等价。斯通对偶使布尔代数与拓扑学之间也建立了联系。1950年，拉谢娃（Rasiowa,H.）与西科尔斯基（Sikorski,R.）发现了一个关于命题和谓词逻辑完全性的一个简洁证明，并提出了布尔值模型的概念。后来，理论进一步完善，布尔代数有助于理解集合论模型，而元数学方法也为布尔代数复杂定理的证明做出了贡献。^[3]

设有集合，它含有两个不同的元素和，在上有两个代数运算和。对于的任何元素，下列公理成立：^[15][23]

（1）若和，则；

（2）中有元素和，对任何元素，有；

（3）如果和都属于，则；

（4）如果和都属于，则；

（5）如果和都属于，则 ；

（6）若公理（2）中的元素和存在，而且是唯一的，则对任何元素，中有元素，使 ；

（7）中至少有两个元素与，且。

此时，称集合和运算“”和“”确定的代数体系是一个布尔代数，叫做并运算，叫做交运算，叫做的补（元素），求的运算叫做补（非）运算。^[15][23]

格：是一个代数系统，它的两个运算都是二元运算，满足：^[9]

（1）交换律：；

（2）结合律：；

（3）吸收律：；

则称是一个格。^[9]

布尔代数等价定义：若一个格既存在补格又是分配格，则称为布尔格。由布尔格诱导的代数系统称为布尔代数。^[9]

布尔环的定义：设为环。当且仅当对一切，有，则称为布尔环。^[15]

性质：（1）设为布尔环，那么对任何，有；

（2）设为具有幺元素的布尔环。对，规定，那么为布尔代数。^[15]

理想：设是布尔代数的一个非空子集，满足条件：

（1）如果，则；

（2）如果，则；

则称为的理想，如果，则称为的真理想。^[11]

只包含布尔代数的零元的集是布尔代数的理想，称为零理想。布尔代数本身是布尔代数的理想。^[11]

命题：命题是可决定其真假的语句，例如：^[13]

（1）糖是甜的；

（2）小于；

（3）如果今天天晴，那么我就上书店买书。^[13]

上述都是命题，而对于“我的天啊！”、“他姓什么？”、“不许随地吐痰！”等，这类感叹句、疑问句、命令句等虽有意义，但不能判断其真假，就都不是命题。如果一个命题是真的，就说它的真值是；如果一个命题是假的，就说它的真值是。^[13]

命题代数模型：如果任给个命题，通过可组成个不同的命题式，它的论域为，由此可构成值命题代数：。一般地，对无穷多个命题构成的命题代数模型：。因此，命题代数可以看作是由命题构成的命题式为基本对象，以为基本运算所形成的布尔代数理论的一种具体模型。这种模型的特点是命题代数的论域取值只能是。^[12]

开关：在一条电路上行使“接通”和“断开”功能的二端器件，叫做开关，由一些开关联结而成的电路叫做开关电路。开关的状态有“接通”和“断开”两种。如果把开关的断开对应于，接通对应于，那么开关的串联、并联、反相运算就与逻辑代数里的与、或、非运算相对应。^[13]

开关代数模型：开关电路满足逻辑代数里的各条规律，表明开关连同串联、并联、反相运算构成了一个代数系统，称它为开关代数。设表示个开关，它的论域为，由此可构成值开关代数。一般地，开关代数为。^[13]

集合：设为的约数所成的集合（包含）：。^[15]

设，规定“与的最小公倍数”，“与的最大公约数”，，

那么是一个布尔代数。^[15]

集合代数模型：设的质因数个数为，即，其中都是的单质因数。它的全体因数为个，由此构成值集合代数模型。这种集合代数的论域取值只能是。^[12]

或运算又称逻辑加，用符号和表示，两个变量做或运算，即，其意思是变量和中只要有一者取值为，则，否则。^[7][23]

与运算又称逻辑乘，用符号和表示，两个变量做与运算，即，其意思是只有当变量和都取值为，则，否则。^[7][23]

非运算又称逻辑取反，用符号和表示，对一个变量做非运算，即，其意思是若为，则；反之，若为，则。^[7][23]

在真值表中，可用表示假，用表示真。^[23]

蕴含关系式可以由基本逻辑运算得出，符号通常用表示。两个变量的蕴含关系，即，意思是，当且仅当命题真而命题假时，命题才是假的，则定义。命题的值是由变元与的值唯一确定的，故它是命题函数。^[24]

等价关系式可以由基本逻辑运算得出，符号通常用表示。两个变量的等价关系，即，意思是，当且仅当命题和同值时（同为或同为），命题才是真的，则称。命题的合取范式表示为：

。可见“”需由三种基本逻辑运算来确定。^[24]

在布尔代数中，如下基本公式成立：，则

交换律：；^[9]

分配律：；

同一律：；

互补律：；

幂等律：；

零一律：；

吸收律：；

结合律：；

全补律：；

对合律：。^[9]

德·摩根定理：一种变换布尔表达式的简便方法。由于它具有反演特性，即把变量的与运算改成或运算，或运算改成与运算，所以又称反演律，可表述为：^[7]

（1）；

（2）。^[7]

香农定理：德·摩根定理的推广，它可以用在任何复杂函数中，可表述为：^[7]

，即任何函数的反函数（或称补函数），可以通过对该函数的所有变量取反，并将常量换为，换为，运算符换为，换为而得到。^[7]

任一逻辑函数都可由逻辑变量，经基本逻辑运算或、与、非而得到。^[8]

设是对于任意布尔代数都成立的命题，若将中的换为，换为，换为，换为，换为则得到的对偶命题，于是也是对于任意布尔代数都成立的命题。^[9]

布尔代数上的顺序关系：设是布尔代数，对于，如果成立，则称。^[10]

定义中的条件具有三种等价形式，即，，。^[10]

性质：对于的元素，下列关系成立：

（1)；

（2)；

（3）对任何，有；

（4）若，且，则。一般地，若，则；

（5）若，且，则。一般地，若，则；

（6）若，则。^[10]

定义：设和是两个布尔代数。如果映射满足下列条件：对任何，

（1)(并的象等于象的并）；

（2)(交的象等于象的交）；

（3)(补的象等于象的补）；

则称为布尔同态，这两个布尔代数是同态的。如果是到上的同态映射，则称为布尔同构，这两个布尔代数具有同构关系。^[10]

有限布尔代数的表示定理：设是有限布尔代数的全部原子集合，那么与布尔同构。^[10]

无限布尔代数同构的相关定理：一个无限布尔代数同构于某个集合的幂集的子族构成的布尔代数。^[25]

定义：布尔代数上的等价关系称为上的合同关系，如果满足下列条件：^[11]

（1）对于任意，如果，则；

（2）对于任意，如果，则；

（3）对于任意，如果，则。换言之，布尔代数上的合同关系是保持所有布尔运算的等价关系。^[11]

性质：设为布尔代数上相应于理想的合同关系，则

（1）对任意，有；

（2）对任意，有；

（3）对任意，有。

因此，在进行布尔运算时，同类的元互相代换，不影响运算结果所在的类。^[11]

设偶数集记作，把奇数集记作。考虑集合，规定，，则是一个域。令，则到的映射是函数，称为元布尔函数。^[19]

例如：（1）一元布尔函数，通常称为补函数。由定义有；

（2）二元布尔函数与：，函数叫做或函数，函数叫做与函数。^[26]

布尔表达式：由布尔变量和或、与、非三种运算符所构成的式子，是一种用公式表示布尔函数的方法。^[7]

异或函数：当两个变量和取值相同时，函数取值为；否则，函数取值为，称为异或函数。通常，异或运算用符号来表示，用布尔表达式表示为：。^[7]

同或函数：当两个变量和取值相同时，函数取值为；否则，函数取值为，称为同或函数。通常，同或运算用符号来表示，用布尔表达式表示为：。^[7]

真值表：布尔函数可用列表法构成一个真值表来进行表示。一个元布尔函数的真值表可分为两列，左边一列的最顶行为，其下按数由小到大的顺序列出自变量的全部可能取值，右边一列的最顶行为，其下列出对应于自变量左边的值时函数的对应值。^[26]

例如，下表为三元布尔函数的真值表。^[26]

卡诺图：卡诺图是由表示逻辑变量的所有可能取值组合的小方格所构成的图形，如下图所示，表示两变量和三变量的卡诺图。^[7]

卡诺图可以方便地表示一个函数，在使函数值为的变量取值组合所对应的小方格上标记，便得该函数的卡诺图。例如，对于异或函数，可以用下图所示的卡诺图来表示。^[7]

卡诺图可以看成是真值表的重新排列，真值表的每一行用一个小方格来表示。当变量为两个时，真值表有行，相应的卡诺图有个方格；当变量为个时，卡诺图有个方格。卡诺图的方格排列方式比真值表更紧凑，便于进行函数的简化。^[7]

公式化简法：利用布尔代数的运算公式，可以化简布尔函数的复杂运算，下列公式是化简积的和型时最常用的公式：^[20]

（1）；

（2）；

（3）；

（4）。^[20]

例如：化简。^[20]

解：由（1），项与可以合并，合并后得到。

由于包含了项，因而由（2），项与项是多余的，消去多余的项得到。

由（3），，于是。

由（4），由于的项与分别包含了原变量与反变量，而余下的因子均为项的因子，因此项是多余的，消去多余的项后得到。^[20]

纽曼代数是推广的布尔代数，它放弃了交换性与结合性的公理。在纽曼代数中，有一个关于两个运算与封闭的集。^[3]

定义：设为代数系统，其运算性质如下：^[27]

（1）；

（2）存在元素，使对所有元素有；

（3）存在元素，使对所有元素有；

（4）对每一个元素至少有一个补元素与之对应，即；

则称为纽曼代数。^[27]

当认为纽曼代数的加法、乘法相当于格定义的代数系统中的加法、乘法运算时，偶元素就构成了一个以为单位元素的分配格，在此格中为的补元素。因为，且的补元为，于是偶元素构成了有补分配格，即布尔代数。^[27]

门限秘密共享方案是基于门限访问结构上的秘密共享方案，传统的方案大都使用比较复杂且抽象的数学理论为基础。基于布尔代数的与或逻辑，引入合式基概念，可构造一种新的秘密共享方案，通过简单的逻辑操作实现秘密共享，具有灵活的扩展能力和自适应能力，减少计算量的同时可便于计算机软件编程和硬件固化。该方案还可以与经典的加密方法紧密结合，具有抗剪切攻击能力，最终达到提高安全性的目的。^[5]

在计算机风险危害中，木马相比于其他恶意代码，具有明显的目的性、针对性以及系统的协作性，传统的特征码的识别和基于一维应用程序编程接口（API）序列的识别技术对木马识别的效果有限。基于布尔代数的木马行为模型，从一般木马行为特点出发，将木马的行为点对应为代数系统中的元素，通过格和布尔代数的偏序关系量化出木马行为的危险级别，为木马行为监测和判别提供了理论的支持和有效的实施方法。^[6]

在数字电子技术中，布尔函数是可以通过数字电路来实现的，常用的门电路根据功能分为与门、或门、非门、与非门、或非门等几种，与门、或门、非门与布尔代数的运算相对应。在实际应用中，复杂的问题一般都可用与、或、非的组合来表示。例如，点灯问题可描述为：三人控制一个电灯，要求任何一个开关状态的改变都使电灯的状态改变。首先可列出三变量的真值表，画出对应的卡诺图，再得出布尔函数的最简积之和的形式，最后画出逻辑图，选择相应的集成电路就可以解决此问题。^[28]

在古代东方文化中，《周易》六十四卦的卦形是由八卦构建而得的，因此八卦是六十四卦的基础。八卦就是由阳爻“——”和阴爻“— —”两种符号（为方便起见，通常用数字表示阳爻，用数字表示阴爻），按三个一组而构成的八组符号的集合，例如，乾、坤等。易图可通过二进制数进行表达，而布尔代数逻辑运算的运算数也只有2个。从离散数学格论的角度出发，通过对先天易图进行重构，可发现先天易图与布尔代数是等价的。^[22]