Functional completeness
Encyclopedia
In logic
, a functionally complete set of logical connective
s or Boolean operators is one which can be used to express all possible truth table
s by combining members of the set into a Boolean expression
. A well known complete set of connectives is { AND, OR, NOT }, consisting of binary conjunction
, binary disjunction
and negation. The sets consisting only of the binary
operator NAND
or NOR
only are also functionally complete.
In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate.
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.
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 . 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 . 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.
(
), or Kpq; disjunction
(
), or Apq; negation
(
), Np, or Fpq; or material conditional
(
), or Cpq; and possibly the biconditional
(
), or Epq. These connectives are functionally complete. However, they do not form a minimal functionally complete set, as the conditional and biconditional may be defined as:
So
is also functionally complete. But then, 
can be defined as
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:
No further simplifications are possible. Hence
and one of 
are each minimal functionally complete subset
s of
.
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:
In fact, Post gave a complete description of the lattice
of all clone
s (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.
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.
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:
One element: {NAND}, {NOR}.
Two elements: {
, ¬}, {
, ¬}, {→, ¬}, {←, ¬}, {→, 
}, {←, 
}, {→, 
}, {←, 
}, {→, 
}, {→, 
}, {←, 
}, {←, 
}, {
, ¬}, {
, ¬}, {
, 
}, {
, 
}, {
, 
}, {
, 
}.
Three elements: {
, 
, 
}, {
, 
, 
}, {
, 
, 
}, {
, 
, 
}, {
, 
, 
}, {
, 
, 
}.
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.
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
.
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, a functionally complete set of logical connective
Logical connective
In logic, a logical connective is a symbol or word used to connect two or more sentences in a grammatically valid way, such that the compound sentence produced has a truth value dependent on the respective truth values of the original sentences.Each logical connective can be expressed as a...
s or Boolean operators is one which can be used to express all possible truth table
Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
s by combining members of the set into a Boolean expression
Boolean expression
In computer science, a Boolean expression is an expression in a programming language that produces a Boolean value when evaluated, i.e. one of true or false...
. A well known complete set of connectives is { AND, OR, NOT }, consisting of binary conjunction
Logical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
, binary disjunction
Logical disjunction
In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
and negation. The sets consisting only of the binary
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
operator NAND
Sheffer stroke
In Boolean functions and propositional calculus, the Sheffer stroke, named after Henry M. Sheffer, written "|" , "Dpq", or "↑", denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both"...
or NOR
Logical NOR
In boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form is true precisely when neither p nor q is true—i.e. when both of p and q are false...
only are also functionally complete.
In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate.
From the point of view of digital electronics, functional completeness means that every possible logic gate
Logic gate
A logic gate is an idealized or physical device implementing a Boolean function, that is, it performs a logical operation on one or more logic inputs and produces a single logic output. Depending on the context, the term may refer to an ideal logic gate, one that has for instance zero rise time and...
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
NAND gate
The Negated AND, NO AND or NAND gate is the opposite of the digital AND gate, and behaves in a manner that corresponds to the opposite of AND gate, as shown in the truth table on the right. A LOW output results only if both the inputs to the gate are HIGH...
s, or only binary NOR gate
NOR gate
The NOR gate is a digital logic gate that implements logical NOR - it behaves according to the truth table to the right. A HIGH output results if both the inputs to the gate are LOW . If one or both input is HIGH , a LOW output results. NOR is the result of the negation of the OR operator...
s.
Formal definition
Given the Boolean domainBoolean domain
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include false and true...
B = {0,1}, a set F of Boolean functions ƒi: Bni → B is functionally complete if the clone
Clone (algebra)
In universal algebra, a clone is a set C of operations on a set A such that*C contains all the projections , defined by ,*C is closed under composition : if f, g1, …, gm are members of C such that f is m-ary, and gj is n-ary for every j, then the n-ary operation is in C.Given an algebra...
on B generated by the basic functions ƒi contains all functions ƒ: Bn → B, for all strictly positive integers . 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 . However, the examples given above are not functionally complete in this stronger sense because it is not possible to write a nullary
Arity
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...
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.
Informal
Modern texts on logic typically take as primitive some subset of the connectives: conjunctionLogical conjunction
In logic and mathematics, a two-place logical operator and, also known as logical conjunction, results in true if both of its operands are true, otherwise the value of false....
(
), or Kpq; disjunctionLogical disjunction
In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
(
), or Apq; negationNegation
In logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...
(
), Np, or Fpq; or material conditionalMaterial conditional
The material conditional, also known as material implication, is a binary truth function, such that the compound sentence p→q is logically equivalent to the negative compound: not . A material conditional compound itself is often simply called a conditional...
(
), or Cpq; and possibly the biconditionalLogical biconditional
In logic and mathematics, the logical biconditional is the logical connective of two statements asserting "p if and only if q", where q is a hypothesis and p is a conclusion...
(
), or Epq. These connectives are functionally complete. However, they do not form a minimal functionally complete set, as the conditional and biconditional may be defined as:So
is also functionally complete. But then, can be defined as 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:No further simplifications are possible. Hence
and one of are each minimal functionally complete subsetSubset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
s of
.Characterization of functional completeness
Emil PostEmil Leon Post
Emil Leon Post was a mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.-Early work:...
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.
, 
, 
, 
.
- The affineAffine transformationIn geometry, an affine transformation or affine map or an affinity is a transformation which preserves straight lines. It is the most general class of transformations with this property...
connectives, such that each connected variable either always or never affects the truth value these connectives return, e.g.
, 
, 
, 
, 
.
- The self-dual connectives, which are equal to their own de Morgan dual, e.g.
, MAJMajority functionIn Boolean logic, the majority function is a function from n inputs to one output. The value of the operation is false when n/2 or more arguments are false, and true otherwise....
(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.
, 
, 
, 
, 
.
In fact, Post gave a complete description of the lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
of all clone
Clone (algebra)
In universal algebra, a clone is a set C of operations on a set A such that*C contains all the projections , defined by ,*C is closed under composition : if f, g1, …, gm are members of C such that f is m-ary, and gj is n-ary for every j, then the n-ary operation is in C.Given an algebra...
s (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 function or sometimes a sole sufficient operator. There are no unaryUnary operation
In mathematics, a unary operation is an operation with only one operand, i.e. a single input. Specifically, it is a functionf:\ A\to Awhere A is a set. In this case f is called a unary operation on A....
operators with this property, and the only binary Sheffer functions are NAND
Sheffer stroke
In Boolean functions and propositional calculus, the Sheffer stroke, named after Henry M. Sheffer, written "|" , "Dpq", or "↑", denotes a logical operation that is equivalent to the negation of the conjunction operation, expressed in ordinary language as "not both"...
and NOR
Logical NOR
In boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the negation of logical or. That is, a sentence of the form is true precisely when neither p nor q is true—i.e. when both of p and q are false...
, its dual. These were discovered but not published by Charles Sanders Peirce around 1880, and rediscovered independently and published by Henry M. Sheffer
Henry M. Sheffer
Henry Maurice Sheffer was an American logician.Sheffer was a Polish Jew born in the western Ukraine, who immigrated to the USA in 1892 with his parents and six siblings. He studied at the Boston Latin School before entering Harvard University, learning logic from Josiah Royce, and completing his...
in 1913.
In digital electronics terminology, the binary NAND gate
NAND gate
The Negated AND, NO AND or NAND gate is the opposite of the digital AND gate, and behaves in a manner that corresponds to the opposite of AND gate, as shown in the truth table on the right. A LOW output results only if both the inputs to the gate are HIGH...
and the binary NOR gate
NOR gate
The NOR gate is a digital logic gate that implements logical NOR - it behaves according to the truth table to the right. A HIGH output results if both the inputs to the gate are LOW . If one or both input is HIGH , a LOW output results. NOR is the result of the negation of the OR operator...
are the only binary universal logic gates.
The following are the minimal functionally complete sets of logical connectives with arity
Arity
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...
≤ 2:
One element: {NAND}, {NOR}.
Two elements: {
, ¬}, {, ¬}, {→, ¬}, {←, ¬}, {→, }, {←, }, {→, }, {←, }, {→, }, {→, }, {←, }, {←, }, {, ¬}, {, ¬}, {, }, {, }, {, }, {, }.Three elements: {
, , }, {, , }, {, , }, {, , }, {, , }, {, , }.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
Fredkin gate
The Fredkin gate is a computational circuit suitable for reversible computing, invented by Ed Fredkin. It is universal, which means that any logical or arithmetic operation can be constructed entirely of Fredkin gates...
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
Toffoli gate
In computer science, the Toffoli gate , invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any reversible circuit can be constructed from Toffoli gates...
.