機能的完全性

論理学において、機能的に完全な論理結合子またはブール演算子の集合とは、集合の要素を組み合わせてブール式にすることで、考えられるすべての真理値表を表現できる集合のことである。^{[ 1 ] [ 2 ]}よく知られている完全な結合子の集合は{ AND , NOT }である。単一要素の集合{ NAND }と{ NOR }はそれぞれ機能的に完全である。しかし、集合{ AND, OR }はNOT を表現できないため、不完全である。

機能的に完全なゲート（またはゲートの集合）は、ユニバーサルゲート（またはユニバーサルゲートの集合）とも呼ばれる。

命題論理の文脈では、機能的に完全な結合子の集合は、（表現的に）適切であるとも呼ばれる。^{[ 3 ]}

デジタルエレクトロニクスの観点から言えば、機能的完全性とは、あらゆる論理ゲートが、規定されたタイプのゲートのネットワークとして実現できることを意味する。具体的には、すべての論理ゲートは、バイナリNANDゲートのみ、またはバイナリNORゲートのみから構成できる。

現代の論理学のテキストでは、通常、結合子のサブセットを原始的なものとして扱います:論理積(${\displaystyle \land }$);選言(${\displaystyle \lor }$);否定(${\displaystyle \neg }$);材料条件付き(${\displaystyle \to }$); そしておそらく双条件(${\displaystyle \leftrightarrow }$) 必要に応じて、これらの基本要素を用いて定義することで、さらに結合子を定義することができます。たとえば、NOR (論理和の否定、時には と表記される) は、${\displaystyle \downarrow }$）は、2つの否定の論理積として表現できます。

${\displaystyle A\downarrow B:=\neg A\land \neg B}$

同様に、論理積の否定である NAND (時には次のように表記される)${\displaystyle \uparrow }$は、選言と否定の観点から定義できます。すべての二項結合子は、${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$つまり、この集合は機能的に完全である。しかし、冗長性がある。条件文と双条件文は他の接続詞で定義できるため、この集合は最小限の機能的に完全な集合ではない。

${\displaystyle {\begin{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}}$

したがって、より小さいセットは${\displaystyle \{\neg ,\land ,\lor \}}$機能的にも完全である。（その機能的完全性は選言標準形定理によっても証明されている。）^{[ 4 ]}しかし、これはまだ最小ではない。${\displaystyle \lor }$定義できる

${\displaystyle A\lor B:=\neg (\neg A\land \neg B).}$

あるいは、${\displaystyle \land }$は、${\displaystyle \lor }$同様の方法で、または${\displaystyle \lor }$は、${\displaystyle \rightarrow }$:

${\displaystyle \ A\vee B:=\neg A\rightarrow B.}$

これ以上の簡略化は不可能である。したがって、結合子の 2 要素セットには、${\displaystyle \neg }$そしてそのうちの1つは${\displaystyle \{\land ,\lor ,\rightarrow \}}$は、機能的に完全な最小部分集合である。${\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}$。

ブール定義域B = {0, 1}が与えられたとき、ブール関数f _i : B ^{n _i} → Bの集合Fは、基本関数f _iによって生成されるB上のクローンが、すべての厳密に正の整数n ≥ 1に対してすべての関数f : B ⁿ → Bを含む場合に機能的に完全である。言い換えれば、少なくとも 1 つの変数を取るすべてのブール関数が関数f _iで表現できる場合に、集合は機能的に完全である。少なくとも 1 つの変数を持つすべてのブール関数はバイナリ ブール関数で表現できるため、F は、すべてのバイナリ ブール関数がFの関数で表現できる場合に限り、機能的に完全である。  

より自然な条件としては、 Fによって生成されるクローンが、すべての整数n ≥ 0に対して、すべての関数f  : B ⁿ → Bから構成されるという条件が考えられます。しかし、上記の例は、このより強い意味では機能的に完全ではありません。なぜなら、F自体が少なくとも 1 つのヌル関数を含まない場合、 Fを用いてヌル関数、すなわち定数式を記述することができないからです。このより強い定義を用いると、機能的に完全な最小集合は 2 つの要素を持つことになります。

もう一つの自然な条件は、 Fによって生成されるクローンと 2 つのヌル引数定数関数が機能的に完全であること、あるいは同等に、前の段落の強い意味で機能的に完全であることです。S ( x , y , z ) = z (x = y の場合) および S ( x , y , z ) = x (それ以外の場合) で与えられるブール関数の例は、この条件が機能的完全性よりも厳密に弱いことを示しています。^{[ 5 ] [ 6 ] [ 7 ]}

エミール・ポストは、論理結合子の集合が機能的に完全であるのは、それが以下のどの結合子の集合の部分集合でもない場合に限ることを証明した。

• 単調結合子。結合された変数の真理値をFからTに変更しても、TからFに変更しない限り、これらの結合子の戻り値はTからFに変わりません。例:${\displaystyle \vee ,\wedge ,\top ,\bot }$。
• アフィン結合子では、各接続変数が常に、または決してこれらの結合子が返す真理値に影響を与えない。例：${\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }$。
• 自己双対結合子は、自身のド・モルガン双対と等しい。すべての変数の真理値が反転すると、これらの結合子が返す真理値も反転する。例：${\displaystyle \neg }$、maj ( p、q、r )。
• 真理値保存結合子。すべての変数にTを割り当てるあらゆる解釈の下で真理値Tを返します。例:${\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow }$。
• 偽値保存結合子。すべての変数にFを割り当てるあらゆる解釈の下で真偽値Fを返します。例:${\displaystyle \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow }$。

ポストは、2要素集合{ T , F }上のすべてのクローン(合成に関して閉じており、すべての射影を含む演算の集合)の格子を完全に記述しました。これは現在ポストの格子と呼ばれており、上記の結果を単純な系として導きます。すなわち、前述の 5 つの結合子の集合は、まさに最大の非自明なクローンです。^{[ 8 ]}

単一の論理結合子またはブール演算子がそれ自体で機能的に完全である場合、それはシェファー関数^{[ 9 ]}または時には単独十分演算子と呼ばれます。この性質を持つ単項演算子はありません。互いに双対であるNANDとNORは、唯一の2つのバイナリシェファー関数です。これらは1880年頃にチャールズ・サンダース・パースによって発見されましたが、公表されず、 1913年にヘンリー・M・シェファーによって独立して再発見され、公表されました。^{[ 10 ]} デジタルエレクトロニクスの用語では、バイナリNANDゲート(↑)とバイナリNORゲート(↓)は、唯一のバイナリユニバーサル論理ゲートです。

以下は、アリティ が2 以下の論理結合子の最小限の機能的に完全な集合です。 ^{[ 11 ]}

1つの要素

{↑}、{↓}。

2つの要素

${\displaystyle \{\vee ,\neg \}}$、${\displaystyle \{\wedge ,\neg \}}$、${\displaystyle \{\to ,\neg \}}$、${\displaystyle \{\gets ,\neg \}}$、${\displaystyle \{\to ,\bot \}}$、${\displaystyle \{\gets ,\bot \}}$、${\displaystyle \{\to ,\nleftrightarrow \}}$、${\displaystyle \{\gets ,\nleftrightarrow \}}$、${\displaystyle \{\to ,\nrightarrow \}}$、${\displaystyle \{\to ,\nleftarrow \}}$、${\displaystyle \{\gets ,\nrightarrow \}}$、${\displaystyle \{\gets ,\nleftarrow \}}$、${\displaystyle \{\nrightarrow ,\neg \}}$、${\displaystyle \{\nleftarrow ,\neg \}}$、${\displaystyle \{\nrightarrow ,\top \}}$、${\displaystyle \{\nleftarrow ,\top \}}$、${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$、${\displaystyle \{\nleftarrow ,\leftrightarrow \}.}$

3つの要素

${\displaystyle \{\lor ,\leftrightarrow ,\bot \}}$、${\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}$、${\displaystyle \{\lor ,\nleftrightarrow ,\top \}}$、${\displaystyle \{\land ,\leftrightarrow ,\bot \}}$、${\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}$、${\displaystyle \{\land ,\nleftrightarrow ,\top \}.}$

機能的に完全な最小のバイナリ論理結合子のセットは、最大で 3 つまでしか存在しません。^{[ 11 ]}上記のリストを読みやすくするために、1 つ以上の入力を無視する演算子は省略されています。たとえば、最初の入力を無視して 2 番目の入力の否定を出力する演算子は、単項否定に置き換えることができます。

アルフレッド・タルスキの論文「ロジスティックの原始項について」は、${\displaystyle \{\leftrightarrow \}}$機能的には完全であるが、^{[ 12 ]}これは命題に対する量化（二階述語論理の装置）が使用されている場合にのみ機能するため、上記のリストには含まれない。

• NAND（↑）完全性の使用例。 ^{[ 13 ]に示されているように。}
  • ¬ A ≡ A ↑ A
  • A ∧ B ≡ ¬( A ↑ B ) ≡ ( A ↑ B ) ↑ ( A ↑ B )
  • A ∨ B ≡ (¬ A ) ↑ (¬ B ) ≡ ( A ↑ A ) ↑ ( B ↑ B )
• NOR(↓)完全性の使用例。 ^{[ 14 ]に示されているように。}
  • ¬ A ≡ A ↓ A
  • A ∨ B ≡ ¬( A ↓ B ) ≡ ( A ↓ B ) ↓ ( A ↓ B )
  • A ∧ B ≡ (¬ A ) ↓ (¬ B ) ≡ ( A ↓ A ) ↓ ( B ↓ B )

電子回路やソフトウェア機能は、再利用によって最適化され、ゲートの数を減らすことができることに注意してください。たとえば、「A ∧ B 」演算は、↑ ゲートで表現すると、「 A ↑ B 」の再利用によって実装されます。

X ≡ ( A ↑ B ); A ∧ B ≡ X ↑ X

論理結合子（ブール演算子）以外にも、機能的完全性は他の領域にも導入できる。例えば、可逆ゲートの集合は、すべての可逆演算子を表現できる場合、機能的に完全であると言われる。

3入力フレドキンゲートは、それ自体で機能的に完全な可逆ゲートであり、唯一の十分演算子である。トフォリゲート など、他にも多くの3入力ユニバーサル論理ゲートが存在する。

量子コンピューティングにおいては、アダマールゲート、CNOTゲート、Tゲートは普遍的なゲートであるが、その定義は機能的完全性の定義よりもやや限定的である。

集合代数とブール代数の間には同型性があり、つまり同じ構造を持っています。したがって、ブール演算子を集合演算子にマッピングすると、上記の「翻訳された」テキストは集合にも適用されます。つまり、他のあらゆる集合関係を生成できる「最小完全集合論演算子セット」が多数存在します。より一般的な「最小完全演算子セット」は、{¬, ∩ }と{¬, ∪ }です。普遍集合が禁止されている場合、集合演算子は偽（Ø）を保存することに制限され、機能的に完全なブール代数と等価になることはできません。

• 集合の代数– 集合に関する恒等式と関係 
• ブール代数– 「真」と「偽」の代数的操作 
• 完全性（論理）– 一部の論理体系の特徴 
• 論理積／論理選言の二重性– 論理積と論理選言を結びつける性質 
• ブール代数のトピック一覧
• NANDロジック– NANDゲートのみで構成されるロジック 
• NOR論理– NORゲートのみを使用して他のゲートを作成する 
• 単一命令セットコンピュータ– 1つの命令のみを使用する抽象機械