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 }.

Examples

The following are some examples of functionally complete sets:

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

Proving 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 Boolean function
  2. self-dual Boolean function
  3. linear boolean function
  4. 0-preserving Boolean function
  5. 1-preserving Boolean function
• Identify functional completeness.

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