Chapter 46 Functional completeness

Of our connectives, $\neg$ attaches to a single sentence, and the others all combine exactly two sentences. We may also introduce the idea of an $n$ -place connective. For example, we could consider a three-place connective, ‘ $\heartsuit$ ’, and stipulate that it is to have the following characteristic truth table:

$A$	$B$	$C$	$\heartsuit(A,B,C)$
T	T	T	F
T	T	F	T
T	F	T	T
T	F	F	F
F	T	T	F
F	T	F	T
F	F	T	F
F	F	F	F

Probably this new connective would not correspond with any natural English expression (at least not in the way that ‘ $\wedge$ ’ corresponds with ‘and’). But a question arises: if we wanted to employ a connective with this characteristic truth table, must we add a new connective to TFL? Or can we get by with the connectives we already have (as we can for the connective ‘neither…nor’ for instance)?

Let us make this question more precise. Say that some connectives are jointly functionally complete if⁠f, for any possible truth table, there is a sentence containing only those connectives with that truth table.

The general point is, when we are armed with some jointly functionally complete connectives, no characteristic truth table lies beyond our grasp. And in fact, we are in luck.

Functional Completeness Theorem. The connectives of TFL are jointly functionally complete. Indeed, the following pairs of connectives are jointly functionally complete:

1.

‘ $\neg$ ’ and ‘ $\vee$ ’
2.

‘ $\neg$ ’ and ‘ $\wedge$ ’
3.

‘ $\neg$ ’ and ‘ $\rightarrow$ ’

Given any truth table, we can use the method of proving the DNF Theorem (or the CNF Theorem) via truth tables from chapter 45, to write down a scheme which has the same truth table. For example, employing the truth table method for proving the DNF Theorem, we find that the following scheme has the same characteristic truth table as $\heartsuit(A,B,C)$ , above:

(A\wedge B\wedge\neg C)\vee(A\wedge\neg B\wedge C)\vee(\neg A\wedge B\wedge% \neg C)

It follows that the connectives of TFL are jointly functionally complete. We now prove each of the subsidiary results.

Subsidiary Result 1: functional completeness of ‘ $\neg$ ’ and ‘ $\vee$ ’. Observe that the scheme that we generate, using the truth table method of proving the DNF Theorem, will only contain the connectives ‘ $\neg$ ’, ‘ $\wedge$ ’ and ‘ $\vee$ ’. So it suffices to show that there is an equivalent scheme which contains only ‘ $\neg$ ’ and ‘ $\vee$ ’. To demonstrate this, we simply consider that

\displaystyle(\mathscr{A}\wedge\mathscr{B})

\displaystyle\Leftrightarrow\neg(\neg\mathscr{A}\vee\neg\mathscr{B})

are logically equivalent.¹¹ 1 We’re here using the convention that to say that $\mathscr{A}$ and $\mathscr{B}$ are equivalent can be abbreviated as $\mathscr{A}\Leftrightarrow\mathscr{B}$ . Note that ‘ $\Leftrightarrow$ ’ is not a connective like ‘ $\leftrightarrow$ ’, but a metalinguistic symbol just like ‘ $\vDash$ ’; compare the discussion of ‘ $\vDash$ ’ and ‘ $\leftrightarrow$ ’ in section 12.6.

Subsidiary Result 2: functional completeness of ‘ $\neg$ ’ and ‘ $\wedge$ ’. Exactly as in Subsidiary Result 1, making use of the fact that

\displaystyle(\mathscr{A}\vee\mathscr{B})

\displaystyle\Leftrightarrow\neg(\neg\mathscr{A}\wedge\neg\mathscr{B})

are logically equivalent.

Subsidiary Result 3: functional completeness of ‘ $\neg$ ’ and ‘ $\rightarrow$ ’. Exactly as in Subsidiary Result 1, making use of these equivalences instead:

	$\displaystyle(\mathscr{A}\vee\mathscr{B})$	$\displaystyle\Leftrightarrow(\neg\mathscr{A}\rightarrow\mathscr{B})$
	$\displaystyle(\mathscr{A}\wedge\mathscr{B})$	$\displaystyle\Leftrightarrow\neg(\mathscr{A}\rightarrow\neg\mathscr{B})$

Alternatively, we could simply rely upon one of the other two subsidiary results, and (repeatedly) invoke only one of these two equivalences.

In short, there is never any need to add new connectives to TFL. Indeed, there is already some redundancy among the connectives we have: we could have made do with just two connectives, if we had been feeling really austere.

46.1 Individually functionally complete connectives

In fact, some two-place connectives are individually functionally complete. These connectives are not standardly included in TFL, since they are rather cumbersome to use. But their existence shows that, if we had wanted to, we could have defined a truth-functional language that was functionally complete, which contained only a single primitive connective.

The first such connective we will consider is ‘ $\uparrow$ ’, which has the following characteristic truth table.

$\mathscr{A}$	$\mathscr{B}$	$\mathscr{A}\mathrel{\uparrow}\mathscr{B}$
T	T	F
T	F	T
F	T	T
F	F	T

This is often called ‘the Sheffer stroke’, after Henry Sheffer, who used it to show how to reduce the number of logical connectives in Russell and Whitehead’s Principia Mathematica.²² 2 Sheffer, “A set of five independent postulates for Boolean algebras, with application to logical constants”, Transactions of the American Mathematical Society 14 (1913), pp. 481–488 (In fact, Charles Sanders Peirce had anticipated Sheffer by about 30 years, but never published his results, and the Polish philosopher Edward Stamm published the same result two years before Sheffer.)³³ 3 See Peirce’s “A Boolian algebra with one constant”, which dates to c. 1880, in Peirce’s Collected Papers, vol. 4, pp. 264–5, and Edward Stamm, “Beitrag zur Algebra der Logik”, Monatshefte für Mathematik und Physik 22 (1911), pp. 137–49. It is quite common, as well, to call it ‘nand’, since its characteristic truth table is the negation of the truth table for ‘ $\wedge$ ’.

‘ $\uparrow$ ’ is functionally complete all by itself.

The Functional Completeness Theorem tells us that ‘ $\neg$ ’ and ‘ $\vee$ ’ are jointly functionally complete. So it suffices to show that, given any scheme which contains only those two connectives, we can rewrite it as an equivalent scheme which contains only ‘ $\uparrow$ ’. As in the proof of the subsidiary cases of the Functional Completeness Theorem, then, we simply apply the following equivalences:

	$\displaystyle\neg\mathscr{A}$	$\displaystyle\Leftrightarrow(\mathscr{A}\uparrow\mathscr{A})$
	$\displaystyle(\mathscr{A}\vee\mathscr{B})$	$\displaystyle\Leftrightarrow((\mathscr{A}\uparrow\mathscr{A})\uparrow(\mathscr% {B}\uparrow\mathscr{B}))$

to the Subsidiary Result 1..

Similarly, we can consider the connective ‘ $\downarrow$ ’:

$\mathscr{A}$	$\mathscr{B}$	$\mathscr{A}\mathrel{\downarrow}\mathscr{B}$
T	T	F
T	F	F
F	T	F
F	F	T

This is sometimes called the ‘Peirce arrow’ (Peirce himself called it ‘ampheck’). More often, though, it is called ‘nor’, since its characteristic truth table is the negation of ‘ $\vee$ ’, that is, of ‘neither … nor …’.

‘ $\downarrow$ ’ is functionally complete all by itself.

As in the previous result for $\uparrow$ , although invoking the equivalences:

	$\displaystyle\neg\mathscr{A}$	$\displaystyle\Leftrightarrow(\mathscr{A}\downarrow\mathscr{A})$
	$\displaystyle(\mathscr{A}\wedge\mathscr{B})$	$\displaystyle\Leftrightarrow((\mathscr{A}\downarrow\mathscr{A})\downarrow(% \mathscr{B}\downarrow\mathscr{B}))$

and Subsidiary Result 2..

46.2 Failures of functional completeness

In fact, the only two-place connectives which are individually functionally complete are ‘ $\uparrow$ ’ and ‘ $\downarrow$ ’. But how would we show this? More generally, how can we show that some connectives are not jointly functionally complete?

The obvious thing to do is to try to find some truth table which we cannot express, using just the given connectives. But there is a bit of an art to this.

To make this concrete, let’s consider the question of whether ‘ $\vee$ ’ is functionally complete all by itself. After a little reflection, it should be clear that it is not. In particular, it should be clear that any scheme which only contains disjunctions cannot have the same truth table as negation, i.e.:

$\mathscr{A}$	$\neg\mathscr{A}$
T	F
F	T

The intuitive reason, why this should be so, is simple: the top line of the desired truth table needs to have the value False; but the top line of any truth table for a scheme which only contains $\vee$ will always be True. The same is true for $\wedge$ , $\rightarrow$ , and $\leftrightarrow$ .

‘ $\vee$ ’, ‘ $\wedge$ ’, ‘ $\rightarrow$ ’, and ‘ $\leftrightarrow$ ’ are not functionally complete by themselves.

In fact, the following is true:

The only two-place connectives that are functionally complete by themselves are ‘ $\uparrow$ ’ and ‘ $\downarrow$ ’.

This is of course harder to prove than for the primitive connectives. For instance, the “exclusive or” connective does not have a T in the first line of its characteristic truth table, and so the method used above no longer suffices to show that it cannot express all truth tables. It is also harder to show that, e.g., ‘ $\leftrightarrow$ ’ and ‘ $\neg$ ’ together are not functionally complete.