Functional completeness

Truth functions

The lesson on the semantics of propositional logic assigned to each formula, under each valuation, a truth value, and showed that this value depends only on the values of the variables that occur in it; hence every formula with $n$ variables has a truth table of $2^{n}$ rows. The question of this lesson is the inverse one. Given an arbitrary table, that is, a column of ones and zeros written at will next to the $2^{n}$ rows, is there a formula that has it as its table? If this holds for every table, the language has no expressive gaps: everything that can be said about the truth value of $n$ statements, as a function of their values, is said by a formula. And since in this course every compound formula is a joint denial, the answer will also tell whether a single connective suffices to say everything.

What is used from the previous lessons

A valuation is a function $v$ from the set of variables $\{v_1, v_2, \ldots\}$ to $\{0, 1\}$, where $1$ is the true and $0$ the false; its extension to all formulas, also written $v$, is defined by recursion: $v((\varphi \downarrow \psi)) = 1$ if and only if $v(\varphi) = 0$ and $v(\psi) = 0$. From the official abbreviations, the same lesson computed, in the theorem on the values of the defined connectives, the value of each connective; written with sums and products, they are the following, for every valuation $v$ and all formulas $\varphi$ and $\psi$:

Moreover, $v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi))$, which equals $1$ if and only if $v(\varphi) = v(\psi)$, and $v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi)$, which equals $1$ if and only if $v(\varphi) \neq v(\psi)$. Since the values are $0$ or $1$, the square of a value is the value itself, $v(\varphi)\,v(\varphi) = v(\varphi)$, and a product of values equals $1$ if and only if each factor equals $1$; both observations will be used without repeating them. The coincidence lemma is also used: if two valuations agree on the variables of $\varphi$, that is, on the variables that are subformulas of $\varphi$, they give $\varphi$ the same value. From the lesson on semantic consequence and equivalence we take semantic equivalence: $\varphi \eqsem \psi$ when $v(\varphi) = v(\psi)$ for every valuation $v$. Finally, the letter convention of the lesson on formalization applies: $p$, $q$ and $r$ denote the variables $v_1$, $v_2$ and $v_3$.

Truth functions and their number

Let $n$ be a natural number. A row of $n$ values is a sequence $a = (a_1, \ldots, a_n)$ in which each $a_i$ is $0$ or $1$; the set of all of them is denoted $\{0, 1\}^{n}$. A truth function of $n$ arguments is a function

that assigns a truth value to each row. It is presented as a table: the rows are written in the order of the table, starting from the one in which all the values are $1$ (for two arguments, $1\,1$, $1\,0$, $0\,1$, $0\,0$), and next to each row its value is written. A truth function is, therefore, a truth table without a formula: the right-hand column, with nothing written in its header.

Formulas that represent functions

A formula and a truth function are related as follows. If $\varphi$ is a formula whose variables are among $v_1, \ldots, v_n$, $\varphi$ is said to represent the truth function $f$ of $n$ arguments when, for every valuation $v$,

that is, when the table of $\varphi$, written with the variables $v_1, \ldots, v_n$, is the table of $f$. The condition on the variables is not a detail: the formula $(p \wedge q)$ represents no function of one argument, because its value does not depend only on that of $p$.

There are infinitely many formulas with variables among $v_1, \ldots, v_n$ and only $2^{2^{n}}$ functions; therefore, many formulas represent the same function, and the proposition says that they are exactly those equivalent to one another. What remains to be known is whether every function is represented by some formula, or whether some tables are left without a formula that has them.