論理演算
論理演算(ろんりえんざん、logical operation)は、論理式において、論理演算子などで表現される論理関数(ブール関数)を評価し(正確には、関数適用を評価し[1])、変数(変項)さらには論理式全体の値を求める演算である。
非古典論理など他にも多くの論理の体系があるが、ここでは古典論理のうちの命題論理、特にそれを形式化したブール論理に話を絞る。従って対象がとる値は真理値の2値のみに限られる。また、その真理値の集合(真理値集合)と演算(演算子)はブール代数を構成する。
コンピュータのプロセッサやプログラミング言語で多用されるものに、ブーリアン型を対象とした通常の論理演算の他に、ワード等のビット毎に論理演算を行なう演算があり、ビット演算という。
なお、証明論的には、公理と推論規則に従って論理式を変形(書き換え)する演算がある(証明論#証明計算の種類)。
演算の種類
ここでは1出力の関数のみを扱う。2出力以上の関数は、(実装はともかく)論理的には1出力の関数を並べるだけであり自明と言ってよいであろう。以下では、真理値の記号は {0, 1} とする。
1入力
1入力1出力のブール関数は以下の4通りのみであり、その中でトリビアルでない、興味があるものはNOTだけであろう。
- 入力がなんであれ、常に 0 を出力する
- 入力がなんであれ、常に 1 を出力する
- 入力がなんであれ、入力と同じ値をそのまま出力する
- 入力が 0 であれば 1 を、入力が 1 であれば 0 を出力する。すなわち入力の反転(「否定」とも言う)を出力する (NOTあるいはinversion、以下では ¬ の記号を使う)
2入力
2つの入力 P、Q に対し、以下の16通りが全てである。
この節、および以降に続く節では、和に ∨、積に ∧ の記号を使う。
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
定理
以上の演算に対して成り立っている定理として、以下のようなものがある。(証明論的には(「命題論理の証明論」)、以下の等式のいくつかに相当する公理 and・or 推論規則が採用される)
- その他
その他
その他の話題
完全性
(詳細は英語版記事 en:Functional completeness を参照のこと)以上の演算のうち、ごく少数の種類の演算の組み合わせによって、任意の演算を「実装」することができる。そのような演算の組の性質を functional completeness という。∨ と ∧ だけでは完全ではなく、必ず ¬ も必要である。一方 ¬ があれば、∨ と ∧ はどちらか一方でも良い。さらに興味深いものとして、¬ と ∨ あるいは ∧ の組合せである、否定論理積(NAND)や否定論理和(NOR)は、それ一つだけで完全である。なお、→ の記号が使われることが多い「ならば」(imply、論理包含)は微妙な点があり(たとえば、演算子だけでなく定数入力を必要とする)、英語版Wikipediaの Implicational propositional calculus の記事(en:Implicational propositional calculus)では「virtual completeness」と表現している。
注
- ^ たとえば、三角関数の sin などといった関数それ自体が「関数」であり、sin(3.14) などのように関数と実引数とを結びつけること and・or 結びつけたものを「関数適用」と言う。
関連項目
- カルノー図
- ド・モルガンの法則
- 真理値
- マスク (情報工学)
- 数学 - 数理論理学
- 論理学
- 論理回路
- ブール関数 - ブール代数
- ベン図 - オイラー図
- ブーリアン演算
- プログラミング言語
- 数学記号の表#記号論理の記号
論理演算 | ||
---|---|---|
![]() ![]() | ||
| |
---|---|
一般 | |
Traditional logic(英語版) | |
述語論理 | |
素朴集合論 | |
集合論 |
|
モデル理論 | |
証明論 | |
計算理論 再帰理論 |
- 表示
- 編集