The book, *The Mathematics of Logic* centres on a propositional
language involving $\top ,\perp ,\wedge ,\vee $ and $\neg $. It shows
how *connectives* (as
they are called) may be taken. We discuss these briefly here, concentrating
on the easier semantic aspects.

Definition.

A *connective* in propositional logic, or *propositional connective*
is a function $f:{2}^{k}\to 2$ where $2=\left\{\top ,\perp \right\}$
is the two valued boolean algebra, and $k\in \mathbb{N}$ is the
*arity* of the connective.

Thus the connectives of arity $0$ are $\top $ and $\perp $ (constant functions with zero arguments). The connectives of arity 1 are the identity function, the negation operation $\neg $, and the two constant functions $\top \left(x\right)$ and $\perp \left(x\right)$ with one argument each. $\wedge $ and $\vee $ are binary connectives (i.e. of arity 2).

A function $f:{2}^{k}\to 2$ can always be specified by a truth table with ${2}^{k}$ rows. So any connective has a truth table and this truth table defines the connective.

Definition.

A set of propositional connectives is *complete* if every
function $f:{2}^{k}\to 2$ for some $k\in \mathbb{N}$
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 $f({x}_{1},\dots {x}_{k})$ can be written as a term $\theta ({x}_{1},\dots {x}_{k})$ in propositional letters ${x}_{1},\dots {x}_{k}$ and using the symbols for the connectives. For example the set $\left\{\top ,\perp ,\neg ,\wedge ,\vee \right\}$ 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 $k=0$ is often deliberately ignored.
The functions with zero arguments $\top ,\perp $ are "almost"
available from many sets of connectives. More precisely, the function
of a single variable $x$ with constant value $\top $,
is given by $(x\vee \neg x)$, and this is in most cases just as
useful as the true 0-ary connective $\top $. Similary for $\perp $ and
$(x\wedge \neg x)$. Thus the definition of *complete* is usually
taken with $k\u2a7e1$. In this sense $\left\{\neg ,\vee ,\wedge \right\}$ is complete
even though strictly speaking neither the 0-ary connectives
$\top $ nor $\perp $ can be defined from these.

Since each connective can be defined in terms of $\neg ,\wedge ,\vee $,
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 $x\to y$ as $\neg x\vee y$ and in the
new rules $\to $-I and $\to $-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, $\left\{\wedge ,\vee ,\neg \right\}$ is complete. Since $(x\wedge y)$ is semantically equivalent to $\neg (\neg x\vee \neg y)$ and $(x\vee y)$ is semantically equivalent to $\neg (\neg x\wedge \neg y)$ it follows that $\wedge $ can be defined in terms of $\neg ,\vee $, and $\vee $ can be defined in terms of $\neg ,\wedge $. Therefore both $\left\{\wedge ,\neg \right\}$ and $\left\{\vee ,\neg \right\}$ are complete.

Example.

Show that $\left\{\wedge ,\vee \right\}$ is not complete.

For a hint, consider proving by induction that every formula $\theta ({x}_{1},\dots ,{x}_{k})$ involving connectives $\wedge ,\vee $ only must have $\theta (\top ,\dots ,\top )=\top $. A slightly harder exercise is to modify this to show that $\left\{\top ,\perp ,\wedge ,\vee \right\}$ is not complete. (Try proving that for any $\theta ({x}_{1},\dots ,{x}_{k})$ in these connectives either the value is a constant $\perp $ or else $\theta (\top ,\dots ,\top )=\top $.)

Example.

The set $\left\{\wedge ,\vee ,\top ,\to \right\}$ is not complete.

This was shown in Exercise 7.24, whereas exercise 7.25 shows what connectives can be defined from this set.

Example.

The set $\left\{\to ,\perp \right\}$ is complete.

This follows from $\neg x$ being equivalent to $(x\to \perp )$ and $(x\vee y)$ being equivalent to $(\neg x)\to y$. A formal system based on these connectives is given in a separate web page here.

Example.

Consider the Sheffer stroke, $x|y=\neg x\vee \neg y$. This forms a complete set $\left\{|\right\}$ on its own. A formal system based on this connective is given in another web page here.

Similarly $x*y=\neg x\wedge \neg y$ defines a complete set $\left\{*\right\}$.