Functional completeness

Remarks

Example: $F = \set{\wedge, \neg}$ on $\set{0, 1}$ is functionally complete. Check: every Boolean function of $n \ge 1$ variables has a disjunctive normal form, with the constant $0$ written as $x_1 \wedge \neg x_1$. The disjunctions are removed with $x \vee y = \neg(\neg x \wedge \neg y)$. Non-example: $F = \set{\wedge, \vee}$ on $\set{0, 1}$ is not functionally complete. Every operation built from $\wedge$ and $\vee$ maps $(1, \dots, 1)$ to $1$, so $\neg$ is not in the generated clone. Some texts, especially in logic, allow constants to be used for free; this changes which sets count as complete.