THE LOGIC NOTES

Functional completeness Glossary

Definition

A set of connectives is functionally complete iff they suffice to express all truth functions of every arity.

Comments

This definition concerns funcional completeness for classical logic, since it is characterised by the bivalent truth tables. The concept does not apply to the non-classical systems presented towards the end of these notes.

Examples

  1. The set {AND, NOT} is functionally complete.
  2. The set {IMP, NOT} is functionally complete.
  3. The set {IFF, NOT} is not functionally complete.

Links