In
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premise ...
, a functionally complete set of
logical connective
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...
s or
Boolean operators is one which can be used to express all possible
truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional argumen ...
s by combining members of the
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
into a
Boolean expression
In computer science, a Boolean expression is an expression used in programming languages that produces a Boolean value when evaluated. A Boolean value is either true or false. A Boolean expression may be composed of a combination of the Boolean c ...
.
[. ("Complete set of logical connectives").][. (" nctional completeness of set of logical operators").] A well-known complete set of connectives is . Each of the
singleton
Singleton may refer to:
Sciences, technology Mathematics
* Singleton (mathematics), a set with exactly one element
* Singleton field, used in conformal field theory Computing
* Singleton pattern, a design pattern that allows only one instance ...
sets and is functionally complete.
A gate or set of gates which is functionally complete can also be called a universal gate / gates.
A functionally complete set of gates may utilise or generate 'garbage bits' as part of its computation which are either not part of the input or not part of the output to the system.
In a context of
propositional logic
Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...
, functionally complete sets of connectives are also called (expressively) adequate.
[. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)]
From the point of view of
digital electronics
Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics and analog signals.
Digital electronic circuits are usual ...
, 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
In digital electronics, a NAND gate (NOT-AND) is a logic gate which produces an output which is false only if all its inputs are true; thus its output is complement to that of an AND gate. A LOW (0) output results only if all the inputs to the ...
s, or only binary
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 (1) results if both the inputs to the gate are LOW (0); if one or both input is HIGH (1), a LOW output (0 ...
s.
Introduction
Modern texts on logic typically take as primitive some subset of the connectives:
conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...
(
);
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
(
);
negation (
);
material conditional
The material conditional (also known as material implication) is an operation commonly used in logic. When the conditional symbol \rightarrow is interpreted as material implication, a formula P \rightarrow Q is true unless P is true and Q i ...
(
); and possibly the
biconditional
In logic and mathematics, the logical biconditional, sometimes known as the material biconditional, is the logical connective (\leftrightarrow) used to conjoin two statements and to form the statement " if and only if ", where is known as t ...
(
). Further connectives can be defined, if so desired, by defining them in terms of these primitives. For example, NOR (sometimes denoted
, the negation of the disjunction) 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. It turns out that every binary connective can be defined in terms of
, so this set is functionally complete.
However, it still contains some 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. But this is still not minimal, as
can be defined as
:
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
In mathematics and abstract algebra, a Boolean domain is a set consisting of exactly two elements whose interpretations include ''false'' and ''true''. In logic, mathematics and theoretical computer science, a Boolean domain is usually written as ...
B = , a set ''F'' of Boolean functions ''ƒ''
i: B
''ni'' → B is functionally complete if the
clone on B generated by the basic functions ''ƒ''
i contains all functions ''ƒ'': B
''n'' → 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 ''ƒ'': B
''n'' → 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 () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. ...
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.
Characterization of functional completeness
Emil Post
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Gove ...
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
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of ord ...
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.
.
* The
affine
Affine may describe any of various topics concerned with connections or affinities.
It may refer to:
* Affine, a relative by marriage in law and anthropology
* Affine cipher, a special case of the more general substitution cipher
* Affine comb ...
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
In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathem ...
; 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
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values ('' true'' or '' false'').
Computing
In some pro ...
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 may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
of all
clones (sets of operations closed under composition and containing all projections) on the two-element set , 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
[The term was originally restricted to ''binary'' operations, but since the end of the 20th century it is used more generally. .] or sometimes a sole sufficient operator. There are no
unary operators with this property.
NAND and
NOR , which are
dual to each other, are the only two binary Sheffer functions. These were discovered, but not published, by
Charles Sanders Peirce
Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American philosopher, logician, mathematician and scientist who is sometimes known as "the father of pragmatism".
Educated as a chemist and employed as a scientist for t ...
around 1880, and rediscovered independently and published by
Henry M. Sheffer in 1913.
[.]
In digital electronics terminology, the binary
NAND gate
In digital electronics, a NAND gate (NOT-AND) is a logic gate which produces an output which is false only if all its inputs are true; thus its output is complement to that of an AND gate. A LOW (0) output results only if all the inputs to the ...
(↑) and the binary
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 (1) results if both the inputs to the gate are LOW (0); if one or both input is HIGH (1), a LOW output (0 ...
(↓) are the only binary
universal logic gates.
The following are the minimal functionally complete sets of logical connectives with
arity ≤ 2:
[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 .]
;One element: , .
;Two elements:
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
;Three elements:
,
,
,
,
,
There are no minimal functionally complete sets of more than three at most binary logical connectives.
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,
** ¬A ≡ A ↑ A
** A ∧ B ≡ ¬(A ↑ B) ≡ (A ↑ B) ↑ (A ↑ B)
** A ∨ B ≡ (A ↑ A) ↑ (B ↑ B)
* Examples of using the
NOR
(↓) completeness. As illustrated by,
["NOR Gate Operations" at http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html]
** ¬A ≡ A ↓ A
** 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
reversible gates is called functionally complete, if it can express every reversible operator.
The 3-input
Fredkin gate
The Fredkin gate (also CSWAP gate and conservative logic gate) is a computational circuit suitable for reversible computing, invented by Edward Fredkin. It is ''universal'', which means that any logical or arithmetic operation can be constructed e ...
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 logic circuits, the Toffoli gate (also CCNOT gate), invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any classical reversible circuit can be constructed from Toffoli gates. It is also known as the "control ...
.
In
quantum computing, the
Hadamard gate
The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogon ...
and the
T gate are universal, albeit with a
slightly more restrictive definition than that of functional completeness.
Set theory
There is an
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
between the
algebra of sets and the
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
, that is, they have the same
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 and . If the
universal set
In set theory, a universal set is a set which contains all objects, including itself. In set theory as usually formulated, it can be proven in multiple ways that a universal set does not exist. However, some non-standard variants of set theory inc ...
is forbidden, set operators are restricted to being falsity- (Ø) preserving, and cannot be equivalent to functionally complete Boolean algebra.
See also
*
*
*
*
*
*
*
References
{{Mathematical logic
Boolean algebra
Logic in computer science
Propositional calculus