ブール論理

ブール論理は、古典論理のひとつで、その名称はブール代数ないしその形式化を示したジョージ・ブールに由来する。

リレーなどによる「スイッチング回路の理論」として1930年代に再発見され、間もなくコンピュータに不可欠な理論として広まり、今日では一般的に使われている。

本項目では、集合代数を用いて、集合、ブール演算、ベン図、真理値表などの基本的解説とブール論理の応用について解説する。ブール代数の記事ではブール論理の公理を満足する代数的構造の型を説明している。ブール論理はブール代数で形式化され2値の意味論を与えられた命題論理とみることができる。

1. 用語
-----

//X//を集合としたとき:

元とは、集合のメンバーを意味する。これを で表す。集合の元でないものは で表す。
普遍集合とは、集合 //X// であり、1 で表される場合がある。ここで universeという言葉が使われるのは「全ての元を考慮している」ことを意味しており、必ずしも「全ての元が存在する」必要があるわけではない。
空集合とは、元を持たない集合であり、 または 0 で表される。
単項演算子は1つの集合に適用される。単項演算子としては論理否定のみがある。補集合をとる働きがある。
二項演算子は2つの集合に適用される。基本的な演算子には論理和と論理積がある。これらは和集合と共通部分をとる。これらから導出される二項演算子として XORなどもある。
部分集合は で表され、集合 A の全ての元が集合 B にも含まれることを意味する。
真部分集合は で表され、集合 A の全ての元が集合 B にも含まれ、かつ両集合は等しくないことを意味する。
上位集合は で表され、集合 B の全ての元が集合 A にも含まれることを意味する。
真上位集合は で表され、集合 B の全ての元が集合 A にも含まれ、かつ両集合が等しくないことを意味する。

2. 例
----

集合 A には普遍集合の中の全ての偶数が含まれ、集合 B には同じ普遍集合の中の全ての 3 の倍数が含まれるとする。そのとき、これらの集合の共通部分は、その普遍集合の中の全ての6の倍数が含まれる。

集合 A の補集合は、その普遍集合の全ての奇数となる。

2.1. 演算の連鎖
----------

たかだか2つの集合に対してブール演算を行い、その演算によって形成された新たな集合と別の集合に対して新たなブール演算を適用することができる。上の例で言えば、普遍集合の全ての 5 の倍数を含む集合 C を新たに定義する。ここで「集合 A AND B AND C」は、その普遍集合の全ての30の倍数を含む。記述を単純化するため、集合 A と B の共通部分を AB と記したり、6の倍数の集合を導入したりする。そうすると「集合 AB AND C」は、同様に全ての30の倍数を含む。このようなステップをさらに進めていくこともでき、この演算の結果として集合 ABC を定義することもできる。

2.2. 括弧の使用
----------

任意個の論理積の連鎖には曖昧さは全くないが、AND と OR と NOT が組み合わされると曖昧な場合が出てくる。そのような場合に演算の順序を明確化するために括弧を使うこともある。通常、最も内側の括弧内の演算が最初に実行され、順次外側に移っていく。

3. 論理演算の法則
----------

2つの二項演算子の記号を と とし、単項演算子の記号を / ~ とする。また、値 0 と 1 も使用する。ブール代数とブール論理では以下のような法則が成り立つ。

{| cellpadding=10| | | 結合法則 |- | | | 交換法則 |- | | | 吸収法則 |- | | | 分配法則 |- | | | 可補束 |- | | | 等冪性 |- | | | rowspan=2 | 有界性 |- | | |- | | | 0 と 1 は相補的 |- | | | ド・モルガンの法則 |- | | | 対合 |}

最初の3つの法則が束を定義し、最初の5つの法則がブール代数を定義する。

4. 真理値表
-------

0 と 1 という2つの値のみを使ったブール論理で、それらの値の共通部分と和集合を真理値表で定義すると次のようになる:


複数の入力や他のブール演算を使った、もっと複雑な真理値表も作成できる。
真理値表は論理学にも応用でき、0 を偽、1 を真、 を AND、 を OR、¬ を NOT に読み替える。

5. 記号
-----

ブール論理の表記に使われる記号は、目的や学術分野、あるいは文化圏などによってさまざまである。まず、英単語にもとづく AND、OR、NOT といった一群がある。数学者や技術者は OR の代わりに +、AND の代わりに を使うことが多い。NOT は式の上に線を引いて表すこともある。

プログラマは、AND を表現するのに & 、OR を表すのに | を使うことが多い。これらの記号はプログラミング言語でビット演算の演算子として使われていることが多い。NOT は ! で表されることが多く、!= などの派生もある。

6. 自然言語でのブール論理
--------------

論理式をそのまま自然言語にすると、しばしば、同じ言葉の日常での意味と異なっていたり、曖昧だったりすることがあるため注意が必要である。

日本語の場合の例をいくつか挙げる。自然言語の「朝食にはパンか御飯を食べることができる」の「パンか御飯」は、そのまま解釈すればORだが、普通は排他的論理和すなわち「パンか御飯のどちらかを選ぶことができる」の意味であることが多い。曖昧な例としては「全ての輝くものが金ではない」という文は「輝くものは全て金ではない」とも「輝くものには金でないものもある」とも解釈できる。

7. 応用
-----

7.1. ブーリアン演算
------------

CG業界用語でその名も「ブーリアン演算」と呼ばれているものであるが、立体などの図形を集合としてとらえる数学的な手法をそのまま工学的に応用したもので、かつそのまま具体化される点で、直観的にわかりやすい応用のひとつである。

7.2. ディジタル回路設計
--------------

ブール論理は論理回路の設計にも使われる。その場合、0 と 1 はディジタル回路でのビットの異なる2つの状態を表し、電圧の高低に対応させることが、現代では多い。回路は変数を含む式で表され、変数が回路の入力、式を評価した結果が回路の出力に相当する。入力と出力の対応が完全に与えられれば、それをブール論理の式で表現することができる。

ANDゲート、ORゲート、NOTゲートのような基本論理回路だけを使うこともできるが、NANDゲート、NORゲート、XORゲートなども組み合わせてディジタル回路を構成することができる。組み合わせ方は、演算子の優先順位に従って直列や並列に結合する。

7.3. データベース
-----------

データベース管理システム等によるデータベースの操作は、各データベースを集合、クエリ結果などを部分集合、データベースに含まれる個々のデータを集合の要素とみなすと、ある種、集合の操作のようなものとみなすことができる。特に関係データベースは、データベースの操作が集合代数にもとづき整理・定義されているデータベースである。以下では、関係データベースの代表的なクエリ言語であるSQLの具体例を示す。

SELECT文の例を示す。

SELECT * FROM EMPLOYEES WHERE LAST_NAME = 'Smith' AND FIRST_NAME = 'John' ;
SELECT * FROM EMPLOYEES WHERE LAST_NAME = 'Smith' OR FIRST_NAME = 'John' ;
SELECT * FROM EMPLOYEES WHERE NOT LAST_NAME = 'Smith' ;複数のブール演算がある場合、括弧を使って演算の順序を制御することもある:

SELECT * FROM EMPLOYEES WHERE  AND  ;必要に応じて括弧をいくつも入れ子にすることも可能である。複数の表をブール演算で組み合わせることを結合と呼ぶ。

7.4. 検索エンジン
-----------

検索エンジンに代表される、検索を行なうネットサービスでも、ブール演算にもとづく検索式が使えるものがある。例として、Google検索のものを示す。

論理積には記号を使用しない。従って、キーワードを2つ並べた場合、論理積と解釈される。 "キーワード1" "キーワード2"
論理和には "OR" を使用する。 "キーワード1" OR "キーワード2"
マイナス記号で論理否定を表す。 "キーワード1" -"キーワード2"カッコは使えない。

8. 関連項目
-------

数理論理学
ブール代数
ブール領域
ブール関数
ブール値関数
論理回路
論理演算
ベン図
ラダー・ロジック
二進法
選言標準形
連言標準形

9. 外部リンク
--------

[1], by George Boole, Cambridge and Dublin Mathematical Journal Vol. III , pp. 183-98.
[2] , 論理式の取りうる値を全て計算するソフトウェア
[3]

fr:Algèbre de Boole hi:बूलीय बीजगणित ko:불 논리ky:Айтылыштар алгебрасыla:Algebra Booleana zh:逻辑代数