The book, The Mathematics of Logic centres on a propositional
language involving and . It shows
A connective in propositional logic, or propositional connective is a function where is the two valued boolean algebra, and is the arity of the connective.
Thus the connectives of arity are and (constant functions with zero arguments). The connectives of arity 1 are the identity function, the negation operation , and the two constant functions and with one argument each. and are binary connectives (i.e. of arity 2).
A function can always be specified by a truth table with rows. So any connective has a truth table and this truth table defines the connective.
A set of propositional connectives is complete if every function for some can be obtained by composing the identity function and connectives from the set.
In other words a set of connectives is complete if every function can be written as a term in propositional letters and using the symbols for the connectives. For example the set is complete. This was proved (and slightly more) when we showed in Exercises 7.21 and 7.22 that every truth table is described by formulas in DNF (or in CNF).
In practice, the case is often deliberately ignored. The functions with zero arguments are "almost" available from many sets of connectives. More precisely, the function of a single variable with constant value , is given by , and this is in most cases just as useful as the true 0-ary connective . Similary for and . Thus the definition of complete is usually taken with . In this sense is complete even though strictly speaking neither the 0-ary connectives nor can be defined from these.
Since each connective can be defined in terms of ,
each formula involving a new connective can be
translated into the
usual propositional logic (not necessarily in a unique or canonical way)
and treated there. In principle this means
that there will be proof rules for the new connectives and Soundness and
Completeness theorems. We have seen this in the examples of the translation of the
connective as and in the
new rules -I and -E.
In practice, finding such proof rules can be quite
challenging. Not all sets of connectives are complete, and it can be quite an
interesting and oftern tricky exercise to show this.
As already indicated, is complete. Since is semantically equivalent to and is semantically equivalent to it follows that can be defined in terms of , and can be defined in terms of . Therefore both and are complete.
Show that is not complete.
For a hint, consider proving by induction that every formula involving connectives only must have . A slightly harder exercise is to modify this to show that is not complete. (Try proving that for any in these connectives either the value is a constant or else .)
The set is not complete.
This was shown in Exercise 7.24, whereas exercise 7.25 shows what connectives can be defined from this set.
The set is complete.
This follows from being equivalent to and being equivalent to . A formal system based on these connectives is given in a separate web page here.
Consider the Sheffer stroke, . This forms a complete set on its own. A formal system based on this connective is given in another web page here.
Similarly defines a complete set .