login or register
u
p
 remember me!
functional completeness
prints friendly
functional completeness


please note:
- the text and code below is from The Pseudopedia
- it has been imported raw for GetWiki
In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.(1)(2) A well known complete set of connectives is { AND, OR, NOT }, consisting of binary conjunction, binary disjunction and negation. The set consisting only of the binary operator NAND is also functionally complete.In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate.(3)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 binary NAND gates.

Formal definition

Given the Boolean domain B = {0,1}, a set F of Boolean functions ƒi: Bni → B is functionally complete if the clone on B generated by the basic functions ƒi contains all functions ƒ: Bn → 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 ƒi. 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 ƒ: Bn → 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 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 S(x, y, z) = z if x = y and S(x, y, z) = x otherwise shows that this condition is strictly weaker than functional completeness.{{citation
| title = A sole sufficient operator
| url =weblink
| year = 1975
| author = Wesselkamper, T.C.
| journal = Notre Dame Journal of Formal Logic
| volume = 16
| pages = 86–88
}}{{citation
| title = Concerning an alleged Sheffer function
| url =weblink
| year = 1975
| author = Massey, G.J.
| journal = Notre Dame Journal of Formal Logic
| volume = 16
| pages = 549–550
}}{{citation
| title = A Correction To My Paper" A. Sole Sufficient Operator
| url =weblink
| year = 1975
| author = Wesselkamper, T.C.
| journal = Notre Dame Journal of Formal Logic
| volume = 16
| pages = 551
}}

Informal

Modern texts on logic typically take as primitive some subset of the connectives conjunction (
∧
), disjunction (
∨
), negation (
≠g
), material conditional (
→
) and possibly the biconditional (
↔
). These connectives are functionally complete. However, they do not form a minimal functionally complete set, as the conditional and biconditional may be defined as:
begin{align}
A to B &:= neg A lor B
A leftrightarrow B &:= (A to B) land (B to A).
end{align}So
≠g ∧ ∨
is also functionally complete. But then,
∨
can be defined as
A ∨ B := ≠g(≠g A ∧ ≠g B).
∧
can also be defined in terms of
∨
in a similar manner.It is also the case that
∨
can be defined in terms of
→
as follows:
A ∨ B := (A → B) → B.
No further simplifications are possible. Hence
≠g
and one of
∧ ∨ →
are each minimal functionally complete subsets of
≠g ∧ ∨ → ↔
.

Characterization of functional completeness

{{further|Post's lattice}}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, e.g.
    ∨
    ,
    ∧
    ,
    →(
    ,
    bot
    .
  • The affine connectives, such that each connected variable either always or never affects the truth value these connectives return, e.g.
    ≠g
    ,
    →(
    ,
    bot
    ,
    ↔
    ,
    not↔
    .
  • The self-dual connectives, which are equal to their own de Morgan dual, e.g.
    ≠g
    , MAJ(p,q,r).
  • The truth-preserving connectives; they return the truth value T under any interpretation which assigns T to all variables, e.g.
    ∨
    ,
    ∧
    ,
    →(
    ,
    →
    ,
    ↔
    .
  • The falsity-preserving connectives; they return the truth value F under any interpretation which assigns F to all variables, e.g.
    ∨
    ,
    ∧
    ,
    bot
    ,
    not→
    ,
    not↔
    .
In fact, Post gave a complete description of the lattice of all clones (sets of operations closed under composition and containing all projections) on the two-element set {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 clones.

Minimal functionally complete operator sets

When a single logical connective or Boolean operator is functionally complete by itself, it is called a Sheffer functionThe 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 = 9780521367707
| page = 54
}}. 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 de Morgan dual. These were discovered but not published by Charles Sanders Peirce around 1880, and rediscovered independently and published by Henry M. Sheffer in 1913.{{Citation
| title = Axiomatization of propositional calculus with Sheffer functors
| url =weblink
| year = 1965
| author = Scharle, T.W.
| journal = Notre Dame J. Formal Logic
| pages = 209–217
| volume = 6
}}.In digital electronics terminology, the binary NAND gate and the binary NOR gate are the only binary universal gates.The following are the minimal functionally complete sets of logical connectives with arity ≤ 2:(4)
One element: {NAND}, {NOR}.
Two elements: {
∨
, ¬}, {
∧
, ¬}, {→, ¬}, {←, ¬}, {→, 
bot
}, {←, 
bot
}, {→, 
not↔
}, {←, 
not↔
}, {→, 
not→
}, {→, 
not←
}, {←, 
not→
}, {←, 
not←
}, {
not→
, ¬}, {
not←
, ¬}, {
not→
, 
→(
}, {
not←
, 
→(
}, {
not→
, 
↔
}, {
not←
, 
↔
}.
Three elements: {
∨
,
↔
,
bot
}, {
∨
,
↔
,
not↔
}, {
∨
,
not↔
,
→(
}, {
∧
,
↔
,
bot
}, {
∧
,
↔
,
not↔
}, {
∧
,
not↔
,
→(
}.
There are no minimal functionally complete sets of more than three at most binary logical connectives. 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
∨
and the binary connective given by negation of the first argument (ignoring the second) is another minimal functionally complete set.

Other meanings

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 Reversible Computing/3 input universal logic gates, such as the Toffoli gate.

References





  1. {{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").


  2. {{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").


  3. {{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.)


  4. 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←
    and
    not→
    .




  • Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32.
Junktor#Reduzierbarkeit der Junktorenmenge, funktionale Vollständigkeit und Sheffer-OperatorenCompletude funcionalКритерий Поста

- content above as imported from The Pseudopedia
- "functional completeness" does not exist on GetWiki
- time: 10:31pm EDT - Thu, Mar 18 2010