利用者:Distart/working/機能的完全性

論理学において、機能的完全性 (汎用性、完全性、英: functional completeness, universalilty, expressive adequateness^[1]) とは、ある種の論理関数の集合のもつ性質で、任意の論理関数がその集合中の演算を組み合わせに還元できることをいう^[2]^[3]。例えば { and, not } や { nand } のような集合は完全である。デジタル回路では、完全になるよう論理ゲートを用意すればどのような計算も実現できる。NANDゲートやNORゲートだけを使って他の素子なしに論理回路を設計できることはよく知られている。

機能的完全性をもつことを、この項では「完全である」のように言い表す。

形式的な定義

ブール領域 B = {0,1} 上で、論理関数 ƒ_i: B^n_i → B の集合 F のクローン（英語版）が全ての論理関数 ƒ: Bⁿ → B (n ≥ 1) を網羅するとき、 F は完全である。言い換えると、任意の論理関数を ƒ_i の組み合わせで定義できることを完全であるという。一つ以上の変数をとる論理関数は二項の論理演算子で表現できるので、これは二つの変数をとる論理関数が全て F 中の関数で表現できることと同値である。

集合としては変数をとらない(つまり定数)関数を定義に含めるほうが自然だが、二項演算子のみを使って定数を定義することはできないため、条件に含める場合は F は定数を含む必要がある。この場合、F は最低二つの要素を持つ。

また、前者の定義の F のクローンに B を加えたものが完全であるとする考え方もある^{[訳語疑問点]}。これは以下のような関数を考えればむしろ弱い条件であることがわかる^[4]^[5]^[6]。

S(x,y,z)={\begin{cases}z&(x=y)\\x&(x\neq y)\end{cases}}

非形式的な定義

よく使われる論理演算子は論理積 ( $\land$ )、論理和 ( $\lor$ )、否定 ( $\neg$ )、含意 ( $\to$ )、同値 ( $\leftrightarrow$ )などが挙げられる。これら5つを入れた集合は完全ではあるが、最小ではない。なぜなら、含意や同値は次のように他の演算子を使って定義できるからである。

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

つまり、集合 $\{\neg ,\land ,\lor \}$ も完全である。また、 $\lor$ も次のように置き換えられる。

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

逆に $\land$ を $\lor$ で置き換えてもよい。他に、 $\vee$ を $\rightarrow$ で置き換えることもできる。

A\vee B:=(A\rightarrow B)\rightarrow B

$\neg$ を集合中の他の演算子で置き換えることはできないので、これ以上の簡略化はできない。よって、 $\neg$ と $\{\land ,\lor ,\rightarrow \}$ のいずれか一つを組み合わせたものが $\{\neg ,\land ,\lor ,\to ,\leftrightarrow \}$ の完全な部分集合としては最小である。

特徴

→詳細は「ポスト束（英語版）」を参照

エミール・ポストは、論理演算子の集合が以下の集合の部分でないことが機能的完全性の必要十分条件であることを示した。

単調な論理演算子。例えば、真の入力に対して真を出力し、偽の出力に対しても真に出力するような関数。 $\vee$ , $\wedge$ , $\top$ , $\bot$ など。

アフィン写像。全ての変数が同時に影響するような関数。 $\neg$ , $\top$ , $\bot$ , $\leftrightarrow$ , $\not \leftrightarrow$ など。

自己双対な演算子。ド・モルガン双対をとったときに真理値表で全ての出力が反転するもの。 $\neg$ , MAJ(p,q,r) (多数決関数（英語版）) など。

真の値を保存する演算子。全ての変数に真を与えたとき結果が真となるもの。 $\vee$ , $\wedge$ , $\top$ , $\rightarrow$ , $\leftrightarrow$ など。

偽の値を保存する演算子。全ての変数に偽を与えたとき結果が偽となるもの。 $\vee$ , $\wedge$ , < $\bot$ , $\not \rightarrow$ , $\not \leftrightarrow$ など。

ポストは真理値 {T, F} 上のすべてのクローン（英語版）（論理関数の集合に組み合わせる演算を定義したもの）を帰納的に数え上げた束を研究した。これはポスト束（英語版）と今日呼ばれている。上に挙げたものはその研究の帰結である。つまり、上の５つはいずれもポスト束の極大元である^{[訳語疑問点]}。

Minimal functionally complete operator sets

When a single logical connective or Boolean operator is functionally complete by itself, it is called a Sheffer function^[7] or sometimes a sole sufficient operator. There are no unary operators with this property, and the only binary Sheffer functions are NAND and NOR, its dual. These were discovered but not published by Charles Sanders Peirce around 1880, and rediscovered independently and published by Henry M. Sheffer in 1913.^[8] In digital electronics terminology, the binary NAND gate and the binary NOR gate are the only binary universal logic gates.

The following are the minimal functionally complete sets of logical connectives with arity ≤ 2:^[9]

One element: {NAND}, {NOR}.
Two elements: { $\vee$ , ¬}, { $\wedge$ , ¬}, {→, ¬}, {←, ¬}, {→, $\bot$ }, {←, $\bot$ }, {→, $\not \leftrightarrow$ }, {←, $\not \leftrightarrow$ }, {→, $\not \to$ }, {→, $\not \leftarrow$ }, {←, $\not \to$ }, {←, $\not \leftarrow$ }, { $\not \to$ , ¬}, { $\not \leftarrow$ , ¬}, { $\not \to$ , $\top$ }, { $\not \leftarrow$ , $\top$ }, { $\not \to$ , $\leftrightarrow$ }, { $\not \leftarrow$ , $\leftrightarrow$ }.
Three elements: { $\lor$ , $\leftrightarrow$ , $\bot$ }, { $\lor$ , $\leftrightarrow$ , $\not \leftrightarrow$ }, { $\lor$ , $\not \leftrightarrow$ , $\top$ }, { $\land$ , $\leftrightarrow$ , $\bot$ }, { $\land$ , $\leftrightarrow$ , $\not \leftrightarrow$ }, { $\land$ , $\not \leftrightarrow$ , $\top$ }.

There are no minimal functionally complete sets of more than three at most binary logical connectives.^[9] Constant unary or binary connectives and binary connectives that depend only on one of the arguments have been suppressed to keep the list readable. E.g. the set consisting of binary $\vee$ and the binary connective given by negation of the first argument (ignoring the second) is another minimal functionally complete set.

Examples

Examples of using the NAND completeness. As illustred by ^[10],
- ¬A = A NAND A
- A ∧ B = (A NAND B) NAND (A NAND B)
- A ∨ B = (A NAND A) NAND (B NAND B)

Examples of using the NOR completeness. As illustred by ^[11],
- ¬A = A NOR A
- A ∧ B = (A NOR A) NOR (B NOR B)
- A ∨ B = (A NOR B) NOR (A NOR B)

NOTE: a eletronic circuit or a software function are optimized by the reuse, that reduce the number of gates. For instance, the "A ∧ B" operation, when expressed by NAND gates, is implemented with the reuse of "A NAND B",

X = (A NAND B); A ∧ B = X NAND X

In other domains

Apart from logical connectives (Boolean operators), functional completeness can be introduced in other domains. For example, a set of reversible gates is called functionally complete, if it can express every reversible operator.

The 3-input Fredkin gate is functionally complete reversible gate by itself – a sole sufficient operator. There are many other three-input universal logic gates, such as the Toffoli gate.

Set theory

There are a isomorphism between Algebra of sets and the Boolean algebra, that is, they have the same structure. Then, if we map boolean operators into set operators, the "translated" above text are valid also for sets: there are many "minimal complete set of set-theory operators" that can generates any other set relations. The more popular "Minimal complete operator sets" are {¬, ∩} and {¬, ∪}.

References

^ Smith, Peter (2003), An introduction to formal logic, Cambridge University Press, ISBN 978-0-521-00804-4 . (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)
^ Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3 . ("Complete set of logical connectives").
^ Nolt, John; Rohatyn, Dennis; Varzi, Achille (1998), Schaum's outline of theory and problems of logic (2nd ed.), New York: McGraw–Hill, ISBN 978-0-07-046649-4 . ("[F]unctional completeness of [a] set of logical operators").
^ Wesselkamper, T.C. (1975), “A sole sufficient operator”, Notre Dame Journal of Formal Logic 16: 86–88, doi:10.1305/ndjfl/1093891614
^ Massey, G.J. (1975), “Concerning an alleged Sheffer function”, Notre Dame Journal of Formal Logic 16 (4): 549–550, doi:10.1305/ndjfl/1093891898
^ Wesselkamper, T.C. (1975), “A Correction To My Paper" A. Sole Sufficient Operator”, Notre Dame Journal of Formal Logic 16 (4): 551, doi:10.1305/ndjfl/1093891899
^ The term was originally restricted to binary operations, but since the end of the 20th century it is used more generally. Martin, N.M. (1989), Systems of logic, Cambridge University Press, p. 54, ISBN 978-0-521-36770-7 .
^ Scharle, T.W. (1965), “Axiomatization of propositional calculus with Sheffer functors”, Notre Dame J. Formal Logic 6 (3): 209–217, doi:10.1305/ndjfl/1093958259 .
^ ^a ^b 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 $\not \leftarrow$ and $\not \rightarrow$ .
^ "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

Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32.

[Smith2003-1] Smith, Peter (2003), An introduction to formal logic, Cambridge University Press, ISBN 978-0-521-00804-4 . (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)

[Enderton2001-2] Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3 . ("Complete set of logical connectives").

[Nolt1998-3] Nolt, John; Rohatyn, Dennis; Varzi, Achille (1998), Schaum's outline of theory and problems of logic (2nd ed.), New York: McGraw–Hill, ISBN 978-0-07-046649-4 . ("[F]unctional completeness of [a] set of logical operators").

[Wesselkamper1975a-4] Wesselkamper, T.C. (1975), “A sole sufficient operator”, Notre Dame Journal of Formal Logic 16: 86–88, doi:10.1305/ndjfl/1093891614

[Massey1975-5] Massey, G.J. (1975), “Concerning an alleged Sheffer function”, Notre Dame Journal of Formal Logic 16 (4): 549–550, doi:10.1305/ndjfl/1093891898

[Wesselkamper1975b-6] Wesselkamper, T.C. (1975), “A Correction To My Paper" A. Sole Sufficient Operator”, Notre Dame Journal of Formal Logic 16 (4): 551, doi:10.1305/ndjfl/1093891899

[Martin1989-7] The term was originally restricted to binary operations, but since the end of the 20th century it is used more generally. Martin, N.M. (1989), Systems of logic, Cambridge University Press, p. 54, ISBN 978-0-521-36770-7 .

[Scharle1965-8] Scharle, T.W. (1965), “Axiomatization of propositional calculus with Sheffer functors”, Notre Dame J. Formal Logic 6 (3): 209–217, doi:10.1305/ndjfl/1093958259 .

[Wernick-9] 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 $\not \leftarrow$ and $\not \rightarrow$ .

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

[11] "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]