Functional completeness

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.

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

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:

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",

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.