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:
-
•
,
-
•
,
-
•
,
-
•
,
-
•
.
For a given set of (propositional) variables, and a set of logical connectives, denote the set of all wffs built from with respect to . From the choices above, we see that for all , and 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 can be defined in terms of and :
and can in turn be defined in terms of and :
etc… This means that, although is a much larger set than, say, , every extra wff in is in some way equivalent to an wff in . 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 of logical connectives is said to be truth functionally complete, or functionally complete if, given logical connective , every wff in is semantically equivalent to a wff in , considered as a subset of .
It is clear that if is functionally complete, so is any of its superset. Also, given a set of logical connectives, if there is a functionally complete set of logical connectives such that every wff in is semantically equivalent to a wff in , then is functionally complete.
For example, it can be shown that above is functionally complete, and as an easy corollary, so is each of the rest of 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 | 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 |