論理演算

論理演算の概要

論理演算は、論理式を用いて真理値を求めるプロセスを指します。このプロセスにおいては論理演算子を通じてブール関数を評価することが主な目的です。特に古典論理の一種である命題論理、さらにその形式化としてのブール論理に焦点を当てます。ブール論理では、対象とする値として真（1）または偽（0）の二つの値のみが用いられ、この二値の集合と演算はブール代数を形成します。コンピュータのプロセッサやプログラミングにおいて使われる通常の論理演算に加え、ビット単位で行うビット演算も重要な役割を果たします。ビット演算は、各ビットに対して論理演算を実施する技術です。

演算の種類

論理演算は、一般に1出力の関数に焦点を当てています。2出力以上の関数に関しては、論理的には単純に1出力関数を組み合わせて構成できるため、ここでは1出力の関数を中心に考えます。真理値の記号としては {0, 1} を使用します。

1入力の演算

1入力の1出力ブール関数は以下の4つに分類されますが、なかでも特に注目すべきは
「否定」を表すNOT演算です。

1. 入力が常に 0 を出力する関数
2. 入力が常に 1 を出力する関数
3. 入力と同じ値をそのまま出力する関数
4. 入力が 0 のときは 1 を、1 のときは 0 を出力する関数（NOT演算）

2入力の演算

二つの入力 P と Q に対しては、全16通りの演算が可能です。
以下はその演算を示す記号です。和は ∨、積は ∧ の記号を使用します。

定理

これらの演算には多くの定理が存在します。ここではいくつかの重要な法則を紹介します。

べき等則

1. p ∨ p ≡ p
2. p ∧ p ≡ p

交換則

1. p ∨ q ≡ q ∨ p
2. p ∧ q ≡ q ∧ p

結合則

1. p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r
2. p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r

分配則

1. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
2. p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

吸収則

1. p ∨ (p ∧ q) ≡ p
2. p ∧ (p ∨ q) ≡ p

ド・モルガンの法則

1. ¬(p ∨ q) ≡ (¬p) ∧ (¬q)
2. ¬(p ∧ q) ≡ (¬p) ∨ (¬q)

その他の基礎定理

1. p ∨ 0 ≡ p
2. p ∧ 0 ≡ 0
3. p ∨ 1 ≡ 1
4. p ∧ 1 ≡ p
5. p ∨ (¬p) ≡ 1
6. p ∧ (¬p) ≡ 0
7. ¬(¬p) ≡ p

完全性

これらの演算の一部を組み合わせることで、任意の論理演算を実装することが可能です。この特性をフルコンプリート性と呼びます。特に否定演算¬の存在により、和 ∨ と積 ∧ のどちらか一方があれば完全な演算が可能となります。興味深いのは、否定論理和(NOR)や否定論理積(NAND)のように、これらの組み合わせの中には完全な機能を果たすものが存在することです。