機能の完全性

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

機能的に完全なゲート (またはゲートのセット) は、ユニバーサル ゲート (またはゲートのユニバーサル セット) とも呼ばれます。

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

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

導入

現代の論理学の教科書では、通常、接続詞のサブセットである連言（）、選言（）、否定（）、質的条件（）、そして場合によっては二条件（）を基本語として取り上げます。必要に応じて、これらの基本語を用いて、さらに接続詞を定義することもできます。例えば、NOR（選言の否定、 と表記されることもあります）は、2つの否定の連言として表現できます。 ${\displaystyle \land }$ ${\displaystyle \lor }$ ${\displaystyle \neg }$ ${\displaystyle \to }$ ${\displaystyle \leftrightarrow }$ ${\displaystyle \downarrow }$

${\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}}}$

より小さい集合も関数的に完全であることが分かる。（その関数的完全性は選言標準形定理によっても証明されている。）^[4]しかし、これはまだ最小ではない。次のように定義できる。 ${\displaystyle \{\neg ,\land ,\lor \}}$ ${\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 }$ ${\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 つの変数を取るすべてのブール関数は、2 値ブール関数で表現できるため、すべての 2 値ブール関数がF内の関数で表現できる場合のみ、F は機能的に完全です。

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

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

機能的完全性の特徴づけ

エミール・ポストは、論理接続詞の集合が機能的に完全であるためには、それが以下の接続詞の集合のいずれの部分集合でもないということを証明しました。

• 単調接続詞。接続された変数の真理値をTからFに変更せずにFからTに変更すると、これらの接続詞の戻り値が T から F に変更されることはありません(例) 。${\displaystyle \vee ,\wedge ,\top ,\bot }$
• アフィン接続子では、接続された各変数は、これらの接続子が返す真理値に常に影響を与えるか、まったく影響を与えないかのいずれかになります。${\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }$
• 自己双対接続子はそれ自身のド・モルガン双対に等しくなります。すべての変数の真理値が反転されると、これらの接続子が返す真理値も反転されます (例: maj ( p、q、r ) )。${\displaystyle \neg }$
• 真理値保存接続子。すべての変数に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 年頃にCharles Sanders Peirceによって発見されたが公表されず、 1913 年にHenry M. Shefferによって独立に再発見され公表された^[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番目の入力の否定を出力する演算子は、単項否定に置き換えることができる。

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

例

• 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入力の汎用論理ゲートは数多く存在します。

量子コンピューティングでは、機能的完全性の定義よりも若干制限が厳しいものの、アダマール ゲートとT ゲートは普遍的です。

集合論

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

参照

• 集合の代数 – 集合に関する恒等式と関係
• ブール代数 – 「真」と「偽」の代数的操作
• 完全性（論理）  – いくつかの論理システムの特徴
• 連言/選言の双対性 – 論理的連言と選言を結びつける性質
• ブール代数のトピックのリスト
• NANDロジック – NANDゲートのみで構成されたロジック
• NORロジック - NORゲートだけを使って他のゲートを作る
• 1命令セットコンピュータ - 1つの命令のみを使用する抽象マシン

参考文献

1. エンダートン、ハーバート（2001）、論理への数学的入門（第2版）、ボストン、マサチューセッツ州：アカデミックプレス、ISBN 978-0-12-238452-3（「論理接続詞の完全なセット」）。
2. ノルト、ジョン、ロハティン、デニス、ヴァルジ、アキレ（1998）、シャウムの理論と論理の問題の概要（第2版）、ニューヨーク：マグロウヒル、ISBN 978-0-07-046649-4. （「論理演算子の集合の機能的完全性」）。
3. スミス、ピーター（2003）、形式論理入門、ケンブリッジ大学出版局、ISBN 978-0-521-00804-4（セクションの見出しで「表現的に適切」、つまり「適切な接続詞のセット」を定義します。）
4. ハウソン、コリン (1997).木による論理：記号論理入門. ロンドン; ニューヨーク: ラウトレッジ. p. 41. ISBN 978-0-415-13342-5。
5. Wesselkamper, TC (1975)、「唯一の十分な演算子」、Notre Dame Journal of Formal Logic、16 : 86–88、doi : 10.1305/ndjfl/1093891614
6. Massey, GJ (1975)、「シェファー関数について」、Notre Dame Journal of Formal Logic、16 (4): 549– 550、doi : 10.1305/ndjfl/1093891898
7. Wesselkamper, TC (1975)、「私の論文の訂正」A. Sole Sufficient Operator、Notre Dame Journal of Formal Logic、16 (4): 551、doi : 10.1305/ndjfl/1093891899
8. エミール・レオン・ポスト (1941). 『数理論理学の2値反復システム』. Annals of Mathematics studies. 第5巻. プリンストン: プリンストン大学出版局. doi :10.1515/9781400882366. ISBN 9781400882366。 定理については105ページ、A ₁、L ₁、C ₂、C ₃、D ₃のクラスの定義については53、59、69、70、131ページ、[A:a]条件とα、β、γ関数の定義については35、43ページを参照してください。
9. この用語はもともと二項演算に限定されていましたが、20世紀末以降はより一般的に使用されるようになりました。Martin , NM (1989), Systems of logic , Cambridge University Press, p. 54, ISBN 978-0-521-36770-7。
10. Scharle, TW (1965)、「シェファー関数による命題計算の公理化」、Notre Dame J. Formal Logic、6 (3): 209– 217、doi : 10.1305/ndjfl/1093958259 。
11. Wernick, William (1942)「Complete Sets of Logical Functions」、Transactions of the American Mathematical Society 51 : 117–32。論文の最終ページにあるリストにおいて、Wernickは ← と → 、あるいは と を区別していない。${\displaystyle \nleftarrow }$ ${\displaystyle \nrightarrow }$
12. Tajtelbaum-Tarski, Alfred (1998), Srzednicki, Jan TJ; Stachniak, Zbigniew (eds.), "On the Primitive Term of Logistic" , Leśniewski's Systems Protothetic , Dordrecht: Springer Netherlands, pp.  43– 68, doi :10.1007/978-94-011-5736-0_3, ISBN 978-94-011-5736-0、2025年8月3日取得
13. 「NANDゲート操作」http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
14. 「NORゲート操作」http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html