Boolean algebra (structure)

ウィキペディア

ブール代数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/08/05 03:56 UTC 版)

出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。記事の信頼性向上にご協力をお願いいたします。（2015年12月）

ブール代数（ブールだいすう、英: 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

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

${\displaystyle x+x=0,\qquad xy=yx}$

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

${\displaystyle x\wedge y=xy,\qquad x\vee y=x+y+xy,\qquad \neg x=1+x}$

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

${\displaystyle xy=x\wedge y,\qquad x+y=(x\wedge \neg y)\vee (\neg x\wedge y)}$

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

脚注

[脚注の使い方]

注釈

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

   x = x² = (− x) ² = − xから

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

   0 = (x − y) − (x − y) ² = xy + yx から

   xy = − yxを導くことで

   xy − yx = xy + xy = 0であると判り

   xy = yxを得る。

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

出典

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

参考文献

• レイモンド・スマリヤン『スマリヤン先生のブール代数入門　嘘つきパズル・パラドックス・論理の花咲く庭園』川辺治之 訳、共立出版、2008年8月。ISBN 978-4-320-01869-3。 
• ガーレット・バーコフ、ソンダース・マクレーン『現代代数学概論』奥川光太郎・辻吉雄 共訳（改訂第3版）、白水社、1967年。 
• 前田 周一郎『束論と量子論理』森北出版、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, https://books.google.com/books?id=vVVTxeuiyvQC 
  • 本田あおい「書評 「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, https://books.google.com/books?id=8lNkXPJas4wC 
• Halmos, Paul R. (2012), Lectures on Boolean Algebras, Undergraduate Texts in Mathematics, Springer-Verlag, ISBN 978-0-387-90094-0, https://books.google.com/books?id=_JPfBwAAQBAJ 

関連項目

• 集合の代数学
• 数理論理学
• ストーンの表現定理
• 束論
• 環 (数学)
• デジタル回路
• ブール関数
• ブール論理
• ラダー・ロジック
• 論理回路

外部リンク

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

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