---
tag: FSZ6PCKN0F
kind: definition
name: Functional completeness
msc: [08A40, "06E30", 03B50]
defines: TDZVCWYJ9F
uses: [PTKR703G6A, EJ8YJVM9BW, 070R982G4B]
sources:
  - url: https://en.wikipedia.org/wiki/Functional_completeness
---

## Definition

Let $A$ be a [[finite set|070R982G4B]] with at least two elements.
A set $F$ of finitary [[operations|EJ8YJVM9BW]] on $A$ is *functionally complete* if the [[clone|PTKR703G6A]] generated by $F$ contains every operation $A^n \to A$ for every $n \ge 1$.

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