functional completeness
Recall that in classical propositional logic^{}, wellformed 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.
References
 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).
Title  functional completeness 

Canonical name  FunctionalCompleteness 
Date of creation  20130322 18:51:32 
Last modified on  20130322 18:51:32 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  11 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03B05 
Synonym  truth functional completeness 
Synonym  truth functionally complete 
Defines  functionally complete 