You are here
Homefunctional completeness
Primary tabs
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}=\{\neg,\vee\}$,

$F_{2}=\{\neg,\wedge\}$,

$F_{3}=\{\neg,\to\}$,

$F_{4}=\{\neg,\vee,\wedge\}$,

$F_{5}=\{\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 $i<5$, and $\overline{V}(F_{j})\subset\overline{V}(F_{4})$ for all $j<3$.
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}(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 $\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\{\phi\})$ is semantically equivalent to a wff in $\overline{V}(F)$, considered as a subset of $\overline{V}(F\cup\{\phi\})$.
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).
Mathematics Subject Classification
03B05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Comments
(truth)functional completeness
Because "functional completeness" is somewhat standard for a different property in lambda calculus and combinators, it is probably best to use "truthfunctional completeness" for the propositional calculus property.
V_i == V(F_i) ?
V(F) was defined:
V(F) the set of all wffs built from V with respect to F
and examples given:
V(F_5)
However, V_i was not defined; yet, its used:
V_5 is a much larger set than, say, V_1
shouldn't V_i be defined as an abbreviation for V(F_i)?
Re: V_i == V(F_i) ?
Yes.. Thank you!