Functional Completeness (Propositional Logic)

logic propositional-logic

Definition

Functional Completeness (Propositional Logic)

A set $C$ of logical connectives is functionally complete if every truth-functional connective can be expressed by a propositional formula that uses only connectives from $C$.

Corollaries

$\{\wedge ,\vee ,\neg \}$

The set $\{\wedge ,\vee ,\neg \}$ is functionally complete.

$\{\wedge ,\neg \}$ and $\{\vee ,\neg \}$

The sets $\{\wedge ,\neg \}$ and $\{\vee ,\neg \}$ are functionally complete.

Significance

Why this matters

If a set of connectives is functionally complete, then every propositional formula can be rewritten using only connectives from that set.