布林代數
布林代數(英語: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一樣的符號p∨q;而最大下界(交或下確界)被表示為同邏輯AND一樣的符號p∧q。
這種格釋義有助於一般化為海廷代數,它是免除要麼一個陳述要麼它的否定必須為真的限制的布林代數。海廷代數對應於直覺邏輯,而布林代數對應於經典邏輯。
布林代數又譯為布爾代數,然而布林代數得名於喬治·布爾,他是愛爾蘭科克的皇后學院的英國數學家。布林(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 Cohen、Dana 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)'。
總結
布林代數的各種運算同時也被應用於集合論和邏輯學,在不同的上下文有不同的名稱。具體的符號和名稱如下:
此條目需要精通或熟悉相關主題的編者參與及協助編輯。 (2015年11月2日) |
運算符號 | 布林代數 | 集合論 | 邏輯學 | 邏輯門 | 溫氏圖 |
---|---|---|---|---|---|
0或 | 底 | 空集 | 偽 | 低電位 | |
1或 | 頂 | 全集 | 真 | 高電位 | |
¬或~或'或c | 補集 | 非 | 反相器 | ||
∧或∩ | 下確界 | 交集 | 與 | 及閘 | |
∨或∪ | 上確界 | 併集 | 或 | 或閘 | |
或 | 補 | 相對補集 | |||
-或 | 減 | 差集 | 實質非蘊涵 | 蘊含非閘 | |
⊕或Δ | 對稱差 | 對稱差 | 異或 | 異或閘 | |
→ | 條件 | 條件 | 蘊含閘 | ||
↔ | 雙向條件 | 雙條件 | 同或閘 | ||
|或↑ | 謝費爾豎線 | 與非 | 反及閘 | ||
↓ | 皮爾斯箭頭 | 或非 | 反或閘 |
例子
- 最簡單的布林代數只有兩個元素0和1,並通過如下規則定義:
|
|
|
- 任何給定集合S的冪集(子集的集合)形成有兩個運算∨ := ∪ (並)和∧ := ∩ (交)的布林代數。最小的元素0是空集而最大元素1是集合S自身。
- 有限的或餘有限的集合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的布林代數。
原型布林代數
在k元素集合X上有kkn個n元運算f: Xn→X,因此在{0,1}上有22n個n元運算。所以得出所有布林代數,不論大小都兩個常數或「零元素」運算,四個一元運算,16個二元運算,256個三元運算,以此類推,它們叫做給定布林代數的布林運算。只有一個例外就是一個元素的布林代數,它叫做退化的或平凡的(被一些早期作者禁用),布林代數的所有運算可以被證明是獨特的。(在退化情況下,給定元數的所有運算都是同樣的運算因為對所有輸入都返回同樣結果。)
在{0,1}上的運算可以用真值表展出,選取0和1為真值假和真。它們可以按統一和不依賴應用的方式列出,允許我們命名或至少單獨列出它們。這些名字對布林運算提供方便的簡寫。n元運算的名字是2n位的二進制數。有22n個這種運算,你不能得到更簡明的命名法了!
下面展示元數從0到2的所有運算的這種格局和關聯的名字。
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
這些表格繼續到更高元數上,對n元有2n行,每個行給出n個變數x0,…xn−1的一個求值或繫結,而每列都有表頭nfi,它們給出第i個n元運算nfi(x0,…,xn−1)在這個求值下的值。運算包括變數本身,例如1f2是x0而2f10是x0 (作為它的一元對應者的兩個復件)而2f12是x1 (沒有一元對應者)。否定或補¬x0出現為1f1再次出現為2f5,連同2f3 (¬x1在1元時沒有出現),析取或並x0∨x1出現為2f14,合取或交x0∧x1出現為2f8,蘊涵x0→x1出現為2f13,異或或對稱差x0⊕x1出現為2f6,差集x0−x1出現為2f2等等。對布林函數的其他命名或表示可參見零階邏輯。
作為關於它的形式而非內容的次要詳情,一個代數的運算傳統上組織為一個列表。我們這裏通過在{0,1}上有限運算索引了布林代數的運算,上述真值表表示的排序首先按元數,其次為每個元數運算的列出表格。給定元數的列表次序是如下兩個規則確定的。
- (i)表格左半部分的第i行是i的二進制表示,最低有效位或第0位在最左(「小端」次序,最初由艾倫·圖靈提議,所以可不無合理的叫做圖靈序)。
- (ii)表格的右半部分的第j列是j的二進制表示,還是按小端次序。在效果上運算的下標就是這個運算的真值表。
序理論的性質
同任何格一樣,布林代數 (A, , )可以引出偏序集(A, ≤),通過定義
- a ≤ b 當且僅當a = a b (它也等價於b = a b)。
事實上你還可以把布林代數定義為有最小元素0和最大元素1的分配格 (A, ≤) (考慮為偏序集合),在其中所有的元素x都有補¬x滿足
- x ¬x = 0並且x ¬x = 1
這裏的 和 用來指示兩個元素的下確界(交)和上確界(並)。還有,如果上述意義上的補存在,則它們是可唯一確定的。
代數的和序理論的觀點通常可以交替的使用,並且二者都是有重要用處的,可從泛代數和序理論引入結果和概念。在很多實際例子中次序關係、合取(邏輯與)、析取(邏輯或)和否定(邏輯非)都是自然的可獲得的,所以可直接利用這種聯絡。
對偶原理
你還可以把來自序理論的對偶性的普遍認識應用於布林代數。特別是,所有的布林代數的次序對偶,或者等價的說通過對換 與 所獲得的代數,也是布林代數。一般的說,布林代數的任何有效的規律都可以轉換成另一個有效的對偶規律,通過對換0與1, 與 ,和≤與≥。
同態和同構
在布林代數A和B之間的同態是一個函數f : A → B,對於在A中所有的a, b都有:
- f(a b) = f(a) f(b)
- f(a b) = f(a) 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使得對於所有布林運算mfi有
- h(mfi(x0,…,xm−1)) = mfi(h(x0),…,h(xm−1)).
布林代數的範疇Bool有所有布林代數作為物件和在它們之間的布林同態作為態射。
從兩元素布林代數2到所有布林代數存在唯一的同態,因為所有態射必須保持兩個常數而它們是2的僅有元素。有這種性質的布林代數叫做初始布林代數。可以證明任何兩個初始布林代數都是同構的,所以在同構的意義下2就是初始布林代數。
在其他方向上,從布林代數B到2存在很多同態。任何這種同態都把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 + xy和x y = xy。因為這兩個運算是互逆的,我們可以說每個布林環引發一個布林代數,或反之。此外,對映f : A → B是布林代數的同態,當且僅當它是布林環的同態。布林環和代數的範疇是等價的。
布林代數A的理想是一個子集I,對於在I中的所有x, y我們有x y在I中,並且對於在A中的所有a我們有a x在I中。理想的概念符合在布林環A中環理想的概念。A的理想I叫做「質理想」,如果I ≠ A;並且如果a b在I中總是蘊涵a在I中或b在I中。A的理想I叫做「極大理想」,如果I ≠ A並且真正包含I的唯一的理想是A自身。這些概念符合布林環A中的質理想和極大理想的環理論概念。
「理想」的對偶是濾子。布林代數A的「濾子」是子集p,對於在p中的所有x, y我們有x y在p中,並且對於在A中的所有a,如果a x = a則a在p中。
表示布林代數
可以證實所有的「有限」的布林代數都同構於一個有限集合的所有子集的布林代數。此外,所有的有限的布林代數的元素數目都是二的冪。Stone的著名的布林代數表示定理陳述了「所有的」布林代數A都同構於在某個(完全不連通緊緻郝斯多夫空間)拓撲空間中所有閉開集合的布林代數。
廣義布林代數
從布林代數的公理中去掉存在最大元1的要求產生了「廣義布林代數」。形式的說,分配格B是廣義布林代數,如果它有最小元0並且對於任何B中的元素a和b使得a ≤ b,存在一個元素x使得 並且 。定義 為唯一的x使得 並且 ,我們可以稱結構 是「廣義布林代數」,而 是「廣義布林半格」。
廣義布林格完全就是布林格的理想。
公理化布林代數
在1933年,美國數學家Edward Vermilye Huntington(1874-1952)展示了對布林代數的如下公理化:
- 交換律: x + y = y + x。
- 結合律: (x + y) + z = x + (y + z)。
- Huntington等式: 。
Herbert Robbins接着擺出下列問題: Huntington等式能否替代為它的對偶等式,並且這個新等式與結合律和交換律一起成為布林代數的基礎?通過一組叫做「Robbins代數」的公理,問題就變成了:是否所有的Robbins代數都是布林代數?
Robbins代數的公理化:
- 交換律: x + y = y + x。
- 結合律: (x + y) + z = x + (y + z)。
- Robbins等式: 。
這個問題自從1930年代一直是公開的,並成為阿爾弗雷德·塔斯基和他的學生最喜好的問題。
在1996年,William McCune在阿貢國家實驗室,建造在Larry Wos、Steve Winker和Bob Veroff的工作之上,肯定的回答了這個長期存在的問題:所有的Robbins代數都是布林代數。這項工作是使用McCune的自動推理程式EQP完成的。
其它記號
此條目需要精通或熟悉相關主題的編者參與及協助編輯。 (2015年11月2日) |
布林代數的運算包含下列幾種,基本包含「與」(AND)、「或」(OR)、「非」(NOT),其中由這三種又可組合成NAND(與非)、NOR(或非)、XOR(異或)與XNOR(異或非)。
常見使用記號:「 」表示AND,「+」表示OR(如CNF和DNF中)或者XOR(如ANF中);A中A上面的一橫表示NOT;⊕表示XOR;⊙表示XNOR。
參見
參考資料
- Brown, Stephen; Vranesic, Zvonko, Fundamentals of Digital Logic with VHDL Design 2nd, McGraw–Hill, 2002, ISBN 978-0-07-249938-4. See Section 2.5.
- Cori, Rene; Lascar, Daniel, Mathematical Logic: A Course with Exercises, Oxford University Press, 2000, ISBN 978-0-19-850048-3. See Chapter 2.
- 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.
- Halmos, Paul, Lectures on Boolean Algebras, Van Nostrand, 1963, ISBN 978-0-387-90094-0.
- Halmos, Paul; Givant, Steven, Logic as Algebra, Dolciani Mathematical Expositions, no. 21, Mathematical Association of America, 1998, ISBN 978-0-88385-327-6.
- Huntington, E. V., New sets of independent postulates for the algebra of logic, Transactions of the American Mathematical Society, 1933, 35: 274–304, ISSN 0002-9947.
- Huntington, E. V., Boolean algebra: A correction, Transactions of the American Mathematical Society, 1933, 35: 557–558, ISSN 0002-9947.
- Mendelson, Elliott, Boolean Algebra and Switching Circuits, Schaum's Outline Series in Mathematics, McGraw–Hill, 1970, ISBN 978-0-07-041460-0.
- Monk, J. Donald; Bonnet, R. (編), Handbook of Boolean Algebras, North-Holland, 1989, 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)
- 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.
外部連結
- Boolean Algebra (頁面存檔備份,存於互聯網檔案館) from AllAboutCircuits
- Stanford Encyclopedia of Philosophy: "The Mathematics of Boolean Algebra, (頁面存檔備份,存於互聯網檔案館)" by J. Donald Monk.
- McCune W., 1997. Robbins Algebras Are Boolean (頁面存檔備份,存於互聯網檔案館) JAR 19(3), 263–276
- "Boolean Algebra" (頁面存檔備份,存於互聯網檔案館) by Eric W. Weisstein、The Wolfram Demonstrations Project, 2007.
A monograph available free online:
- Burris, Stanley N.; Sankappanavar, H. P., 1981. A Course in Universal Algebra. (頁面存檔備份,存於互聯網檔案館) Springer-Verlag. ISBN 978-3-540-90578-3.