查看“︁布尔代数”︁的源代码

{{About|一種代数结构|相关的數學分支|邏輯代數}}
{{Merge from|真值|discuss=Talk:布尔代数#请求与真值合并|time=2020-06-30T07:24:41+00:00}}
{{No footnotes |time=2019-11-5}}
{{NoteTA
|G1 = IT
|G2 = Math
|1 = zh-hans:余; zh-hant:餘;
}}
'''布尔代数'''（{{lang-en|Boolean algebra}}）在[[抽象代数]]中是指捕获了[[集合 (数学)|集合]]运算和[[逻辑]]运算二者的根本性质的一个[[代数结构]]（就是说一组元素和服从定义的[[公理]]的在这些元素上运算）。特别是，它处理[[集合 (数学)|集合]]运算[[交集]]、[[并集]]、[[补集]]；和[[逻辑]]运算[[逻辑合取|与]]、[[逻辑析取|或]]、[[逻辑否定|非]]。

[[File:Hasse diagram of powerset of 3.svg|thumb|250px|子集的布尔格的[[哈斯圖]]]]
例如，逻辑断言[[命题|陈述]]''a''和它的否定¬''a''不能都同时为真，
:<math>a\land(\lnot a) = \mbox{FALSE}</math>，
相似于集合论断言子集''A''和它的补集''A''<sup>''C''</sup>有空交集，
:<math>A\cap(A^C) = \varnothing</math>。

因为真值可以在[[逻辑电路]]中表示为[[二进制]]数或电平，这种相似性同样扩展到它们，所以布尔代数在[[电子工程]]和[[计算机科学]]中同在[[数理逻辑]]中一样有很多实践应用。在电子工程领域专门化了的布尔代数也叫做[[逻辑代数]]，在计算机科学领域专门化了布尔代数也叫做[[布尔逻辑]]。

布尔代数也叫做'''布尔格'''。关联于[[格 (数学)|格]]（特殊的[[偏序集合]]）是在集合[[子集|包含]]''A'' ⊆ ''B''和[[格 (数学)|次序]]  ''a'' ≤ ''b''之间的相似所预示的。考虑{''x'',''y'',''z''}的所有子集按照包含排序的格。这个布尔格是偏序集合，在其中{''x''}  ≤ {''x'',''y''}。任何两个格的元素，比如''p'' = {''x'',''y''}和''q'' = {''y'',''z''}，都有一个最小上界，这里是{''x'',''y'',''z''}，和一个最大下界，这里是{''y''}。这预示了最小上界（并或上确界）被表示为同逻辑OR一样的符号''p''∨''q''；而最大下界（交或下确界）被表示为同逻辑AND一样的符号''p''∧''q''。

这种格释义有助于一般化为[[海廷代数]]，它是免除要么一个陈述要么它的否定必须为真的限制的布尔代数。海廷代数对应于[[直觉逻辑]]，而布尔代数对应于[[经典逻辑]]。

布尔代数又譯為'''-{zh-hans:布林代数; zh-hant:布爾代數;}-'''，然而布尔代数得名于[[乔治·布尔]]，他是[[爱尔兰]][[科克 (爱尔兰)|科克]]的皇后学院的英国数学家。布-{}-林（boolean）在英文中的意思是「布-{}-尔的」，這是為了表彰布-{}-尔的貢獻，而「布-{}-林」只是一種音譯。

==历史==

术语“布尔代数”得名于[[乔治·布尔]]（1815–1864），他是自学成材的英国数学家。他最初在1847年出版的一个小册子《逻辑的数学分析》中介入了[[代数逻辑]]系统，用来响应在[[奥古斯都·德·摩根]]和[[Sir William Hamilton, 9th Baronet|William Hamilton]]之间的公开论战，后来又出现在1854年出版的更充实的书《思维规律》中。布尔的公式化在一些重要方面不同于上述描述。例如，布尔的合取和析取不是一对对偶的运算。布尔代数出现在1860年代[[威廉姆·斯坦利·杰文斯]]和[[查尔斯·皮尔士]]的论文中。到了1890年[[Ernst Schröder]]写的《Vorlesungen》，我们才有了布尔代数和[[分配格]]的首次系统表述。首次用英语写的对布尔代数的广泛处置是[[阿弗烈·诺夫·怀海德]]在1898年的《泛代数》。在现代公理化意义上的作为公理化代数结构的布尔代数开始于[[Edward Vermilye Huntington]] 1904年的论文。布尔代数随着[[Marshall Stone]]在1930年代的工作和[[Garrett Birkhoff]]在1940年的《格理论》而进入了严肃数学时期。在1960年代，[[Paul Cohen]]、[[Dana Scott]]和其他人使用布尔代数的分支也就是[[力迫 (数学)|力迫]]和[[布尔值模型]]，深入发现了[[数理逻辑]]和[[公理化集合论]]中的新成果。

== 形式定义 ==

'''布尔代数'''是一个[[集合 (数学)|集合]]A，其上定义了以下结构：
*二元运算∧:A×A→A。
*二元运算∨:A×A→A。
*一元运算 ':A→A。
*零元运算（常数）0和1。
这些运算满足以下条件：∀a，b，c∈A，

{| class="wikitable" cellpadding=5
|<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,∧,∨)是一个[[格 (数学)|格]]。所以布尔代数也可以定义为一个[[补运算|有补]][[分配格]]。

从这些[[公理]]，你可以展示出最小元素0、最大元素1和任何元素a的补a'都是唯一确定的。

另外，∀a,b∈A，下列[[恒等式]]也成立：

{| class="wikitable" cellpadding=5
| <math> a \lor a = a</math>
|<math> a \land a = a </math>
| [[幂等律]]
|-
|<math> a \lor 0 = a </math>
|<math> a \land 1 = a </math>
| rowspan=2 | [[有界律]]
|-
|<math> a \lor 1 = 1 </math>
|<math> a \land 0 = 0 </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>
| [[德·摩根定律]]
|-
| <math> \lnot \lnot a = a </math>
|
| [[对合律]]
|}

===其它运算===
在上述基本定义基础上，布尔代数中常见的还有以下的运算：
*二元运算-: A×A→A，定义为：a-b = a∧b'；
*二元运算+或Δ: A×A→A，定义为：a+b = (a-b)∨(b-a)；
*二元运算→: A×A→A，定义为：a→b = (a-b)'；
*二元运算↔: A×A→A，定义为：a↔b = (a→b)∧(b→a)；
*二元运算|或↑: A×A→A，定义为：a|b = (a∧b)'。
*二元运算⊕或↓: A×A→A，定义为：a⊕b = a'∧b'

注意：-和→，+和↔是对偶的。即a→b = (a-b)'，a↔b=(a+b)'。

===总结===
布尔代数的各种运算同时也被应用于[[集合论]]和[[逻辑学]]，在不同的上下文有不同的名称。具体的符号和名称如下：
{{expert-subject|time=2015-11-02T19:31:10+00:00}}
{| class="wikitable"
! scope="col" | [[逻辑运算符|运算符号]]
! scope="col" | 布尔代数
! scope="col" | [[集合论]]
! scope="col" | [[逻辑学]]
! scope="col" | [[邏輯閘]]
! scope="col" | [[溫氏圖]]
|-
| 0或<math>\bot</math> || 底 || [[空集]] || [[恆真式|偽]]  || [[數字信號|低電位]] || [[File:Venn0000.svg|center|60px]]
|-
| 1或<math>\top</math> || 顶 || [[全集]] || [[恆真式|真]] || [[數字信號|高電位]] || [[File:Venn1111.svg|center|60px]]
|-
| ¬或~或'或<sup>c</sup> ||  || [[补集#绝对补集|补集]] || [[逻辑非|非]] || [[反相器]] || [[File:Venn1010.svg|center|60px]]
|-
| ∧或∩ || 下确界 || [[交集]] || [[逻辑与|与]] || [[及閘]] || [[File:Venn0001.svg|center|60px]]
|-
| ∨或∪ || 上确界 || [[聯集]] || [[逻辑或|或]] || [[或閘]] || [[File:Venn0111.svg|center|60px]]
|-
| <math>\not\leftarrow</math>或<math>\not\subset</math> || 补 || [[补集#相对补集|相对补集]] ||  ||  || [[File:Venn0010.svg|center|60px]]
|-
| -或<math>\not\rightarrow</math> || 减 || [[差集]] || [[实质非蕴涵]] || [[蘊含閘#蘊含非閘|蘊含非閘]] || [[File:Venn0100.svg|center|60px]]
|-
| ⊕或Δ || [[对称差]] || [[对称差]] || [[逻辑异或|异或]] || [[互斥或閘|異或閘]] || [[File:Venn0110.svg|center|60px]]
|-
| → || 条件 ||  || [[实质条件|条件]] || [[蘊含閘]] || [[File:Venn1011.svg|center|60px]]
|-
| ↔ || 双向条件 ||  || [[当且仅当|双条件]] || [[反互斥或閘|同或閘]] || [[File:Venn1001.svg|center|60px]]
|-
|| |或↑ || [[谢费尔竖线]] ||  || [[逻辑与非|与非]] || [[反及閘]] || [[File:Venn1110.svg|center|60px]]
|-
|| ↓ || 皮尔斯箭头 ||  || [[逻辑或非|或非]] || [[反或閘]] || [[File:Venn1000.svg|center|60px]]
|}

== 例子 ==

*最简单的布尔代数只有两个元素0和1，并通过如下规则定义:
{|
|-
| width="70" |
|{{乘法表
| table class = class="wikitable" style="text-align:center;"
| first number list = 0,1
| calculate title = {{unicode|∧}}
| expr = {{{left}}} ∧ {{{right}}}
| number css = css
| number class = boolean
}}
|
| width="30" |
|
|{{乘法表
| table class = class="wikitable" style="text-align:center;"
| first number list = 0,1
| calculate title = {{unicode|∨}}
| expr = {{{left}}} ∨ {{{right}}}
| number css = css
| number class = boolean
}}
|
| width="40" |
|
{{乘法表
| table class = class="wikitable" style="text-align:center;"
| first number list = ¬a
| first number show = ¬a
| second number list = 0, 1
| expr = not {{{right}}}
| calculate title = a
| number css = css
| number class = boolean
}}
|}
:*它应用于[[逻辑]]中，解释0为“偽”，1为“真”，∧为“与”，∨为“或”，¬为“非”。涉及变量和布尔运算的表达式代表了陈述形式，两个这样的表达式可以使用上面的公理证实为等价的，当且仅当对应的陈述形式是[[逻辑等价]]的。

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

:* [[两元素布尔代数]]在布尔代数的一般理论中也是重要的，因为涉及多个变量的等式是在所有布尔代数中普遍为真，当且仅当它在两个元素的布尔代数中为真（这总是可以通过平凡的[[穷举法]]算法证实）。比如证实下列定律（“合意定理”）在所有布尔代数中是普遍有效的:
:** (''a'' ∨ ''b'') ∧ (¬''a'' ∨ ''c'') ∧ (''b'' ∨ ''c'') ≡ (''a'' ∨ ''b'') ∧ (¬''a'' ∨ ''c'')
:** (''a'' ∧ ''b'') ∨ (¬''a'' ∧ ''c'') ∨ (''b'' ∧ ''c'') ≡ (''a'' ∧ ''b'') ∨ (¬''a'' ∧ ''c'')

*任何给定集合''S''的[[幂集]]（子集的集合）形成有两个运算∨ := ∪ (并)和∧ := ∩ (交)的布尔代数。最小的元素0是[[空集]]而最大元素1是集合''S''自身。
*有限的或[[余有限]]的集合''S''的所有子集的集合是布尔代数。
*对于任何[[自然数]]''n''，''n''的所有正[[约数]]的集合形成一个[[分配格]]，如果我们对''a'' | ''b''写''a'' ≤ ''b''。这个格是布尔代数当且仅当''n''是[[无平方数因数的数]]。这个布尔代数的最小的元素0是自然数1；这个布尔代数的最大元素1是自然数''n''。
*布尔代数的另一个例子来自[[拓扑空间]]:如果''X''是一个拓扑空间，它既是开放的又是闭合的，''X''的所有子集的搜集形成有两个运算∨ := ∪ (并)和∧ := ∩ (交)的布尔代数。
*如果''R''是一个任意的环，并且我们定义“中心幂等元”（central idempotent）的集合为<br> ''A'' = { ''e'' ∈ ''R'' : ''e''<sup>2</sup> = ''e'', ''ex'' = ''xe'', ∀''x'' ∈ ''R'' } <br>则集合''A''成为有两个运算''e'' ∨ ''f'' := ''e'' + ''f'' + ''ef''和''e'' ∧ ''f'' := ''ef''的布尔代数。

==原型布尔代数==

在''k''元素集合''X''上有''k''<sup>''k''<span><sup>''n''</sup></span></sup>个''n''元运算''f'': ''X''<sup>''n''</sup>→''X''，因此在{0,1}上有2<sup>2<span><sup>''n''</sup></span></sup>个''n''元运算。所以得出所有布尔代数，不论大小都两个常量或“零元”运算，四个一元运算，16个二元运算，256个三元运算，以此类推，它们叫做给定布尔代数的'''[[布尔运算]]'''。只有一个例外就是一个元素的布尔代数，它叫做退化的或平凡的（被一些早期作者禁用），布尔代数的所有运算可以被证明是独特的。（在退化情况下，给定元数的所有运算都是同样的运算因为对所有输入都返回同样结果。）

在{0,1}上的运算可以用[[真值表]]展出，选取0和1为真值'''假'''和'''真'''。它们可以按统一和不依赖应用的方式列出，允许我们命名或至少单独列出它们。这些名字对布尔运算提供方便的简写。''n''元运算的名字是2<sup>''n''</sup>位的二进制数。有2<sup>2<span><sup>''n''</sup></span></sup>个这种运算，你不能得到更简明的命名法了!

下面展示元数从0到2的所有运算的这种格局和关联的名字。

{|
|+ '''直到2元的布尔运算的真值表'''
|- valign="top"
|
{| class="wikitable" style="text-align:center;border:2px"
|+ 常量
| style="width:2em" | <sup>0</sup>''f''<sub>0</sub>
| style="width:2em" | <sup>0</sup>''f''<sub>1</sub>
|-
| 0 || 1
|}
|
{| class="wikitable" style="text-align:center;border:2px"
|+ 一元运算
|-
! style="width:2em" | ''x''<sub>0</sub>
| style="width:1px" |
| style="width:2em" | <sup>1</sup>''f''<sub>0</sub>
| style="width:2em" | <sup>1</sup>''f''<sub>1</sub>
| style="width:2em" | <sup>1</sup>''f''<sub>2</sub>
| style="width:2em" | <sup>1</sup>''f''<sub>3</sub>
|-
| 0 || || 0 || 1 || 0 || 1
|-
| 1 || || 0 || 0 || 1 || 1
|}
|-
| colspan="5" |
{| class="wikitable" style="text-align:center;border:2px"
|+ 二元运算
|-
! style="width:2em" | ''x''<sub>0</sub>
! style="width:2em" | ''x''<sub>1</sub>
| style="width:1px" |
| style="width:2em" | <sup>2</sup>''f''<sub>0</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>1</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>2</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>3</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>4</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>5</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>6</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>7</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>8</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>9</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>10</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>11</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>12</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>13</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>14</sub>
| style="width:2em" | <sup>2</sup>''f''<sub>15</sub>
|-
| 0 || 0 || || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1 || 0 || 1
|-
| 1 || 0 || || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
| 0 || 1 || || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1 || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1
|-
| 1 || 1 || || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 1 || 1 || 1 || 1 || 1 || 1 || 1 || 1
|}
|}

这些表格继续到更高元数上，对''n''元有2<sup>''n''</sup>行，每个行给出''n''个变量''x''<sub>0</sub>,…''x''<sub>''n''−1</sub>的一个求值或绑定，而每列都有表头<sup>''n''</sup>''f''<sub>''i''</sub>，它们给出第''i''个''n''元运算<sup>''n''</sup>''f''<sub>''i''</sub>(''x''<sub>0</sub>,…,''x''<sub>''n''−1</sub>)在这个求值下的值。运算包括变量本身，例如<sup>1</sup>''f''<sub>2</sub>是''x''<sub>0</sub>而<sup>2</sup>''f''<sub>10</sub>是''x''<sub>0</sub> (作为它的一元对应者的两个复件)而<sup>2</sup>''f''<sub>12</sub>是''x''<sub>1</sub> (没有一元对应者)。否定或补¬''x''<sub>0</sub>出现为<sup>1</sup>''f''<sub>1</sub>再次出现为<sup>2</sup>''f''<sub>5</sub>，连同<sup>2</sup>''f''<sub>3</sub> (¬''x''<sub>1</sub>在1元时没有出现)，析取或并''x''<sub>0</sub>∨''x''<sub>1</sub>出现为<sup>2</sup>''f''<sub>14</sub>，合取或交''x''<sub>0</sub>∧''x''<sub>1</sub>出现为<sup>2</sup>''f''<sub>8</sub>，蕴涵''x''<sub>0</sub>→''x''<sub>1</sub>出现为<sup>2</sup>''f''<sub>13</sub>，异或或对称差''x''<sub>0</sub>⊕''x''<sub>1</sub>出现为<sup>2</sup>''f''<sub>6</sub>，差集''x''<sub>0</sub>−''x''<sub>1</sub>出现为<sup>2</sup>''f''<sub>2</sub>等等。对布尔函数的其他命名或表示可参见[[零阶逻辑]]。

作为关于它的形式而非内容的次要详情，一个代数的运算传统上组织为一个列表。我们这里通过在{0,1}上有限运算索引了布尔代数的运算，上述真值表表示的排序首先按元数，其次为每个元数运算的列出表格。给定元数的列表次序是如下两个规则确定的。

:(i)表格左半部分的第''i''行是''i''的二进制表示，最低有效位或第0位在最左（“小端”次序，最初由[[艾伦·图灵]]提议，所以可不无合理的叫做图灵序）。

:(ii)表格的右半部分的第''j''列是''j''的二进制表示，还是按小端次序。在效果上运算的下标就是这个运算的真值表。

== 序理论的性质 ==

同任何格一样，布尔代数 (''A'', <math>\land</math>, <math>\lor</math>)可以引出[[偏序集]]（''A'', ≤），通过定义
: ''a'' ≤ ''b'' [[当且仅当]]''a'' = ''a'' <math>\land</math> ''b'' (它也等价于''b'' = ''a'' <math>\lor</math> ''b'')。

事实上你还可以把布尔代数定义为有最小元素0和最大元素1的分配格 (''A'', ≤) (考虑为偏序集合)，在其中所有的元素''x''都有补¬''x''满足

: ''x'' <math>\land</math> ¬''x'' = 0并且''x'' <math>\lor</math> ¬''x'' = 1

这裡的<math>\land</math>和<math>\lor</math>用来指示两个元素的[[下确界]]（交）和[[上确界]]（并）。还有，如果上述意义上的补存在，则它们是可唯一确定的。

代数的和序理论的观点通常可以交替的使用，并且二者都是有重要用处的，可从[[泛代数]]和[[序理论]]引入结果和概念。在很多实际例子中次序关系、合取（逻辑与）、析取（逻辑或）和否定（逻辑非）都是自然的可获得的，所以可直接利用这种联系。

=== 对偶原理 ===

你还可以把来自[[对偶性 (序理论)|序理论的对偶性]]的普遍认识应用于布尔代数。特别是，所有的布尔代数的次序对偶，或者等价的说通过对换<math>\land</math>与<math>\lor</math>所获得的代数，也是布尔代数。一般的说，布尔代数的任何有效的规律都可以变换成另一个有效的对偶规律，通过对换0与1，<math>\land</math>与<math>\lor</math>，和≤与≥。

== 同态和同构 ==

在布尔代数''A''和''B''之间的'''同态'''是一个[[函数]]''f'' : ''A'' → ''B''，对于在''A''中所有的''a'', ''b''都有:

: ''f''(''a'' <math>\lor</math> ''b'') = ''f''（''a''）<math>\lor</math> ''f''（''b''）
: ''f''(''a'' <math>\land</math> ''b'') = ''f''（''a''）<math>\land</math> ''f''（''b''）
: ''f''（0）= 0
: ''f''（1）= 1

接着对于在''A''中所有的''a''，''f''(¬''a'') = ¬''f''（''a''）同样成立。所有布尔代数的[[类 (数学)|类]]，和与之在一起的[[态射]]的概念，形成了一个[[范畴论|范畴]]。从''A''到''B''的'''同构'''是[[双射]]的从''A''到''B''的同态。同构的逆也是同构，我们称两个布尔代数''A''和''B''为“同构”的。从布尔代数理论的立场上，它们是不能区分的；它们只在它们的元素的符号上有所不同。

===布尔同态===
布尔[[同态]]是在布尔代数''A''和''B''之间的函数''h'': ''A''→''B''使得对于所有[[布尔运算]]<sup>''m''</sup>''f''<sub>''i''</sub>有
: ''h''(<sup>''m''</sup>''f''<sub>''i''</sub>(''x''<sub>0</sub>,…,''x''<sub>''m''−1</sub>)) = <sup>''m''</sup>''f''<sub>''i''</sub>(''h''(''x''<sub>0</sub>),…,''h''(''x''<sub>''m''−1</sub>)).

布尔代数的[[范畴论|范畴]]'''Bool'''有所有布尔代数作为对象和在它们之间的布尔同态作为态射。

从两元素布尔代数'''2'''到所有布尔代数存在唯一的同态，因为所有态射必须保持两个常量而它们是'''2'''的仅有元素。有这种性质的布尔代数叫做'''初始'''布尔代数。可以证明任何两个初始布尔代数都是同构的，所以在同构的意義下'''2'''就是初始布尔代数。

在其他方向上，从布尔代数''B''到'''2'''存在很多同态。任何这种同态都把''B'' [[集合划分|划分]]成映射到1的元素和映射到0的元素。由前者组成的''B''的子集叫做''B''的[[超滤子]]。在''B''是有限的时候，它的超滤子配对于它的[[原子 (序理论)|原子]]；一个原子被映射到1而其他被映射到0。''B''的每个超滤子因此由''B''的一个原子和所有其上的元素组成；所以精确的有''B''的一半元素在这个超滤子中，并且有和原子一样的多的超滤子。

对于无限布尔代数，超滤子的概念变得相当微妙。大于等于原子的那些元素总是形成超滤子，但是很多其他集合也能形成；例如在整数的有限和[[余有限]]集合的布尔代数中，余有限集合形成了超滤子即使它们中没有原子。类似的整数的幂集有包含给定整数的所有子集的集合作为超滤子之一；有可数多个这种“标准”超滤子，它们可以用整数自身来识别，但是还有不可数多个“非标准”超滤子。这些形成了[[非标准分析]]的基础，它提供了对这种经典不相容对象作为无穷小和delta函数的表述。

== 布尔环、理想和滤子 ==

每个布尔代数 (''A'', <math>\land</math>, <math>\lor</math>)都引出一个环（''A'', +, *），通过定义''a'' + ''b'' = (''a'' <math>\land</math> ¬''b'') <math>\lor</math> (''b'' <math>\land</math> ¬''a'') (这个运算在集合论中叫做“[[对称差]]”在逻辑中叫做[[逻辑异或|XOR]]（异或）)和''a'' * ''b'' = ''a'' <math>\land</math> ''b''。这个环的零元素符合布尔代数的0；环的乘法单位元素是布尔代数的1。这个环有对于''A''中的所有的''a''保持''a'' * ''a'' = ''a''的性质；有这种性质的环叫做[[布尔环]]。

反过来，如果给出布尔环''A''，我们可以把它转换成布尔代数，通过定义''x'' <math>\lor</math> ''y'' = ''x'' + ''y'' + ''xy''和''x'' <math>\land</math> ''y'' = ''xy''。因为这两个运算是互逆的，我们可以说每个布尔环引发一个布尔代数，或反之。此外，映射''f'' : ''A'' → ''B''是布尔代数的同态，当且仅当它是布尔环的同态。布尔环和代数的[[范畴论|范畴]]是等价的。

布尔代数''A''的[[理想 (数学)|理想]]是一个子集''I''，对于在''I''中的所有''x'', ''y''我们有''x'' <math>\lor</math> ''y''在''I''中，并且对于在''A''中的所有''a''我们有''a'' <math>\land</math> ''x''在''I''中。理想的概念符合在布尔环''A''中[[环理想]]的概念。''A''的理想''I''叫做“素理想”，如果''I'' ≠ ''A''；并且如果''a'' <math>\land</math> ''b''在''I''中总是蕴涵''a''在''I''中或''b''在''I''中。''A''的理想''I''叫做“极大理想”，如果''I'' ≠ ''A''并且真正包含''I''的唯一的理想是''A''自身。这些概念符合布尔环''A''中的[[素理想]]和[[极大理想]]的环理论概念。

“理想”的对偶是[[滤子 (数学)|滤子]]。布尔代数''A''的“滤子”是子集''p''，对于在''p''中的所有''x'', ''y''我们有''x'' <math>\land</math> ''y''在''p''中，并且对于在''A''中的所有''a''，如果''a'' <math>\lor</math> ''x'' = ''a''则''a''在''p''中。

== 表示布尔代数 ==

可以证实所有的“有限”的布尔代数都同构于一个有限集合的所有子集的布尔代数。此外，所有的有限的布尔代数的元素-{}-数目都是[[二的幂]]。[[Marshall H. Stone|Stone]]的著名的[[Stone布尔代数表示定理|布尔代数表示定理]]陈述了“所有的”布尔代数''A''都同构于在某个（[[完全不连通空间|完全不连通]][[紧致空间|紧致]][[豪斯多夫空间]]）拓扑空间中所有[[闭开集|闭开]]集合的布尔代数。

== 广义布尔代数 ==

从布尔代数的公理中去掉存在最大元1的要求产生了“广义布尔代数”。形式的说，[[分配格]]''B''是广义布尔代数，如果它有最小元0并且对于任何''B''中的元素''a''和''b''使得''a'' ≤ ''b''，存在一个元素''x''使得<math>a\land x=0</math>并且<math>a\lor x=b</math>。定义<math>a - b \,</math>为唯一的''x''使得<math>(a\land b)\lor x=a</math>并且<math>(a\land b)\land x=0</math>，我们可以称结构<math>(B,\land,\lor,-,0)</math>是“广义布尔代数”，而<math>(B,\lor,0)</math>是“广义布尔半格”。

广义布尔格完全就是布尔格的[[理想 (数学)|理想]]。

== 公理化布尔代数 ==

在1933年，美国数学家[[Edward Vermilye Huntington]]（1874-1952）展示了对布尔代数的如下公理化:

# '''交换律''': ''x'' + ''y'' = ''y'' + ''x''。
# '''结合律''': (''x'' + ''y'') + ''z'' = ''x'' + (''y'' + ''z'')。
# '''Huntington等式''': <math>\overline{ \overline{x}+y} + \overline{\overline{x}+\overline{y}} = x</math>。

[[Herbert Robbins]]接着摆出下列问题:  Huntington等式能否替代为它的对偶等式，并且这个新等式与结合律和交换律一起成为布尔代数的基础?通过一组叫做“Robbins代数”的公理，问题就变成了：是否所有的Robbins代数都是布尔代数?

Robbins代数的公理化:

# '''交换律''': ''x'' + ''y'' = ''y'' + ''x''。
# '''结合律''': (''x'' + ''y'') + ''z'' = ''x'' + (''y'' + ''z'')。
# '''Robbins等式''': <math>\overline{\overline{x + y}+ \overline{x +\overline{y}}} = x</math>。

这个问题自从1930年代一直是公开的，并成为[[阿尔弗雷德·塔斯基]]和他的学生最喜好的问题。

在1996年，[[William McCune]]在[[阿贡国家实验室]]，建造在Larry Wos、Steve Winker和Bob Veroff的工作之上，肯定的回答了这个长期存在的问题：所有的Robbins代数都是布尔代数。这项工作是使用McCune的[[自动推理程序]][[EQP]]完成的。

== 其它记号 ==
{{expert-subject|time=2015-11-02T19:31:10+00:00}}
布林代數的運算包含下列幾種，基本包含“與”(AND)、“或”(OR)、“非”(NOT)，其中由這三種又可組合成NAND（[[與非]]）、NOR（[[或非]]）、XOR（[[異或]]）與XNOR（[[異或非]]）。

常見使用記號：“<math>\cdot</math>”表示AND，“＋”表示OR（如[[合取范式|CNF]]和[[析取范式|DNF]]中）或者XOR（如[[代數范式|ANF]]中）；<font style="text-decoration:overline">A</font>中A上面的一橫表示NOT；⊕表示XOR；⊙表示XNOR。

==参见==
* [[布尔代数主题列表]]
* [[布尔逻辑]]
* [[逻辑代数]]
* [[代数逻辑]]

== 参考资料 ==
{{reflist|2}}

*{{citation
| last1 = Brown
| first1 = Stephen
| last2 = Vranesic
| first2 = Zvonko
| year = 2002
| title = Fundamentals of Digital Logic with VHDL Design
| edition = 2nd
| publisher = [[McGraw-Hill|McGraw–Hill]]
| isbn = 978-0-07-249938-4}}. See Section 2.5.

*{{citation
| last1 = Cori
| first1 = Rene
| last2 = Lascar
| first2 = Daniel
| year = 2000
| title = Mathematical Logic:  A Course with Exercises
| publisher = [[Oxford University Press]]
| isbn = 978-0-19-850048-3}}. See Chapter 2.

*{{citation
| last = Dahn
| first = B. I.
| year = 1998
| title = Robbins Algebras are Boolean:  A Revision of McCune's Computer-Generated Solution of the Robbins Problem
| journal = Journal of Algebra
| volume = 208
| pages = 526–532
| issn = 0021-8693}}.

*{{citation
| authorlink = Paul Halmos
| last = Halmos
| first = Paul
| year = 1963
| title = Lectures on Boolean Algebras
| publisher = Van Nostrand
| isbn = 978-0-387-90094-0}}.

*{{citation
| authorlink1 = Paul Halmos
| last1 = Halmos
| first1 = Paul
| first2 = Steven
| last2 = Givant
| year = 1998
| title = Logic as Algebra
| publisher = Dolciani Mathematical Expositions, no. 21, [[Mathematical Association of America]]
| isbn = 978-0-88385-327-6}}.

*{{citation
| authorlink = Edward Vermilye Huntington
| last = Huntington
| first = E. V.
| year = 1933
| title = New sets of independent postulates for the algebra of logic
| journal = [[Transactions of the American Mathematical Society]]
| volume = 35
| pages = 274–304
| issn = 0002-9947}}.

*{{citation
| authorlink = Edward Vermilye Huntington
| last = Huntington
| first = E. V.
| year = 1933
| title = Boolean algebra: A correction
| journal = [[Transactions of the American Mathematical Society]]
| volume = 35
| pages = 557–558
| issn = 0002-9947}}.

*{{citation
| last = Mendelson
| first = Elliott
| year = 1970
| title = Boolean Algebra and Switching Circuits
| publisher = Schaum's Outline Series in Mathematics, [[McGraw-Hill|McGraw–Hill]]
| isbn = 978-0-07-041460-0}}.

*{{citation
| editor1-last = Monk
| editor1-first = J. Donald
| editor2-first = R.
| editor2-last = Bonnet
| year = 1989
| title = Handbook of Boolean Algebras
| publisher = [[Elsevier|North-Holland]]
| isbn = 978-0-444-87291-3}}. In 3 volumes. (Vol.1:ISBN 978-0-444-70261-6, Vol.2:ISBN 978-0-444-87152-7, Vol.3:ISBN 978-0-444-87153-4)

*{{citation
| last = Stoll
| first = R. R.
| year = 1963
| title = Set Theory and Logic
| publisher = W. H. Freeman
| isbn = 978-0-486-63829-4}}. Reprinted by [[Dover Publications]], 1979.<!--
Use [[WP:CITET|templates]] for consistency -->
* {{cite journal
| last = Birkhoff
| first = Garrett
| authorlink = Garrett Birkhoff
| title = On the structure of abstract algebras
| journal = Proc. Camb. Phil. Soc.
| volume = 31
| pages = 433–454
| date = 1935
| id = {{ISSN|0008-1981}} }}
* {{cite book
| last = Boole
| first = George
| authorlink = George Boole
| title = An Investigation of the Laws of Thought
| publisher = Prometheus Books
| origyear = 1854
| date = 2003
| id = ISBN 978-1-59102-089-9 }}
* {{cite book
| last = Dwinger
| first = Philip
| title = Introduction to Boolean algebras
| publisher = Physica Verlag
| location = Würzburg
| date = 1971 }}
* {{cite journal
| last = Gaifman
| first = Haim
| title = Infinite Boolean Polynomials, I
| journal = Fundamenta Mathematicae
| volume = 54
| pages = 229–250
| date = 1964
| id = {{ISSN|0016-2736}} }}
* {{cite journal
| last = Grau
| first = A.A.
| title = Ternary Boolean algebra
| journal = Bull: Am. Math. Soc.
| volume = 33
| pages = 567–572
| date = 1947 }}
* {{cite journal
| last = Hales
| first = Alfred W.
| title = On the Non-Existence of Free Complete Boolean Algebras
| journal = Fundamenta Mathematicae
| volume = 54
| pages = 45–66
| date = 1964
| id = {{ISSN|0016-2736}} }}
*--------, and Givant, Steven (1998) ''Logic as Algebra''. Dolciani Mathematical Exposition, No. 21. [[Mathematical Association of America]].
* {{cite book
| last = Johnstone
| first = Peter T.
| title = Stone Spaces
| publisher = Cambridge University Press
| date = 1982
| location = Cambridge, UK
| id = ISBN 978-0-521-33779-3 }}
* {{cite journal
| last = Ketonen
| first = Jussi
| title = The structure of countable Boolean algebras
| url = https://archive.org/details/sim_annals-of-mathematics_1978-07_108_4/page/41
| journal = Annals of Mathematics
| volume = 108
| pages = 41–89
| date = 1978
| id = }}
* Koppelberg, Sabine (1989) "General Theory of Boolean Algebras" in Monk, J. Donald, and Bonnet, Robert, eds., ''Handbook of Boolean Algebras, Vol. 1''. North Holland. ISBN 978-0-444-70261-6.<!--
The following alternatives do not work; still searching for good template
* {{cite book
| last = Koppelberg
| first = Sabine
| chapter = General Theory of Boolean Algebras
| title = Handbook of Boolean Algebras, Vol. 1 (ed. J. Donald Monk with Robert Bonnet)
| publisher = North Holland
| date = 1989
| location = Amsterdam
| id = ISBN 978-0-444-70261-6--> <!--0-444-70261-X
* {{cite conference
| first = Koppelberg
| last = Sabine
| year = 1989
| title = General Theory of Boolean Algebras
| booktitle = Handbook of Boolean Algebras, Vol. 1
| editor = J. Donald Monk with Robert Bonnet
| publisher = North Holland
| location = Amsterdam
| pages =
| id = ISBN 978-0-444-70261-6
}}-->
*[[Charles Peirce|Peirce, C. S.]]（1989）''Writings of Charles S. Peirce: A Chronological Edition: 1879–1884''. Kloesel, C. J. W., ed. Indianapolis: Indiana University Press. ISBN 978-0-253-37204-8.
* {{cite journal
| last = Lawvere
| first = F. William
| authorlink = William Lawvere
| title = Functorial semantics of algebraic theories
| journal = Proceedings of the National Academy of Sciences
| volume = 50
| issue = 5
| pages = 869–873
| date = 1963
| url = http://www.tac.mta.ca/tac/reprints/articles/5/tr5abs.html }}
* {{cite book
| last = Schröder
| first = Ernst
| authorlink = Ernst Schröder
| title = Vorlesungen über die Algebra der Logik (exakte Logik), I–III<!--, III.1-->
| publisher = B.G. Teubner
| location = Leipzig
| date = 1890–1910<!--1895-->
| id =  }}
* {{cite book
| last = Sikorski
| first = Roman
| authorlink = Roman Sikorski
| title = Boolean Algebras
| publisher = Springer-Verlag
| location = Berlin
| edition = 3rd. ed.
| date = 1969
| id = ISBN 978-0-387-04469-9 }}
* {{cite journal
| last = Stone
| first = Marshall
| authorlink = Marshall Harvey Stone
| title = The Theory of Representations for Boolean Algebras
| journal = Transactions of the American Mathematical Society
| volume = 40
| pages = 37–111
| date = 1936
| id = {{ISSN|0002-9947}} }}
*[[Alfred Tarski|Tarski, Alfred]]（1983）. ''Logic, Semantics, Metamathematics'', Corcoran, J., ed. Hackett. 1956 1st edition edited and translated by J. H. Woodger, Oxford Uni. Press. Includes English translations of the following two articles:
** {{cite journal
| last = Tarski
| first = Alfred
| authorlink = Alfred Tarski
| title = Sur les classes closes par rapport à certaines opérations élémentaires
| journal = Fundamenta Mathematicae
| volume = 16
| pages = 195–97
| date = 1929
| id = {{ISSN|0016-2736}} }}
** {{cite journal
| last = Tarski
| first = Alfred
| authorlink = Alfred Tarski
| title = Zur Grundlegung der Booleschen Algebra, I
| journal = Fundamenta Mathematicae
| volume = 24
| pages = 177–98
| date = 1935
| id = {{ISSN|0016-2736}} }}
* {{ cite book
| last = Vladimirov
| first = D.A.
| title = булевы алгебры (Boolean algebras, in Russian, German translation Boolesche Algebren 1974)
| publisher = Nauka (German translation Akademie-Verlag)
| year = 1969 }}

== 外部链接 ==
* [http://www.allaboutcircuits.com/vol_4/chpt_7/1.html Boolean Algebra] {{Wayback|url=http://www.allaboutcircuits.com/vol_4/chpt_7/1.html |date=20150423100549 }} from AllAboutCircuits
* [[Stanford Encyclopedia of Philosophy]]: "[http://plato.stanford.edu/entries/boolalg-math/ The Mathematics of Boolean Algebra,] {{Wayback|url=http://plato.stanford.edu/entries/boolalg-math/ |date=20201106235633 }}" by J. Donald Monk.
* McCune W., 1997. ''[http://www.cs.unm.edu/~mccune/papers/robbins/ Robbins Algebras Are Boolean] {{Wayback|url=http://www.cs.unm.edu/~mccune/papers/robbins/ |date=20200918094223 }}'' JAR 19(3), 263–276
* [http://demonstrations.wolfram.com/BooleanAlgebra/ "Boolean Algebra"] {{Wayback|url=http://demonstrations.wolfram.com/BooleanAlgebra/ |date=20201125002238 }} by [[Eric W. Weisstein]]、[[The Wolfram Demonstrations Project]], 2007.
A monograph available free online:
* Burris, Stanley N.; Sankappanavar, H. P., 1981. ''[http://www.thoralf.uwaterloo.ca/htdocs/ualg.html A Course in Universal Algebra.] {{Wayback|url=http://www.thoralf.uwaterloo.ca/htdocs/ualg.html |date=20050123031934 }}''  Springer-Verlag. ISBN 978-3-540-90578-3.

{{数字电路}}

{{DEFAULTSORT:Boolean algebra}}
[[Category:布尔代数|*]]
[[Category:序理论]]
[[Category:格理论]]
[[Category:代数逻辑]]
[[Category:代数结构]]