Propositionally complete languages

1. Introduction

The book, The Mathematics of Logic centres on a propositional language involving $⊤, ⊥, \land, \lor$ and $\neg$ . It shows how may be defined in terms of these. However this is not the only route that may be taken. Other sets of connectives (as they are called) may be taken. We discuss these briefly here, concentrating on the easier semantic aspects.

2. Other sets of connectives

Definition.

A connective in propositional logic, or propositional connective is a function $f : 2^{k} \to 2$ where $2 = \{⊤ ⊥\}$ is the two valued boolean algebra, and $k \in ℕ$ is the arity of the connective.

Thus the connectives of arity $0$ are $⊤$ and $⊥$ (constant functions with zero arguments). The connectives of arity 1 are the identity function, the negation operation $\neg$ , and the two constant functions $⊤ (x)$ and $⊥ (x)$ with one argument each. $\land$ and $\lor$ 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 ℕ$ 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 $θ (x_{1}, \dots x_{k})$ in propositional letters $x_{1}, \dots x_{k}$ and using the symbols for the connectives. For example the set $\{⊤ ⊥ \neg \land \lor\}$ 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 $⊤, ⊥$ are "almost" available from many sets of connectives. More precisely, the function of a single variable $x$ with constant value $⊤$ , is given by $(x \lor \neg x)$ , and this is in most cases just as useful as the true 0-ary connective $⊤$ . Similary for $⊥$ and $(x \land \neg x)$ . Thus the definition of complete is usually taken with $k ⩾ 1$ . In this sense $\{\neg \lor \land\}$ 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 $\neg, \land, \lor$ , 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 \lor 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.

3. Examples

As already indicated, $\{\land \lor \neg\}$ is complete. Since $(x \land y)$ is semantically equivalent to $\neg (\neg x \lor \neg y)$ and $(x \lor y)$ is semantically equivalent to $\neg (\neg x \land \neg y)$ it follows that $\land$ can be defined in terms of $\neg, \lor$ , and $\lor$ can be defined in terms of $\neg, \land$ . Therefore both $\{\land \neg\}$ and $\{\lor \neg\}$ are complete.

Example.

Show that $\{\land \lor\}$ is not complete.

For a hint, consider proving by induction that every formula $θ (x_{1}, \dots, x_{k})$ involving connectives $\land, \lor$ only must have $θ (⊤, \dots, ⊤) = ⊤$ . A slightly harder exercise is to modify this to show that $\{⊤ ⊥ \land \lor\}$ is not complete. (Try proving that for any $θ (x_{1}, \dots, x_{k})$ in these connectives either the value is a constant $⊥$ or else $θ (⊤, \dots, ⊤) = ⊤$ .)

Example.

The set $\{\land \lor ⊤ \to\}$ 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 $\{\to ⊥\}$ is complete.

This follows from $\neg x$ being equivalent to $(x \to ⊥)$ and $(x \lor 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 \lor \neg y$ . This forms a complete set $\{|\}$ on its own. A formal system based on this connective is given in another web page here.

Similarly $x * y = \neg x \land \neg y$ defines a complete set $\{*\}$ .