Functional completeness
Logical connectives | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||
Related concepts | ||||||||||||||||||||||
Applications | ||||||||||||||||||||||
Category | ||||||||||||||||||||||
In logic, a functionally complete set of logical connectives or Boolean operators is one that 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, NOT }. Each of the singleton sets { NAND } and { NOR } is functionally complete. However, the set { AND, 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
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 gates, or only binary NOR gates.
Introduction
Modern texts on logic typically take as primitive some subset of the connectives: conjunction (); disjunction (); negation (); material conditional (); and possibly the biconditional (). 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 ) can be expressed as conjunction of two negations:
Similarly, the negation of the conjunction, NAND (sometimes denoted as ), can be defined in terms of disjunction and negation. Every binary connective can be defined in terms of , 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
It follows that the smaller set is also functionally complete. (Its functional completeness is also proved by the
Alternatively, may be defined in terms of in a similar manner, or may be defined in terms of :
No further simplifications are possible. Hence, every two-element set of connectives containing and one of is a minimal functionally complete subset of .
Formal definition
Given the Boolean domain B = {0, 1}, a set F of Boolean functions fi : Bni → B is functionally complete if the clone on B generated by the basic functions fi contains all functions f : Bn → B, for all strictly positive integers 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 fi. 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 f : Bn → B, for all integers 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.[5][6][7]
Characterization of functional completeness
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 monotonicconnectives; 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. .
- The affine 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; if the truth values of all variables are reversed, so is the truth value these connectives return, e.g. , 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. .
- The falsity-preserving connectives; they return the truth value F under any interpretation that assigns F to all variables, e.g. .
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 nontrivial clones.[8]
Minimal functionally complete operator sets
When a single logical connective or Boolean operator is functionally complete by itself, it is called a Sheffer function
The following are the minimal functionally complete sets of logical connectives with arity ≤ 2:[11]
- One element
- {↑}, {↓}.
- Two elements
- , , , , , , , , , , , , , , , , ,
- Three elements
- , , , , ,
There are no minimal functionally complete sets of more than three at most binary logical connectives.[11] 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
NAND
(↑) completeness. As illustrated by,[12]- ¬A ≡ A ↑ A
- A ∧ B ≡ ¬(A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
- A ∨ B ≡ (¬A) ↑ (¬B) ≡ (A ↑ A) ↑ (B ↑ B)
- Examples of using the
NOR
(↓) completeness. As illustrated by,[13]- ¬A ≡ A ↓ A
- A ∨ B ≡ ¬(A ↓ B) ≡ (A ↓ B) ↓ (A ↓ B)
- A ∧ 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 "A ∧ B" operation, when expressed by ↑ gates, is implemented with the reuse of "A ↑ B",
- X ≡ (A ↑ B); A ∧ 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
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.
In
Set theory
There is an
See also
- Algebra of sets – Identities and relationships involving sets
- Boolean algebra – Algebraic manipulation of "true" and "false"
- Completeness (logic) – Characteristic of some logical systems
- Conjunction/disjunction duality – Properties linking logical conjunction and disjunction
- List of Boolean algebra topics
- NAND logic – Logic constructed only from NAND gates
- NOR logic – Making other gates using just NOR gates
- One-instruction set computer – Abstract machine that uses only one instruction
References
- ISBN 978-0-12-238452-3. ("Complete set of logical connectives").
- ISBN 978-0-07-046649-4. ("[F]unctional completeness of [a] set of logical operators").
- ISBN 978-0-521-00804-4. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)
- ISBN 978-0-415-13342-5.
- ^ Wesselkamper, T.C. (1975), "A sole sufficient operator", Notre Dame Journal of Formal Logic, 16: 86–88,
- ^ Massey, G.J. (1975), "Concerning an alleged Sheffer function", Notre Dame Journal of Formal Logic, 16 (4): 549–550,
- ^ Wesselkamper, T.C. (1975), "A Correction To My Paper" A. Sole Sufficient Operator", Notre Dame Journal of Formal Logic, 16 (4): 551,
- ISBN 9781400882366. See p.105 for the theorem, pp.53, 59, 69, 70, 131 for a definition of the classes A1, L1, C2, C3, D3, 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.
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, .
- ^ 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 and .
- ^ "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