View source for Functional completeness

{{Short description|Concept in mathematical logic}}
{{Logical connectives sidebar}}
In [[Mathematical logic|logic]], a '''functionally complete''' set of [[logical connective]]s or [[Boolean function|Boolean operators]] is one that can be used to express all possible [[truth table]]s by combining members of the [[Set (mathematics)|set]] into a [[Boolean expression]].<ref name="Enderton2001">{{citation | last1=Enderton | first1=Herbert | title=A mathematical introduction to logic | publisher=[[Academic Press]] | location=Boston, MA | edition=2nd | isbn=978-0-12-238452-3 | year=2001}}. ("Complete set of logical connectives").</ref><ref name="Nolt1998">{{citation | last1=Nolt | first1=John | last2=Rohatyn | first2=Dennis | last3=Varzi | first3=Achille | title=Schaum's outline of theory and problems of logic | publisher=[[McGraw–Hill]] | location=New York | edition=2nd | isbn=978-0-07-046649-4 | year=1998}}. ("[F]unctional completeness of [a] set of logical operators").</ref> A well-known complete set of connectives is {{nowrap|{{mset| [[logical conjunction|AND]], [[Negation|NOT]] }}}}. Each of the [[singleton (mathematics)|singleton]] sets {{nowrap|{{mset| [[Sheffer stroke|NAND]] }}}} and {{nowrap|{{mset| [[Logical NOR|NOR]] }}}} is functionally complete. However, the set {{nowrap|{{mset| AND, [[Logical disjunction|OR]] }}}} is incomplete, due to its inability to express NOT.

A gate (or set of gates) that is functionally complete can also be called a universal gate (or a universal set of gates).

In a context of [[propositional logic]], functionally complete sets of connectives are also called (''expressively'') ''adequate''.<ref name="Smith2003">{{citation | last1=Smith | first1=Peter | title=An introduction to formal logic | publisher=[[Cambridge University Press]] | isbn=978-0-521-00804-4 | year=2003}}. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)</ref>

From the point of view of [[digital electronics]], functional completeness means that every possible [[logic gate]] can be realized as a network of gates of the types prescribed by the set. In particular, all logic gates can be assembled from either only binary [[NAND gate]]s, or only binary [[NOR gate]]s.

== Introduction ==
Modern texts on logic typically take as primitive some subset of the connectives: [[logical conjunction|conjunction]] (<math>\land</math>); [[logical disjunction|disjunction]] (<math>\lor</math>); [[negation]] (<math>\neg</math>); [[material conditional]] (<math>\to</math>); and possibly the [[Logical biconditional|biconditional]] (<math>\leftrightarrow</math>). Further connectives can be defined, if so desired, by defining them in terms of these primitives. For example, NOR (the negation of the disjunction, sometimes denoted <math>\downarrow</math>) can be expressed as conjunction of two negations:
: <math>A \downarrow B := \neg A \land \neg B</math>
Similarly, the negation of the conjunction, NAND (sometimes denoted as <math>\uparrow</math>), can be defined in terms of disjunction and negation. Every binary connective can be defined in terms of <math>\{ \neg, \land, \lor, \to, \leftrightarrow \}</math>, which means that set is functionally complete. However, it contains redundancy: this set is not a ''minimal'' functionally complete set, because the conditional and biconditional can be defined in terms of the other connectives as
: <math>\begin{align}
  A \to B &:= \neg A \lor B\\
  A \leftrightarrow B &:= (A \to B) \land (B \to A).
\end{align}</math>

It follows that the smaller set <math>\{\neg, \land, \lor\}</math> is also functionally complete. (Its functional completeness is also proved by the [[Disjunctive Normal Form Theorem]].)<ref name=":13">{{Cite book |last=Howson |first=Colin |title=Logic with trees: an introduction to symbolic logic |date=1997 |publisher=Routledge |isbn=978-0-415-13342-5 |location=London; New York |pages=41}}</ref> But this is still not minimal, as <math>\lor</math> can be defined as
: <math>A \lor B := \neg(\neg A \land \neg B).</math>

Alternatively, <math>\land</math> may be defined in terms of <math>\lor</math> in a similar manner, or <math>\lor</math> may be defined in terms of <math> \rightarrow </math>:
: <math> \ A \vee B := \neg A \rightarrow B. </math>

No further simplifications are possible. Hence, every two-element set of connectives containing <math>\neg</math> and one of <math>\{\land, \lor, \rightarrow\}</math> is a minimal functionally complete [[subset]] of <math>\{\neg, \land, \lor, \to, \leftrightarrow\}</math>.

== Formal definition ==
Given the [[Boolean domain]] {{nowrap|1='''B''' = {{mset|0, 1}}}}, a set ''F'' of Boolean functions {{nowrap|''f''<sub>''i''</sub> : '''B'''<sup>''n''<sub>''i''</sub></sup> → '''B'''}} is ''functionally complete'' if the [[clone (algebra)|clone]] on '''B''' generated by the basic functions ''f''<sub>''i''</sub> contains all functions {{nowrap|''f'' : '''B'''<sup>''n''</sup> → '''B'''}}, for all ''strictly positive'' integers {{nowrap|''n'' ≥ 1}}. In other words, the set is functionally complete if every Boolean function that takes at least one variable can be expressed in terms of the functions ''f''<sub>''i''</sub>. Since every Boolean function of at least one variable can be expressed in terms of binary Boolean functions, ''F'' is functionally complete if and only if every binary Boolean function can be expressed in terms of the functions in ''F''.

A more natural condition would be that the clone generated by ''F'' consist of all functions {{nowrap|''f'' : '''B'''<sup>''n''</sup> → '''B'''}}, for all integers {{nowrap|''n'' ≥ 0}}. However, the examples given above are not functionally complete in this stronger sense because it is not possible to write a [[arity|nullary]] function, i.e. a constant expression, in terms of ''F'' if ''F'' itself does not contain at least one nullary function. With this stronger definition, the smallest functionally complete sets would have 2 elements.

Another natural condition would be that the clone generated by ''F'' together with the two nullary constant functions be functionally complete or, equivalently, functionally complete in the strong sense of the previous paragraph. The example of the Boolean function given by {{nowrap|1=''S''(''x'', ''y'', ''z'') = ''z''}} if {{nowrap|1=''x'' = ''y''}} and {{nowrap|1=''S''(''x'', ''y'', ''z'') = ''x''}} otherwise shows that this condition is strictly weaker than functional completeness.<ref name=Wesselkamper1975a>
{{citation
 | title = A sole sufficient operator
 | url = http://projecteuclid.org/euclid.ndjfl/1093891614
 | year = 1975
 | author = Wesselkamper, T.C.
 | journal = Notre Dame Journal of Formal Logic
 | volume = 16
 | pages = 86–88
 | doi = 10.1305/ndjfl/1093891614
 | doi-access = free
}}</ref><ref name=Massey1975>
{{citation
 | title = Concerning an alleged Sheffer function
 | url = http://projecteuclid.org/euclid.ndjfl/1093891898
 | year = 1975
 | author = Massey, G.J.
 | journal = Notre Dame Journal of Formal Logic
 | volume = 16
 | pages = 549–550
 | doi = 10.1305/ndjfl/1093891898
 | issue = 4
 | doi-access = free
}}</ref><ref name=Wesselkamper1975b>
{{citation
 | title = A Correction To My Paper" A. Sole Sufficient Operator
 | url = http://projecteuclid.org/euclid.ndjfl/1093891899
 | year = 1975
 | author = Wesselkamper, T.C.
 | journal = Notre Dame Journal of Formal Logic
 | volume = 16
 | pages = 551
 | doi = 10.1305/ndjfl/1093891899
 | issue = 4
 | doi-access = free
}}</ref>

== Characterization of functional completeness ==
{{further|Post's lattice}}
[[Emil Leon Post|Emil Post]] proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives:
* The [[monotonic]] connectives; changing the truth value of any connected variables from '''F''' to '''T''' without changing any from '''T''' to '''F''' never makes these connectives change their return value from '''T''' to '''F''', e.g. <math>\vee, \wedge, \top, \bot</math>.
* The [[affine transformation|affine]] connectives, such that each connected variable either always or never affects the truth value these connectives return, e.g. <math>\neg, \top, \bot, \leftrightarrow, \nleftrightarrow</math>.
* The ''self-dual'' connectives, which are equal to their own [[de Morgan dual]]; if the truth values of all variables are reversed, so is the truth value these connectives return, e.g. <math>\neg</math>, {{nowrap|[[majority function|maj]](''p'', ''q'', ''r'')}}.
* The ''truth-preserving'' connectives; they return the [[truth value]] '''T''' under any interpretation that assigns '''T''' to all variables, e.g. <math>\vee, \wedge, \top, \rightarrow, \leftrightarrow</math>.
* The ''falsity-preserving'' connectives;  they return the truth value '''F''' under any interpretation that assigns '''F''' to all variables, e.g. <math>\vee, \wedge, \bot, \nrightarrow, \nleftrightarrow</math>.

Post gave a complete description of the [[lattice (order)|lattice]] of all [[clone (algebra)|clone]]s (sets of operations closed under composition and containing all projections) on the two-element set {{nowrap|{{mset|'''T''', '''F'''}}}}, nowadays called [[Post's lattice]], which implies the above result as a simple corollary: the five mentioned sets of connectives are exactly the maximal nontrivial clones.<ref>{{cite book | url=https://dokumen.pub/qdownload/the-two-valued-iterative-systems-of-mathematical-logic-am-5-volume-5-9781400882366.html | isbn=9781400882366 | doi=10.1515/9781400882366 | author=Emil Leon Post | title=The Two-Valued Iterative Systems of Mathematical Logic | location=Princeton | publisher=Princeton University Press | series=Annals of Mathematics studies | volume=5 | date=1941 }} See p.105 for the theorem, pp.53, 59, 69, 70, 131 for a definition of the classes A<sub>1</sub>, L<sub>1</sub>, C<sub>2</sub>, C<sub>3</sub>, D<sub>3</sub>, and pp.35, 43 for the definition of [A:a] condition and α, β, γ function.</ref>

== Minimal functionally complete operator sets ==
When a single logical connective or Boolean operator is functionally complete by itself, it is called a ''Sheffer function''<ref name=Martin1989>The term was originally restricted to ''binary'' operations, but since the end of the 20th century it is used more generally.
{{citation
 | title =  Systems of logic
 | year = 1989
 | author = Martin, N.M.
 | publisher = Cambridge University Press
 | isbn = 978-0-521-36770-7
 | page = 54
}}.</ref> or sometimes a '''sole sufficient operator'''. There are no [[unary operation|unary]] operators with this property. [[Logical NAND|NAND]] and [[Logical NOR|NOR]], which are [[Boolean algebra#Duality principle|dual to each other]], are the only two binary Sheffer functions. These were discovered, but not published, by [[Charles Sanders Peirce]] around 1880, and rediscovered independently and published by [[Henry M. Sheffer]] in 1913.<ref name=Scharle1965>
{{citation
 | title = Axiomatization of propositional calculus with Sheffer functors
 | url = http://projecteuclid.org/euclid.ndjfl/1093958259
 | year = 1965
 | author = Scharle, T.W.
 | journal = Notre Dame J. Formal Logic
 | pages = 209–217
 | volume = 6
 | doi = 10.1305/ndjfl/1093958259
 | issue = 3
 | doi-access = free
}}.</ref>
In digital electronics terminology, the binary [[NAND gate]] (↑) and the binary [[NOR gate]] (↓) are the only binary [[universal logic gate]]s.

The following are the minimal functionally complete sets of logical connectives with [[arity]] ≤&nbsp;2:<ref name="Wernick">Wernick, William (1942) "Complete Sets of Logical Functions," ''Transactions of the American Mathematical Society 51'': 117&ndash;32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between <math>\nleftarrow</math> and <math>\nrightarrow</math>.</ref>

;One element: {↑}, {↓}.
;Two elements: <math>\{\vee, \neg\}</math>, <math>\{\wedge, \neg\}</math>, <math>\{\to, \neg\}</math>, <math>\{\gets, \neg\}</math>, <math>\{\to, \bot\}</math>, <math>\{\gets, \bot\}</math>, <math>\{\to, \nleftrightarrow\}</math>, <math>\{\gets, \nleftrightarrow\}</math>, <math>\{\to, \nrightarrow\}</math>, <math>\{\to, \nleftarrow\}</math>, <math>\{\gets, \nrightarrow\}</math>, <math>\{\gets, \nleftarrow\}</math>, <math>\{\nrightarrow, \neg\}</math>, <math>\{\nleftarrow, \neg\}</math>, <math>\{\nrightarrow, \top\}</math>, <math>\{\nleftarrow, \top\}</math>, <math>\{\nrightarrow, \leftrightarrow\}</math>, <math>\{\nleftarrow, \leftrightarrow\}.</math>
;Three elements: <math>\{\lor, \leftrightarrow, \bot\}</math>, <math>\{\lor, \leftrightarrow, \nleftrightarrow\}</math>, <math>\{\lor, \nleftrightarrow, \top\}</math>, <math>\{\land, \leftrightarrow, \bot\}</math>, <math>\{\land, \leftrightarrow, \nleftrightarrow\}</math>, <math>\{\land, \nleftrightarrow, \top\}.</math>

There are no minimal functionally complete sets of more than three at most binary logical connectives.<ref name="Wernick" /> In order to keep the lists above readable, operators that ignore one or more inputs have been omitted.  For example, an operator that ignores the first input and outputs the negation of the second can be replaced by a unary negation.

== Examples ==

* Examples of using the <code>NAND</code> (↑) completeness. As illustrated by,<ref>"NAND Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html</ref>
** ¬''A'' ≡ ''A'' ↑ ''A''
** ''A'' &and; ''B'' ≡ ¬(''A'' ↑ ''B'') ≡ (''A'' ↑ ''B'') ↑ (''A'' ↑ ''B'')
** ''A'' &or; ''B'' ≡ (¬''A'') ↑ (¬''B'') ≡ (''A'' ↑ ''A'') ↑ (''B'' ↑ ''B'')
* Examples of using the <code>NOR</code> (↓) completeness. As illustrated by,<ref>"NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html</ref>
** ¬''A'' ≡ ''A'' ↓ ''A''
** ''A'' &or; ''B'' ≡ ¬(''A'' ↓ ''B'') ≡ (''A'' ↓ ''B'') ↓ (''A'' ↓ ''B'')
** ''A'' &and; ''B'' ≡ (¬''A'') ↓ (¬''B'') ≡ (''A'' ↓ ''A'') ↓ (''B'' ↓ ''B'')

Note that an electronic circuit or a software function can be optimized by reuse, to reduce the number of gates.  For instance, the "{{nowrap|''A'' &and; ''B''}}" operation, when expressed by ↑ gates, is implemented with the reuse of "{{nowrap|A ↑ B}}",
: ''X'' ≡ (''A'' ↑ ''B'');  ''A'' &and; ''B'' ≡ ''X'' ↑ ''X''

== In other domains ==
Apart from logical connectives (Boolean operators), functional completeness can be introduced in other domains. For example, a set of [[reversible computation|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&nbsp;– a sole sufficient operator. There are many other three-input universal logic gates, such as the [[Toffoli gate]].

In [[quantum computing]], the [[Hadamard gate]] and the [[quantum logic gate#Phase shift gates|T gate]] are universal, albeit with a [[quantum logic gate#Universal quantum gates|slightly more restrictive definition]] than that of functional completeness.

== Set theory ==
There is an [[isomorphism]] between the [[algebra of sets]] and the [[Boolean algebra]], that is, they have the same [[Boolean algebra (structure)|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 generate any other set relations. The more popular "Minimal complete operator sets" are {{nowrap|{{mset|¬, &cap;}}}} and {{nowrap|{{mset|¬, &cup;}}}}. If the [[universal set]] [[Russell's Paradox|is forbidden]], set operators are restricted to being falsity (Ø) preserving, and cannot be equivalent to functionally complete Boolean algebra.

== See also ==
* {{annotated link|Algebra of sets}}
* {{annotated link|Boolean algebra}}
* {{annotated link|Completeness (logic)}}
* {{annotated link|Conjunction/disjunction duality}}
* {{annotated link|List of Boolean algebra topics}}
* {{annotated link|NAND logic}}
* {{annotated link|NOR logic}}
* {{annotated link|One-instruction set computer}}

== References ==
{{reflist|30em}}

{{Mathematical logic}}

[[Category:Boolean algebra]]
[[Category:Logic in computer science]]
[[Category:Propositional calculus]]
[[Category:Charles Sanders Peirce]]