ブール論理

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

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

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

用語編集

共通部分 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 にも含まれ、かつ両集合が等しくないことを意味する。

例編集

30までの自然数を普遍集合とし、2の倍数の集合、3の倍数の集合、5の倍数の集合の関係を表した図

集合 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 は ! （感嘆符）で表されることが多く、!= などの派生もある。

自然言語でのブール論理編集

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

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

応用編集

ブーリアン演算編集

「ブーリアン演算」を参照

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

ディジタル回路設計編集

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

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

データベース編集

データベース管理システム等によるデータベースの操作は、各データベースを集合、クエリ結果などを部分集合、データベースに含まれる個々のデータを集合の要素とみなすと、ある種、集合の操作のようなものとみなすことができる。特に関係データベースは、データベースの操作が集合代数にもとづき整理・定義されているデータベースである（関係代数 (関係モデル) ）。以下では、関係データベースの代表的なクエリ言語である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

ブール論理

目次

用語編集