論理演算

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

論理演算(ろんりえんざん、logical operation)は、論理式において、論理演算子などで表現される論理関数(ブール関数)を評価し(正確には、関数適用を評価し[1])、変数(変項)さらには論理式全体の値を求める演算である。

非古典論理など他にも多くの論理の体系があるが、ここでは古典論理のうちの命題論理、特にそれを形式化したブール論理に話を絞る。従って対象がとる値は真理値の2値のみに限られる。また、その真理値の集合(真理値集合)と演算(演算子)はブール代数を構成する。

コンピュータのプロセッサプログラミング言語で多用されるものに、ブーリアン型を対象とした通常の論理演算の他に、ワード等のビット毎に論理演算を行なう演算があり、ビット演算という。

なお、以上はモデル論的な議論であり、証明論的には、公理推論規則に従って論理式を変形(書き換え)する演算がある(証明論#証明計算の種類)。

演算の種類[編集]

ここでは1出力の関数のみを扱う。2出力以上の関数は、(実装はともかく)論理的には1出力の関数を並べるだけであり自明と言ってよいであろう。以下では、真理値の記号は {0, 1} とする。

1入力[編集]

1入力1出力のブール関数は以下の4通りのみであり、その中でトリビアルでない、興味があるものはNOTだけであろう。

  • 入力がなんであれ、常に 0 を出力する
  • 入力がなんであれ、常に 1 を出力する
  • 入力がなんであれ、入力と同じ値をそのまま出力する
  • 入力が 0 であれば 1 を、入力が 1 であれば 0 を出力する。すなわち入力の反転(「否定」とも言う)を出力する (NOTあるいはinversion、以下では ¬ の記号を使う)

2入力[編集]

2つの入力 PQ に対し、以下の16通りが全てである。

この節、および以降に続く節では、に ∨、に ∧ の記号を使う。

矛盾
記法 等価式 真理値表 ベン図
P ¬P
  Q
0 1
P 0    0   0 
1    0   0 
Venn0000.svg


トートロジー
記法 等価式 真理値表 ベン図
P ¬P
  Q
0 1
P 0    1   1 
1    1   1 
Venn1111.svg


論理積
記法 等価式 真理値表 ベン図
P Q
P & Q
P AND Q
P ¬Q
¬P Q
¬P ¬Q
  Q
0 1
P 0    0   0 
1    0   1 
Venn0001.svg


否定論理積
記法 等価式 真理値表 ベン図
PQ
P | Q
P NAND Q
P → ¬Q
¬PQ
¬P ¬Q
  Q
0 1
P 0    1   1 
1    1   0 
Venn1110.svg


非含意
記法 等価式 真理値表 ベン図
P Q
P Q
P & ¬Q
¬PQ
¬P ¬Q
  Q
0 1
P 0    0   0 
1    1   0 
Venn0100.svg


含意 (条件式)
記法 等価式 真理値表 ベン図
PQ
P Q
P ↑ ¬Q
¬P Q
¬P ← ¬Q
  Q
0 1
P 0    1   1 
1    0   1 
Venn1011.svg


命題 P
記法 等価式 真理値表 ベン図
P                   
  Q
0 1
P 0    0   0 
1    1   1 
Venn0101.svg


否定 P
記法 等価式 真理値表 ベン図
¬P                   
  Q
0 1
P 0    1   1 
1    0   0 
Venn1010.svg


逆非含意
記法 等価式 真理値表 ベン図
P Q
P Q
P ↓ ¬Q
¬P & Q
¬P ¬Q
  Q
0 1
P 0    0   1 
1    0   0 
Venn0010.svg


逆含意
記法 等価式 真理値表 ベン図
P Q
P Q
P ¬Q
¬PQ
¬P → ¬Q
  Q
0 1
P 0    1   0 
1    1   1 
Venn1101.svg


命題 Q
記法 等価式 真理値表 ベン図
Q                   
  Q
0 1
P 0    0   1 
1    0   1 
Venn0011.svg


否定 Q
記法 等価式 真理値表 ベン図
¬Q                   
  Q
0 1
P 0    1   0 
1    1   0 
Venn1100.svg


排他的論理和
記法 等価式 真理値表 ベン図
P Q
P Q
P Q
P XOR Q
P ¬Q
¬P Q
¬P ¬Q
  Q
0 1
P 0    0   1 
1    1   0 
Venn0110.svg


同値 (必要十分条件)
記法 等価式 真理値表 ベン図
P Q
PQ
P XNOR Q
P IFF Q
P ¬Q
¬P Q
¬P ¬Q
  Q
0 1
P 0    1   0 
1    0   1 
Venn1001.svg


論理和
記法 等価式 真理値表 ベン図
P Q
P OR Q
P ¬Q
¬PQ
¬P ↑ ¬Q
  Q
0 1
P 0    0   1 
1    1   1 
Venn0111.svg


否定論理和
記法 等価式 真理値表 ベン図
PQ
P NOR Q
P ¬Q
¬P Q
¬P & ¬Q
  Q
0 1
P 0    1   0 
1    0   0 
Venn1000.svg


定理[編集]

以上の演算に対して成り立っている定理として、以下のようなものがある。(証明論的には(「命題論理の証明論」)、以下の等式のいくつかに相当する公理 and・or 推論規則が採用される)

  • その他

その他[編集]

その他の話題

完全性[編集]

(詳細は英語版記事 en:Functional completeness を参照のこと)以上の演算のうち、ごく少数の種類の演算の組み合わせによって、任意の演算を「実装」することができる。そのような演算の組の性質を functional completeness という。∨ と ∧ だけでは完全ではなく、必ず ¬ も必要である。一方 ¬ があれば、∨ と ∧ はどちらか一方でも良い。さらに興味深いものとして、¬ と ∨ あるいは ∧ の組合せである、否定論理積NAND)や否定論理和NOR)は、それ一つだけで完全である。なお、→ の記号が使われることが多い「ならば」(imply、論理包含)は微妙な点があり(たとえば、演算子だけでなく定数入力を必要とする)、英語版Wikipediaの Implicational propositional calculus の記事(en:Implicational propositional calculus)では「virtual completeness」と表現している。

[編集]

  1. ^ たとえば、三角関数の sin などといった関数それ自体が「関数」であり、sin(3.14) などのように関数と実引数とを結びつけること and・or 結びつけたものを「関数適用」と言う。

関連項目[編集]