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=\lbrace \neg, \vee \rbrace$ ,
• $F_2=\lbrace \neg, \wedge \rbrace$ ,
• $F_3=\lbrace \neg, \to \rbrace$ ,
• $F_4=\lbrace \neg, \vee, \wedge \rbrace$ ,
• $F_5=\lbrace \neg, \vee, \wedge, \to, \leftrightarrow \rbrace$ .

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 $\neg$ : $$p\to q:= (\neg p) \vee q,$$ etc... This means that, although $\overline{V}_5$ is a much larger set than, say, $\overline{V}_1$ , every extra wff in $\overline{V}_5$ is in some way equivalent to an wff in $\overline{V}_1$ . This equivalence is the familiar semantic equivalence. If fact, we can show that $\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 $\phi$ , every wff in $\overline{V}(F \cup \lbrace \phi \rbrace)$ is semantically equivalent to a wff in $\overline{V}(F)$ , considered as a subset of $\overline{V}(F \cup \lbrace \phi \rbrace)$ .

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.

Bibliography

1

D. van Dalen: Logic and Structure, Springer, 4th Ed., Berlin (2008).

2

H. Enderton: A Mathematical Introduction to Logic, Academic Press, San Diego (1972).