非古典論理など他にも多くの論理の体系があるが、ここでは古典論理のうちの命題論理、特にそれを形式化したブール論理に話を絞る。従って対象がとる値は真理値の2値のみに限られる。また、その真理値の集合(真理値集合)と演算(演算子)はブール代数を構成する。
コンピュータのプロセッサやプログラミング言語で多用されるものに、ブーリアン型を対象とした通常の論理演算の他に、ワード等のビット毎に論理演算を行なう演算があり、ビット演算という。
なお、証明論的には、公理と推論規則に従って論理式を変形(書き換え)する演算がある(証明論#証明計算の種類)。
演算の種類
ここでは1出力の関数のみを扱う。2出力以上の関数は、(実装はともかく)論理的には1出力の関数を並べるだけであり自明と言ってよいであろう。以下では、真理値の記号は {0, 1} とする。
1入力
1入力1出力のブール関数は以下の4通りのみであり、その中でトリビアルでない、興味があるものはNOTだけであろう。
- 入力がなんであれ、常に 0 を出力する
- 入力がなんであれ、常に 1 を出力する
- 入力がなんであれ、入力と同じ値をそのまま出力する
- 入力が 0 であれば 1 を、入力が 1 であれば 0 を出力する。すなわち入力の反転(「否定」とも言う)を出力する (NOTあるいはinversion、以下では ¬ の記号を使う)
2入力
2つの入力 P、Q に対し、以下の16通りが全てである。
この節、および以降に続く節では、和に ∨、積に ∧ の記号を使う。
|
|
|
否定論理積
|
記法
|
等価式
|
真理値表
|
ベン図
|
P ↑ Q P | Q P NAND Q
|
P → ¬Q ¬P ← Q ¬P
|
|
非含意
|
記法
|
等価式
|
真理値表
|
ベン図
|
P
|
|
|
|
|
逆非含意
|
記法
|
等価式
|
真理値表
|
ベン図
|
P
|
|
逆含意
|
記法
|
等価式
|
真理値表
|
ベン図
|
P
|
|
|
|
|
|
|
否定論理和
|
記法
|
等価式
|
真理値表
|
ベン図
|
P ↓ Q P NOR Q
|
P
|
|
定理
以上の演算に対して成り立っている定理として、以下のようなものがある。(証明論的には(「命題論理の証明論」)、以下の等式のいくつかに相当する公理 and・or 推論規則が採用される)