A set of logic operations is functionally complete in Boolean algebra provided every propositional function can be expressed entirely in terms of operations in the set - i.e. by combining the various logic operations in a set one could create every truth table. Two notable sets are { NAND } and { NOR }. Such sets are also called universal or complete sets.

Examples

The following are some examples of functionally complete sets:

• { NOR }, { NAND }, { MIN }, { INH }, { MUX }
• { AND, NOT }, { OR, NOT }, { XOR, AND }, { MAJ, NOT }

Determining Completeness

Func	Monotone	Self-dual	Linear	0-preserving	1-preserving
NOT	✘	✔	✔	✘	✘
AND	✔	✘	✘	✔	✔
OR	✔	✘	✘	✔	✔

• Given a set of Boolean functions
• Find at least one of each:
  1. monotone increasing
  2. self-dual
  3. linear
  4. 0-preserving
  5. 1-preserving
• Identify functional completeness.

From the table it can be seen that the following sets are functionally complete: { AND, NOT }, { OR, NOT }, { AND, OR, NOT }.

See also

• gate universality