ブール論理

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ブール論理（英: Boolean logic）とは、論理的算法の完全な体系である。その名称は19世紀中ごろに論理の代数系を初めて定義したジョージ・ブールに由来する。ブール論理は、電子工学、制御工学、コンピュータハードウェア/ソフトウェアなどで広く応用されている。1938年、クロード・シャノンはブール論理をリレーによる電気回路で実装する方法を示した。この事実は間もなく電子式コンピュータの創造に不可欠であることが判明した。

本項目では、集合代数を用いて、集合、ブール演算、ベン図、真理値表などの基本的解説とブール論理の応用について解説する。ブール代数の記事ではブール論理の公理を満足する代数的構造の型を説明している。二進記数法の記事ではコンピュータで使われる二進数を説明している。

[編集] 用語

積集合 A AND B（紫の部分）、和集合 A OR B（色が付いている部分全体）、A XOR B（紫以外の色が付いている部分）。四角い外枠は「普遍集合; universe」

Xを集合としたとき:

元（element; 要素）とは、集合のメンバーを意味する。これを $\in$ で表す。集合の元でないものは $\notin$ で表す。
普遍集合（universe; 全集合）とは、集合 X であり、1 で表される場合がある。ここで universe（通常の意味は宇宙）という言葉が使われるのは「全ての元を考慮している」ことを意味しており、必ずしも「全ての元が存在する」必要があるわけではない。
空集合（empty set, null set）とは、元を持たない集合であり、 $\varnothing$ または 0 で表される。
単項演算子（unary operator）は1つの集合に適用される。単項演算子としては論理否定（NOT）のみがある。補集合をとる働きがある。
二項演算子（binary operator）は2つの集合に適用される。基本的な演算子には論理和（OR）と論理積（AND）がある。これらは和集合と積集合をとる。これらから導出される二項演算子として XOR（排他的OR）などもある。
部分集合（subset）は $A \subseteq B$ で表され、集合 A の全ての元が集合 B にも含まれることを意味する。
真部分集合（proper subset）は $A \subset B$ で表され、集合 A の全ての元が集合 B にも含まれ、かつ両集合は等しくないことを意味する。
上位集合（superset）は $A \supseteq B$ で表され、集合 B の全ての元が集合 A にも含まれることを意味する。
真上位集合（proper superset）は $A \supset B$ で表され、集合 B の全ての元が集合 A にも含まれ、かつ両集合が等しくないことを意味する。

[編集] 例

集合 A には普遍集合の中の全ての偶数（2の倍数）が含まれ、集合 B には同じ普遍集合の中の全ての 3 の倍数が含まれるとする。そのとき、これらの集合の積集合（A AND B の集合の全ての元）は、その普遍集合の中の全ての6の倍数が含まれる。

集合 A の補集合（NOT A に含まれる全ての元）は、その普遍集合の全ての奇数となる。

[編集] 演算の連鎖

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

[編集] 括弧の使用

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

[編集] 論理演算の法則

2つの二項演算子の記号を $\land / \cap$ （論理積/AND/積集合）と $\lor / \cup$ （論理和/OR/和集合）とし、単項演算子の記号を $\lnot$ / ~ （論理否定/NOT/補集合）とする。また、値 0 （偽/空集合）と 1 （真/普遍集合）も使用する。ブール代数とブール論理では以下のような法則が成り立つ。

$a \lor (b \lor c) = (a \lor b) \lor c$	$a \land (b \land c) = (a \land b) \land c$	結合法則
$a \lor b = b \lor a$	$a \land b = b \land a$	交換法則
$a \lor (a \land b) = a$	$a \land (a \lor b) = a$	吸収法則
$a \lor (b \land c) = (a \lor b) \land (a \lor c)$	$a \land (b \lor c) = (a \land b) \lor (a \land c)$	分配法則
$a \lor \lnot a = 1$	$a \land \lnot a = 0$	可補束
$a \lor a = a$	$a \land a = a$	等冪性
$a \lor 0 = a$	$a \land 1 = a$	有界性
$a \lor 1 = 1$	$a \land 0 = 0$	有界性
$\lnot 0 = 1$	$\lnot 1 = 0$	0 と 1 は相補的
$\lnot (a \lor b) = \lnot a \land \lnot b$	$\lnot (a \land b) = \lnot a \lor \lnot b$	ド・モルガンの法則
$\lnot \lnot a = a$		対合

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

[編集] 真理値表

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

$\cap$	0	1
0	0	0
1	0	1

$\cup$	0	1
0	0	1
1	1	1

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

[編集] その他の記法

ブール論理の演算子の表現方法は様々である。AND、OR、NOT が最も直観的である。数学者や技術者は OR の代わりに +、AND の代わりに $\cdot$ を使うことが多い（これらの演算子は他の代数的構造での加算や乗算と性質が似ており、通常の代数に詳しい者にとっては加法標準形を理解しやすいため）。NOT は式の上に線を引いて表すこともある。

プログラマは、AND を表現するのに & （アンパサンド）、OR を表すのに | （パイプ記号）を使うことが多い。これらの記号はプログラミング言語でビット演算の記号として使われていることが多い。NOT は ! （感嘆符）で表されることが多い。

[編集] 初等数学でのブール論理

並列の等式があるとき、それらは AND で結合されていると見なすことができる:

x + y = 2

AND

x - y = 2

並列の不等式も同様である:

x + y < 2

AND

x - y < 2

等号付き不等号（ $\ge$ と $\le$ ）は以下のように OR の意味を持つと解釈される:

X < 2

X = 2

正負の符号（ $\pm$ ）が平方根問題の解に使われる場合、以下のように OR の意味を持つと解釈される:

WIDTH = 3

WIDTH = -3

[編集] 日本語でのブール論理

日本語の文を形式的なブール論理に変換する際には注意が必要である。日本語には意味が曖昧な場合が多々ある。例えば「全ての輝くものが金ではない」という文は「輝くものは全て金ではない」（全否定）とも「輝くものには金でないものもある」（部分否定）とも解釈できる。

この節は執筆中です。加筆、訂正して下さる協力者を求めています。

[編集] 応用

[編集] デジタル回路設計

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

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

[編集] データベース

関係データベースではクエリのためにSQLなどのデータベース固有の言語を使うが、これらはブール論理を含んでいる。この場合、表内のレコードは「集合」の中の「元」に相当する。例えば、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 (NOT LAST_NAME = 'Smith') AND (FIRST_NAME = 'John' OR FIRST_NAME = 'Mary') ;

必要に応じて括弧をいくつも入れ子にすることも可能である。複数の表をブール演算で組み合わせることを結合と呼ぶ（関係代数）。

[編集] 検索エンジン

この場合、インターネット上の各ウェブページが「集合」の「元」に相当する。検索エンジンによってクエリの文法は様々である。ここではGoogleでの文法を説明する。

論理積には記号を使用しない。従って、キーワードを2つ並べた場合、論理積と解釈される。

"キーワード1" "キーワード2"

論理和には "OR" を使用する。

"キーワード1" OR "キーワード2"

マイナス記号で論理否定を表す（実際にはAND NOT）。

"キーワード1" -"キーワード2"

演算子の優先順位が決まっているため、括弧は使用しない。

面白いことに、Google Scholarでは "OR" を使うと排他的論理和(XOR)の操作が行われる。

[編集] 関連項目

[編集] 外部リンク

The Calculus of Logic, by George Boole, Cambridge and Dublin Mathematical Journal Vol. III (1848), pp. 183-98.
Logical Formula Evaluator (for Windows), 論理式の取りうる値を全て計算するソフトウェア
How Stuff Works - Boolean Logic

"http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%BC%E3%83%AB%E8%AB%96%E7%90%86" より作成