functional completeness

Recall that in classical propositional logic, well-formed formulas (wffs) can be built up (recursively) from propositional variables via logical connectives. There are several choices for the logical connectives used:

• $F_1=\{\mathrm{\neg },\vee \}$,

• $F_2=\{\mathrm{\neg },\wedge \}$,

• $F_3=\{\mathrm{\neg },\to \}$,

• $F_4=\{\mathrm{\neg },\vee ,\wedge \}$,

• $F_5=\{\mathrm{\neg },\vee ,\wedge ,\to ,\leftrightarrow \}$.

For a given set $V$ of (propositional) variables, and a set $F$ of logical connectives, denote $\overline{V}(F)$ the set of all wffs built from $V$ with respect to $F$. From the choices above, we see that $\overline{V}(F_i)\subset \overline{V}(F_5)$ for all , and $\overline{V}(F_j)\subset \overline{V}(F_4)$ for all .

However, we know that, intuitively, some of the connectives are “redundant” in that they can be “defined” using existing connectives. For example, the connective $\leftrightarrow$ can be defined in terms of $\to$ and $\vee$:

$$p\leftrightarrow q:=(p\to q)\vee (q\to p),$$

and $\to$ can in turn be defined in terms of $\vee$ and $\mathrm{\neg }$:

$$p\to q:=(\mathrm{\neg }p)\vee q,$$

etc… This means that, although $\overline{V}(F_5)$ is a much larger set than, say, $\overline{V}(F_1)$, every extra wff in $\overline{V}(F_5)$ is in some way equivalent to an wff in $\overline{V}(F_1)$. This equivalence is the familiar semantic equivalence. If fact, we can show that $\mathrm{\neg }$ and $\vee$ are all we need: “any” logical connective can be “defined” in terms of them, not just the ones mentioned above. This is the notion of truth functional completeness, or functional completeness for short. To make this precise, we have the following:

Definition A set $F$ of logical connectives is said to be truth functionally complete, or functionally complete if, given logical connective $\varphi$, every wff in $\overline{V}(F\cup \{\varphi \})$ is semantically equivalent to a wff in $\overline{V}(F)$, considered as a subset of $\overline{V}(F\cup \{\varphi \})$.

It is clear that if $F$ is functionally complete, so is any of its superset. Also, given a set $F$ of logical connectives, if there is a functionally complete set $G$ of logical connectives such that every wff in $\overline{V}(G)$ is semantically equivalent to a wff in $\overline{V}(F)$, then $F$ is functionally complete.

For example, it can be shown that $F_1$ above is functionally complete, and as an easy corollary, so is each of the rest of $F_i$ above.