functional completeness


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

  • F1={¬,},

  • F2={¬,},

  • F3={¬,},

  • F4={¬,,},

  • F5={¬,,,,}.

For a given set V of (propositional) variables, and a set F of logical connectives, denote V¯(F) the set of all wffs built from V with respect to F. From the choices above, we see that V¯(Fi)V¯(F5) for all i<5, and V¯(Fj)V¯(F4) 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 can be defined in terms of and :

pq:=(pq)(qp),

and can in turn be defined in terms of and ¬:

pq:=(¬p)q,

etc… This means that, although V¯(F5) is a much larger set than, say, V¯(F1), every extra wff in V¯(F5) is in some way equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to an wff in V¯(F1). This equivalence is the familiar semantic equivalence. If fact, we can show that ¬ and 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 ϕ, every wff in V¯(F{ϕ}) is semantically equivalent to a wff in V¯(F), considered as a subset of V¯(F{ϕ}).

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

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

References

  • 1 D. van Dalen: Logic and StructureMathworldPlanetmath, 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 2013-03-22 18:51:32
Last modified on 2013-03-22 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