ブール代数

ブール代数（ブールだいすう、英: boolean algebra）またはブール束（ブールそく、英: boolean lattice）とは、ジョージ・ブールが19世紀中頃に考案した代数系の一つである。ブール代数の研究は束の理論が築かれるひとつの契機ともなった。ブール論理の演算はブール代数の一例であり、現実の応用例としては、組み合わせ回路（論理回路）はブール代数の式で表現できる。

定義

ブール代数（ブール束）とは束論における可補分配束（complemented distributive lattice）のことである。

集合 L と L 上の二項演算 ∨（結び（join）と呼ぶ），∧（交わり（meet）と呼ぶ）の組 ⟨ L; ∨, ∧ ⟩ が以下を満たすとき分配束（distributive lattice）と呼ぶ。

交換則：x ∧ y = y ∧ x 、x ∨ y = y ∨ x
結合則：(x ∧ y)∧ z = x ∧(y ∧ z) 、(x ∨ y)∨ z = x ∨(y ∨ z)
吸収則^{[注釈 1]}：(x ∧ y)∨ x =x 、(x ∨ y)∧ x = x
分配則：(x ∨ y)∧ z = (x ∧ z)∨(y ∧ z) 、(x ∧ y)∨ z = (x ∨ z)∧(y ∨ z)

さらに L の特別な元 0, 1 と単項演算 ¬ について、以下が成り立つとき組 ⟨ L; ∨, ∧, ¬, 0, 1 ⟩ を可補分配束（ブール束）と呼ぶ。

補元則： x ∨ ¬x = 1， x ∧ ¬ x = 0。

典型的な例は、台集合として特別な２つの元 0, 1 のみの２点集合 {0, 1} からなるものであり、コンピュータの動作原理の理論としても知られている。この代数の上では排他的論理和 (xor) や否定論理積(nand)など応用上重要な演算子が ∧、 ∨、 ¬ の組み合わせで記述される(∧ または ∨ も ¬ と残りの1つの組み合わせで記述される。)。

ブール環

任意の元 x に対して積の冪等則x² = x を満たす単位的環 B をブール環（boolean ring）という。このとき単位的環の公理から

- x =(-1) x = x (-1)

さらに

(- x)(- y)= xy

が導かれ、それらと冪等則により

x+x=0,\qquad xy=yx

を得る^{[注釈 2]}。つまり(乗法が)冪等的かつ単位的な環は加法に関して全ての元の位数が高々2であるような可換環となる。したがって

x\wedge y=xy,\qquad x\vee y=x+y+xy,\qquad \neg x=1+x

とおけば B はブール代数となる。また B がブール代数のとき

xy=x\wedge y,\qquad x+y=(x\wedge \neg y)\vee (\neg x\wedge y)

と^{[注釈 3]}おけば B はブール環となる。この対応はブール代数とブール環の間の自然な一対一対応を定めるので、しばしばこの2つは同一視される。 ^[1]。

脚注

[脚注の使い方]

注釈

^ x ∧ x = x、x ∨ x = x と書かれる冪等則を要求する場合もあるが、これは吸収則により導かれる定理である。それでも明示するのは、 $\land 、\lor$ のそれぞれのみに注目した半束においてはこれが特徴的な公理だからである。
^ 具体的には加法群の性質も用いて
$x = x 2 = (- x) 2 = - x$ から

$x + x = 0$ を得、これにより

$0 = (x - y) - (x - y) 2 = xy + yx$ から

$xy = - yx$ を導くことで

$xy - yx = xy + xy = 0$ であると判り

$xy = yx$ を得る。
^ 2元からなるブール束から2元からなるブール環を構成するなら、この定義は積を論理積の真理値、和を排他的論理和の真理値と定める事と同値。また、位数2の非零環は(一意でありかつ)明らかに、上記の対応によりブール論理の真理値と同値となるようなブール環でもある(対応するのはあくまでも真理値であることに注意)。

出典

^ Davey & Priestley 2002, p. 109, Exercise 4.27.

参考文献

レイモンド・スマリヤン『スマリヤン先生のブール代数入門　嘘つきパズル・パラドックス・論理の花咲く庭園』川辺治之訳、共立出版、2008年8月。ISBN 978-4-320-01869-3。
ガーレット・バーコフ、ソンダース・マクレーン『現代代数学概論』奥川光太郎・辻吉雄共訳（改訂第3版）、白水社、1967年。
前田周一郎『束論と量子論理』（POD版）森北出版、2015年8月。ISBN 978-4-627-05399-1。 - 1980年に槙書店から出版され、2015年に森北出版から復刊された。
Birkhoff, Garrett (1979), Lattice Theory (3rd Revised ed.), American Mathematical Society, ISBN 978-0-8218-1025-5
Davey, B. A.; Priestley, H. A. (2002), Introduction to lattices and order (2nd ed.), Cambridge University Press, ISBN 978-0-521-78451-1, MR1902334, Zbl 1002.06001
- 本田あおい「書評「Introduction to Lattices and Order」」（PDF）『知能と情報』第19巻第2号、日本知能情報ファジィ学会、2007年4月、148頁。
Grätzer, George (2008), Universal Algebra (2nd ed.), Springer, ISBN 978-0-387-77486-2
Halmos, Paul R. (2012), Lectures on Boolean Algebras, Undergraduate Texts in Mathematics, Springer-Verlag, ISBN 978-0-387-90094-0

外部リンク

西村敏男『ブール代数』 - コトバンク
『ブール束』 - コトバンク
Weisstein, Eric W. "Boolean Algebra". mathworld.wolfram.com (英語).
The Mathematics of Boolean Algebra （英語） - スタンフォード哲学百科事典「ブール代数」の項目。
Hazewinkel, Michiel, ed. (2001), “Boolean algebra”, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4

[冪等則の扱い-1] x ∧ x = x、x ∨ x = x と書かれる冪等則を要求する場合もあるが、これは吸収則により導かれる定理である。それでも明示するのは、 $\land 、\lor$ のそれぞれのみに注目した半束においてはこれが特徴的な公理だからである。

[2x=0と可換律の導き方-2] 具体的には加法群の性質も用いて
$x = x 2 = (- x) 2 = - x$ から

$x + x = 0$ を得、これにより

$0 = (x - y) - (x - y) 2 = xy + yx$ から

$xy = - yx$ を導くことで

$xy - yx = xy + xy = 0$ であると判り

$xy = yx$ を得る。

[ブール論理との対応-3] 2元からなるブール束から2元からなるブール環を構成するなら、この定義は積を論理積の真理値、和を排他的論理和の真理値と定める事と同値。また、位数2の非零環は(一意でありかつ)明らかに、上記の対応によりブール論理の真理値と同値となるようなブール環でもある(対応するのはあくまでも真理値であることに注意)。

[FOOTNOTEDaveyPriestley2002109Exercise_4.27-4] Davey & Priestley 2002, p. 109, Exercise 4.27.

[注釈 1]

[注釈 2]

[注釈 3]

[1]

表話編歴数理論理学
一般	形式言語構成規則形式体系演繹システム（英語版）形式的証明形式意味論論理式集合元クラス古典論理公理自然演繹推論規則関係定理論理的帰結公理系型理論記号（英語版）統語論（英語版）理論（英語版）
Traditional logic（英語版）	命題推論論証妥当性 Cogency 三段論法 Square of opposition（英語版）ベン図
命題論理・ブール論理	ブール関数命題論理命題論理式（英語版）論理演算真理値表多値論理
述語論理	一階量化子述語（英語版）二階 Monadic predicate calculus（英語版）
素朴集合論	集合空集合元数え上げ外延有限集合無限集合部分集合冪集合可算集合非可算集合帰納的集合定義域終域像写像関数関係順序対
集合論	数学基礎論ツェルメロ＝フレンケル集合論選択公理一般集合論（英語版） Kripke–Platek 集合論（英語版）フォン・ノイマン＝ベルナイス＝ゲーデル集合論（英語版）モース-ケリー集合論タルスキ＝グロタンディーク集合論（英語版）
モデル理論	モデル（英語版）解釈（英語版）超準モデル（英語版）有限モデル理論真理値妥当性
証明論	形式的証明演繹システム（英語版）形式体系定理論理的帰結推論規則統語論（英語版）シークエント計算
計算理論再帰理論	計算可能性計算複雑性複雑性クラス P≠NP予想再帰帰納的集合帰納的可算集合決定問題停止性問題チャーチ＝チューリングのテーゼ計算可能関数原始再帰関数 μ再帰関数チューリングマシンラムダ計算

定義

ブール環

脚注

注釈

出典

参考文献

関連項目

外部リンク