関数的に完全な集合とは何か？

定義¹

ブール関数の集合$\left\{ f_{k} \right\} = \left\{ f_{k} : \left\{ 0, 1 \right\}^{n_{k}} \to \left\{ 0, 1 \right\} \right\}_{k\in \Gamma}$が与えられたとしよう。$\Gamma$は有限集合だ。任意のブール関数

$$ \left\{ 0, 1 \right\}^{n} \to \left\{ 0, 1 \right\}\quad (n \in \mathbb{N}) $$

が$\left\{ f_{k} \right\}$の合成で表現できるとき、集合$\left\{ f_{k} \right\}$を機能的に完全^{functionally complete}だという。

定理

$\text{NOT}$ゲートと$\text{AND}$ゲートの集合$\left\{ \lnot, \land \right\}$は機能的に完全だ。

説明

つまり、全てのブール関数は$\text{NOT}$と$\text{AND}$の繰り返しで作ることができる。機能的に完全な集合は一意ではなく、無数にある。例えば$a \land b = \lnot(\lnot a \lor \lnot b)$であるため、$\left\{ \lnot, \lor \right\}$も機能的に完全な集合だ。この定理から、任意の集合が$\text{AND}$ゲートと$\text{NOT}$ゲートを作ることができるかだけ示せば、機能的に完全な集合であることを証明できる。

機能的に完全な集合の例:

• $\text{NAND}$ゲート
• $\text{NOR}$ゲート
• $T$(トフォリゲート)
• $F$(フレドキンゲート)
• $\left\{ \lnot, \lor \right\}$
• $\left\{ \oplus, \land \right\}$

もちろん複製関数が必要な場合もある。これらの結果をコンピュータ回路の言葉で述べれば以下のようになる。全ての論理演算は:

• $\text{NOT}$ゲートと$\text{AND}$ゲートのみを使用して回路に実装できる。
• $\text{NAND}$ゲートと複製関数のみを使用して回路に実装できる。
• $\text{NOR}$ゲートと複製関数のみを使用して回路に実装できる。
• トフォリゲートのみを使用して回路に実装できる。
• フレドキンゲートのみを使用して回路に実装できる。

ユニバーサルゲート

特に、自分自身だけで構成された集合$\left\{ f \right\}$が機能的に完全なとき、そのような$f$をユニバーサルゲートという。ユニバーサルゲートは自分自身だけで全てのブール関数を表現できる。$\text{NAND}$、$\text{NOR}$、$T$、$F$はユニバーサルゲートだ。