# Functional completeness

**Functional completeness** is the property of a set of [logical connectives](https://www.edgepedia.org/logical-connective) (or Boolean functions, or logic gates) whereby every truth function, meaning every function from truth values to truth values, can be expressed by a formula built using only connectives from that set, together with propositional variables and brackets.<sup>[1](https://www.studocu.com/en-gb/document/university-of-leeds/mathematical-logic-1/logic-lecture-notes-chapter-3-truth-functions-and-equivalences/136604638?origin=related-document)</sup> A set with this property is called functionally complete, or adequate; a single connective that is complete on its own is called a Sheffer function, and the corresponding gate in electronics is called a universal gate.<sup>[2](https://iep.utm.edu/sheffers/)</sup>

| Key fact | Detail |
|---|---|
| Definition | A set X of connectives is functionally complete if every truth function can be expressed by a formula using only connectives from X, variables, and brackets<sup>[1](https://www.studocu.com/en-gb/document/university-of-leeds/mathematical-logic-1/logic-lecture-notes-chapter-3-truth-functions-and-equivalences/136604638?origin=related-document)</sup> |
| Counting truth functions | With one atom there are 4 unary truth functions; with two atoms each table has 4 lines, giving \( 2^{4} = 16 \) binary truth functions<sup>[3](https://users.cecs.anu.edu.au/~jks/LogicNotes/functional-completeness.html)</sup> |
| Standard complete sets | \(\{\neg, \wedge, \vee\}\) is complete, and so are the smaller pairs \(\{\neg, \wedge\}\) and \(\{\neg, \vee\}\)<sup>[4](https://plato.sydney.edu.au/entries//////logic-propositional/)</sup> |
| Single-connective sets | NAND (the Sheffer stroke, \(\mid\)) and NOR (the Peirce arrow, \(\downarrow\)) are each functionally complete alone<sup>[2](https://iep.utm.edu/sheffers/)</sup> |
| Post's criterion | A set of two-valued operations is complete if and only if it is contained in none of the five maximal clones: 0-preserving, 1-preserving, monotone, self-dual, and linear functions<sup>[5](https://api.pageplace.de/preview/DT0400.9781107266636_A24418083/preview-9781107266636_A24418083.pdf)</sup><sup> • </sup><sup>[6](https://plato.stanford.edu/entries/logic-manyvalued/index.html)</sup> |
| Engineering use | NAND and NOR are the only single gate types able to mimic any other gate; the Apollo Guidance Computer was built from about 5600 packages containing two three-input NOR gates each<sup>[7](https://www.allaboutcircuits.com/textbook/digital/chpt-3/gate-universality/)</sup><sup> • </sup><sup>[8](https://www.engineeringdevotion.com/digital-electronics/lecture/nand-nor-universal-logic.html)</sup> |

## Truth functions and the definition

Any formula of propositional logic has a truth table: for each assignment of truth values to its atoms, the formula itself receives a truth value. Semantically it therefore expresses a function from truth values to truth values, with as many arguments as there are atoms in the formula; such an operation is called a truth function.<sup>[3](https://users.cecs.anu.edu.au/~jks/LogicNotes/functional-completeness.html)</sup> Formally, with \( T = \{T, F\} \), a truth function is a map \( f : T^{n} \to T \), and each such function determines a truth table of \( 2^{n} \) rows.<sup>[9](https://www.macs.hw.ac.uk/~markl/teaching/LOGIC/LOGIC-NOTES.pdf)</sup>

The numbers grow quickly. With a single atom there are just four unary truth functions: the constant 0, the identity \( p \), negation \( \neg p \), and the constant 1 (expressed by a tautology such as \( p \to p \), while the contradiction \( p \wedge \neg p \) expresses the constant 0).<sup>[3](https://users.cecs.anu.edu.au/~jks/LogicNotes/functional-completeness.html)</sup> With two atoms, each of the four table lines may independently be 0 or 1, giving \( 2^{4} = 16 \) binary truth functions; for three arguments there are \( 2^{2^{3}} = 256 \) such tables.<sup>[3](https://users.cecs.anu.edu.au/~jks/LogicNotes/functional-completeness.html)</sup><sup> • </sup><sup>[10](https://people.maths.bris.ac.uk/~mapdw/pdw-logic-revised.pdf)</sup>

A set of connectives is functionally complete when no truth function escapes it: every one of these tables can be matched by some formula using only the given connectives.<sup>[1](https://www.studocu.com/en-gb/document/university-of-leeds/mathematical-logic-1/logic-lecture-notes-chapter-3-truth-functions-and-equivalences/136604638?origin=related-document)</sup> In universal algebra the corresponding algebra is termed primal, and in some older and East European literature a complete set is called functionally complete.<sup>[5](https://api.pageplace.de/preview/DT0400.9781107266636_A24418083/preview-9781107266636_A24418083.pdf)</sup>

## The standard complete sets

The disjunctive normal form theorem shows that \(\{\neg, \wedge, \vee\}\) is complete: every formula is equivalent to a disjunction of conjunctions of variables and negated variables, read off from the rows of its truth table where the formula is true.<sup>[10](https://people.maths.bris.ac.uk/~mapdw/pdw-logic-revised.pdf)</sup> For example, the exclusive-or table with 1s on the rows 01 and 10 yields \( (\neg p \wedge q) \vee (p \wedge \neg q) \).<sup>[11](https://homeweb.unifr.ch/liechtli/pub/mmcs/MMI2021.pdf)</sup> A function that is 0 everywhere is represented by \( p_{1} \wedge \neg p_{1} \).<sup>[11](https://homeweb.unifr.ch/liechtli/pub/mmcs/MMI2021.pdf)</sup>

The set can be shrunk. Since \( A \vee B \) is equivalent to \( \neg(\neg A \wedge \neg B) \), the pair \(\{\neg, \wedge\}\) is complete; symmetrically, \(\{\neg, \vee\}\) is complete.<sup>[4](https://plato.sydney.edu.au/entries//////logic-propositional/)</sup><sup> • </sup><sup>[11](https://homeweb.unifr.ch/liechtli/pub/mmcs/MMI2021.pdf)</sup> Going further, the single connective \( \uparrow \), NAND, whose table outputs 1 except when both inputs are 1, is functionally complete on its own.<sup>[11](https://homeweb.unifr.ch/liechtli/pub/mmcs/MMI2021.pdf)</sup>

## NAND, NOR, and the Sheffer stroke

The connective written \( \mid \), called the [Sheffer stroke](https://www.edgepedia.org/sheffer-stroke), NAND, Alternate Denial, or Negated Conjunction, captures the phrase "not both ___ and —". Its dual \( \downarrow \), the Peirce arrow, NOR, Joint Denial, or Negated Disjunction, captures "neither-nor".<sup>[2](https://iep.utm.edu/sheffers/)</sup> Each is complete as a one-member set, so the connectives themselves are said to have the property of functional completeness.<sup>[2](https://iep.utm.edu/sheffers/)</sup> Concretely, NOT is made by tying both inputs of a NAND together, and AND and OR then follow by combining NOT with NAND; since \(\{\text{AND}, \text{OR}, \text{NOT}\}\) is already complete, NAND alone is complete too.<sup>[12](https://mindspaneducation.com/learn/digital-logic/universal-gates/)</sup>

The discovery has a layered history. Charles Sanders Peirce had already realized the point in a fragment of 1880, and again in 1902, describing the operation by which "two propositions written in a pair are considered to be both denied"; in the same manuscript he also discovered the expressive completeness of NOR.<sup>[2](https://iep.utm.edu/sheffers/)</sup><sup> • </sup><sup>[13](https://iep.utm.edu/peir-log/)</sup> [Henry M. Sheffer](https://www.edgepedia.org/henry-m-sheffer) rediscovered the result independently in 1913, and the discovery was hailed by [Ludwig Wittgenstein](https://www.edgepedia.org/ludwig-wittgenstein) and [Bertrand Russell](https://www.edgepedia.org/bertrand-russell); Wittgenstein took the availability of a Sheffer function, in the *Tractatus Logico-Philosophicus* (1922), to illustrate deeper features of formal logic.<sup>[2](https://iep.utm.edu/sheffers/)</sup><sup> • </sup><sup>[4](https://plato.sydney.edu.au/entries//////logic-propositional/)</sup> Arthur Prior (1958, 1964) showed that Peirce's 1880 paper provides a complete basis for propositional logic.<sup>[13](https://iep.utm.edu/peir-log/)</sup>

## Post's criterion and incomplete sets

Not every set is complete, and Emil Post gave the exact boundary. In 1921 Post found a completeness criterion, a necessary and sufficient condition for a set of Boolean functions to be complete, and twenty years later, in 1941, he gave a full description of the lattice of Boolean clones, the composition-closed collections of finitary operations containing all projections.<sup>[5](https://api.pageplace.de/preview/DT0400.9781107266636_A24418083/preview-9781107266636_A24418083.pdf)</sup><sup> • </sup><sup>[6](https://plato.stanford.edu/entries/logic-manyvalued/index.html)</sup> There are exactly five maximal clones immediately below the complete system, namely the 0-preserving, 1-preserving, monotone, self-dual, and linear functions, and every closed system other than the complete one is included in at least one of them.<sup>[14](https://www.jstor.org/stable/j.ctt1bgzb1r)</sup> A set is complete if and only if for each of the five it contains some function outside it.<sup>[5](https://api.pageplace.de/preview/DT0400.9781107266636_A24418083/preview-9781107266636_A24418083.pdf)</sup>

The criterion explains familiar failures. The set \(\{\text{AND}, \text{OR}, \text{XOR}\}\) is not complete because the value 0 is a fixed point for all three connectives; \(\{\text{IFF}, \text{NOT}\}\) fails because every definable truth function has an even number of 1 values in its table; and \(\{\wedge\}\) alone fails because every member outputs 1 when all inputs are 1.<sup>[3](https://users.cecs.anu.edu.au/~jks/LogicNotes/functional-completeness.html)</sup><sup> • </sup><sup>[15](https://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture34.pdf)</sup> NAND escapes all five classes at once: it is not truth-preserving, not falsity-preserving, not monotone, not self-dual, and not affine.

Beyond two values, Jerzy Słupecki (1939) proposed general criteria for the functional completeness of arbitrary collections of \( \kappa \)-valued operations, for any fixed \( \kappa \), together with axiomatization procedures for the associated logics. For \( \kappa > 2 \) the lattices of clones are not countable, so the two-valued picture does not generalize simply.<sup>[6](https://plato.stanford.edu/entries/logic-manyvalued/index.html)</sup>

## Universal gates in digital electronics

In circuit theory the Boolean functions are implemented by logic gates, and the gate implementing the Sheffer stroke is called NAND and is known as a universal gate.<sup>[2](https://iep.utm.edu/sheffers/)</sup> Given enough gates, either NAND or NOR can mimic the operation of any other gate type, a property enjoyed only by these two; digital control systems have been designed around nothing but one of them.<sup>[7](https://www.allaboutcircuits.com/textbook/digital/chpt-3/gate-universality/)</sup> Standardizing on one gate type means one part number, one cell in a standard-cell library, and one repeated layout, with spare gates usable for anything and uniform delay on every path.<sup>[8](https://www.engineeringdevotion.com/digital-electronics/lecture/nand-nor-universal-logic.html)</sup>

The property has been acted on at scale. In the 1960s, the entire [Apollo Guidance Computer](https://www.edgepedia.org/apollo-guidance-computer)—arithmetic, memory control, and everything else—was assembled from roughly 5600 units of a single kind of circuit: a resistor-transistor logic package holding two three-input NOR gates.<sup>[8](https://www.engineeringdevotion.com/digital-electronics/lecture/nand-nor-universal-logic.html)</sup> In CMOS technology, transistors naturally produce an inverting gate—either a NAND or a NOR—while the non-inverting AND is that gate with an inverter appended, making it larger and slower than the gate from which it is built.<sup>[8](https://www.engineeringdevotion.com/digital-electronics/lecture/nand-nor-universal-logic.html)</sup> Completeness does not make every construction cheap: building XOR from NAND alone takes 4 NAND gates in the standard minimal circuit, which is why parity and error-checking designs often add XOR cells explicitly.<sup>[16](https://university.kurz.fyi/computer-science/computer/digital-logic-computer-organization/nand-as-a-universal-gate)</sup>

## References

1. [Definition 3.3, Truth Functions and Equivalences, Logic Lecture Notes, University of Leeds (Studocu)](https://www.studocu.com/en-gb/document/university-of-leeds/mathematical-logic-1/logic-lecture-notes-chapter-3-truth-functions-and-equivalences/136604638?origin=related-document)
2. [The Sheffer Stroke, Internet Encyclopedia of Philosophy](https://iep.utm.edu/sheffers/)
3. [Functional Completeness, Logic Notes, ANU](https://users.cecs.anu.edu.au/~jks/LogicNotes/functional-completeness.html)
4. [Propositional Logic, Stanford Encyclopedia of Philosophy](https://plato.sydney.edu.au/entries//////logic-propositional/)
5. [Compositions and Clones of Boolean Functions, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering (Cambridge University Press preview)](https://api.pageplace.de/preview/DT0400.9781107266636_A24418083/preview-9781107266636_A24418083.pdf)
6. [Many-Valued Logic, Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/entries/logic-manyvalued/index.html)
7. [Gate Universality, Logic Gates, Electronics Textbook, All About Circuits](https://www.allaboutcircuits.com/textbook/digital/chpt-3/gate-universality/)
8. [NAND and NOR as Universal Gates, Digital Electronics Ch. 10, Engineering Devotion](https://www.engineeringdevotion.com/digital-electronics/lecture/nand-nor-universal-logic.html)
9. [A First Course in Logic, lecture notes, Heriot-Watt University](https://www.macs.hw.ac.uk/~markl/teaching/LOGIC/LOGIC-NOTES.pdf)
10. [A First Course on Logic, lecture notes, University of Bristol](https://people.maths.bris.ac.uk/~mapdw/pdw-logic-revised.pdf)
11. [Syntax and Semantics of Propositional Logic, lecture notes, University of Fribourg](https://homeweb.unifr.ch/liechtli/pub/mmcs/MMI2021.pdf)
12. [Universal Gates: NAND and NOR, MindSpan Education](https://mindspaneducation.com/learn/digital-logic/universal-gates/)
13. [Peirce's Logic, Internet Encyclopedia of Philosophy](https://iep.utm.edu/peir-log/)
14. [Post, E. L. The Two-Valued Iterative Systems of Mathematical Logic (AM-5), JSTOR](https://www.jstor.org/stable/j.ctt1bgzb1r)
15. [Lecture 34 scribe notes, CS6840, IIT Madras](https://www.cse.iitm.ac.in/~jayalal/teaching/CS6840/2012/lecture34.pdf)
16. [NAND as a Universal Gate, Digital Logic & Computer Organization, Kurz](https://university.kurz.fyi/computer-science/computer/digital-logic-computer-organization/nand-as-a-universal-gate)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › Formal logic and foundations › Logical calculi and logical syntax › Propositional logic › Propositional formulas, syntax and semantics*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license