ブール代数

数学および数理論理学において、ブール代数は代数の一分野です。ブール代数は初等代数とは2つの点で異なります。第1に、変数の値は真理値trueとfalse であり、通常は 1 と 0 で表されますが、初等代数では変数の値は数値です。第2に、ブール代数は、 ∧で表される連言( and ) 、∨で表される選言( or ) 、¬で表される否定( not )などの論理演算子を使用します。一方、初等代数では、加算、乗算、減算、除算などの算術演算子を使用します。したがって、ブール代数は、初等代数が数値演算を記述するのと同じ方法で 論理演算を記述する正式な方法です。

ブール代数は、ジョージ・ブールが処女作『論理の数学的分析』（1847年）^{[ 1 ]}で導入し、より詳しくは『思考の法則の探究』 （1854年）で述べられました。^{[ 2 ]}ハンティントンによれば、ブール代数という用語を初めて提唱したのは1913年のヘンリー・M・シェファーです。 ^{[ 3 ]}ただし、チャールズ・サンダース・パースは1880年に『最も単純な数学』の第一章に「定数1つを持つブール代数」という題名を付けました。^{[ 4 ]}ブール代数はデジタルエレクトロニクスの発展において基礎となり、現代のすべてのプログラミング言語に採用されています。集合論や統計学にも用いられています。^{[ 5 ]}

歴史

ブール代数の先駆者は、ゴットフリート・ヴィルヘルム・ライプニッツの概念代数である。易経における二項の使用は、ライプニッツの普遍性（characteristica universalis）の中心的概念であった。これは最終的に概念代数の基礎を築いた。^{[ 6 ]}ライプニッツの概念代数は、集合のブール代数と演繹的に同値である。^{[ 7 ]}

ブール代数は抽象代数学や数理論理学の現代的な発展に先行していたが、両分野の起源と関連していると見なされている。^{[ 8 ]}抽象的な設定では、ブール代数は 19 世紀後半にジェヴォンズ、シュレーダー、ハンチントンらによって完成され、（抽象的な）数学的構造という現代的な概念に至った。^{[ 8 ]}例えば、集合代数の式をブール代数の式に変換することで操作できるという経験的観察は、現代的な言葉で言えば、集合代数はブール代数である（不定冠詞 に注意）と説明される。実際、MHストーンは 1936 年にすべてのブール代数が集合体と同型であることを証明した。^{[ 9 ] [ 10 ]}

1930年代、クロード・シャノンはスイッチング回路を研究していた際、ブール代数の規則をこの状況にも適用できることに気づき^{[ 11 ]} 、論理ゲートを用いた代数的手法で回路を解析・設計する方法としてスイッチング代数を導入した。シャノンは既に抽象的な数学的装置を利用可能であったため、スイッチング代数を2要素ブール代数と名付けた。現代の回路工学の分野では、他のブール代数を考慮する必要性はほとんどないため、「スイッチング代数」と「ブール代数」はしばしば互換的に使用される。^{[ 12 ] [ 13 ] [ 14 ]}

ブール関数の効率的な実装は、組み合わせ論理回路の設計における基本的な問題です。超大規模集積回路（VLSI）回路向けの現代の電子設計自動化ツールは、論理合成や形式検証において、（縮約順序付き）二分決定図（BDD）と呼ばれるブール関数の効率的な表現を利用することがよくあります。^{[ 15 ]}

古典的な命題計算で表現できる論理文は、ブール代数でも同等の表現を持つ。そのため、ブール論理は、このように実行される命題計算を表すために用いられることがある。^{[ 16 ] [ 17 ] [ 18 ]}ブール代数は、一階述語論理のような量指定子を用いた論理式を表現するには不十分である。

数理論理学の発展はブールの計画に沿わなかったが、ブールの代数と論理の関係は、他の多くの論理の代数体系も研究する代数論理学の分野で後に確固たる基盤を得た。 ^{[ 8 ]}与えられたブール（命題）式の変数を、式が真と評価されるように割り当てることができるかどうかを判断する問題は、ブール充足可能性問題（SAT）と呼ばれ、 NP完全であることが示された最初の問題であるため、理論計算機科学にとって重要である。ブール回路として知られる密接に関連する計算モデルは、（アルゴリズムの）時間計算量と回路計算量を関連付けている。

価値観

初等代数では式は主に数値を表しますが、ブール代数では、式は真理値falseとtrueを表します。これらの値は、ビット、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 つの演算（加算、減算、乗算、除算）がありますが、ブール代数には、対応する二項演算子AND ( ) と OR ( )、および単項演算子NOT ( ) で表現される、論理積、論理和、否定の 3 つの基本演算しかありません。これらをまとめてブール演算子と呼びます。^{[ 20 ]}ブール代数では、論理値 0 と 1 を格納する変数をブール変数と呼びます。これらは、真または偽の値を格納するために使用されます。^{[ 21 ]}ブール変数xとyの基本演算は次のように定義されます。${\displaystyle \land}$ ${\displaystyle \lor}$ ${\displaystyle \neg}$

論理演算 オペレーター 表記 代替表記 意味 接続詞 そして x ∧ y xおよびy、 K xy x ∧ y = 1 の場合x = y = 1、それ以外の場合はx ∧ y = 0 分離 または x ∨ y xまたはy、 A xy x = y = 0 の場合x ∨ y = 0、それ以外の場合x ∨ y = 1 否定 ない ¬ x NOT x、 N x、x̅、x'、 ! x ¬ x = 1 の場合x = 0、x = 0 の場合¬ x = 1

あるいは、 x∧y 、x∨y、¬xの値は、次のように真理値表を使って^表すことで表すことができる。 ^{[ 22} ]

${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\wedge y}$ ${\displaystyle x\vee y}$ 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1

${\displaystyle x}$ ${\displaystyle \neg x}$ 0 1 1 0

式の中で使用される場合、演算子は優先順位に従って適用されます。初等代数と同様に、括弧内の式は優先順位に従って最初に評価されます。^{[ 23 ]}

真理値 0 と 1 が整数として解釈される場合、これらの演算は通常の算術演算 ( x + yは加算を使用し、xy は乗算を使用します) または最小/最大関数で表現できます。

${\displaystyle {\begin{aligned}x\wedge y&=xy=\min(x,y)\\x\vee y&=x+y-xy=x+y(1-x)=\max(x,y)\\\neg x&=1-x\end{aligned}}}$

否定と他の2つの演算のうち1つだけが基本的な演算であると考える人もいるかもしれない。それは、次のような等式により、否定と選言によって連言を定義でき、またその逆も成り立つからである（ド・モルガンの法則）。^{[ 24 ]}

${\displaystyle {\begin{aligned}x\wedge y&=\neg (\neg x\vee \neg y)\\x\vee y&=\neg (\neg x\wedge \neg y)\end{aligned}}}$

二次操作

基本操作から構成される操作には、次のようなものがあります。

材料条件：	${\textstyle x\rightarrow y=\neg {x}\vee y}$
材料の双条件:	${\textstyle x\leftrightarrow y=(x\land y)\lor (\neg x\land \neg y)=(x\lor \neg y)\land (\neg x\lor y)}$
排他的論理和（XOR）:	${\textstyle x\oplus y=\neg (x\leftrightarrow y)=(x\vee y)\wedge \neg (x\wedge y)=(x\vee y)\wedge (\neg x\vee \neg y)=(x\wedge \neg y)\vee (\neg x\wedge y)}$

これらの定義により、4 つの可能な入力すべてに対するこれらの演算の値を示す次の真理値表が生成されます。

二次操作。表1

${\displaystyle x}$	${\displaystyle y}$	${\displaystyle x\rightarrow y}$	${\displaystyle x\oplus y}$	${\displaystyle x\leftrightarrow y,x\equiv y}$
0	0	1	0	1
1	0	0	1	0
0	1	1	1	0
1	1	1	0	1

材料条件付き

最初の演算x  →  y、または C xyは、物質的含意と呼ばれます。xが真の場合、式x  →  yの結果はyの結果とみなされます（例えば、xが真でyが偽の場合、x  →  yも偽です）。しかし、xが偽の場合、 yの値は無視できます。ただし、この演算は何らかのブール値を返す必要があり、選択肢は2つしかありません。したがって、定義上、 x が偽の場合、x  →  yは真です（関連性ロジックは、誤った前提を持つ含意を真でも偽でもないものとして扱うことで、この定義を拒否します）。

排他的論理和（XOR）

2番目の演算x  ⊕  y、または J xyは、包含的な論理和である論理和と区別するために、排他的論理和（しばしばXORと略される）と呼ばれます。これは、 xとyの両方が真となる可能性を排除します（例えば、表を参照）。つまり、両方が真であれば結果は偽となります。算術的に定義すると、これは mod 2 が 1 + 1 = 0 となる加算です。

論理的等価性

3番目の演算、排他的論理和の補数は、同値性、つまりブール等価性です。x  ≡  y、つまり E xyは、 xとy が同じ値を持つ場合にのみ真となります。したがって、その補数であるx  ⊕  y は、 x  ≠  yと理解でき、 xとy が異なる場合にのみ真となります。したがって、算術 mod 2 における同値性の対応はx + yです。算術 mod 2 における同値性の対応はx + y + 1 です。

法律

ブール代数の法則とは、2つのブール項間の x ∨ ( y ∨ z ) = ( x ∨ y ) ∨ z のような恒等式である。ここでブール項とは、変数と定数0および1を用いて、演算∧、∨、¬を用いて構築される式として定義される。この概念は、⊕、→、≡といった他のブール演算を含む項にも拡張できるが、この法則の適用目的においては、そのような拡張は不要である。このような目的には、ブール代数をブール法則の任意のモデルとして定義することや、y ∧ z = z ∧ yからx ∨ ( y ∧ z ) = x ∨ ( z ∧ y )を導出する場合のように、古い法則から新しい法則を導出する手段として定義することが含まれます( § ブール代数の公理化で扱われているように)。

単調な法律

ブール代数は、∨を加算、∧を乗算と対応させると、通常の代数と同じ法則の多くを満たします。特に、以下の法則は両方の代数に共通しています。^{[ 25 ] [ 26 ]}

∨の結合性:		${\displaystyle x\vee (y\vee z)}$	${\displaystyle =(x\vee y)\vee z}$
∧の結合性:		${\displaystyle x\wedge (y\wedge z)}$	${\displaystyle =(x\wedge y)\wedge z}$
∨の可換性:		${\displaystyle x\vee y}$	${\displaystyle =y\vee x}$
∧の可換性:		${\displaystyle x\wedge y}$	${\displaystyle =y\wedge x}$
∧の∨上の分配性:		${\displaystyle x\wedge (y\vee z)}$	${\displaystyle =(x\wedge y)\vee (x\wedge z)}$
∨の恒等式:		${\displaystyle x\vee 0}$	${\displaystyle =x}$
∧の恒等式:		${\displaystyle x\wedge 1}$	${\displaystyle =x}$
∧の消滅者:		${\displaystyle x\wedge 0}$	${\displaystyle =0}$

次の法則はブール代数では成り立ちますが、通常の代数では成り立ちません。

∨の消滅者：		${\displaystyle x\vee 1}$	${\displaystyle =1}$
∨ のべき等性:		${\displaystyle x\vee x}$	${\displaystyle =x}$
∧のべき等性:		${\displaystyle x\wedge x}$	${\displaystyle =x}$
吸収1：		${\displaystyle x\wedge (x\vee y)}$	${\displaystyle =x}$
吸収2：		${\displaystyle x\vee (x\wedge y)}$	${\displaystyle =x}$
∨ の∧上の分配性:		${\displaystyle x\vee (y\wedge z)}$	${\displaystyle =(x\vee y)\wedge (x\vee z)}$

上記の第三法則においてx = 2とすると、2 × 2 = 4となるため、これは通常の代数法則ではないことが分かります。残りの5つの法則は、通常の代数法則において、すべての変数を1とすることで反証できます。例えば、吸収法則1では、左辺は1(1 + 1) = 2となり、右辺は 1 となります（以下同様）。

これまで扱ってきた法則はすべて、連言と選言に関するものでした。これらの演算は、どちらかの引数を変更しても出力が変化しないか、入力と同様に変化するという性質を持っています。同様に、任意の変数を0から1に変更しても、出力が1から0に変化することはありません。この性質を持つ演算は単調であると言われています。したがって、これまで扱ってきた公理はすべて単調ブール論理に関するものでした。非単調性は、補数¬を介して次のように現れます。^{[ 5 ]}

非単調法則

補数演算は次の 2 つの法則によって定義されます。

${\displaystyle {\begin{aligned}&{\text{補完 1}}&x\wedge \neg x&=0\\&{\text{補完 2}}&x\vee \neg x&=1\end{aligned}}}$

以下の法則を含む否定のすべての性質は、上記の2つの法則のみから導かれます。^{[ 5 ]}

通常の代数とブール代数の両方において、否定は要素のペアを交換することによって機能するため、両方の代数において二重否定法則（反転法則とも呼ばれる）を満たす。

${\displaystyle {\begin{aligned}&{\text{二重否定}}&\neg {(\neg {x})}&=x\end{aligned}}}$

しかし、通常の代数は2つの法則を満たすが、

${\displaystyle {\begin{aligned}(-x)(-y)&=xy\\(-x)+(-y)&=-(x+y)\end{aligned}}}$

ブール代数はド・モルガンの法則を満たす。

${\displaystyle {\begin{aligned}&{\text{ド・モルガン 1}}&\neg x\wedge \neg y&=\neg {(x\vee y)}\\&{\text{ド・モルガン 2}}&\neg x\vee \neg y&=\neg {(x\wedge y)}\end{aligned}}}$

完全

上に挙げた法則は、ブール代数の残りの部分を含意するという意味において、ブール代数を定義する。補法則1と2は、単調法則と合わせてこの目的に十分であり、したがって、ブール代数の法則あるいは公理化の可能な完全な集合の一つとして捉えることができる。ブール代数のあらゆる法則は、これらの公理から論理的に導かれる。さらに、ブール代数は、 § ブール代数で扱われているように、これらの公理のモデルとして定義することができる。

ブール代数の法則をさらに書き出しても、これらの公理から新たな帰結を導き出すことはできず、また、それらの公理のいかなるモデルも排除することはできない。対照的に、同じ法則の一部のみを列挙したリストにおいては、リスト上の法則から導かれないブール代数の法則が存在する可能性があり、さらには、列挙された法則のモデルがブール代数ではない可能性もある。

この公理化は決して唯一のものではなく、また、ある公理が他の公理から従うかどうかについては注意が払われなかったことを考えると、必ずしも最も自然でもありません。十分な法則に気づいた時点で止めるという選択肢があっただけであり、これについては§ ブール代数の公理化でさらに扱います。あるいは、ブール法則を任意のトートロジーとして直接定義することにより、公理の中間概念を完全に回避することもできます。トートロジーとは、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を表しています。

図2. 連言、選言、補語のベン図

結合の場合、両方の円の内側の領域が塗りつぶされ、両方の変数が 1 のときにx ∧ yが 1 になることを示します。他の領域は塗りつぶされていないままで、他の 3 つの組み合わせでは x ∧ yが 0 になることを示します。

2番目の図は、どちらかの円または両方の円の内側にある領域を塗りつぶすことで、論理和x ∨ yを表しています。3番目の図は、円の内側に ない領域を塗りつぶすことで、補数 ¬ xを表しています。

定数 0 と 1 のベン図は示していませんが、それぞれ白いボックスと黒いボックスで、どちらにも円は描かれていないため、単純なものです。しかし、これらのボックスにxを表す円を配置することは可能です。その場合、それぞれが x を1つの引数として受け取り、xに依存せずに同じ値を返す関数（定数関数）を表します。出力に関する限り、定数と定数関数は区別できません。違いは、定数は引数を取らず、ゼロ引数演算またはヌル引数演算と呼ばれるのに対し、定数関数は引数を1つ受け取り、それを無視する単引数演算である点です。

ベン図は法則を視覚化するのに役立ちます。∧と∨の交換法則は、図の対称性から見ることができます。交換法則のない二項演算は対称的な図を持つことはできません。なぜなら、xとyを入れ替えると、図が水平方向に反転する効果が生じ、交換法則が破綻すると対称性が破綻するからです。

∧ と ∨ のべき等性は、2 つの円を一緒にスライドさせ、∧ と ∨ の両方において、網掛けされた領域が円全体になることに注目することで視覚化できます。

最初の吸収法則x ∧ ( x ∨ y ) = xを理解するには、まず中央のx ∨ yの図から始め、 x円と共通する陰影部分はx円全体であることに注目してください。2番目の吸収法則x ∨ ( x ∧ y ) = xを理解するには、まず左のx ∧ yの図から始め、 x 円全体を陰影で覆うと、 x円だけが陰影で覆われることに注意してください。これは、前の陰影がx円の内側にあったためです。

二重否定の法則は、 x円を塗りつぶす¬ xの 3 番目の図の塗りつぶしを補完することで確認できます。

ド・モルガンの法則の第一項(¬ x ) ∧ (¬ y ) = ¬( x ∨ y )を視覚的に表現するには、まずx ∨ yの中央の図から始め、法則の右辺が示すように、両方の円の外側の領域のみが塗りつぶされるように塗りつぶします。結果は、法則の左辺が示すように、x円とy円の両方の外側の領域、つまりそれらの外接部分を塗りつぶした場合と同じになります。

2 番目のド・モルガンの法則、(¬ x ) ∨ (¬ y ) = ¬( x ∧ y )は、2 つの図を入れ替えても同じ方法で機能します。

最初の補数法則x ∧ ¬ x = 0は、 x円の内側と外側は重なり合わないことを示しています。2番目の補数法則x ∨ ¬ x = 1は、すべてのものがx円の内側か外側にあることを示しています。

デジタル論理ゲート

デジタル論理とは、0と1のブール代数を、回路図を形成するように接続された論理ゲートからなる電子ハードウェアに適用したものです。各ゲートはブール演算を実行し、演算を示す図形で模式的に表されます。論理積（ANDゲート）、論理和（ORゲート）、および補数（インバータ）のゲートに関連付けられた図形は以下のとおりです。^{[ 30 ]}

左から右へ: AND ゲート、ORゲート、NOTゲート。

各ゲートの左側の線は入力線またはポートを表します。入力値は端子の電圧で表されます。いわゆる「アクティブハイ」ロジックでは、0はゼロまたは「グランド」に近い電圧で表され、1は電源電圧に近い電圧で表されます。アクティブローではこれが逆になります。各ゲートの右側の線は出力ポートを表し、通常は入力ポートと同じ電圧規則に従います。

補数は反転ゲートで実装されます。三角形は入力を単純に出力にコピーする演算を表し、出力上の小さな丸は入力を反転する実際の演算を表します。ポートにこのような丸を付けるという慣例から、入力ポートでも出力ポートでも、このポートを通過する信号は途中で反転されることを意味します。

双対性原理、あるいはド・モルガンの法則は、ANDゲートの3つのポートすべてを相補的に接続することでORゲートに変換され、その逆もまた成り立つことを主張するものとして理解できます（下の図4を参照）。ただし、インバータの両方のポートを相補的に接続しても動作は変わりません。

より一般的には、ANDゲートまたはORゲートの3つのポートの8つのサブセットのいずれかを補集合とすることができます。結果として得られる16通りの可能性から、ブール演算、すなわち真理値表に奇数個の1が含まれる演算は8つだけ生じます。奇数ビット出力は0または1のいずれかであり、真理値表の4つの位置のいずれかに位置できるため、このような演算が8つあります。2値ブール演算は16通りあるため、真理値表に偶数個の1が含まれる演算は8つ残ります。これらのうち2つは定数0と1（両方の入力を無視する2値演算）です。4つは、2つの入力のうち正確に1つに非自明に依存する演算、すなわちx、y、 ¬ x、および ¬ yです。残りの2つはx ⊕ y (XOR) とその補数x ≡ yです。

ブール代数

「代数」という用語は、主題、すなわち代数の主題と、対象、すなわち代数的構造の両方を指します。前節ではブール代数の主題について述べてきましたが、本節ではブール代数と呼ばれる数学的対象を扱います。ブール代数は、ブール法則の任意のモデルとして完全に一般化して定義されます。まず、法則を参照することなく定義できる概念の特殊なケース、すなわち具体的ブール代数を取り上げ、次に一般的な概念の 正式な定義を示します。

具体的なブール代数

具体的なブール代数または集合体とは、与えられた集合Xの部分集合で、 Xに対する和集合、積集合、補集合の演算によって閉じた空でない集合のことである。^{[ 5 ]}

(歴史的には、退化ブール代数または 1 要素ブール代数を除外するために、 X自体も空でないことが要求されました。これは、退化代数はすべての方程式を満たすため、すべてのブール代数が同じ方程式を満たすという規則の唯一の例外です。ただし、この除外は、「ブール代数」の好ましい純粋に方程式による定義と矛盾します。方程式のみを使用して 1 要素代数を除外する方法がないためです。0 ≠ 1 は否定方程式であるためカウントされません。したがって、現代の著者は退化ブール代数を許可し、X を空にします。)

例1. Xのすべての部分集合からなるXの冪集合2 ^X。ここでX は空集合、有限集合、無限集合、あるいは無数集合など、任意の集合である。

例2.空集合とX。この2要素代数は、具体的なブール代数が無限集合の部分集合から構成される場合でも有限になり得ることを示しています。X の部分集合体はすべて、空集合とX を必ず含むことがわかります。したがって、空集合とX が一致するようにX を空とすることで得られる退化した代数以外に、より小さな例は考えられません。

例3.整数の有限集合と余有限集合の集合。余有限集合とは、有限個の整数のみを除外した集合です。これは明らかに補集合に関して閉じており、また、余有限集合と任意の集合との和集合は余有限ですが、2つの有限集合の和集合は有限であるため、和集合に関しても閉じています。積集合は、「有限」と「余有限」を入れ替えた和集合のように振舞います。整数の有限集合は可算個しかないため、この例は可算無限です。

例 4.例 2 で述べた点のより単純な例として、n 個の閉曲線で形成され、その図を 2 ^{n 個の}領域に分割するベン図を考えます。Xは、平面上の、どの曲線上にもなく、図内のどこかにあるすべての点の (無限) 集合とします。したがって、各領域の内部はXの無限部分集合であり、X内のすべての点は 1 つの領域内にあります。すると、すべての 2 ^{2 n 個}の可能な領域の和集合(領域の空集合の和集合として得られる空集合と、すべての 2 ⁿ個の領域の和集合として得られる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] の任意のサブセットを形成します)。 ${\displaystyle X=\{a,b,c\}}$

このビット ベクトルの観点から、具体的なブール代数は、すべて同じ長さ (より一般的には、同じセットでインデックス付けされる) で、ビット単位の∧、∨、および ¬のビット ベクトル演算で閉じている、空でないビット ベクトル セットとして等価に定義できます(1010∧0110 = 0010、1010∨0110 = 1110、および¬1010 = 0101のように、それぞれ交差、和、および補数のビット ベクトル実現になります)。

典型的なブール代数

上で扱った集合 {0,1} とそのブール演算は、長さ 1 のビットベクトルの特殊なケースとして理解でき、ビットベクトルを部分集合と同一視することで、1要素集合の2つの部分集合としても理解できます。これはプロトタイプブール代数と呼ばれ、以下の観察によって正当化されます。

すべての非退化の具体的なブール代数が満たす法則は、プロトタイプのブール代数が満たす法則と一致します。

この観察は以下のように証明される。確かに、すべての具体的なブール代数が満たす法則は、プロトタイプ代数が具体的であるため、その法則も満たす。逆に、ある具体的なブール代数で満たされない法則は、特定のビット位置で満たされていないはずであり、その場合、その位置自体がその法則に対する1ビットの反例となる。非退化性は、空のビットベクトルが1つしかないため、少なくとも1つのビット位置が存在することを保証する。

次の節の最終目標は、上記の観察から「具体的」という概念を排除することと理解できる。この目標は、同型性を除き、すべてのブール代数は具体的であるという、より強い観察によって達成される。

ブール代数：定義

これまでのブール代数はすべて具体的なものであり、ビットベクトル、あるいはそれと同等の集合の部分集合から構成されていました。このようなブール代数は、集合と、ブール代数の法則を満たすことが 証明できるその集合に対する演算から構成されます。

ブール代数の法則が満たされることを示す代わりに、集合X 、 X上の2つの二項演算、および1つの単項演算を仮定し、これらの演算がブール代数の法則を満たすことを要求することができます。 Xの要素はビットベクトルや部分集合である必要はなく、任意の値を取ることができます。これにより、より一般的な抽象定義が導かれます。

ブール代数とは、ブール法則を満たす二項演算∧と∨、およびそれに対する一項演算¬を持つ任意の集合である。^{[ 31 ]}

この定義においては、演算がどのようにして法則を満たすようになったか、すなわち命令によるか証明によるかは重要ではありません。すべての具体的なブール代数は（命令ではなく証明によって）法則を満たしており、したがってすべての具体的なブール代数は、我々の定義によればブール代数です。ブール代数を集合と、命令によって特定の法則または公理を満たす特定の演算として定義するというこの公理的な定義は、現代代数、すなわち抽象代数に特徴的な群、環、体などの抽象的な定義と完全に類似しています。

ブール代数の完全な公理化、例えば補分配格子の公理が与えられた場合、この種の代数構造がすべてのブール法則を満たすための十分条件は、それらの公理のみを満たすことである。したがって、以下は同値な定義である。

ブール代数は補完分配格子です。

公理化に関するセクションでは、他の公理化をリストします。いずれも同等の定義の基礎にすることができます。

表現可能なブール代数

すべての具体的なブール代数はブール代数ですが、すべてのブール代数が具体的である必要はありません。nを平方でない正の整数、つまり整数の平方で割り切れない整数（例えば 30 は割り切れますが 12 は割り切れません）とします。最大公約数、最小公倍数、およびnの除算（つまり ¬ x = n / x ）の演算は、その引数がnの正の約数にわたる場合、すべてのブール法則を満たすことが示されます。したがって、これらの約数はブール代数を形成します。これらの約数は集合の部分集合ではないため、nの約数は定義によれば具体的ではないブール代数になります。

しかし、nの各約数をその素因数の集合で表すと、この非具象ブール代数はnのすべての素因数の集合からなる具象ブール代数と同型となり、和集合は最小公倍数、積集合は最大公約数、補集合はnの除算に対応する。したがって、この例は技術的には具象ではないものの、この表現によって少なくとも「道義的には」具象となり、同型性と呼ばれる。この例は、以下の概念の一例である。

ブール代数は、具体的なブール代数と同型である場合に表現可能であると呼ばれます。

次の質問に対する肯定的な答えは、次のとおりです。

すべてのブール代数は表現可能です。

つまり、同型性を除き、抽象ブール代数と具象ブール代数は同じものである。この結果は、選択公理よりもわずかに弱い選択原理であるブール素イデアル定理に依存している。この強い関係は、前の節での観察を、表現可能性に関する以下の簡単な帰結へと強化する、より弱い結果を意味する。

すべてのブール代数が満たす法則は、プロトタイプのブール代数が満たす法則と一致します。

それ自体が表現可能性を意味しないという意味で、より弱い。ブール代数はここで特別な意味を持つ。例えば、関係代数は追加の構造を持つブール代数であるが、すべての関係代数が関係代数に適切な意味で表現可能であるわけではない。

ブール代数の公理化

抽象ブール代数を「ブール法則」を満たす演算を含む集合として定義した上記の定義は、それらの法則が何であるかという疑問を提起します。単純な答えは「すべてのブール法則」であり、これは0と1のブール代数に成立するすべての方程式として定義できます。しかし、そのような法則は無限に存在するため、実際にはこの答えは満足のいくものではなく、成立する法則が有限個あれば十分ではないかという疑問が生じます。

ブール代数の場合、答えは「はい」です。つまり、上に挙げた有限個の方程式で十分です。したがって、ブール代数は有限公理化可能、あるいは有限基底であると言われます。

さらに、必要な方程式の数をさらに減らすことができます。まず、上記の法則のいくつかは、他の法則のいくつかから導かれます。上記の法則の十分な部分集合は、結合法則、可換法則、吸収法則のペア、∧ の ∨ に対する分配法則（またはもう一方の分配法則。どちらか一方だけで十分です）、そして2つの補法則から構成されます。実際、これはブール代数の伝統的な公理化であり、補分配束として用いられます。

上記に挙げていない追加の法則を導入することで、必要な方程式のリストをさらに短縮することが可能になります。例えば、シェファーストローク演算を表す縦棒を用いると、ブール代数を完全に公理化するには単一の公理で十分です。より一般的な演算を用いて、より長い単一の公理を見つけることも可能です。ブール代数の最小公理を参照してください。^{[ 32 ]}${\displaystyle ((a\mid b)\mid c)\mid (a\mid ((a\mid c)\mid a))=c}$

命題論理

命題論理はブール代数と密接に関係する論理体系である^{。 [ 5 ]}ブール代数の多くの統語的概念は、表記法や用語にわずかな変更を加えるだけで命題論理に引き継がれるが、命題論理の意味論はブール代数を介して定義され、命題論理のトートロジー（定理）はブール代数の方程式定理に対応する。

構文上、すべてのブール項は命題論理の命題式に対応します。ブール代数と命題論理の間のこの変換において、ブール変数x、y、 … は命題変数（またはアトム）P、Q 、… になります。 x ∨ yのようなブール項は命題式P ∨ Qになります。0 は偽または⊥になり、1 は真または⊤になります。一般的な命題を参照する際には、命題を表すメタ変数（命題計算の言語外で、命題計算 について話す際に使用される変数）としてギリシャ文字 Φ、Ψ、… を使用すると便利です。

命題論理の意味論は真理値割り当てに依存します。真理値割り当ての基本的な考え方は、命題変数が固定ブール代数の要素にマッピングされ、これらの文字を使用した命題式の真理値が、式に対応するブール項の値を計算することで得られるブール代数の要素になるというものです。古典的な意味論では2要素ブール代数のみが使用され、ブール値意味論では任意のブール代数が考慮されます。トートロジーとは、任意のブール代数への命題変数の真理値割り当てごとに（または、同等に、2要素ブール代数への真理値割り当てごとに）真理値1が割り当てられる命題式です。

これらの意味論は、命題論理のトートロジーとブール代数の等式定理との間の変換を可能にする。命題論理のすべてのトートロジー Φ は、ブール方程式 Φ = 1 として表現することができ、これはブール代数の定理となる。逆に、ブール代数のすべての定理 Φ = Ψ は、トートロジー (Φ ∨ ¬Ψ) ∧ (¬Φ ∨ Ψ) および (Φ ∧ Ψ) ∨ (¬Φ ∧ ¬Ψ) に対応する。→ が言語に存在する場合、これらの最後のトートロジーは、(Φ → Ψ) ∧ (Ψ → Φ) と書くことも、あるいは Φ → Ψ および Ψ → Φ という 2 つの別々の定理として書くこともでき、≡ が利用可能な場合は、単一のトートロジー Φ ≡ Ψ を使用できる。

アプリケーション

命題計算の魅力的な応用例の一つは、自然言語における命題と演繹的議論の分析である。^{[ 33 ]} 「 x = 3ならば、x + 1 = 4」という命題は、+や1といった記号の意味に依存するが、「x = 3ならば、x = 3」という命題は依存しない。この命題は、その構造によって真となり、「x = 3」を「x = 4」や「月は緑色のチーズでできている」に置き換えても真である。このトートロジーの一般形または抽象形は「Pならば、P」であり、ブール代数の言語ではP → Pとなる。

Pをx = 3 あるいは他の命題に置き換えることを、その命題によるPのインスタンス化（instination）といいます。抽象命題においてP をインスタンス化した結果は、その命題のインスタンス化（instance）といいます。例えば、 x = 3 → x = 3 は、抽象トートロジーP → Pのインスタンスであるため、トートロジーとなります。インスタンス化された変数のすべての出現は、 P → x = 3 やx = 3 → x = 4といった無意味な結果を避けるために、同じ命題でインスタンス化されなければなりません。

命題計算は、ブール演算を用いて命題変数から構築される抽象命題にのみ着目します。命題計算においてもインスタンス化は可能ですが、それは抽象命題によって命題変数をインスタンス化することによってのみ可能です。例えば、P → ( Q → P )においてQ → PによってQ をインスタンス化すると、インスタンスP → ( ( Q → P ) → P )が得られます。

(命題計算の仕組みの一部としてインスタンス化が利用できることにより、命題計算の言語内でメタ変数を使用する必要がなくなります。これは、通常の命題変数は言語内で任意の命題を表すものと考えられるためです。メタ変数自体はインスタンス化の範囲外にあり、命題計算の言語の一部ではなく、この文が書かれているのと同じ言語の一部です。この言語では、命題変数とそのインスタンス化を異なる構文エンティティとして区別できる必要があります。)

命題論理のための演繹システム

命題計算の公理化とは、公理と呼ばれるトートロジーの集合と、古いトートロジーから新しいトートロジーを生み出すための1つ以上の推論規則である。公理系Aにおける証明は、有限個の空でない命題列であり、各命題はAの公理の例であるか、証明の前の命題からAの何らかの規則に従っている（したがって循環論法は不可能である）かのいずれかである。最後の命題は、証明によって証明される定理である。証明の最初の空でない部分はすべてそれ自体が証明であり、したがって証明中のすべての命題はそれ自体が定理である。すべての定理がトートロジーであるとき、公理化は健全であり、すべてのトートロジーが定理であるとき、公理化は完全である。 ^{[ 34 ]}

シーケント計算

命題計算は一般にヒルベルト体系として体系化されており、その演算はブール代数の演算とまったく同じで、その定理はブール同語反復（ブール項はブール定数 1 に等しい）である。もう 1 つの形式はシークエント計算で、これには 2 種類あり、通常の命題計算のような命題と、A ∨ B、A ∧ C、... ⊢ A、B → C、...のような、シークエントと呼ばれる命題のリストのペアがある。シークエントの 2 つの半分は、それぞれ前件部と後件部と呼ばれる。前件部またはその一部を示す慣習的なメタ変数は Γ であり、後件部の場合は Δ である。したがって、 Γ, A ⊢ Δ は、後件部がリスト Δ であり、前件部がリスト Γ にその後に命題Aが付加されたものであるシークエントを示す。先行詞はその命題の論理積として解釈され、後続詞はその命題の論理和として解釈され、後続詞自体は先行詞による後続詞の 含意として解釈されます。

含意は含意とは異なり、後者はブール代数の値を返す二項演算であるのに対し、前者は成立するか成立しないかの二項関係である。この意味で、含意は含意の外部形式であり、ブール代数の外部にあるという意味で、シークエントの読者も外部にいて、あるブール代数における前件と後件を解釈・比較すると考える。⊢の自然な解釈は、x ∨ y = yのとき、x ≤ yで定義されるブール代数の部分順序における≤となる。このように外部含意⊢と内部含意→を一つの論理で混在させることができる点は、シークエント計算と命題計算の本質的な違いの一つである。^{[ 35 ]}

アプリケーション

2つの値の計算としてのブール代数は、コンピュータ回路、コンピュータプログラミング、数学論理の基礎であり、集合論や統計などの数学の他の分野でも使用されています。^{[ 5 ]}

コンピューター

20世紀初頭、何人かの電気技術者は、ブール代数が特定の種類の電気回路の挙動に類似していることを直感的に認識しました。クロード・シャノンは、1937年の修士論文「リレーおよびスイッチング回路の記号解析」において、そのような挙動がブール代数と論理的に等価であることを正式に証明しました。

今日、現代の汎用コンピュータはすべて、2値ブール論理を用いて機能を実行します。つまり、その電気回路は2値ブール論理の物理的な表現です。この表現は、高速回路や容量性記憶装置における配線の電圧、強磁性記憶装置における磁区の向き、パンチカードや紙テープにおける穴など、様々な方法で実現されています。（初期のコンピュータの中には、2値論理回路の代わりに10進回路や機構を用いていたものもありました。）

もちろん、どの媒体でも2つ以上の記号をコード化することは可能です。例えば、0、1、2、3ボルトをそれぞれ使用して、4つの記号からなるアルファベットを電線にコード化したり、パンチカードに異なるサイズの穴を開けたりすることができます。しかし実際には、高速、小型、低消費電力という厳しい制約が重なり、ノイズが大きな要因となります。そのため、1つの場所に複数の記号が出現する可能性がある場合、記号を区別することが困難になります。デジタル設計者は、1本の電線で4つの電圧を区別しようとするのではなく、電線ごとに高電圧と低電圧の2つの電圧を使用することにしました。

コンピュータは上記の理由から、2値ブール回路を使用します。最も一般的なコンピュータアーキテクチャは、ビットと呼ばれる32または64値のブール値の順序付けられたシーケンスを使用します（例：01101000110101100101010101001011）。マシンコード、アセンブリ言語、およびその他の特定のプログラミング言語でプログラミングする場合、プログラマはデータレジスタの低レベルのデジタル構造を操作します。これらのレジスタは電圧で動作し、0ボルトはブール値の0を表し、基準電圧（多くの場合、+5V、+3.3V、または+1.8V）はブール値の1を表します。このような言語は、数値演算と論理演算の両方をサポートしています。ここで「数値」とは、コンピュータがビットのシーケンスを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を意味するからです。質問も同様です。例えば、「空は青いですか？ なぜ空は青いのですか？」という順序は、逆の順序よりも意味が通ります。行動に関する接続命令は、「服を着て」や「学校に行く」といった行動に関する断定的な表現に似ています。 「私を愛して」や「私を離れて」や「魚を」や「餌を切る」といった接続命令は、どちらかの選択肢が好ましくないという含意を持つため、非対称的になりがちです。 「tea」や「milk」といった接続名詞は、一般的に集合体としての結合を表すのに対し、「tea」や「milk」は選択肢を表します。しかし、文脈によってこれらの意味が逆転することもあります。例えば、「 you choice are coffee and tea」は、通常、「you choice are coffee or tea (alternatives)」と同じ意味になります。「I don't not like milk」のような二重否定は、文字通り「I do like milk」を意味することは稀で、むしろ第三の可能性を暗示するような、ある種の曖昧さを帯びた表現となります。「Not not P」は「surely P」と大まかに解釈することができ、Pは必然的に「not not not P 」を意味しますが、英語では直観主義論理と同様に、その逆は疑わしいものです。自然言語における接続詞の使用法は非常に特異であるため、ブール代数は接続詞を解釈するための信頼できる枠組みとはみなされません。

デジタルロジック

ブール演算は、デジタル論理において、個々の配線に伝送されるビットを結合し、{0,1} の解釈を行うために使用されます。n 個の同一のバイナリゲートからなるベクトルを用いて、それぞれ n ビットの 2 つのビットベクトルを結合する場合、個々のビット演算は、 2 ⁿ個の要素を持つブール代数の値に対する単一の演算としてまとめて理解できます。

素朴集合論

素朴集合論では、ブール演算は与えられた集合Xの部分集合に作用するものと解釈されます。前述のように、この動作はビットベクトルの座標方向の結合と完全に一致しており、2つの集合の和は2つのビットベクトルの和集合に対応し、以下同様です。

ビデオカード

3つのジェネレータに基づく256要素の自由ブール代数は、ラスターグラフィックスに基づくコンピュータディスプレイで採用されています。ラスターグラフィックスでは、ビットブリットを用いてピクセルで構成される領域全体を操作し、ブール演算を用いてソース領域とデスティネーション領域をどのように組み合わせるかを指定します。この際、通常はマスクと呼ばれる3番目の領域が使用されます。最新のビデオカードは、この目的のために2 ^{2 3} = 256通りの3項演算をすべて提供しており、演算の選択は1バイト（8ビット）のパラメータで行います。定数SRC = 0xaaまたは0b10101010、DST = 0xccまたは0b11001100、およびMSK = 0xf0または0b11110000を使用すると、 (ソースとデスティネーションの XOR 演算を行い、その結果とマスクの AND 演算を行うことを意味します)などのブール演算を、コンパイル時に計算されたバイトを示す定数 (例では0x80、だけの場合は0x88など) として直接書き込むことができます。 実行時に、ビデオ カードは、必要なハードウェアが非常に少なく、式の複雑さにまったく関係なく、均一な方法で、バイトを元の式で示されたラスター操作として解釈します。 (SRC^DST)&MSK(SRC^DST)&MSKSRC^DST

モデリングとCAD

コンピュータ支援設計用のソリッド モデリングシステムは、オブジェクトを他のオブジェクトから構築するためのさまざまな方法を提供しており、ブール演算による組み合わせもその 1 つです。この方法では、オブジェクトが存在する空間はボクセルの集合S (2 次元グラフィックスのピクセルの 3 次元版) として理解され、形状はSのサブセットとして定義されるため、結合、交差などによってオブジェクトを集合として組み合わせることができます。明らかな用途の 1 つは、単純な形状の和として複雑な形状を構築することです。もう 1 つの用途は、材料の除去として理解される彫刻です。物理的な機械で物理的な材料に対して実行できる研削、フライス加工、ルーティング、または穴あけ操作は、ブール演算x ∧ ¬ yまたはx − yを使用してコンピュータ上でシミュレートできます。これは、集合論では差集合であり、yの要素をxの要素から削除します。したがって、機械加工する形状と除去する材料の 2 つの形状が与えられた場合、前者を機械加工して後者を除去した結果は、差集合として単純に記述されます。

ブール検索

検索エンジンのクエリもブール論理を採用しています。この用途では、インターネット上の各ウェブページは「集合」の「要素」とみなすことができます。以下の例では、Googleがサポートする構文を使用しています。^{[注 1 ]}

• 二重引用符は、空白で区切られた単語を1つの検索用語に結合するために使用されます。^{[ NB 2 ]}
• 空白は、検索用語を結合するためのデフォルトの演算子であるため、論理 AND を指定するために使用されます。

「検索語1」「検索語2」 

• OR キーワードは論理 OR に使用されます。

「検索語1」または「検索語2」 

• 接頭辞のマイナス記号は論理否定に使用されます。

「検索語1」−「検索語2」 

参照

• 標準的に定義されたブール代数
• ブール微分積分
• ブールレオ
• カントール代数
• ハイティング代数
• ブール代数のトピックのリスト
• ロジック設計
• プリンキピア・マテマティカ
• 三値論理
• ウカシェヴィチ論理
• ベクトル論理

注記

1. すべての検索エンジンが同じクエリ構文をサポートしているわけではありません。また、Googleなどの一部の組織は、代替構文や拡張構文をサポートする「専用」検索エンジンを提供しています。（構文チートシートを参照してください。）現在は廃止されたGoogleコード検索は、かつては正規表現をサポートしていましたが、現在は存在しません。
2. 二重引用符で区切られた検索用語は、Google ドキュメントでは「完全一致フレーズ」検索と呼ばれます。

参考文献

1. ブール、ジョージ(2011年7月28日). 「論理の数学的分析 ― 演繹的推論の微積分に向けた試論」 .
2. ブール、ジョージ(2003) [1854]. 『思考の法則の探究』プロメテウス・ブックス. ISBN 978-1-59102-089-9。
3. 「ブール代数（またはブール代数）という名称は、ブールによって考案され、シュレーダーによって拡張され、ホワイトヘッドによって完成された微積分学において、1913年にシェファーによって初めて提案されたようです。」エドワード・ヴァーミリー・ハンティントン、「ホワイトヘッドとラッセルの『プリンキピア・マセマティカ』を特に参照した、論理代数のための新しい独立公準の集合」、アメリカ数学会誌35（1933年）、274-304ページ、脚注、278ページ。
4. ピアース、チャールズ・S. (1931). Collected Papers . 第3巻.ハーバード大学出版局. p. 13. ISBN 978-0-674-13801-8。
5. ギヴァント, スティーブン・R.;ハルモス, ポール・リチャード(2009).ブール代数入門. 数学の学部テキスト,シュプリンガー. pp.  21– 22. ISBN 978-0-387-40293-2。
6. ネルソン、エリック・S. (2011). 「易経と哲学：ライプニッツからデリダまで」中国哲学ジャーナル38 (3): 377– 396. doi : 10.1111/j.1540-6253.2011.01661.x .
7. レンツェン、ヴォルフガング。「ライプニッツ：論理」。フィーザーでは、ジェームズ。ブラッドリー・ダウデン (編)。インターネット哲学百科事典。ISSN 2161-0002。OCLC 37741658。  
8. Dunn, J. Michael; Hardegree, Gary M. (2001).哲学的論理における代数的手法.オックスフォード大学出版局. p. 2. ISBN 978-0-19-853192-0。
9. ビンボ、カタリン; ダン、J. マイケル (2008).一般化ガロア論理：非古典的論理計算の関係意味論. CSLI Publications. ISBN 978-1-57586-573-7。
10. Stone, MH (1936). 「ブール代数の表現理論」 .アメリカ数学会誌. 40 (1): 37–111 . doi : 10.2307/1989664 . ISSN 0002-9947 . JSTOR 1989664 .  
11. Weisstein, Eric W. 「ブール代数」 . mathworld.wolfram.com . 2020年9月2日閲覧。
12. バラバニアン、ノーマン; カールソン、ブラッドリー (2001).デジタルロジック設計原理. John Wiley. pp.  39– 40. ISBN 978-0-471-29351-4。、オンラインサンプル
13. Rajaraman; Radhakrishnan (2008-03-01). 『デジタルコンピュータ設計入門』 PHI Learning Pvt. Ltd. p. 65. ISBN 978-81-203-3409-0。
14. Camara, John A. (2010).電気・電子工学リファレンスマニュアル 電気・コンピュータPE試験対策. www.ppi2pass.com. p. 41. ISBN 978-1-59126-166-7。
15. 湊真一、室賀三郎 (2007). 「第29章 二分決定図」. 陳偉凱 (編). VLSIハンドブック(第2版). CRC Press . ISBN 978-0-8493-4199-1。
16. パークス、アラン (2002).言語、機械、論理入門：計算可能言語、抽象機械、形式論理. シュプリンガー. p. 276. ISBN 978-1-85233-464-2。
17. バーワイズ, ジョン;エチェメンディ, ジョン; オールウェイン, ジェラード; バーカー・プラマー, デイブ; リウ, アルバート (1999).言語、証明、論理. CSLI Publications. ISBN 978-1-889119-08-3。
18. ベン・ゴーツェル（1994年）『カオス論理：複雑系科学の観点から見た言語、思考、そして現実』シュプリンガー社、p.48、ISBN 978-0-306-44690-0。
19. ハルモス、ポール・リチャード(1963). ブール代数講義. ヴァン・ノストランド.
20. Bacon, Jason W. (2011). 「Computer Science 315 Lecture Notes」 . 2021年10月2日時点のオリジナルよりアーカイブ。 2021年10月1日閲覧。
21. 「ブール代数 - 表現、規則、定理、例」 . GeeksforGeeks . 2021年9月24日. 2024年6月3日閲覧。
22. 「ブール論理演算」（PDF） .
23. 「ブール代数演算」bob.cs.sonoma.edu . 2024年6月3日閲覧。
24. 「ブール代数」（PDF） .
25. O'Regan, Gerard (2008). 『コンピューティングの歴史』 Springer. p. 33. ISBN 978-1-84800-083-4。
26. 「ブール代数の要素」 www.ee.surrey.ac.uk . 2020年7月21日時点のオリジナルよりアーカイブ。2020年9月2日閲覧。
27. McGee, Vann,文理計算の再考：ブール代数（PDF）
28. グッドスタイン、ルーベン・ルイス（2012年）、「第4章 文論理」、ブール代数、クーリエ・ドーバー出版、ISBN 978-0-48615497-8
29. ヴェン、ジョン（1880年7月）「I. 命題と推論の図式的および機械的な表現について」（PDF） .ロンドン、エディンバラ、ダブリン哲学雑誌・科学ジャーナル. 5. 10 (59): 1– 18. Bibcode : 1880LEDPM..10....1V . doi : 10.1080/14786448008626877 . 2017年5月16日時点のオリジナルよりアーカイブ（PDF） .[1] [2]
30. シャノン、クロード(1949). 「2端子スイッチング回路の合成」.ベルシステム技術ジャーナル. 28 : 59–98 . Bibcode : 1949BSTJ...28...59S . doi : 10.1002/j.1538-7305.1949.tb03624.x .
31. Koppelberg, Sabine (1989). 「ブール代数の一般理論」.ブール代数ハンドブック 第1巻 (J. Donald Monk, Robert Bonnet編) . アムステルダム, オランダ: North Holland . ISBN 978-0-444-70261-6。
32. McCune, William ; Veroff, Robert; Fitelson, Branden ; Harris, Kenneth; Feist, Andrew; Wos, Larry (2002)「ブール代数のための短い単一公理」、Journal of Automated Reasoning、29 (1): 1– 16、doi : 10.1023/A:1020542009983、MR 1940227、S2CID 207582048  
33. オールウッド、ジェンス;アンダーソン、グンナール・グンナール。アンダーソン、ラース＝グンナール。ダール、オステン (1977-09-15)。言語学における論理学。ケンブリッジ大学出版局。ISBN 978-0-521-29174-3。
34. ハウスマン、アラン、カハネ、ハワード、ティドマン、ポール (2010) [2007].論理学と哲学：現代入門. ワズワース・センゲージ・ラーニング. ISBN 978-0-495-60158-6。
35. ジャン＝イヴ・ジラール、ポール・テイラー、イヴ・ラフォン (1990) [1989]. Proofs and Types . Cambridge University Press (Cambridge Tracts in Theoretical Computer Science, 7). ISBN 978-0-521-37181-0。

さらに読む

• マノ、モリス; シレッティ、マイケル・D. (2013).デジタルデザイン. ピアソン. ISBN 978-0-13-277420-8。
• ホワイトシット、J. エルドン (1995).ブール代数とその応用.クーリエ・ドーバー出版. ISBN 978-0-486-68483-3。
• フィリップ・ドウィンガー (1971). 『ブール代数入門』ドイツ、ヴュルツブルク: Physica Verlag.
• シコルスキー、ローマン(1969)。ブール代数(第 3 版)。ベルリン、ドイツ: Springer-Verlag。ISBN 978-0-387-04469-9。
• ボチェンスキ、ヨゼフ・マリア(1959). 『数学論理学の概説』 . フランス語版とドイツ語版からのオットー・バード訳. ドルドレヒト、南ホラント州: D. ライデル.

歴史的視点

• ブール、ジョージ(1848). 「論理の微積分」 .ケンブリッジ・アンド・ダブリン数学ジャーナル. III : 183–198 .
• ヘイルペリン、セオドア（1986年）『ブールの論理と確率：現代代数学、論理学、確率論の観点からの批判的解説』（第2版）エルゼビア社ISBN 978-0-444-87952-3。
• ガベイ、ドヴ・M.、ウッズ、ジョン編 (2004).近代論理学の興隆：ライプニッツからフレーゲまで. 論理学史ハンドブック 第3巻.エルゼビア. ISBN 978-0-444-51611-4。、ハイルペリン、バレンシア、グラッタン・ギネスによるいくつかの関連章
• バデサ、カリクスト（2004年）「第1章 クラス代数と命題計算」モデル理論の誕生：相対論の枠組みにおけるレーヴェンハイムの定理。プリンストン大学出版局。ISBN 978-0-691-05853-5。
• Stanković, Radomir S. [ドイツ語] ; Astola, Jaakko Tapio [フィンランド語] (2011). ニシュ（セルビア）およびタンペレ（フィンランド）にて執筆。『ブール論理からスイッチング回路とオートマトンへ：現代情報技術に向けて』。計算知能研究。第335巻（第1版）。ベルリンおよびハイデルベルク（ドイツ）：Springer - Verlag。pp . xviii + 212。doi ：10.1007/978-3-642-11682-7。ISBN 978-3-642-11681-0。ISSN  1860-949X。LCCN  2011921126 。2022-10-25に取得。
• スタンフォード哲学百科事典、2012年2月21日、バリス、スタンリー著「論理伝統の代数」

外部リンク