Functional completeness
Encyclopedia
In logic
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 domain
Boolean 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 ƒiBni → 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(xyz) = z if x = y and S(xyz) = 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: 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....

 (), or Kpq; 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...

 (), or Apq; negation
Negation
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 conditional
Material 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 biconditional
Logical 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 subset
Subset
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 Post
Emil 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 affine
    Affine transformation
    In 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. , MAJ
    Majority function
    In 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 unary
Unary 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...

.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK