Loading article…
数学および数理論理学において、ブール代数は代数の一分野です。初等代数とは2つの点で異なります。第一に、変数の値は真偽値である真と偽であり、通常は1と0で表されますが、初等代数では変数の値は数値です。第二に、ブール代数では、論理積（and ） （∧）、論理和（or）（∨ ） 、否定（not）（ ¬）などの論理演算子を使用します。一方、初等代数では、加算、乗算、減算、除算などの算術演算子を使用します。したがって、ブール代数は、初等代数が数値演算を記述するのと同様に、論理演算を形式的に記述する方法と言えます。
ブール代数は、ジョージ・ブールが最初の著書『論理の数学的分析』（1847年）で導入し[ 1 ] 、彼の著書『思考の法則の調査』（1854年）でより詳細に説明しました[ 2 ] 。ハンティントンによれば、ブール代数という用語はヘンリー・M・シェファーが1913年に初めて提案しましたが[ 3 ] 、チャールズ・サンダース・パースは1880年に著書『最も単純な数学』の第1章に「定数1つのブール代数」というタイトルを付けています[ 4 ]。ブール代数はデジタルエレクトロニクスの開発において基礎的な役割を果たしており、現代のすべてのプログラミング言語で提供されています。また、集合論や統計学でも使用されています[ 5 ]。
ブール代数の先駆けは、ゴットフリート・ヴィルヘルム・ライプニッツの概念代数であった。易経に関連した二進法の使用は、ライプニッツの普遍的特性の中心であった。それは最終的に概念代数の基礎を築いた。[ 6 ]ライプニッツの概念代数は、演繹的に集合のブール代数と等価である。[ 7 ]
ブール代数は、抽象代数や数理論理学の現代的な発展に先立つものでしたが、両分野の起源と関連していると考えられています。[ 8 ]抽象的な設定では、ブール代数は19世紀後半にジェボンズ、シュレーダー、ハンティントンらによって完成され、（抽象的な）数学的構造の現代的な概念に至りました。[ 8 ]例えば、集合代数の式をブール代数の式に変換することで操作できるという経験的観察は、集合代数がブール代数である（不定冠詞に注意）という現代的な用語で説明されます。実際、MHストーンは1936年に、すべてのブール代数は集合の体と同型であることを証明しました。[ 9 ] [ 10 ]
1930年代、スイッチング回路を研究していたクロード・シャノンは、この設定でもブール代数の規則を適用できることに気づき、[ 11 ]論理ゲートの観点から代数的な手段で回路を解析および設計する方法としてスイッチング代数を導入しました。シャノンはすでに抽象的な数学的装置を自由に使える状態にあったため、スイッチング代数を2要素ブール代数として定式化しました。現代の回路工学の分野では、他のブール代数を考慮する必要はほとんどないため、「スイッチング代数」と「ブール代数」はしばしば同義語として使用されます。[ 12 ] [ 13 ] [ 14 ]
ブール関数の効率的な実装は、組み合わせ論理回路の設計における基本的な問題です。超大規模集積回路（VLSI）向けの最新の電子設計自動化ツールは、論理合成と形式検証のために、（縮小順序付き）二分決定図（BDD）として知られるブール関数の効率的な表現に依存することがよくあります。[ 15 ]
古典的な命題論理で表現できる論理文は、ブール代数で同等の表現を持つ。そのため、ブール論理は、このように実行される命題論理を表すために使われることがある。[ 16 ] [ 17 ] [ 18 ]ブール代数は、一階述語論理のような量化子を用いた論理式を捉えるには十分ではない。
数学論理の発展はブールのプログラムに従わなかったものの、彼の代数と論理のつながりは、後に代数論理の枠組みの中で確固たるものとなり、代数論理は他の多くの論理の代数システムも研究する。[ 8 ]与えられたブール（命題）式の変数を、式が真と評価されるように割り当てることができるかどうかを判定する問題は、ブール充足可能性問題（SAT）と呼ばれ、理論計算機科学にとって重要であり、 NP完全であることが示された最初の問題である。密接に関連する計算モデルであるブール回路は、（アルゴリズムの）時間計算量を回路の複雑さに関連付ける。
初等代数では式は主に数を表しますが、ブール代数では、式は偽と真という真理値 を表します。これらの値はビット0 と 1 で表されます。これらは1 + 1 = 2 となる整数0 と 1 のように振る舞うのではなく、 2 要素体GF(2)の要素、つまり2 を法とする整数演算( 1 + 1 = 0となる) と同一視できます。加算と乗算は、それぞれ XOR (排他的論理和) と AND (論理積) のブール演算の役割を果たします。論理和x ∨ y (包含的論理和)はx + y − xyと定義でき、否定¬ x は1 − xと定義できます。GF (2)では、− は+に置き換えることができます。これらは同じ演算を表すからです。しかし、このブール演算の記述方法では、通常の整数の算術演算を適用できます（これは、GF(2)が実装されていないプログラミング言語を使用する場合に役立つ可能性があります）。
ブール代数では、値が集合{0,1}に含まれる関数も扱います。ビット列は、このような関数の一般的な例です。もう一つの一般的な例は、集合Eの部分集合全体です。Eの部分集合Fに対して、F内では値1、F外では値0をとる指示関数を定義できます。最も一般的な例はブール代数の集合要素であり、上記すべてはブール代数のインスタンスです。
初等代数と同様に、理論の純粋に等式的な部分は、変数の明示的な値を考慮せずに展開することができる。[ 19 ]
初等代数には 4 つの演算 (加算、減算、乗算、除算) がありますが、ブール代数には 3 つの基本演算 (論理積、論理和、否定) しかなく、これらは対応する二項演算子AND (）または（) および単項演算子NOT (）はまとめてブール演算子と呼ばれます。[ 20 ]ブール代数において、0 と 1 の論理値を格納する変数はブール変数と呼ばれます。これらは真または偽の値を格納するために使用されます。[ 21 ]ブール変数xとyの基本演算は次のように定義されます。
あるいは、 x ∧ y、x ∨ y、および ¬ xの値は、真理値表を使用して次のように表にまとめることができます。[ 22 ]
式中で使用される場合、演算子は優先順位規則に従って適用されます。初等代数と同様に、括弧内の式は優先順位規則に従って最初に評価されます。[ 23 ]
真理値0と1を整数として解釈する場合、これらの演算は通常の算術演算（x + yは加算、xyは乗算を使用）または最小値/最大値関数で表現できます。
否定と他の 2 つの演算のうちの 1 つだけが基本であると考える人もいるかもしれない。なぜなら、否定と選言によって論理積を定義でき、またその逆も可能となる以下の恒等式 (ド・モルガンの法則) があるからである。[ 24 ]
基本演算から構成される演算には、とりわけ以下のものが含まれる。
これらの定義から、考えられる4つの入力すべてに対するこれらの演算の値を示す以下の真理値表が得られます。
ブール代数の法則とは、2 つのブール項間の恒等式、例えば x ∨ ( y ∨ z ) = ( x ∨ y ) ∨ z のような式です。ここで、ブール項とは、変数と定数0および1から演算∧、∨、および ¬ を使用して構築された式として定義されます。この概念は、⊕、→、および ≡ などの他のブール演算を含む項にも拡張できますが、法則が適用される目的においては、そのような拡張は不要です。そのような目的には、ブール代数をブール法則の任意のモデルとして定義すること、および、y ∧ z = z ∧ yからx ∨ ( y ∧ z ) = x ∨ ( z ∧ y )を導出する（§ブール代数の公理化で扱われている）ように、古い法則から新しい法則を導出する手段としてのブール代数の定義が含まれます。
ブール代数は、∨ を加算に、∧ を乗算に対応させると、通常の代数と同じ法則の多くを満たします。特に、次の法則は両方の種類の代数に共通しています。[ 25 ] [ 26 ]
以下の法則はブール代数では成り立つが、通常の代数では成り立たない。
上記の第3法則でx = 2とすると、2 × 2 = 4となるため、これは通常の代数法則ではないことがわかります。残りの5つの法則は、すべての変数を 1 とすることで、通常の代数で反証できます。たとえば、吸収法則 1 では、左辺は1(1 + 1) = 2となり、右辺は 1 となります (以下同様)。
これまで扱ってきた法則はすべて論理積と論理和に関するものです。これらの演算は、いずれかの引数を変更しても出力は変化しないか、入力と同じように変化するという性質を持っています。言い換えれば、任意の変数を 0 から 1 に変更しても、出力が 1 から 0 に変わることはありません。このような性質を持つ演算は単調であると言われます。したがって、これまでの公理はすべて単調ブール論理に関するものでした。非単調性は、補数 ¬ を介して次のように導入されます。[ 5 ]
補数演算は、以下の2つの法則によって定義される。
否定のすべての性質（以下の法則を含む）は、上記の２つの法則のみから導かれる。[ 5 ]
通常の代数とブール代数の両方において、否定は要素のペアを交換することによって行われるため、どちらの代数においても二重否定法則（対合法則とも呼ばれる）を満たす。
しかし、通常の代数学は2つの法則を満たす
ブール代数はド・モルガンの法則を満たす。
上記の法則は、ブール代数の残りの部分を包含するという意味で、ブール代数を定義します。法則1と2は、単調法則とともにこの目的に十分であり、したがって、ブール代数の法則または公理化の可能な完全なセットの1つとして考えることができます。ブール代数のすべての法則は、これらの公理から論理的に導き出されます。さらに、ブール代数は、 §ブール代数で扱われているように、これらの公理のモデルとして定義できます。
ブール代数の法則をさらに書き記しても、これらの公理から新たな帰結が生じることはなく、また、それらのモデルを排除することもできません。対照的に、同じ法則の一部のみを列挙した場合、その法則から導かれないブール法則が存在する可能性があり、さらに、列挙された法則のモデルの中には、ブール代数ではないものも存在するでしょう。
この公理化は決して唯一のものではなく、また、一部の公理が他の公理から導かれるかどうかに注意を払わず、単に十分な法則が見つかった時点で停止するという選択をしただけであることを考えると、必ずしも最も自然なものでもない。これについては、 § ブール代数の公理化でさらに詳しく説明する。あるいは、ブール法則を任意のトートロジーとして直接定義することによって、公理の中間概念を完全に回避することもできる。トートロジーとは、変数の 0 と 1 を超えるすべての値に対して成り立つ方程式として理解される。[ 27 ] [ 28 ]これらのブール代数の定義はすべて同等であることが示される。
原理：{X, R}が半順序集合であるならば、{X, R(逆)}も半順序集合である。
ブール代数の値を表す記号の選択に特別な意味はありません。0と1をαとβに名前変更しても、一貫して行われる限り、多少見た目の違いはあるものの、依然としてブール代数であることに変わりはありません。
しかし、仮に0と1がそれぞれ1と0に名前変更されたとしましょう。それでもブール代数であることに変わりはなく、同じ値に対して演算が行われます。ただし、∨が以前の∧と同じように動作し、その逆もまた然りとなるため、元のブール代数と全く同じではありません。したがって、0と1が依然として使用されているにもかかわらず、表記法が変更されたことを示すための、いくつかの外観上の違いが残ります。
しかし、値の名前を入れ替えるだけでなく、2つの二項演算の名前も入れ替えると、何が行われたのか痕跡が全く残らなくなります。最終的な結果は、元の結果と全く区別がつかなくなります。真理値表のx ∧ yとx ∨ yの列の位置は入れ替わっていますが、その入れ替えは重要ではありません。
値と演算を、すべてのペアを同時に入れ替えても重要な部分がすべて変化しないように組み合わせることができる場合、各ペアの要素は互いに双対であると呼ばれます。したがって、0と1は双対であり、∧と∨も双対です。双対性原理（ド・モルガンの双対性とも呼ばれる）は、すべての双対ペアを入れ替えてもブール代数は変化しないと主張します。
この交換の一部として行う必要のない変更の 1 つは、補数です。補数は自己双対演算です。恒等演算または何もしない演算x (入力を出力にコピーする) も自己双対です。自己双対演算のより複雑な例は、( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x )です。両方の引数に依存する自己双対二項演算はありません。自己双対演算の合成は自己双対演算です。たとえば、f ( x , y , z ) = ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x )の場合、f ( f ( x , y , z ), x , t )は、4 つの引数x、y、z、tの自己双対演算です。
双対性の原理は、群論の観点から、ブール多項式の集合からそれ自身への一対一写像（自己同型写像）となる関数が正確に4つ存在するという事実によって説明できる。すなわち、恒等関数、補関数、双対関数、および反双対関数（補双対）である。これらの4つの関数は、関数合成に関して群を形成し、クラインの4群と同型であり、ブール多項式の集合に作用する。ウォルター・ゴットシャルクは、この現象には四元性の原理（または四元性の平方）という、より適切な名称がふさわしいと指摘した。[ 5 ]： 21-22
ベン図[ 29 ]は、重なり合う領域を塗りつぶしてブール演算を表すために使用できます。各変数には1つの領域があり、ここでの例ではすべて円形です。領域xの内部と外部は、それぞれ変数xの値1（真）と0（偽）に対応します。塗りつぶしは、領域の各組み合わせに対する演算の値を示し、濃い色は1、薄い色は0を表します（著者によっては逆の規則を使用する場合もあります）。
下の図の 3 つのベン図は、それぞれ論理積x ∧ y、論理和x ∨ y、補集合 ¬ xを表しています。
結合の場合、両方の円の内側の領域が塗りつぶされており、両方の変数が1のときにx∧yが1になることを示しています。他の領域は塗りつぶされずに残されており、他の3つの組み合わせではx∧yが0になることを示しています。
2番目の図は、x ∨ yという論理和を、どちらか一方または両方の円の内側にある領域を塗りつぶすことで表しています。3番目の図は、¬ xという補集合を、円の内側にない領域を塗りつぶすことで表しています。
定数0と1のベン図は示していませんが、それぞれ白い四角と黒い四角で表され、どちらにも円は含まれていないため、自明です。しかし、これらの四角の中にxを表す円を入れることもできます。その場合、それぞれが1つの引数xを持つ関数を表し、 xの値に関係なく同じ値を返します。これを定数関数と呼びます。出力に関しては、定数と定数関数は区別できません。違いは、定数は引数を取らない（ゼロ項演算またはヌル項演算と呼ばれる）のに対し、定数関数は1つの引数を取り、それを無視する（単項演算）という点です。
ベン図は法則を視覚化するのに役立ちます。∧と∨の交換法則は、図の対称性からわかります。交換法則を満たさない二項演算では、xとyを入れ替えると図が水平方向に反転するため、対称的な図にはなりません。交換法則が成り立たない場合、対称性が崩れることになります。
∧と∨の冪等性は、2つの円をスライドさせて重ね合わせることで視覚的に確認できます。∧と∨の両方において、影付きの領域が円全体になることに注目してください。
最初の吸収法則x ∧ ( x ∨ y ) = xを確認するには、 x ∨ yの中央の図から始め、 x円と共通する陰影部分の領域がx円全体であることに注意してください。2 番目の吸収法則x ∨ ( x ∧ y ) = xを確認するには、 x ∧ yの左側の図から始め、 x 円全体を陰影付けしても、前の陰影付けがx円の内側であったため、x円だけが陰影付けされることに注意してください。
二重否定の法則は、3 番目の図の ¬ xの塗りつぶしを補うことで確認できます。これはxの円を塗りつぶします。
第一のド・モルガンの法則(¬ x ) ∧ (¬ y ) = ¬( x ∨ y )を視覚化するには、 x ∨ yの中央の図から始め、両方の円の外側の領域のみが塗りつぶされるように塗りつぶしを補完します。これは、法則の右辺が表す内容です。結果は、x円の外側とy円の外側の両方の領域、つまり両方の外側の結合部分を塗りつぶした場合と同じになります。これは、法則の左辺が表す内容です。
2 番目のド・モルガンの法則、(¬ x ) ∨ (¬ y ) = ¬( x ∧ y )は、2 つの図を入れ替えても同じように機能します。
第一補集合法則x ∧ ¬ x = 0は、 x円の内部と外部には重なりがないことを示しています。第二補集合法則x ∨ ¬ x = 1は、すべてのものがx円の内部か外部のどちらかであることを示しています。
デジタルロジックとは、0と1のブール代数を、回路図を形成するように接続された論理ゲートで構成される電子ハードウェアに適用することです。各ゲートはブール演算を実行し、演算を示す形状によって概略的に表されます。論理積（ANDゲート）、論理和（ORゲート）、および補数（インバータ）のゲートに関連付けられた形状は次のとおりです。[ 30 ]
各ゲートの左側の線は入力ワイヤまたはポートを表します。入力値は、リード線上の電圧で表されます。いわゆる「アクティブハイ」ロジックでは、0はゼロまたは「グランド」に近い電圧で表され、1は電源電圧に近い電圧で表されます。アクティブローでは、この関係が反転します。各ゲートの右側の線は出力ポートを表し、通常は入力ポートと同じ電圧規則に従います。
補数演算はインバータゲートを用いて実現されます。三角形は入力信号をそのまま出力にコピーする動作を表し、出力側の小さな円は入力信号を反転して補数化する実際の動作を表します。このような円を任意のポートに配置する慣例は、入力ポートであろうと出力ポートであろうと、そのポートを通過する信号は通過する過程で補数化されることを意味します。
双対原理、すなわちド・モルガンの法則は、ANDゲートの3つのポートすべてを反転させるとORゲートに変換され、その逆もまた同様である、という原理として理解できます（下図4参照）。ただし、インバータの2つのポートを反転させても、動作は変わりません。
より一般的には、AND ゲートまたは OR ゲートの 3 つのポートの 8 つのサブセットのいずれかを補数にすることができます。結果として得られる 16 通りの可能性から、真理値表に奇数個の 1 が含まれるブール演算は 8 つだけになります。これは、「奇数ビット」が 0 または 1 のいずれかになり、真理値表の 4 つの位置のいずれかに入ることができるためです。バイナリ ブール演算は 16 個あるため、真理値表に偶数個の 1 が含まれる演算は 8 つ残ります。これらの 2 つは定数 0 と 1 (両方の入力を無視するバイナリ演算として) です。4 つは、2 つの入力のうちのちょうど 1 つに非自明に依存する演算、つまりx、y、¬ x、および ¬ yです。残りの 2 つはx ⊕ y (XOR) とその補数x ≡ yです。
「代数」という用語は、主題、すなわち代数の主題と、対象、すなわち代数構造の両方を指します。前述の内容はブール代数について述べてきましたが、本節では、ブール法則の任意のモデルとして一般的に定義されるブール代数と呼ばれる数学的対象を扱います。まず、法則を参照せずに定義できる概念の特殊なケース、すなわち具体的なブール代数から始め、次に一般的な概念の形式的な定義を示します。
具体的なブール代数または集合の体とは、与えられた集合Xの部分集合の空でない集合で、 Xに関する和集合、積集合、補集合の集合演算に関して閉じているものを指します。[ 5 ]
（歴史的には、退化ブール代数、すなわち1要素ブール代数を除外するために、 X自体も空でないことが求められていました。退化ブール代数はすべての等式を満たすため、すべてのブール代数が同じ等式を満たすという規則の唯一の例外となります。しかし、この除外は、等式のみを用いる「ブール代数」の好ましい定義と矛盾します。等式のみを用いて1要素代数を除外する方法がないからです。0 ≠ 1 は 否定等式であるため、除外対象にはなりません。したがって、現代の著者は退化ブール代数を許容し、Xを空としています。）
例 1. Xの冪集合2 X は、 Xのすべての部分集合から構成されます。ここで、 X は任意の集合です。空集合、有限集合、無限集合、または非可算集合でも構いません。
例2．空集合とX。この2要素代数は、具体的なブール代数が無限集合の部分集合から構成されている場合でも有限になり得ることを示しています。Xの部分集合のどの体も空集合とXを含まなければならないことがわかります。したがって、空集合とXが一致するようにXを空集合とすることで得られる退化代数以外に、これより小さい例は存在しません。
例3.有限整数集合と余有限整数集合の集合。ここで、余有限集合とは、有限個の整数のみを除外した集合のことである。これは補集合に関して明らかに閉じており、余有限集合と任意の集合との和集合は余有限集合であるのに対し、2つの有限集合の和集合は有限集合であるため、和集合に関しても閉じている。共通部分は、「有限」と「余有限」を入れ替えた和集合と同様の振る舞いをする。この例は、整数の有限集合が可算個しかないため、可算無限集合である。
例4.例2で述べた点のより複雑な例として、n個の閉曲線によって2n個の領域に分割されたベン図を考えます。Xを、平面上のどの曲線上にもなく、かつベン図内のどこかにあるすべての点の（無限）集合とします。各領域の内部はXの無限部分集合であり、X内のすべての点はちょうど1つの領域に属します。すると、領域の可能なすべての2n個の和集合（空集合とすべての2n個の領域の和集合として得られるXの和集合を含む）は、 Xに関して和集合、積集合、補集合に関して閉じており、具体的なブール代数を形成します。ここでも、具体的なブール代数を形成する無限集合の部分集合は有限個しか存在せず、例2はn =0、つまり曲線がない場合として生じます。
Xの部分集合Y は、インデックス集合Xを持つインデックス付きビットの族で識別でき、 x ∈ Xでインデックス付けされたビットは、x ∈ Yであるかどうかに応じて 1 または 0 になります。（これは、部分集合のいわゆる特性関数概念です。）たとえば、32 ビットのコンピュータ ワードは、集合 {0,1,2,...,31} でインデックス付けされた 32 ビットで構成され、0 と 31 はそれぞれ下位ビットと上位ビットをインデックス付けします。より小さな例として、もしここで、a、b、c は左から右の順にビット位置とみなされ、X の 8 つの部分集合 {}、{ c }、{ b }、{ b , c }、{ a }、{ a, c }、{ a , b }、および { a , b , c } は、それぞれビットベクトル 000、001、010、011、100、101、110、および 111 と識別できます。自然数の集合によってインデックス付けされたビットベクトルは無限のビット列ですが、単位区間 [0,1] の実数によってインデックス付けされたビットベクトルは、従来の方法で記述するには密度が高すぎますが、それでも明確に定義されたインデックス付きファミリーを形成します (区間 [0,1] のすべての点を独立して黒または白に色付けすることを想像してください。黒い点は [0,1] の任意の部分集合を形成します)。
このビットベクトルの観点から、具体的なブール代数は、同じ長さの（より一般的には同じセットでインデックス付けされた）空でないビットベクトルの集合として等価に定義でき、ビットごとの∧、∨、および¬のビットベクトル演算に関して閉じている。例えば、1010∧0110 = 0010、1010∨0110 = 1110、および¬1010 = 0101は、それぞれ積集合、和集合、および補集合のビットベクトル実現である。
上記で扱った集合 {0,1} とそのブール演算は、長さ 1 のビットベクトルの特殊なケースとして理解することができ、ビットベクトルと部分集合の同一視により、1 要素集合の 2 つの部分集合としても理解できます。これはプロトタイプブール代数と呼ばれ、次の観察によって正当化されます。
この観察結果は次のように証明される。確かに、すべての具体的なブール代数が満たす法則は、プロトタイプとなるブール代数も満たす。なぜなら、プロトタイプとなるブール代数は具体的だからである。逆に、ある具体的なブール代数で成り立たない法則は、特定のビット位置で成り立たなかったに違いない。その場合、そのビット位置自体がその法則に対する1ビットの反例となる。非退化性により、空のビットベクトルは1つしかないため、少なくとも1つのビット位置が存在することが保証される。
次のセクションの最終目標は、上記の考察から「具体的」という概念を排除することと理解できる。この目標は、同型を除いてすべてのブール代数は具体的であるという、より強い考察によって達成される。
これまでのブール代数はすべて具体的なものであり、ビットベクトル、あるいはそれと同等に何らかの集合の部分集合から構成されていました。このようなブール代数は、集合と、その集合に対する演算から成り、それらの演算はブール代数の法則を満たすことが示されます。
ブール法則が満たされていることを示す代わりに、集合X 、 Xに対する 2 つの二項演算、および 1 つの単項演算を仮定し、これらの演算がブール代数の法則を満たすことを要求することができます。X の要素はビットベクトルや部分集合である必要はなく、何でも構いません。これにより、より一般的な抽象的な定義が得られます。
この定義においては、演算が法則を満たすようになった経緯（命令によるものか証明によるものか）は関係ありません。すべての具体的なブール代数は（命令ではなく証明によって）法則を満たしており、したがって、すべての具体的なブール代数は、我々の定義によればブール代数です。特定の法則または公理を満たす集合と特定の演算からなるブール代数のこの公理的定義は、現代代数または抽象代数に特徴的な群、環、体などの抽象的な定義と全く類似しています。
補元分配束の公理など、ブール代数の完全な公理化が与えられた場合、この種の代数構造がすべてのブール法則を満たすための十分条件は、それらの公理のみを満たすことである。したがって、以下は同等の定義である。
公理化に関するセクションでは、他の公理化が列挙されており、それらのいずれも同等の定義の基礎とすることができる。
すべての具体的なブール代数はブール代数ですが、すべてのブール代数が具体的である必要はありません。nを平方因子を持たない正の整数、つまり整数の平方で割り切れない整数とします。たとえば、30 は割り切れますが、12 は割り切れません。最大公約数、最小公倍数、およびnへの除算(つまり、¬ x = n / x ) の演算は、引数がnの正の約数である場合に、すべてのブール法則を満たすことが示されます。したがって、これらの約数はブール代数を形成します。これらの約数は集合の部分集合ではないため、nの約数は、私たちの定義によれば具体的ではないブール代数になります。
しかし、 nの各約数がその素因数の集合で表される場合、この非具体的なブール代数は、 nのすべての素因数の集合からなる具体的なブール代数と同型であり、和集合は最小公倍数、積集合は最大公約数、補集合はnへの割り算に対応します。したがって、この例は厳密には具体的ではありませんが、同型と呼ばれるこの表現によって、少なくとも「道徳的に」具体的です。この例は、次の概念の例です。
次の質問に対する答えは、以下のとおり肯定的なものです。
つまり、同型性を除けば、抽象ブール代数と具体ブール代数は同一のものである。この結果は、選択公理よりもやや弱い選択原理であるブール素イデアル定理に基づいている。この強い関係性から、前の節の考察を補強するより弱い結果が導き出され、表現可能性という次の容易な帰結が得られる。
それ自体が表現可能性を意味するわけではないという意味で、より弱いと言えます。ブール代数はここで特別な存在であり、例えば関係代数は追加の構造を持つブール代数ですが、すべての関係代数が関係代数にふさわしい意味で表現可能であるとは限りません。
抽象ブール代数を「ブール法則」を満たす演算の集合として定義すると、それらの法則とは何かという疑問が生じる。単純な答えは「すべてのブール法則」であり、これは0と1のブール代数に対して成り立つすべての等式として定義できる。しかし、そのような法則は無限に存在するため、実際には満足のいく答えとは言えず、有限個の法則が成り立つだけで十分かどうかという疑問が生じる。
ブール代数の場合、答えは「はい」です。上に挙げた有限個の等式で十分です。したがって、ブール代数は有限公理化可能、または有限基底であると言われます。
さらに、必要な方程式の数をさらに減らすことができます。まず、上記の法則のいくつかは、他の法則のいくつかによって暗黙的に導かれます。上記の法則の十分な部分集合は、結合法則、交換法則、吸収法則のペア、∧ の ∨ に対する分配法則（または他の分配法則 ― 1 つで十分です）、および 2 つの補法則から構成されます。実際、これはブール代数を補元付き分配束として公理化する伝統的な方法です。
上記に挙げていない追加の法則を導入することで、必要な方程式のリストをさらに短縮することが可能になります。たとえば、縦棒がシェッファーストローク操作を表す場合、単一の公理これはブール代数を完全に公理化するのに十分である。より一般的な操作を使用して、より長い単一の公理を見つけることも可能である。ブール代数の最小公理を参照のこと。[ 32 ]
命題論理は、ブール代数と密接に関連した論理体系です。 [ 5 ]ブール代数の多くの構文概念は、表記法と用語にわずかな変更を加えるだけで命題論理に引き継がれますが、命題論理の意味論は、命題論理のトートロジー（定理）がブール代数の等式定理に対応するように、ブール代数によって定義されます。
構文的には、すべてのブール項は命題論理の命題式に対応します。ブール代数と命題論理の間のこの変換では、ブール変数x、y、 ... は命題変数(または原子) P、Q 、... になります。x ∨ yのようなブール項は命題式P ∨ Qになります。0 は偽または⊥になり、1 は真または⊤になります。一般的な命題を参照する場合、命題を表すメタ変数 (命題計算の言語外の変数で、命題計算について話すときに使用される) としてギリシャ文字 Φ、Ψ、... を使用すると便利です。
命題論理の意味論は真理値の割り当てに依存します。真理値の割り当ての基本的な考え方は、命題変数が固定されたブール代数の要素にマッピングされ、これらの文字を使用した命題式の真理値は、その式に対応するブール項の値を計算することによって得られるブール代数の要素であるということです。古典意味論では、2要素ブール代数のみが使用され、ブール値意味論では任意のブール代数が考慮されます。トートロジーとは、命題変数を任意のブール代数に（または同等に、2要素ブール代数に）真理値を割り当てるたびに真理値1が割り当てられる命題式のことです。
これらの意味論により、命題論理のトートロジーとブール代数の等式定理との間の変換が可能になります。命題論理のすべてのトートロジー Φ は、ブール方程式 Φ = 1 として表現でき、これはブール代数の定理になります。逆に、ブール代数のすべての定理 Φ = Ψ は、トートロジー (Φ ∨ ¬Ψ) ∧ (¬Φ ∨ Ψ) および (Φ ∧ Ψ) ∨ (¬Φ ∧ ¬Ψ) に対応します。→ が言語に含まれている場合、これらの最後のトートロジーは (Φ → Ψ) ∧ (Ψ → Φ) または 2 つの別々の定理 Φ → Ψ および Ψ → Φ として記述することもできます。≡ が使用可能な場合は、単一のトートロジー Φ ≡ Ψ を使用できます。
命題論理の動機となる応用例の 1 つは、自然言語における命題と演繹的議論の分析です。[ 33 ]命題「もしx = 3 ならば、x + 1 = 4」は + や 1 などの記号の意味に依存しますが、命題「もしx = 3 ならば、x = 3」は依存しません。これは単にその構造によって真であり、「x = 3」を「 x = 4」または「月は緑色のチーズでできている」に置き換えても真のままです。このトートロジーの一般的または抽象的な形式は「もしPならば、P」、またはブール代数の言語ではP → Pです。
Pをx = 3 または他の命題に置き換えることを、その命題によるPのインスタンス化と呼びます。抽象命題でP をインスタンス化した結果を、その命題のインスタンスと呼びます。したがって、 x = 3 → x = 3 は、抽象命題P → Pのインスタンスであるため、トートロジーです。インスタンス化された変数のすべての出現箇所は、 P → x = 3 やx = 3 → x = 4のような無意味な事態を避けるために、同じ命題でインスタンス化されなければなりません。
命題論理では、ブール演算を用いて命題変数から構築される抽象的な命題にのみ注意を限定します。命題論理内でもインスタンス化は可能ですが、それは抽象的な命題によって命題変数をインスタンス化することによってのみ可能です。例えば、Q → P を P → ( Q → P ) でインスタンス化して、インスタンスP → ( ( Q → P ) → P )を生成します。
（命題論理の仕組みの一部としてインスタンス化が利用できるため、命題論理の言語内でメタ変数は不要となる。なぜなら、通常の命題変数は、この言語内で任意の命題を表すものとみなせるからである。メタ変数自体はインスタンス化の範囲外であり、命題論理の言語の一部ではなく、むしろこの文が書かれている、命題論理について語るための同じ言語の一部である。その言語では、命題変数とそのインスタンス化を、異なる構文的実体として区別する必要がある。）
命題論理の公理化とは、公理と呼ばれる一連の恒真式と、古い恒真式から新しい恒真式を生成するための 1 つ以上の推論規則からなるものです。公理系Aにおける証明とは、有限個の空でない命題の列であり、各命題はAの公理のインスタンスであるか、または証明の先に現れる命題からAの何らかの規則によって導かれるものです(これにより循環論法が排除されます)。最後の命題は、証明によって証明される定理です。証明の空でない最初の部分はすべてそれ自体が証明であり、したがって証明中のすべての命題はそれ自体が定理です。公理化は、すべての定理が恒真式である場合に健全であり、すべての恒真式が定理である場合に完全です。[ 34 ]
命題論理は一般的にヒルベルト系として構成され、その演算はブール代数の演算のみであり、その定理はブール定数 1 に等しいブール項であるブール恒真式である。別の形式はシーケント計算であり、これは 2 種類ある。通常の命題論理と同様の命題と、 A ∨ B、A ∧ C、... ⊢ A、B → C、...のような命題のリストのペアであるシーケントである。シーケントの 2 つの半分は、それぞれ前件と後件と呼ばれる。前件またはその一部を表す慣習的なメタ変数は Γ であり、後件の場合は Δ である。したがって、Γ、A ⊢ Δ は、後件がリスト Δ であり、前件がリスト Γ に命題Aが追加されたシーケントを表す。前件はその命題の連言として解釈され、後件はその命題の選言として解釈され、後件自体は前件による後件の含意として解釈される。
含意は、含意とは異なり、後者がブール代数で値を返す二項演算であるのに対し、前者は成り立つか成り立たないかの二項関係である。この意味で、含意は含意の外部形式であり、ブール代数の外部にあることを意味する。つまり、シーケントの読み手も外部にあり、何らかのブール代数で前件と後件を解釈および比較していると考える。⊢ の自然な解釈は、x ≤ yで定義されるブール代数の半順序における ≤ であり、これはx ∨ y = yの場合に限る。外部含意⊢と内部含意 → を一つの論理で混在させるこの能力は、シーケント計算と命題論理の本質的な違いの一つである。[ 35 ]
2つの値の計算としてのブール代数は、コンピュータ回路、コンピュータプログラミング、数理論理学の基礎であり、集合論や統計学などの他の数学分野でも使用されています。[ 5 ]
20世紀初頭、数名の電気技術者は、ブール代数が特定の種類の電気回路の挙動と類似していることを直感的に認識していた。クロード・シャノンは、1937年の修士論文「リレーおよびスイッチング回路の記号解析」の中で、そのような挙動が論理的にブール代数と等価であることを正式に証明した。
今日、あらゆる汎用コンピュータは、2値ブール論理を用いて動作しています。つまり、その電気回路は2値ブール論理の物理的な表現なのです。これは、高速回路や容量性記憶装置における配線の電圧、強磁性体記憶装置における磁区の向き、パンチカードや紙テープの穴など、さまざまな方法で実現されています。（初期のコンピュータの中には、2値論理回路の代わりに10進数回路や機構を用いたものもありました。）
もちろん、任意の媒体で2つ以上の記号を符号化することは可能です。例えば、ワイヤ上で4つの記号からなるアルファベットを符号化するために、それぞれ0、1、2、3ボルトを使用したり、パンチカードの異なるサイズの穴を使用したりすることができます。実際には、高速性、小型化、低消費電力という厳しい制約が相まって、ノイズが大きな問題となります。そのため、1つの箇所で複数の記号が出現する可能性がある場合、記号を区別することが困難になります。デジタル設計者は、1本のワイヤで4つの電圧を区別しようとするのではなく、ワイヤごとに高電圧と低電圧の2つの電圧を使用するという方法を採用しています。
コンピュータは、上記の理由から2値ブール回路を使用します。最も一般的なコンピュータアーキテクチャでは、32または64個の値からなるブール値の順序付きシーケンス（ビットと呼ばれる）を使用します。例：0110100011010110010101010101001011。マシンコード、アセンブリ言語、およびその他の特定のプログラミング言語でプログラミングする場合、プログラマはデータレジスタの低レベルのデジタル構造を扱います。これらのレジスタは電圧で動作し、0ボルトはブール値0を表し、基準電圧（多くの場合+ 5V、+3.3V 、または+1.8V ）はブール値1を表します。このような言語は、数値演算と論理演算の両方をサポートします。この文脈では、「数値」とは、コンピュータがビットのシーケンスをバイナリ数（2進数）として扱い、加算、減算、乗算、除算などの算術演算を実行することを意味します。 「論理演算」とは、2つのビット列間の論理和、論理積、否定といったブール論理演算を指し、一方のビット列の各ビットを他方のビット列の対応するビットと比較します。したがって、プログラマーは必要に応じて数値代数またはブール代数のいずれかの規則を選択して適用することができます。これらの演算群の重要な違いは、前者には桁上がり演算が存在するが、後者には存在しない点です。
2値論理が適している分野としては、法律と数学が挙げられる。日常の気楽な会話では、「たぶん」や「週末だけ」といったニュアンスのある、あるいは複雑な答えも許容される。しかし、法廷や定理に基づく数学といった、より専門的な状況では、被告は有罪か無罪か、命題は真か偽かといった単純なイエス・ノーの答えしか認めず、それ以外の答えを認めないような質問をするのが有利だと考えられている。実際には、この原則は回答者にとって制約となるかもしれないが、単純なイエス・ノーの質問という原則は、司法論理と数学論理の両方において中心的な特徴となっており、2値論理はそれ自体で体系化され、研究されるに値するものとなっている。
集合論の中心概念の一つはメンバーシップである。組織では、初心者、準会員、正会員など、複数のメンバーシップレベルが認められる場合がある。しかし、集合においては、要素はメンバーであるか、メンバーでないかのどちらかである。集合へのメンバーシップ候補は、デジタルコンピュータの配線と全く同じように機能する。各候補はメンバーであるか非メンバーであるかのどちらかであり、各配線がハイかローかのどちらかであるのと同様である。
代数学は、数学的処理が可能なあらゆる分野において基本的なツールであるため、これらの考察を総合すると、2つの値の代数学は、コンピュータハードウェア、数理論理学、集合論にとって根本的に重要なものとなる。
2値論理は、特にブール領域 {0, 1} を単位区間 [0,1] に置き換えることで、多値論理に拡張できます。この場合、0 または 1 の値のみを取るのではなく、0 と 1 の間の任意の値を想定できます。代数的には、否定 (NOT) は 1 − xに、論理積 (AND) は乗算 ( xy ) に、論理和 (OR) はド・モルガンの法則によって定義されます。これらの値を論理的真理値として解釈すると、ファジー論理と確率論理の基礎となる多値論理が得られます。これらの解釈では、値は真理の「度合い」、つまり命題がどの程度真であるか、または命題が真である確率として解釈されます。
ブール演算の本来の応用分野は数理論理学であり、そこでは個々の数式の真偽値（真または偽）を組み合わせる。
英語などの自然言語には、特に論理積 ( and )、論理和 ( or )、否定 ( not )、含意 ( implies ) など、いくつかのブール演算を表す単語があります。しかし、not はand notと同義です。「ブロックはテーブルの上にある」や「猫は牛乳を飲む」など、素朴に真か偽かのどちらかである状況的主張を組み合わせる場合、これらの論理結合子の意味は、多くの場合、対応する論理的意味を持ちます。しかし、「ジムはドアを通り抜けた」などの行動の説明では、交換法則の不成立などの相違に気づき始めます。たとえば、「ジムはドアを開けた」と「ジムはドアを通り抜けた」の順序での結合は、通常and がand thenを意味するため、逆の順序での結合と等価ではありません。質問も同様です。「空は青いですか、そしてなぜ空は青いのですか？」という順序は、逆の順序よりも意味が通じます。行動に関する結合命令は、get dressed and go to schoolのように、行動の主張に似ています。「私を愛するか、私を去るか」や「魚を釣るか、餌を切るか」といった選言的な命令は、一方の選択肢が好ましくないという含意によって非対称になる傾向があります。「tea」と「milk」のような結合名詞は、一般的に集合の和集合のように集合を表し、「tea or milk」は選択肢を表します。しかし、文脈によってはこれらの意味が逆転することもあり、 「 your choices are coffee and tea」は通常、「 your choices are coffee or tea (選択肢)」と同じ意味になります。「I don't not like milk」のような二重否定は、文字通り「私は牛乳が好きです」という意味になることはほとんどなく、むしろ何らかの曖昧さを伝え、第三の可能性を示唆しているかのようです。「Not not P」は「確かにP」と大まかに解釈できますが、Pは必然的に「not not P」を意味しますが、英語ではその逆は疑わしく、直観主義論理と同様です。自然言語における接続詞の非常に独特な用法を考慮すると、ブール代数はそれらを解釈するための信頼できる枠組みとは考えられません。
デジタル論理では、個々のワイヤで伝送されるビットを結合するためにブール演算が使用され、それによってビットは{ 0,1}の範囲で解釈されます。n個の同一のバイナリゲートからなるベクトルを使用して、それぞれnビットの2つのビットベクトルを結合する場合、個々のビット演算は、 2<sup> n</sup>個の要素を持つブール代数の値に対する単一の演算としてまとめて理解できます。
素朴な集合論では、ブール演算は与えられた集合Xの部分集合に作用するものとして解釈されます。先に見たように、この動作はビットベクトルの座標ごとの組み合わせと完全に一致しており、2 つの集合の和集合は 2 つのビットベクトルの論理和に対応し、以下同様です。
3 つのジェネレータに基づく 256 要素の自由ブール代数は、ラスタグラフィックスに基づくコンピュータ ディスプレイで使用されています。ラスタグラフィックスでは、ビット ブレットを使用してピクセルで構成される領域全体を操作し、ブール演算を使用してソース領域とデスティネーションをどのように組み合わせるかを指定します。通常、マスクと呼ばれる 3 番目の領域の助けを借りて、この組み合わせが行われます。最新のビデオ カードは、この目的のために2 2 3 = 256個の三値演算すべてを提供し、演算の選択は 1 バイト (8 ビット) のパラメータで行います。定数SRC = 0xaaまたは0b10101010、DST = 0xccまたは0b11001100、およびMSK = 0xf0または0b11110000を使用すると、(ソースとデスティネーションを XOR し、その結果をマスクと AND することを意味する) などのブール演算を、コンパイル時に計算されたバイト (例では0x80、単に の場合は0x88など) を示す定数として直接書き込むことができます。実行時には、ビデオ カードは、元の式で示されるラスタ操作としてバイトを統一的に解釈します。この方法では、非常に少ないハードウェアしか必要とせず、式の複雑さとは全く無関係に時間がかかります。(SRC^DST)&MSK(SRC^DST)&MSKSRC^DST
コンピュータ支援設計用のソリッドモデリングシステムは、オブジェクトを他のオブジェクトから構築するためのさまざまな方法を提供しており、ブール演算による組み合わせもその1つです。この方法では、オブジェクトが存在する空間はボクセル（2次元グラフィックスのピクセルの3次元版）の集合Sとして理解され、形状はSの部分集合として定義されるため、オブジェクトは和集合、積集合などを介して集合として組み合わせることができます。明らかな用途の1つは、単純な形状から複雑な形状を単純に和集合として構築することです。もう1つの用途は、材料の除去として理解される彫刻です。物理的な機械で物理的な材料に対して実行できる研削、フライス加工、ルーティング、または穴あけ操作は、集合論で集合差であるブール演算x ∧ ¬ yまたはx − yを使用してコンピュータ上でシミュレートできます。これは、 xの要素からyの要素を除去します。したがって、加工する形状と除去する材料の2つの形状が与えられた場合、前者を加工して後者を除去する結果は、単純にそれらの集合差として記述されます。
検索エンジンのクエリもブール論理を使用します。このアプリケーションでは、インターネット上の各ウェブページは「集合」の「要素」とみなすことができます。以下の例では、Googleがサポートする構文を使用しています。[ NB 1 ]
「検索語句1」「検索語句2」
「検索語1」または「検索語2」
「検索語1」−「検索語2」
「検索語1」かつ（「検索語2」または「検索語3」）
{{cite book}}ISBN /日付の不一致（ヘルプ）