関数完全性

テンプレート:Sidebar 論理学において、論理結合子あるいはブール演算子の関数完全（かんすうかんぜん、テンプレート:Lang-en-short）な集合とは、その集合の元をブール式に組み合わせることで、あらゆる可能な真理値表を表現できるもののことである^[1]^[2]。よく知られた完全な結合子の集合はテンプレート:Nowrap である。単集合テンプレート:Nowrap とテンプレート:Nowrap はそれぞれ関数完全である。しかし、集合テンプレート:Nowrap はNOTを表現できないため不完全である。

関数完全であるゲート（あるいはゲートの集合）は、万能ゲート（あるいは万能なゲートの集合）と呼ばれることもある。

命題論理の文脈では、関数完全な結合子の集合は（表現的に）「十全」とも呼ばれる^[3]。

デジタル電子工学の観点からは、関数完全性とは、可能なあらゆる論理ゲートが、その集合によって規定された種類のゲートのネットワークとして実現できることを意味する。特に、あらゆる論理ゲートは、二項のNANDゲートのみから、あるいは二項のNORゲートのみから組み立てることができる。

序論

現代の論理学の教科書は、通常、結合子のいくつかの部分集合を原始的なものとして採用する。すなわち、連言（ $\land$ ）、選言（ $\lor$ ）、否定（ $\neg$ ）、実質条件法（ $\to$ ）、そして場合によっては双条件法（ $\leftrightarrow$ ）である。望むならば、さらに他の結合子を、これらの原始的な結合子を用いて定義することもできる。例えば、NOR（選言の否定であり、時に $↓$ と表される）は、2つの否定の連言として表すことができる。

A ↓ B := \neg A \land \neg B

同様に、連言の否定であるNAND（時に $↑$ と表される）は、選言と否定によって定義できる。あらゆる二項結合子は ${\neg, \land, \lor, \to, \leftrightarrow}$ によって定義できるため、この集合は関数完全である。しかし、これには冗長性がある。すなわち、この集合は「最小」の関数完全な集合ではない。なぜなら、条件法と双条件法は、他の結合子を用いて次のように定義できるからである。

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

したがって、より小さな集合 ${\neg, \land, \lor}$ もまた関数完全である。（この関数完全性はテンプレート:仮リンクによっても証明される。）^[4]しかし、これもまだ最小ではない。なぜなら $\lor$ は次のように定義できるからである。

A \lor B := \neg (\neg A \land \neg B) .

あるいは、同様の方法で $\land$ を $\lor$ によって定義することもできるし、 $\lor$ を $\to$ によって定義することもできる。

A \lor B := \neg A \to B .

これ以上の単純化は不可能である。したがって、 $\neg$ と ${\land, \lor, \to}$ のいずれか一つを含む2元の結合子の集合はいずれも、 ${\neg, \land, \lor, \to, \leftrightarrow}$ の最小の関数完全な部分集合である。

形式的定義

ブール領域テンプレート:Nowrap が与えられたとき、ブール関数の集合 F = テンプレート:Nowrap が「関数完全」であるとは、基本関数 f_i によって生成される B 上のテンプレート:仮リンクが、すべての「厳密に正の」整数テンプレート:Nowrap について、すべての関数テンプレート:Nowrap を含むことをいう。言い換えれば、少なくとも1つの変数を取るあらゆるブール関数が関数 f_i によって表現できるならば、その集合は関数完全である。少なくとも1つの変数を持つあらゆるブール関数は二項ブール関数によって表現できるため、F が関数完全であることと、あらゆる二項ブール関数が F 中の関数によって表現できることとは同値である。

より自然な条件は、F によって生成されるクローンが、すべての整数テンプレート:Nowrap について、すべての関数テンプレート:Nowrap からなることであろう。しかし、上記の例はこのより強い意味では関数完全ではない。なぜなら、F 自体が少なくとも1つの0項関数を含んでいなければ、F によって0項関数、すなわち定数式を書くことができないからである。このより強い定義のもとでは、最小の関数完全な集合は2つの元を持つことになる。

もう一つの自然な条件は、F と2つの0項定数関数とをあわせて生成されるクローンが関数完全である、あるいは同値であるが、前段落のより強い意味において関数完全であることであろう。テンプレート:Nowrap のときテンプレート:Nowrap であり、それ以外のときテンプレート:Nowrap であるようなブール関数の例は、この条件が関数完全性よりも厳密に弱いことを示している^[5]^[6]^[7]

関数完全性の特徴づけ

テンプレート:Further エミール・ポストは、論理結合子の集合が関数完全であることと、次に挙げる結合子の集合のいずれの部分集合でもないこととが同値であることを証明した。

単調的結合子。結びつけられた変数のいずれかの真理値をFからTへ変えても、いずれの変数もTからFへ変えないならば、これらの結合子はその返り値をTからFへ変えることはない。例えば $\lor, \land, ⊤, ⊥$ 。
アフィン結合子。結びつけられたそれぞれの変数が、その結合子が返す真理値に常に影響するか、あるいは決して影響しないかのいずれかである。例えば $\neg, ⊤, ⊥, \leftrightarrow, ↮$ 。
「自己双対」結合子。自らのテンプレート:仮リンクと等しい結合子であり、すべての変数の真理値が反転すれば、これらの結合子が返す真理値も反転する。例えば $\neg$ 、テンプレート:Nowrap。
「真理保存的」結合子。すべての変数にTを割り当てるいかなる解釈のもとでも真理値Tを返す。例えば $\lor, \land, ⊤, \to, \leftrightarrow$ 。
「偽性保存的」結合子。すべての変数にFを割り当てるいかなる解釈のもとでも真理値Fを返す。例えば $\lor, \land, ⊥, ↛, ↮$ 。

ポストは、2元集合テンプレート:Nowrap 上のすべてのテンプレート:仮リンク（合成について閉じており、すべての射影を含む演算の集合）の束についての完全な記述を与えた。これは今日ではテンプレート:仮リンクと呼ばれ、これは上記の結果を単純な系として含意する。すなわち、上に挙げた5つの結合子の集合は、まさに極大な非自明クローンである^[8]。

最小の関数完全な演算子集合

単一の論理結合子あるいはブール演算子だけで関数完全であるとき、それは「シェファー関数」と呼ばれ^[9]、時に「唯一十分演算子」とも呼ばれる。この性質を持つ単項演算子は存在しない。互いに双対であるNANDとNORは、唯一の2つの二項シェファー関数である。これらは1880年頃にチャールズ・サンダース・パースによって発見されたが公表されず、1913年にテンプレート:仮リンクによって独立に再発見され、公表された^[10]。デジタル電子工学の用語では、二項NANDゲート（↑）と二項NORゲート（↓）が、唯一の二項テンプレート:仮リンクである。

以下は、アリティ ≤ 2 を持つ最小の関数完全な論理結合子の集合である^[11]。

1元：{↑}、{↓}。
2元： ${\lor, \neg}$ , ${\land, \neg}$ , ${\to, \neg}$ , ${\leftarrow, \neg}$ , ${\to, ⊥}$ , ${\leftarrow, ⊥}$ , ${\to, ↮}$ , ${\leftarrow, ↮}$ , ${\to, ↛}$ , ${\to, ↚}$ , ${\leftarrow, ↛}$ , ${\leftarrow, ↚}$ , ${↛, \neg}$ , ${↚, \neg}$ , ${↛, ⊤}$ , ${↚, ⊤}$ , ${↛, \leftrightarrow}$ , ${↚, \leftrightarrow} .$
3元： ${\lor, \leftrightarrow, ⊥}$ , ${\lor, \leftrightarrow, ↮}$ , ${\lor, ↮, ⊤}$ , ${\land, \leftrightarrow, ⊥}$ , ${\land, \leftrightarrow, ↮}$ , ${\land, ↮, ⊤} .$

高々二項の論理結合子が4つ以上からなる最小の関数完全な集合は存在しない^[11]。上記の一覧を読みやすく保つため、1つ以上の入力を無視する演算子は省略されている。例えば、最初の入力を無視し、2番目の入力の否定を出力する演算子は、単項の否定に置き換えることができる。

アルフレト・タルスキの論文「On the Primitive Term of Logistic」は、 ${\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)

電子回路やソフトウェア関数は、再利用によって最適化し、ゲート数を減らすことができることに注意されたい。例えば、「テンプレート:Nowrap」という演算は、↑ゲートによって表現される場合、「テンプレート:Nowrap」を再利用して実装される。

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

他の領域における応用

論理結合子（ブール演算子）とは別に、関数完全性は他の領域にも導入することができる。例えば、あらゆる可逆演算子を表現できるならば、可逆ゲートの集合は関数完全であると呼ばれる。

3入力のフレドキンゲートは、それ自体で関数完全な可逆ゲートである。すなわち唯一十分演算子である。他にも、トフォリゲートのような多くの3入力の万能論理ゲートが存在する。

量子計算においては、テンプレート:仮リンク、テンプレート:仮リンク、テンプレート:仮リンクは万能であるが、関数完全性の定義よりもいくぶん制限の強い定義のもとでのことである。

集合論

集合の代数とブール代数の間には同型が存在する。すなわち、両者は同じ構造を持つ。したがって、ブール演算子を集合演算子に写せば、上記の「翻訳された」文章は集合についても成り立つ。すなわち、他のあらゆる集合関係を生成できる「集合論演算子の最小完全集合」は数多く存在する。より一般的な「最小完全演算子集合」はテンプレート:Nowrap とテンプレート:Nowrap である。もし全体集合が禁じられるならば、集合演算子は偽性（Ø）を保存するものに制限され、関数完全なブール代数と同値にはなりえない。

出典

テンプレート:Reflist

テンプレート:数理論理学

↑ テンプレート:Citation. ("Complete set of logical connectives").
↑ テンプレート:Citation. ("[F]unctional completeness of [a] set of logical operators").
↑ テンプレート:Citation. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)
↑ テンプレート:Cite book
↑ テンプレート:Citation
↑ テンプレート:Citation
↑ テンプレート:Citation
↑ テンプレート:Cite book See p.105 for the theorem, pp.53, 59, 69, 70, 131 for a definition of the classes A₁, L₁, C₂, C₃, D₃, and pp.35, 43 for the definition of [A:a] condition and α, β, γ function.
↑ The term was originally restricted to binary operations, but since the end of the 20th century it is used more generally. テンプレート:Citation.
↑ テンプレート:Citation.
↑ ^11.0 ^11.1 Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between $↚$ and $↛$ .
↑ テンプレート:Citation
↑ "NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html
↑ "NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html

[Enderton2001-1] テンプレート:Citation. ("Complete set of logical connectives").

[Nolt1998-2] テンプレート:Citation. ("[F]unctional completeness of [a] set of logical operators").

[Smith2003-3] テンプレート:Citation. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)

[:13-4] テンプレート:Cite book

[Wesselkamper1975a-5] テンプレート:Citation

[Massey1975-6] テンプレート:Citation

[Wesselkamper1975b-7] テンプレート:Citation

[8] テンプレート:Cite book See p.105 for the theorem, pp.53, 59, 69, 70, 131 for a definition of the classes A₁, L₁, C₂, C₃, D₃, and pp.35, 43 for the definition of [A:a] condition and α, β, γ function.

[Martin1989-9] The term was originally restricted to binary operations, but since the end of the 20th century it is used more generally. テンプレート:Citation.

[Scharle1965-10] テンプレート:Citation.

[Wernick-11] 11.0 ^11.1 Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between $↚$ and $↛$ .

[12] テンプレート:Citation

[13] "NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html

[14] "NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

関数完全性

目次

序論

形式的定義

関数完全性の特徴づけ

最小の関数完全な演算子集合

例

他の領域における応用

集合論

関連項目

出典

ナビゲーションメニュー

関数完全性

序論

形式的定義

関数完全性の特徴づけ

最小の関数完全な演算子集合

例

他の領域における応用

集合論

関連項目

出典

ナビゲーション メニュー

検索

ナビゲーションメニュー