布林代數

代数结构

布林代數(英語:Boolean algebra)在抽象代數中是指擷取了集合運算和邏輯運算二者的根本性質的一個代數結構(就是說一組元素和服從定義的公理的在這些元素上運算)。特別是,它處理集合運算交集併集補集;和邏輯運算

子集的布林格的哈斯圖

例如,邏輯斷言陳述a和它的否定¬a不能都同時為真,

相似於集合論斷言子集A和它的補集AC有空交集,

因為真值可以在邏輯電路中表示為二進制數或電平,這種相似性同樣擴充到它們,所以布林代數在電子工程電腦科學中同在數理邏輯中一樣有很多實踐應用。在電子工程領域專門化了的布林代數也叫做邏輯代數,在電腦科學領域專門化了布林代數也叫做布林運算

布林代數也叫做布林格。關聯於(特殊的偏序集合)是在集合包含A ⊆ B次序 a ≤ b之間的相似所預示的。考慮{x,y,z}的所有子集按照包含排序的格。這個布林格是偏序集合,在其中{x}  ≤ {x,y}。任何兩個格的元素,比如p = {x,y}和q = {y,z},都有一個最小上界,這裏是{x,y,z},和一個最大下界,這裏是{y}。這預示了最小上界(並或上確界)被表示為同邏輯OR一樣的符號pq;而最大下界(交或下確界)被表示為同邏輯AND一樣的符號pq

這種格釋義有助於一般化為海廷代數,它是免除要麼一個陳述要麼它的否定必須為真的限制的布林代數。海廷代數對應於直覺邏輯,而布林代數對應於經典邏輯

布林代數又譯為布爾代數,然而布林代數得名於喬治·布爾,他是愛爾蘭科克的皇后學院的英國數學家。布林(boolean)在英文中的意思是「布爾的」,這是為了表彰布爾的貢獻,而「布林」只是一種音譯。

歷史

術語「布林代數」得名於喬治·布爾(1815–1864),他是自學成材的英國數學家。他最初在1847年出版的一個小冊子《邏輯的數學分析》中介入了代數邏輯系統,用來響應在奧古斯都·德·摩根William Hamilton之間的公開論戰,後來又出現在1854年出版的更充實的書《思維規律》中。布林的公式化在一些重要方面不同於上述描述。例如,布林的合取和析取不是一對對偶的運算。布林代數出現在1860年代威廉姆·斯坦利·傑文斯查爾斯·皮爾士的論文中。到了1890年Ernst Schröder寫的《Vorlesungen》,我們才有了布林代數和分配格的首次系統表述。首次用英語寫的對布林代數的廣泛處置是阿弗烈·諾夫·懷海德在1898年的《泛代數》。在現代公理化意義上的作為公理化代數結構的布林代數開始於Edward Vermilye Huntington 1904年的論文。布林代數隨着Marshall Stone在1930年代的工作和Garrett Birkhoff在1940年的《格理論》而進入了嚴肅數學時期。在1960年代,Paul CohenDana Scott和其他人使用布林代數的分支也就是力迫布林值模型,深入發現了數理邏輯公理化集合論中的新成果。

形式定義

布林代數是一個集合A,其上定義了以下結構:

  • 二元運算∧:A×A→A。
  • 二元運算∨:A×A→A。
  • 一元運算 ':A→A。
  • 零元素運算(常數)0和1。

這些運算滿足以下條件:∀a,b,c∈A,

    結合律
    交換律
    吸收律
    分配律
    互補律

上面的前三對公理:結合律、交換律和吸收律,意味着 (A,∧,∨)是一個。所以布林代數也可以定義為一個有補分配格

從這些公理,你可以展示出最小元素0、最大元素1和任何元素a的補a'都是唯一確定的。

另外,∀a,b∈A,下列恆等式也成立:

    冪等律
    有界律
   
    0和1是互補的
    德·摩根定律
  對合律

其它運算

在上述基本定義基礎上,布林代數中常見的還有以下的運算:

  • 二元運算-: 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)'。

總結

布林代數的各種運算同時也被應用於集合論邏輯學,在不同的上下文有不同的名稱。具體的符號和名稱如下:

運算符號 布林代數 集合論 邏輯學 邏輯門 溫氏圖
0或  空集 低電位
 
1或  全集 高電位
 
¬或~或'或c 補集 反相器
 
∧或∩ 下確界 交集 及閘
 
∨或∪ 上確界 併集 或閘
 
   相對補集
 
-或  差集 實質非蘊涵 蘊含非閘
 
⊕或Δ 對稱差 對稱差 異或 異或閘
 
條件 條件 蘊含閘
 
雙向條件 雙條件 同或閘
 
|或↑ 謝費爾豎線 與非 反及閘
 
皮爾斯箭頭 或非 反或閘
 

例子

  • 最簡單的布林代數只有兩個元素0和1,並通過如下規則定義:
0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1
a 0 1
¬a 1 0
  • 它應用於邏輯中,解釋0為「偽」,1為「真」,∧為「與」,∨為「或」,¬為「非」。涉及變數和布林運算的表達式代表了陳述形式,兩個這樣的表達式可以使用上面的公理證實為等價的,當且僅當對應的陳述形式是邏輯等價的。
  • 兩元素的布林代數也是在電子工程中用於電路設計;這裏的0和1代表數字電路中一個的兩種不同狀態,典型的是高和低電壓。電路通過包含變數的表達式來描述,兩個這種表達式對這些變數的所有的值是等價的,當且僅當對應的電路有相同的輸入-輸出行為。此外,所有可能的輸入-輸出行為都可以使用合適的布林表達式來建摸。
  • 兩元素布林代數在布林代數的一般理論中也是重要的,因為涉及多個變數的等式是在所有布林代數中普遍為真,當且僅當它在兩個元素的布林代數中為真(這總是可以通過平凡的窮舉法演算法證實)。比如證實下列定律(「合意定理」)在所有布林代數中是普遍有效的:
    • (ab) ∧ (¬ac) ∧ (bc) ≡ (ab) ∧ (¬ac)
    • (ab) ∨ (¬ac) ∨ (bc) ≡ (ab) ∨ (¬ac)
  • 任何給定集合S冪集(子集的集合)形成有兩個運算∨ := ∪ (並)和∧ := ∩ (交)的布林代數。最小的元素0是空集而最大元素1是集合S自身。
  • 有限的或餘有限的集合S的所有子集的集合是布林代數。
  • 對於任何自然數nn的所有正因數的集合形成一個分配格,如果我們對a | bab。這個格是布林代數當且僅當n無平方數因數的數。這個布林代數的最小的元素0是自然數1;這個布林代數的最大元素1是自然數n
  • 布林代數的另一個例子來自拓撲空間:如果X是一個拓撲空間,它既是開放的又是閉合的,X的所有子集的搜集形成有兩個運算∨ := ∪ (並)和∧ := ∩ (交)的布林代數。
  • 如果R是一個任意的環,並且我們定義「中心冪等元」(central idempotent)的集合為
    A = { eR : e2 = e, ex = xe, ∀xR }
    則集合A成為有兩個運算ef := e + f + efef := ef的布林代數。

原型布林代數

k元素集合X上有kknn元運算fXnX,因此在{0,1}上有22nn元運算。所以得出所有布林代數,不論大小都兩個常數或「零元素」運算,四個一元運算,16個二元運算,256個三元運算,以此類推,它們叫做給定布林代數的布林運算。只有一個例外就是一個元素的布林代數,它叫做退化的或平凡的(被一些早期作者禁用),布林代數的所有運算可以被證明是獨特的。(在退化情況下,給定元數的所有運算都是同樣的運算因為對所有輸入都返回同樣結果。)

在{0,1}上的運算可以用真值表展出,選取0和1為真值。它們可以按統一和不依賴應用的方式列出,允許我們命名或至少單獨列出它們。這些名字對布林運算提供方便的簡寫。n元運算的名字是2n位的二進制數。有22n個這種運算,你不能得到更簡明的命名法了!

下面展示元數從0到2的所有運算的這種格局和關聯的名字。

直到2元的布林運算的真值表
常數
0f0 0f1
0 1
一元運算
x0 1f0 1f1 1f2 1f3
0 0 1 0 1
1 0 0 1 1
二元運算
x0 x1 2f0 2f1 2f2 2f3 2f4 2f5 2f6 2f7 2f8 2f9 2f10 2f11 2f12 2f13 2f14 2f15
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元有2n行,每個行給出n個變數x0,…xn−1的一個求值或繫結,而每列都有表頭nfi,它們給出第in元運算nfi(x0,…,xn−1)在這個求值下的值。運算包括變數本身,例如1f2x02f10x0 (作為它的一元對應者的兩個復件)而2f12x1 (沒有一元對應者)。否定或補¬x0出現為1f1再次出現為2f5,連同2f3x1在1元時沒有出現),析取或並x0x1出現為2f14,合取或交x0x1出現為2f8,蘊涵x0x1出現為2f13,異或或對稱差x0x1出現為2f6,差集x0x1出現為2f2等等。對布林函數的其他命名或表示可參見零階邏輯

作為關於它的形式而非內容的次要詳情,一個代數的運算傳統上組織為一個列表。我們這裏通過在{0,1}上有限運算索引了布林代數的運算,上述真值表表示的排序首先按元數,其次為每個元數運算的列出表格。給定元數的列表次序是如下兩個規則確定的。

(i)表格左半部分的第i行是i的二進制表示,最低有效位或第0位在最左(「小端」次序,最初由艾倫·圖靈提議,所以可不無合理的叫做圖靈序)。
(ii)表格的右半部分的第j列是j的二進制表示,還是按小端次序。在效果上運算的下標就是這個運算的真值表。

序理論的性質

同任何格一樣,布林代數 (A,  ,  )可以引出偏序集A, ≤),通過定義

ab 當且僅當a = a   b (它也等價於b = a   b)。

事實上你還可以把布林代數定義為有最小元素0和最大元素1的分配格 (A, ≤) (考慮為偏序集合),在其中所有的元素x都有補¬x滿足

x   ¬x = 0並且x   ¬x = 1

這裏的  用來指示兩個元素的下確界(交)和上確界(並)。還有,如果上述意義上的補存在,則它們是可唯一確定的。

代數的和序理論的觀點通常可以交替的使用,並且二者都是有重要用處的,可從泛代數序理論引入結果和概念。在很多實際例子中次序關係、合取(邏輯與)、析取(邏輯或)和否定(邏輯非)都是自然的可獲得的,所以可直接利用這種聯絡。

對偶原理

你還可以把來自序理論的對偶性的普遍認識應用於布林代數。特別是,所有的布林代數的次序對偶,或者等價的說通過對換  所獲得的代數,也是布林代數。一般的說,布林代數的任何有效的規律都可以轉換成另一個有效的對偶規律,通過對換0與1,  ,和≤與≥。

同態和同構

在布林代數AB之間的同態是一個函數f : AB,對於在A中所有的a, b都有:

f(a   b) = fa  fb
f(a   b) = fa  fb
f(0)= 0
f(1)= 1

接着對於在A中所有的afa) = ¬fa)同樣成立。所有布林代數的,和與之在一起的態射的概念,形成了一個範疇。從AB同構對射的從AB的同態。同構的逆也是同構,我們稱兩個布林代數AB為「同構」的。從布林代數理論的立場上,它們是不能區分的;它們只在它們的元素的符號上有所不同。

布林同態

布林同態是在布林代數AB之間的函數h: AB使得對於所有布林運算mfi

h(mfi(x0,…,xm−1)) = mfi(h(x0),…,h(xm−1)).

布林代數的範疇Bool有所有布林代數作為物件和在它們之間的布林同態作為態射。

從兩元素布林代數2到所有布林代數存在唯一的同態,因為所有態射必須保持兩個常數而它們是2的僅有元素。有這種性質的布林代數叫做初始布林代數。可以證明任何兩個初始布林代數都是同構的,所以在同構的意義下2就是初始布林代數。

在其他方向上,從布林代數B2存在很多同態。任何這種同態都把B 劃分成對映到1的元素和對映到0的元素。由前者組成的B的子集叫做B超濾子。在B是有限的時候,它的超濾子配對於它的原子;一個原子被對映到1而其他被對映到0。B的每個超濾子因此由B的一個原子和所有其上的元素組成;所以精確的有B的一半元素在這個超濾子中,並且有和原子一樣的多的超濾子。

對於無限布林代數,超濾子的概念變得相當微妙。大於等於原子的那些元素總是形成超濾子,但是很多其他集合也能形成;例如在整數的有限和餘有限集合的布林代數中,餘有限集合形成了超濾子即使它們中沒有原子。類似的整數的冪集有包含給定整數的所有子集的集合作為超濾子之一;有可數多個這種「標準」超濾子,它們可以用整數自身來辨識,但是還有不可數多個「非標準」超濾子。這些形成了非標準分析的基礎,它提供了對這種經典不相容物件作為無窮小和delta函數的表述。

布林環、理想和濾子

每個布林代數 (A,  ,  )都引出一個環(A, +, *),通過定義a + b = (a   ¬b)   (b   ¬a) (這個運算在集合論中叫做「對稱差」在邏輯中叫做XOR(異或))和a * b = a   b。這個環的零元素符合布林代數的0;環的乘法單位元素是布林代數的1。這個環有對於A中的所有的a保持a * a = a的性質;有這種性質的環叫做布林環

反過來,如果給出布林環A,我們可以把它轉換成布林代數,通過定義x   y = x + y + xyx   y = xy。因為這兩個運算是互逆的,我們可以說每個布林環引發一個布林代數,或反之。此外,對映f : AB是布林代數的同態,當且僅當它是布林環的同態。布林環和代數的範疇是等價的。

布林代數A理想是一個子集I,對於在I中的所有x, y我們有x   yI中,並且對於在A中的所有a我們有a   xI中。理想的概念符合在布林環A環理想的概念。A的理想I叫做「質理想」,如果IA;並且如果a   bI中總是蘊涵aI中或bI中。A的理想I叫做「極大理想」,如果IA並且真正包含I的唯一的理想是A自身。這些概念符合布林環A中的質理想極大理想的環理論概念。

「理想」的對偶是濾子。布林代數A的「濾子」是子集p,對於在p中的所有x, y我們有x   yp中,並且對於在A中的所有a,如果a   x = aap中。

表示布林代數

可以證實所有的「有限」的布林代數都同構於一個有限集合的所有子集的布林代數。此外,所有的有限的布林代數的元素數目都是二的冪Stone的著名的布林代數表示定理陳述了「所有的」布林代數A都同構於在某個(完全不連通緊緻郝斯多夫空間)拓撲空間中所有閉開集合的布林代數。

廣義布林代數

從布林代數的公理中去掉存在最大元1的要求產生了「廣義布林代數」。形式的說,分配格B是廣義布林代數,如果它有最小元0並且對於任何B中的元素ab使得ab,存在一個元素x使得 並且 。定義 為唯一的x使得 並且 ,我們可以稱結構 是「廣義布林代數」,而 是「廣義布林半格」。

廣義布林格完全就是布林格的理想

公理化布林代數

在1933年,美國數學家Edward Vermilye Huntington(1874-1952)展示了對布林代數的如下公理化:

  1. 交換律: x + y = y + x
  2. 結合律: (x + y) + z = x + (y + z)。
  3. Huntington等式:  

Herbert Robbins接着擺出下列問題: Huntington等式能否替代為它的對偶等式,並且這個新等式與結合律和交換律一起成為布林代數的基礎?通過一組叫做「Robbins代數」的公理,問題就變成了:是否所有的Robbins代數都是布林代數?

Robbins代數的公理化:

  1. 交換律: x + y = y + x
  2. 結合律: (x + y) + z = x + (y + z)。
  3. Robbins等式:  

這個問題自從1930年代一直是公開的,並成為阿爾弗雷德·塔斯基和他的學生最喜好的問題。

在1996年,William McCune阿貢國家實驗室,建造在Larry Wos、Steve Winker和Bob Veroff的工作之上,肯定的回答了這個長期存在的問題:所有的Robbins代數都是布林代數。這項工作是使用McCune的自動推理程式EQP完成的。

其它記號

布林代數的運算包含下列幾種,基本包含「與」(AND)、「或」(OR)、「非」(NOT),其中由這三種又可組合成NAND(與非)、NOR(或非)、XOR(異或)與XNOR(異或非)。

常見使用記號:「 」表示AND,「+」表示OR(如CNFDNF中)或者XOR(如ANF中);A中A上面的一橫表示NOT;⊕表示XOR;⊙表示XNOR。

參見

參考資料

  • Dahn, B. I., Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem, Journal of Algebra, 1998, 208: 526–532, ISSN 0021-8693 .
  • Stoll, R. R., Set Theory and Logic, W. H. Freeman, 1963, ISBN 978-0-486-63829-4 . Reprinted by Dover Publications, 1979.
  • Birkhoff, Garrett. On the structure of abstract algebras. Proc. Camb. Phil. Soc. 1935, 31: 433–454. ISSN 0008-1981. 
  • Boole, George. An Investigation of the Laws of Thought. Prometheus Books. 2003 [1854]. ISBN 978-1-59102-089-9. 
  • Dwinger, Philip. Introduction to Boolean algebras. Würzburg: Physica Verlag. 1971. 
  • Gaifman, Haim. Infinite Boolean Polynomials, I. Fundamenta Mathematicae. 1964, 54: 229–250. ISSN 0016-2736. 
  • Grau, A.A. Ternary Boolean algebra. Bull: Am. Math. Soc. 1947, 33: 567–572. 
  • Hales, Alfred W. On the Non-Existence of Free Complete Boolean Algebras. Fundamenta Mathematicae. 1964, 54: 45–66. ISSN 0016-2736. 
  • --------, and Givant, Steven (1998) Logic as Algebra. Dolciani Mathematical Exposition, No. 21. Mathematical Association of America.
  • Johnstone, Peter T. Stone Spaces. Cambridge, UK: Cambridge University Press. 1982. ISBN 978-0-521-33779-3. 
  • Ketonen, Jussi. The structure of countable Boolean algebras. Annals of Mathematics. 1978, 108: 41–89. 
  • 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.
  • 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.
  • Lawvere, F. William. Functorial semantics of algebraic theories. Proceedings of the National Academy of Sciences. 1963, 50 (5): 869–873. 
  • Schröder, Ernst. Vorlesungen über die Algebra der Logik (exakte Logik), I–III. Leipzig: B.G. Teubner. 1890–1910. 
  • Sikorski, Roman. Boolean Algebras 3rd. ed. Berlin: Springer-Verlag. 1969. ISBN 978-0-387-04469-9. 
  • Stone, Marshall. The Theory of Representations for Boolean Algebras. Transactions of the American Mathematical Society. 1936, 40: 37–111. ISSN 0002-9947. 
  • 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:
    • Tarski, Alfred. Sur les classes closes par rapport à certaines opérations élémentaires. Fundamenta Mathematicae. 1929, 16: 195–97. ISSN 0016-2736. 
    • Tarski, Alfred. Zur Grundlegung der Booleschen Algebra, I. Fundamenta Mathematicae. 1935, 24: 177–98. ISSN 0016-2736. 
  • Vladimirov, D.A. булевы алгебры (Boolean algebras, in Russian, German translation Boolesche Algebren 1974). Nauka (German translation Akademie-Verlag). 1969. 

外部連結

A monograph available free online: