【論理関数③】完全系 | 魁高専 -SAKIGAKE Colleges of Technology-

論理関数の完全系とは、他の全ての論理関数をその関数の組み合わせだけで表現できる論理関数のセットを指します。例えばNAND、あるいはNORは組み合わせる事で、それだけで他の全ての論理関数を表現することができます。これは、NANDやNORが単独で完全系となることを意味します。

NORを用いたNOT回路

NOT回路は、入力の論理値を反転させる回路です。つまり、入力が0の場合は出力が1になり、入力が1の場合は出力が0になります。

NORゲートは、2つの入力のどちらも0の場合のみ出力が1となる論理ゲートです。それ以外の場合（すなわち、少なくとも1つの入力が1の場合）は出力が0になります。

NOT回路をNORゲートで表現するには、NORゲートの2つの入力に同じ値を供給します。このとき、NORゲートは次のように動作します：

このように、NORゲートの両方の入力に同じ値を供給することで、NOTの動作を模倣することができます。したがって、NORゲートを使用してNOT回路を実装することが可能です。

NANDゲートは、2つの入力が共に1のときのみ出力が0となる論理ゲートです。それ以外の場合（すなわち、少なくとも1つの入力が0の場合）は出力が1になります。

NOT回路の動作をNANDゲートで再現するためには、NANDゲートの2つの入力端子に同じ信号を入力します。このとき、NANDゲートは以下のように動作します：

このように、NANDゲートの両方の入力に同じ値を供給することで、NOTの動作を模倣することができます。したがって、NANDゲートだけでNOT回路の動作を実現することが可能です。

先ほどのNOR（NAND）回路を使ったNOT回路を応用すると、NOR（NAND）だけでOR（AND）回路も構成できます。

手順は以下の通りです：

NOR回路のみを用いてAND回路を構成することが出来ます。

AのNOTを取得する
AのNOTは次のように表現できます。
$\text{NOT}(A) &= \text{NOR}(A, A) = \overline{A + A} = \overline{A} \\$
BのNOTを取得する
同様に、BのNOTも次のように表現できます。
$\text{NOT}(B) &= \text{NOR}(B, B) = \overline{B + B} = \overline{B} \\$
AND動作の再現
2つのNOT出力を次のNORゲートに入力として供給します。
$\text{AND}(A, B) &= \text{NOR}(\overline{A}, \overline{B}) \\$