Functional Completeness

Definition

A set of logical connectives is functionally complete if every possible truth function can be expressed using only the connectives in that set. In other words, a functionally complete set of connectives allows us to define any Boolean function through combinations of those connectives alone.

Examples

Classical Logic

In classical propositional logic, several sets are functionally complete:

• $\{\neg ,\wedge \}$ (negation and conjunction)
• $\{\neg ,\vee \}$ (negation and disjunction)
• $\{\neg ,\to \}$ (negation and implication)
• $\{\uparrow \}$ (Sheffer stroke/NAND alone)
• $\{\downarrow \}$ (Peirce arrow/NOR alone)

Intuitionistic Logic

In intuitionistic logic, functional completeness takes on a different character due to the rejection of certain classical equivalences. The standard connectives $\{\neg ,\wedge ,\vee ,\to \}$ are typically used, but not all classical reductions hold.

Significance in Intuitionism

Functional completeness in intuitionistic logic is more complex than in classical logic because:

1. The Law of the Excluded Middle $A\vee \neg A$ does not hold generally
2. Double negation elimination $\neg \neg A\to A$ fails
3. De Morgan’s laws do not fully apply
4. Classical definitions of connectives in terms of others may not preserve meaning

This means that apparently equivalent sets of connectives in classical logic may not be functionally complete in intuitionistic logic, requiring careful analysis of what can actually be expressed constructively.

Connection to Other Completeness Notions

Functional completeness is distinct from but related to other notions of completeness in logic:

• Semantic Completeness: Every valid formula is provable in the system
• Syntactic Completeness: For every formula, either it or its negation is provable
• Expressive completeness: The ability to express all functions of a given type

These different completeness concepts address separate aspects of logical systems: functional completeness concerns the expressive power of connectives, while semantic and syntactic completeness concern the relationship between provability and truth.