論理演算

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

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

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

なお、証明論的には、公理と推論規則に従って論理式を変形︵書き換え︶する演算がある︵証明論#証明計算の種類︶。

演算の種類

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

1入力

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

●入力がなんであれ、常に 0 を出力する

●入力がなんであれ、常に1を出力する

●入力がなんであれ、入力と同じ値をそのまま出力する

●入力が 0 であれば1を、入力が1であれば 0 を出力する。すなわち入力の反転︵﹁否定﹂とも言う︶を出力する (NOTあるいはinversion、以下では ¬ の記号を使う)

2入力

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

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

矛盾 記法 等価式 真理値表 ベン図 $\bot$ P $\wedge$ ¬P   Q 0 1 P 0    0   0  1    0   0	恒真 記法 等価式 真理値表 ベン図 $\top$ P $\vee$ ¬P   Q 0 1 P 0    1   1  1    1   1
論理積 記法 等価式 真理値表 ベン図 P $\wedge$ Q P & Q P AND Q P $\not \rightarrow$¬Q ¬P $\not \leftarrow$ Q ¬P $\downarrow$ ¬Q   Q 0 1 P 0    0   0  1    0   1	否定論理積 記法 等価式 真理値表 ベン図 P ↑ Q P | Q P NAND Q P → ¬Q ¬P ← Q ¬P $\lor$ ¬Q   Q 0 1 P 0    1   1  1    1   0
非含意 記法 等価式 真理値表 ベン図 P $\not \rightarrow$ Q P $\not \supset$ Q P & ¬Q ¬P ↓ Q ¬P $\not \leftarrow$ ¬Q   Q 0 1 P 0    0   0  1    1   0	含意 (条件式) 記法 等価式 真理値表 ベン図 P → Q P $\supset$ Q P ↑ ¬Q ¬P $\lor$ Q ¬P ← ¬Q   Q 0 1 P 0    1   1  1    0   1
命題 P 記法 等価式 真理値表 ベン図 P                      Q 0 1 P 0    0   0  1    1   1	否定 P 記法 等価式 真理値表 ベン図 ¬P                      Q 0 1 P 0    1   1  1    0   0
逆非含意 記法 等価式 真理値表 ベン図 P $\not \leftarrow$ Q P $\not \subset$ Q P ↓ ¬Q ¬P & Q ¬P $\not \rightarrow$ ¬Q   Q 0 1 P 0    0   1  1    0   0	逆含意 記法 等価式 真理値表 ベン図 P $\leftarrow$ Q P $\subset$ Q P $\lor$ ¬Q ¬P ↑ Q ¬P → ¬Q   Q 0 1 P 0    1   0  1    1   1
命題 Q 記法 等価式 真理値表 ベン図 Q                      Q 0 1 P 0    0   1  1    0   1	否定 Q 記法 等価式 真理値表 ベン図 ¬Q                      Q 0 1 P 0    1   0  1    1   0
排他的論理和 記法 等価式 真理値表 ベン図 P $\not \leftrightarrow$ Q P $\not \equiv$ Q P $\oplus$ Q P XOR Q P $\leftrightarrow$ ¬Q ¬P $\leftrightarrow$ Q ¬P $\not \leftrightarrow$ ¬Q   Q 0 1 P 0    0   1  1    1   0	同値 (必要十分条件) 記法 等価式 真理値表 ベン図 P $\leftrightarrow$ Q P ≡ Q P XNOR Q P IFF Q P $\not \leftrightarrow$ ¬Q ¬P $\not \leftrightarrow$ Q ¬P $\leftrightarrow$ ¬Q   Q 0 1 P 0    1   0  1    0   1
論理和 記法 等価式 真理値表 ベン図 P $\lor$ Q P OR Q P $\leftarrow$ ¬Q ¬P → Q ¬P ↑ ¬Q   Q 0 1 P 0    0   1  1    1   1	否定論理和 記法 等価式 真理値表 ベン図 P ↓ Q P NOR Q P $\not \leftarrow$ ¬Q ¬P $\not \rightarrow$ Q ¬P & ¬Q   Q 0 1 P 0    1   0  1    0   0

定理

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

• べき等則

${\begin{aligned}p\lor p&\equiv p\\p\land p&\equiv p\\\end{aligned}}$

• 交換則

${\begin{aligned}p\lor q&\equiv q\lor p\\p\land q&\equiv q\land p\\\end{aligned}}$

• 結合則

${\begin{aligned}p\lor (q\lor r)&\equiv (p\lor q)\lor r\\p\land (q\land r)&\equiv (p\land q)\land r\\\end{aligned}}$

• 分配則

${\begin{aligned}p\lor (q\land r)&\equiv (p\lor q)\land (p\lor r)\\p\land (q\lor r)&\equiv (p\land q)\lor (p\land r)\\\end{aligned}}$

• 吸収則

${\begin{aligned}p\lor (p\land q)&\equiv p\\p\land (p\lor q)&\equiv p\\\end{aligned}}$

• ド・モルガンの法則

${\begin{aligned}\lnot (p\lor q)&\equiv (\lnot p)\land (\lnot q)\\\lnot (p\land q)&\equiv (\lnot p)\lor (\lnot q)\\\end{aligned}}$

• その他

${\begin{aligned}&p\lor 0\equiv p\\&p\land 0\equiv 0\\&p\lor 1\equiv 1\\&p\land 1\equiv p\\&p\lor (\lnot p)\equiv 1\\&p\land (\lnot p)\equiv 0\\&\lnot (\lnot p)\equiv p\\\end{aligned}}$

その他

その他の話題

完全性

「否定論理積#完全性」も参照

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

関連項目

• カルノー図
• ド・モルガンの法則
• 真理値
• マスク (情報工学)
• 数学 - 数理論理学
• 論理学
• 論理回路
• ブール関数 - ブール代数
• ベン図 - オイラー図
• ブーリアン演算
• プログラミング言語
• 数学記号の表#記号論理の記号