布林代數

布林代數。特別是，它處理集合運算交集、並集、補集；和邏輯運算與、或、非。例如，邏輯斷言陳述"a"和它的否定¬"a"不能都同時為真，formula_1，相似於集合論斷言子集"A"和它的補集"A""C"有空交集，formula_2。因為真值可以在邏輯電路中表示為二進位制數或電平，這種相似性同樣擴充套件到它們，所以布林代數在電子工程和計算機科學中同在數理邏輯中一樣有很多實踐應用。在電子工程領域專門化了的布林代數也叫做邏輯代數，在計算機科學領域專門化了布林代數也叫做布林邏輯。布林代數也叫做布林格。關聯於格被表示為同邏輯AND一樣的符號"p"∧"q"。這種格釋義有助於一般化為海廷代數，它是免除要麼一個陳述要麼它的否定必須為真的限制的布林代數。海廷代數對應於直覺邏輯，而布林代數對應於經典邏輯。布林代數又譯為布林代數，然而布林代數得名於喬治·布林，他是愛爾蘭科克的皇后學院的英國數學家。布-{}-林在英文中的意思是「布-{}-爾的」，這是為了表彰布-{}-爾的貢獻，而「布-{}-林」只是一種音譯。歷史.術語“布林代數”得名於喬治·布林，他是自學成材的英國數學家。他最初在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，b，c∈A，上面的前三對公理：結合律、交換律和吸收律，意味著 (A,∧,∨)是一個格。所以布林代數也可以定義為一個有補分配格。從這些公理，你可以展示出最小元素0、最大元素1和任何元素a的補a'都是唯一確定的。另外，∀a,b∈A，下列恆等式也成立：其它運算.在上述基本定義基礎上，布林代數中常見的還有以下的運算：注意：-和→，+和↔是對偶的。即a→b = (a-b)'，a↔b=(a+b)'。總結.布林代數的各種運算同時也被應用於集合論和邏輯學，在不同的上下文有不同的名稱。具體的符號和名稱如下：*它應用於邏輯中，解釋0為“偽”，1為“真”，∧為“與”，∨為“或”，¬為“非”。涉及變數和布林運算的表示式代表了陳述形式，兩個這樣的表示式可以使用上面的公理證實為等價的，當且僅當對應的陳述形式是邏輯等價的。*兩元素的布林代數也是在電子工程中用於電路設計；這裡的0和1代表數位電路中一個位的兩種不同狀態，典型的是高和低電壓。電路透過包含變數的表示式來描述，兩個這種表示式對這些變數的所有的值是等價的，當且僅當對應的電路有相同的輸入-輸出行為。此外，所有可能的輸入-輸出行為都可以使用合適的布林表示式來建摸。* 兩元素布林代數在布林代數的一般理論中也是重要的，因為涉及多個變數的等式是在所有布林代數中普遍為真，當且僅當它在兩個元素的布林代數中為真在所有布林代數中是普遍有效的:** ("a" ∨ "b") ∧ (¬"a" ∨ "c") ∧ ("b" ∨ "c") ≡ ("a" ∨ "b") ∧ (¬"a" ∨ "c")** ("a" ∧ "b") ∨ (¬"a" ∧ "c") ∨ ("b" ∧ "c") ≡ ("a" ∧ "b") ∨ (¬"a" ∧ "c")原型布林代數.在"k"元素集合"X"上有"k""k""n"個"n"元運算"f": "X""n"→"X"，因此在{0,1}上有22"n"個"n"元運算。所以得出所有布林代數，不論大小都兩個常量或“零元”運算，四個一元運算，16個二元運算，256個三元運算，以此類推，它們叫做給定布林代數的布林運算。只有一個例外就是一個元素的布林代數，它叫做退化的或平凡的在{0,1}上的運算可以用真值表展出，選取0和1為真值假和真。它們可以按統一和不依賴應用的方式列出，允許我們命名或至少單獨列出它們。這些名字對布林運算提供方便的簡寫。"n"元運算的名字是2"n"位的二進位制數。有22"n"個這種運算，你不能得到更簡明的命名法了!下面展示元數從0到2的所有運算的這種格局和關聯的名字。這些表格繼續到更高元數上，對"n"元有2"n"行，每個行給出"n"個變數"x"0,…"x""n"−1的一個求值或繫結，而每列都有表頭"n""f""i"，它們給出第"i"個"n"元運算"n""f""i"("x"0,…,"x""n"−1)在這個求值下的值。運算包括變數本身，例如1"f"2是"x"0而2"f"10是"x"0 (作為它的一元對應者的兩個復件)而2"f"12是"x"1 (沒有一元對應者)。否定或補¬"x"0出現為1"f"1再次出現為2"f"5，連同2"f"3 (¬"x"1在1元時沒有出現)，析取或並"x"0∨"x"1出現為2"f"14，合取或交"x"0∧"x"1出現為2"f"8，蘊涵"x"0→"x"1出現為2"f"13，異或或對稱差"x"0⊕"x"1出現為2"f"6，差集"x"0−"x"1出現為2"f"2等等。對布林函式的其他命名或表示可階邏輯。作為關於它的形式而非內容的次要詳情，一個代數的運算傳統上組織為一個列表。我們這裡透過在{0,1}上有限運算索引了布林代數的運算，上述真值表表示的排序首先按元數，其次為每個元數運算的列出表格。給定元數的列表次序是如下兩個規則確定的。(i)表格左半部分的第"i"行是"i"的二進位制表示，最低有效位或第0位在最左。(ii)表格的右半部分的第"j"列是"j"的二進位制表示，還是按小端次序。在效果上運算的下標就是這個運算的真值表。序理論的性質.同任何格一樣，布林代數 ("A", formula_3, formula_4)可以引出偏序集，透過定義"a" ≤ "b" 當且僅當"a" = "a" formula_3 "b" (它也等價於"b" = "a" formula_4 "b")。事實上你還可以把布林代數定義為有最小元素0和最大元素1的分配格 ("A", ≤) (考慮為偏序集合)，在其中所有的元素"x"都有補¬"x"滿足"x" formula_3 ¬"x" = 0並且"x" formula_4 ¬"x" = 1這裡的formula_3和formula_4用來指示兩個元素的下確界。還有，如果上述意義上的補存在，則它們是可唯一確定的。代數的和序理論的觀點通常可以交替的使用，並且二者都是有重要用處的，可從泛代數和序理論引入結果和概念。在很多實際例子中次序關係、合取都是自然的可獲得的，所以可直接利用這種聯絡。對偶原理.你還可以把來自序理論的對偶性的普遍認識應用於布林代數。特別是，所有的布林代數的次序對偶，或者等價的說透過對換formula_3與formula_4所獲得的代數，也是布林代數。一般的說，布林代數的任何有效的規律都可以變換成另一個有效的對偶規律，透過對換0與1，formula_3與formula_4，和≤與≥。同態和同構.在布林代數"A"和"B"之間的同態是一個函式"f" : "A" → "B"，對於在"A"中所有的"a", "b"都有:"f"("a" formula_4 "b") = "f""f"("a" formula_3 "b") = "f""f"= 0"f"= 1接著對於在"A"中所有的"a"，"f"(¬"a") = ¬"f"同樣成立。所有布林代數的類，和與之在一起的態射的概念，形成了一個範疇。從"A"到"B"的同構是雙射的從"A"到"B"的同態。同構的逆也是同構，我們稱兩個布林代數"A"和"B"為“同構”的。從布林代數理論的立場上，它們是不能區分的；它們只在它們的元素的符號上有所不同。布林同態.布林同態是在布林代數"A"和"B"之間的函式"h": "A"→"B"使得對於所有布林運算"m""f""i"有"h"("m""f""i"("x"0,…,"x""m"−1)) = "m""f""i"("h"("x"0),…,"h"("x""m"−1)).布林代數的範疇Bool有所有布林代數作為物件和在它們之間的布林同態作為態射。從兩元素布林代數2到所有布林代數存在唯一的同態，因為所有態射必須保持兩個常量而它們是2的僅有元素。有這種性質的布林代數叫做初始布林代數。可以證明任何兩個初始布林代數都是同構的，所以在同構的意義下2就是初始布林代數。在其他方向上，從布林代數"B"到2存在很多同態。任何這種同態都把"B" 劃分成對映到1的元素和對映到0的元素。由前者組成的"B"的子集叫做"B"的超濾子。在"B"是有限的時候，它的超濾子配對於它的原子；一個原子被對映到1而其他被對映到0。"B"的每個超濾子因此由"B"的一個原子和所有其上的元素組成；所以精確的有"B"的一半元素在這個超濾子中，並且有和原子一樣的多的超濾子。對於無限布林代數，超濾子的概念變得相當微妙。大於等於原子的那些元素總是形成超濾子，但是很多其他集合也能形成；例如在整數的有限和餘有限集合的布林代數中，餘有限集合形成了超濾子即使它們中沒有原子。類似的整數的冪集有包含給定整數的所有子集的集合作為超濾子之一；有可數多個這種“標準”超濾子，它們可以用整數自身來識別，但是還有不可數多個“非標準”超濾子。這些形成了非標準分析的基礎，它提供了對這種經典不相容物件作為無窮小和delta函式的表述。布林環、理想和濾子.每個布林代數 ("A", formula_3, formula_4)都引出一個環)和"a" * "b" = "a" formula_3 "b"。這個環的零元素符合布林代數的0；環的乘法單位元素是布林代數的1。這個環有對於"A"中的所有的"a"保持"a" * "a" = "a"的性質；有這種性質的環叫做布林環。反過來，如果給出布林環"A"，我們可以把它轉換成布林代數，透過定義"x" formula_4 "y" = "x" + "y" + "xy"和"x" formula_3 "y" = "xy"。因為這兩個運算是互逆的，我們可以說每個布林環引發一個布林代數，或反之。此外，對映"f" : "A" → "B"是布林代數的同態，當且僅當它是布林環的同態。布林環和代數的範疇是等價的。布林代數"A"的理想是一個子集"I"，對於在"I"中的所有"x", "y"我們有"x" formula_4 "y"在"I"中，並且對於在"A"中的所有"a"我們有"a" formula_3 "x"在"I"中。理想的概念符合在布林環"A"中環理想的概念。"A"的理想"I"叫做“素理想”，如果"I" ≠ "A"；並且如果"a" formula_3 "b"在"I"中總是蘊涵"a"在"I"中或"b"在"I"中。"A"的理想"I"叫做“極大理想”，如果"I" ≠ "A"並且真正包含"I"的唯一的理想是"A"自身。這些概念符合布林環"A"中的素理想和極大理想的環理論概念。“理想”的對偶是濾子。布林代數"A"的“濾子”是子集"p"，對於在"p"中的所有"x", "y"我們有"x" formula_3 "y"在"p"中，並且對於在"A"中的所有"a"，如果"a" formula_4 "x" = "a"則"a"在"p"中。表示布林代數.可以證實所有的“有限”的布林代數都同構於一個有限集合的所有子集的布林代數。此外，所有的有限的布林代數的元素-{}-數目都是二的冪。Stone的著名的布林代數表示定理陳述了“所有的”布林代數"A"都同構於在某個拓撲空間中所有閉開集合的布林代數。廣義布林代數.從布林代數的公理中去掉存在最大元1的要求產生了“廣義布林代數”。形式的說，分配格"B"是廣義布林代數，如果它有最小元0並且對於任何"B"中的元素"a"和"b"使得"a" ≤ "b"，存在一個元素"x"使得formula_32並且formula_33。定義formula_34為唯一的"x"使得formula_35並且formula_36，我們可以稱結構formula_37是“廣義布林代數”，而formula_38是“廣義布林半格”。廣義布林格完全就是布林格的理想。公理化布林代數.在1933年，美國數學家Edward Vermilye Huntington展示了對布林代數的如下公理化:Herbert Robbins接著擺出下列問題: Huntington等式能否替代為它的對偶等式，並且這個新等式與結合律和交換律一起成為布林代數的基礎?透過一組叫做“Robbins代數”的公理，問題就變成了：是否所有的Robbins代數都是布林代數?Robbins代數的公理化:這個問題自從1930年代一直是公開的，併成為阿爾弗雷德·塔斯基和他的學生最喜好的問題。在1996年，William McCune在阿貢國家實驗室，建造在Larry Wos、Steve Winker和Bob Veroff的工作之上，肯定的回答了這個長期存在的問題：所有的Robbins代數都是布林代數。這項工作是使用McCune的自動推理程式EQP完成的。其它記號.布林代數的運算包含下列幾種，基本包含“與”(AND)、“或”(OR)、“非”(NOT)，其中由這三種又可組合成NAND。常見使用記號：“formula_41”表示AND，“＋”表示OR；A中A上面的一橫表示NOT；⊕表示XOR；⊙表示XNOR。A monograph available free online: