ブール代数
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/Hasse_diagram_of_powerset_of_3.svg/250px-Hasse_diagram_of_powerset_of_3.svg.png)
ブール代数(ブールだいすう、英: 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。
典型的な例は、台集合として特別な2つの元 0, 1 のみの2点集合 {0, 1} からなるものであり、コンピュータの動作原理の理論としても知られている。 この代数の上では排他的論理和 (xor) や否定論理積(nand)など応用上重要な演算子が ∧、 ∨、 ¬ の組み合わせで記述される(∧ または ∨ も ¬ と残りの1つの組み合わせで記述される。)。
ブール環
任意の元 x に対して 積の冪等則x2 = x を満たす単位的環 B をブール環(boolean ring)という。 このとき単位的環の公理から
- −x=(−1)x=x(−1)
さらに
- (−x)(−y)=xy
が導かれ、それらと冪等則により
を得る[注釈 2]。つまり(乗法が)冪等的かつ単位的な環は加法に関して全ての元の位数が高々2であるような可換環となる。したがって
とおけば B はブール代数となる。 また B がブール代数のとき
と[注釈 3]おけば B はブール環となる。 この対応はブール代数とブール環の間の自然な一対一対応を定めるので、しばしばこの2つは同一視される。 [1]。
脚注
注釈
- ^ x ∧ x = x、x ∨ x = x と書かれる冪等則を要求する場合もあるが、これは吸収則により導かれる定理である。それでも明示するのは、 ∧ 、∨ のそれぞれのみに注目した半束においてはこれが特徴的な公理だからである。
- ^ 具体的には加法群の性質も用いて
- x = x2 = (− 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, https://books.google.co.jp/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.co.jp/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.co.jp/books?id=_JPfBwAAQBAJ
関連項目
外部リンク
- 西村敏男『ブール代数』 - コトバンク
- 『ブール束』 - コトバンク
- 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, https://www.encyclopediaofmath.org/index.php?title=Boolean_algebra
| |
---|---|
一般 | |
Traditional logic(英語版) | |
命題論理・ ブール論理 | |
述語論理 | |
素朴集合論 | |
集合論 |
|
モデル理論 | |
証明論 | |
計算理論 再帰理論 |