Functional completeness

In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.

Description

A well-known complete set of connectives is { AND, NOT }, consisting of binary conjunction and negation. The singleton sets { NAND } and { NOR } are also functionally complete.

Propositional logic

In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate.

Digital electronics

From the point of view of digital electronics, 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 gates, or only binary NOR gates.

See also

• Boolean expression
• Boolean function
• Boolean operator
• Digital electronics
• Logic
• Logical mathematics
• Logic gate
• Mathematics
• Truth table
• Turing completeness

External links

• Functional completeness @ Wikipedia