Logical connectives
NOT ${\displaystyle \mathrm{\neg }A,-A,\overline{A},\sim A}$ AND NAND ${\displaystyle A\overline{\wedge }B,A\uparrow B,A\mid B,\overline{A\cdot B}}$ OR ${\displaystyle A\vee B,A+B,A\mid B,A\parallel B}$ NOR ${\displaystyle A\overline{\vee }B,A\downarrow B,\overline{A+B}}$ XNOR ${\displaystyle A\odot B,\overline{A\overline{\vee }B}}$ └equivalent ${\displaystyle A\equiv B,A\iff B,A\leftrightharpoons B}$ XOR ${\displaystyle A\underset{\_}{\vee }B,A\oplus B}$ └nonequivalent ${\displaystyle A\not\equiv B,A\nLeftrightarrow B,A\nleftrightarrow B}$ implies ${\displaystyle A\Rightarrow B,A\supset B,A\to B}$ nonimplication (NIMPLY) ${\displaystyle A\nRightarrow B,A\not\supset B,A\nrightarrow B}$ converse ${\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}$ converse nonimplication ${\displaystyle A\nLeftarrow B,A\not\subset B,A\nleftarrow B}$
Related concepts
Propositional calculus Predicate logic Boolean algebra Truth table Truth function Boolean function Functional completeness Scope (logic)
Applications
Digital logic Programming languages Mathematical logic Philosophy of logic
Category
v t e

Inlogic, afunctionally complete set oflogical connectives orBoolean operators is one that can be used to express all possibletruth tables by combining members of theset into aBoolean expression.^[1][2] A well-known complete set of connectives is{AND,NOT }. Each of thesingleton 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 ofpropositional logic, functionally complete sets of connectives are also called (expressively)adequate.^[3]

From the point of view ofdigital electronics, functional completeness means that every possiblelogic 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 binaryNAND gates, or only binaryNOR gates.

Modern texts on logic typically take as primitive some subset of the connectives:conjunction (${\displaystyle \wedge }$);disjunction (${\displaystyle \vee }$);negation (${\displaystyle \mathrm{\neg }}$);material conditional (${\displaystyle \to }$); and possibly thebiconditional (${\displaystyle \leftrightarrow }$). 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${\displaystyle \downarrow }$) can be expressed as conjunction of two negations:

${\displaystyle A\downarrow B:=\mathrm{\neg }A\wedge \mathrm{\neg }B}$

Similarly, the negation of the conjunction, NAND (sometimes denoted as${\displaystyle \uparrow }$), can be defined in terms of disjunction and negation. Every binary connective can be defined in terms of${\displaystyle \{\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow \}}$, which means that set is functionally complete. However, it contains redundancy: this set is not aminimal functionally complete set, because the conditional and biconditional can be defined in terms of the other connectives as

It follows that the smaller set${\displaystyle \{\mathrm{\neg },\wedge ,\vee \}}$ is also functionally complete. (Its functional completeness is also proved by theDisjunctive Normal Form Theorem.)^[4] But this is still not minimal, as${\displaystyle \vee }$ can be defined as

${\displaystyle A\vee B:=\mathrm{\neg }(\mathrm{\neg }A\wedge \mathrm{\neg }B).}$

Alternatively,${\displaystyle \wedge }$ may be defined in terms of${\displaystyle \vee }$ in a similar manner, or${\displaystyle \vee }$ may be defined in terms of${\displaystyle \to }$:

${\displaystyle A\vee B:=\mathrm{\neg }A\to B.}$

No further simplifications are possible. Hence, every two-element set of connectives containing${\displaystyle \mathrm{\neg }}$ and one of${\displaystyle \{\wedge ,\vee ,\to \}}$ is a minimal functionally completesubset of${\displaystyle \{\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow \}}$.

Given theBoolean domainB = {0, 1}, a setF of Boolean functionsf_i :B^n_i →B isfunctionally complete if theclone onB generated by the basic functionsf_i contains all functionsf :Bⁿ →B, for allstrictly positive integersn ≥ 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 functionsf_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 inF.

A more natural condition would be that the clone generated byF consist of all functionsf :Bⁿ →B, for all integersn ≥ 0. However, the examples given above are not functionally complete in this stronger sense because it is not possible to write anullary function, i.e. a constant expression, in terms ofF ifF 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 byF 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 byS(x,y,z) =z ifx =y andS(x,y,z) =x otherwise shows that this condition is strictly weaker than functional completeness.^[5][6][7]

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:

• Themonotonic connectives; changing the truth value of any connected variables fromF toT without changing any fromT toF never makes these connectives change their return value fromT toF, e.g.${\displaystyle \vee ,\wedge ,\mathrm{\top },\mathrm{\perp }}$.
• Theaffine connectives, such that each connected variable either always or never affects the truth value these connectives return, e.g.${\displaystyle \mathrm{\neg },\mathrm{\top },\mathrm{\perp },\leftrightarrow ,\nleftrightarrow }$.
• Theself-dual connectives, which are equal to their ownde Morgan dual; if the truth values of all variables are reversed, so is the truth value these connectives return, e.g.${\displaystyle \mathrm{\neg }}$,maj(p,q,r).
• Thetruth-preserving connectives; they return thetruth valueT under any interpretation that assignsT to all variables, e.g.${\displaystyle \vee ,\wedge ,\mathrm{\top },\to ,\leftrightarrow }$.
• Thefalsity-preserving connectives; they return the truth valueF under any interpretation that assignsF to all variables, e.g.${\displaystyle \vee ,\wedge ,\mathrm{\perp },\nrightarrow ,\nleftrightarrow }$.

Post gave a complete description of thelattice of allclones (sets of operations closed under composition and containing all projections) on the two-element set{T,F}, nowadays calledPost's lattice, which implies the above result as a simple corollary: the five mentioned sets of connectives are exactly the maximal nontrivial clones.^[8]

When a single logical connective or Boolean operator is functionally complete by itself, it is called aSheffer function^[9] or sometimes asole sufficient operator. There are nounary operators with this property.NAND andNOR, which aredual to each other, are the only two binary Sheffer functions. These were discovered, but not published, byCharles Sanders Peirce around 1880, and rediscovered independently and published byHenry M. Sheffer in 1913.^[10]In digital electronics terminology, the binaryNAND gate (↑) and the binaryNOR gate (↓) are the only binaryuniversal logic gates.

The following are the minimal functionally complete sets of logical connectives witharity ≤ 2:^[11]

One element

{↑}, {↓}.

Two elements

${\displaystyle \{\vee ,\mathrm{\neg }\}}$,${\displaystyle \{\wedge ,\mathrm{\neg }\}}$,${\displaystyle \{\to ,\mathrm{\neg }\}}$,${\displaystyle \{\leftarrow ,\mathrm{\neg }\}}$,${\displaystyle \{\to ,\mathrm{\perp }\}}$,${\displaystyle \{\leftarrow ,\mathrm{\perp }\}}$,${\displaystyle \{\to ,\nleftrightarrow \}}$,${\displaystyle \{\leftarrow ,\nleftrightarrow \}}$,${\displaystyle \{\to ,\nrightarrow \}}$,${\displaystyle \{\to ,\nleftarrow \}}$,${\displaystyle \{\leftarrow ,\nrightarrow \}}$,${\displaystyle \{\leftarrow ,\nleftarrow \}}$,${\displaystyle \{\nrightarrow ,\mathrm{\neg }\}}$,${\displaystyle \{\nleftarrow ,\mathrm{\neg }\}}$,${\displaystyle \{\nrightarrow ,\mathrm{\top }\}}$,${\displaystyle \{\nleftarrow ,\mathrm{\top }\}}$,${\displaystyle \{\nrightarrow ,\leftrightarrow \}}$,${\displaystyle \{\nleftarrow ,\leftrightarrow \}.}$

Three elements

${\displaystyle \{\vee ,\leftrightarrow ,\mathrm{\perp }\}}$,${\displaystyle \{\vee ,\leftrightarrow ,\nleftrightarrow \}}$,${\displaystyle \{\vee ,\nleftrightarrow ,\mathrm{\top }\}}$,${\displaystyle \{\wedge ,\leftrightarrow ,\mathrm{\perp }\}}$,${\displaystyle \{\wedge ,\leftrightarrow ,\nleftrightarrow \}}$,${\displaystyle \{\wedge ,\nleftrightarrow ,\mathrm{\top }\}.}$

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 of using theNAND (↑) 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 theNOR (↓) 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

Apart from logical connectives (Boolean operators), functional completeness can be introduced in other domains. For example, a set ofreversible gates is called functionally complete, if it can express every reversible operator.

The 3-inputFredkin gate is functionally complete reversible gate by itself – a sole sufficient operator. There are many other three-input universal logic gates, such as theToffoli gate.

Inquantum computing, theHadamard gate and theT gate are universal, albeit with aslightly more restrictive definition than that of functional completeness.

There is anisomorphism between thealgebra of sets and theBoolean algebra, that is, they have the samestructure. 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 theuniversal setis forbidden, set operators are restricted to being falsity (Ø) preserving, and cannot be equivalent to functionally complete Boolean algebra.

• 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

• Boolean algebra
• Logic in computer science
• Propositional calculus
• Charles Sanders Peirce

• Articles with short description
• Short description is different from Wikidata