I’d like to give a simple account of what I call the hierarchy of logical expressivity for fragments of classical propositional logic. The idea is to investigate and classify the expressive power of fragments of the traditional language of propositional logic, with the five familiar logical connectives listed below, by considering subsets of these connectives and organizing the corresponding sublanguages of propositional logic into a hierarchy of logical expressivity.

• conjunction (“and”), denoted $\wedge$
• disjunction (“or”), denoted  $\vee$
• negation (“not”), denoted $\mathrm{\neg }$
• conditional (“if…, then”), denoted  $\to$
• biconditional (“if and only if”), denoted  $\leftrightarrow$

With these five connectives, there are, of course, precisely thirty-two ($32=2^5$) subsets, each giving rise to a corresponding sublanguage, the language of propositional assertions using only those connectives. Which sets of connectives are equally as expressive or more expressive than which others? Which sets of connectives are incomparable in their expressivity? How many classes of expressivity are there?

Before continuing, let me mention that Ms. Zoë Auerbach (CUNY Graduate Center), one of the students in my logic-for-philosophers course this past semester, Survey of Logic for Philosophers, at the CUNY Graduate Center in the philosophy PhD program, had chosen to write her term paper on this topic.  She has kindly agreed to make her paper, “The hierarchy of expressive power of the standard logical connectives,” available here, and I shall post it soon.

To focus the discussion, let us define what I call the (pre)order of logical expressivity on sets of connectives. Namely, for any two sets of connectives, I define that $A\le B$ with respect to logical expressivity, just in case every logical expression in any number of propositional atoms using only connectives in $A$ is logically equivalent to an expression using only connectives in $B$. Thus, $A\le B$ means that the connectives in $B$ are collectively at least as expressive as the connectives in $A$, in the sense that with the connectives in $B$ you can express any logical assertion that you were able to express with the connectives in $A$. The corresponding equivalence relation $A\equiv B$ holds when $A\le B$ and $B\le A$, and in this case we shall say that the sets are expressively equivalent, for this means that the two sets of connectives can express the same logical assertions.

The full set of connectives $\{\wedge ,\vee ,\mathrm{\neg },\to ,\leftrightarrow \}$ is well-known to be complete for propositional logic in the sense that every conceivable truth function, with any number of propositional atoms, is logically equivalent to an expression using only the classical connectives. Indeed, already the sub-collection $\{\wedge ,\vee ,\mathrm{\neg }\}$ is fully complete, and hence expressively equivalent to the full collection, because every truth function can be expressed in disjunctive normal form, as a disjunction of finitely many conjunction clauses, each consisting of a conjunction of propositional atoms or their negations (and hence altogether using only disjunction, conjunction and negation). One can see this easily, for example, by noting that for any particular row of a truth table, there is a conjunction expression that is true on that row and only on that row. For example, the expression $p\wedge \mathrm{\neg }r\wedge s\wedge \mathrm{\neg }t$ is true on the row where $p$ is true, $r$ is false, $s$ is true and $t$ is false, and one can make similar expressions for any row in any truth table. Simply by taking the disjunction of such expressions for suitable rows where a $T$ is desired, one can produce an expression in disjunctive normal form that is true in any desired pattern (use $p\wedge \mathrm{\neg }p$ for the never-true truth function). Therefore, every truth function has a disjunctive normal form, and so $\{\wedge ,\vee ,\mathrm{\neg }\}$ is complete.

Pressing this further, one can eliminate either $\wedge$ or $\vee$ by systematically applying the de Morgan laws
$$p\vee q\equiv \mathrm{\neg }(\mathrm{\neg }p\wedge \mathrm{\neg }q)p\wedge q\equiv \mathrm{\neg }(\mathrm{\neg }p\vee \mathrm{\neg }q),$$
which allow one to reduce disjunction to conjunction and negation or reduce conjunction to disjunction and negation. It follows that $\{\wedge ,\mathrm{\neg }\}$ and $\{\vee ,\mathrm{\neg }\}$ are each complete, as is any superset of these sets, since a set is always at least as expressive as any of it subsets. Similarly, because we can express disjunction with negation and the conditional via $$p\vee q\equiv \mathrm{\neg }p\to q,$$ it follows that the set $\{\to ,\mathrm{\neg }\}$ can express $\vee$, and hence also is complete. From these simple observations, we may conclude that each of the following fourteen sets of connectives is complete. In particular, they are all expressively equivalent to each other.
$$\{\wedge ,\vee ,\mathrm{\neg },\to ,\leftrightarrow \}$$
$$\{\wedge ,\vee ,\mathrm{\neg },\leftrightarrow \}\{\wedge ,\to ,\mathrm{\neg },\leftrightarrow \}\{\vee ,\to ,\mathrm{\neg },\leftrightarrow \}\{\wedge ,\vee ,\mathrm{\neg },\to \}$$
$$\{\wedge ,\mathrm{\neg },\leftrightarrow \}\{\vee ,\mathrm{\neg },\leftrightarrow \}\{\to ,\mathrm{\neg },\leftrightarrow \}$$
$$\{\wedge ,\vee ,\mathrm{\neg }\}\{\wedge ,\to ,\mathrm{\neg }\}\{\vee ,\to ,\mathrm{\neg }\}$$
$$\{\wedge ,\mathrm{\neg }\}\{\vee ,\mathrm{\neg }\}\{\to ,\mathrm{\neg }\}$$

Notice that each of those complete sets includes the negation connective $\mathrm{\neg }$. If we drop it, then the set $\{\wedge ,\vee ,\to ,\leftrightarrow \}$ is not complete, since each of these four connectives is truth-preserving, and so any logical expression made from them will have a $T$ in the top row of the truth table, where all atoms are true. In particular, these four connectives collectively cannot express negation $\mathrm{\neg }$, and so they are not complete.

Clearly, we can express the biconditional as two conditionals, via $$p\leftrightarrow q\equiv (p\to q)\wedge (q\to p),$$ and so the $\{\wedge ,\vee ,\to ,\leftrightarrow \}$ is expressively equivalent to $\{\wedge ,\vee ,\to \}$. And since disjunction can be expressed from the conditional with $$p\vee q\equiv ((p\to q)\to q),$$ it follows that the set is expressively equivalent to $\{\wedge ,\to \}$. In light of $$p\wedge q\equiv p\leftrightarrow (p\to q),$$ it follows that $\{\to ,\leftrightarrow \}$ can express conjunction and hence is also expressively equivalent to $\{\wedge ,\vee ,\to ,\leftrightarrow \}$. Since
$$p\vee q\equiv (p\wedge q)\leftrightarrow (p\leftrightarrow q),$$ it follows that $\{\wedge ,\leftrightarrow \}$ can express $\vee$ and hence also $\to$, because $$p\to q\equiv q\leftrightarrow (q\vee p).$$ Similarly, using $$p\wedge q\equiv (p\vee q)\leftrightarrow (p\leftrightarrow q),$$ we can see that $\{\vee ,\leftrightarrow \}$ can express $\wedge$ and hence also is expressively equivalent to $\{\wedge ,\vee ,\leftrightarrow \}$, which we have argued is equivalent to $\{\wedge ,\vee ,\to ,\leftrightarrow \}$.  For these reasons, the following sets of connectives are expressively equivalent to each other.
$$\{\wedge ,\vee ,\to ,\leftrightarrow \}$$
$$\{\wedge ,\vee ,\to \}\{\wedge ,\vee ,\leftrightarrow \}\{\vee ,\to ,\leftrightarrow \}\{\wedge ,\to ,\leftrightarrow \}$$
$$\{\wedge ,\leftrightarrow \}\{\vee ,\leftrightarrow \}\{\to ,\leftrightarrow \}\{\wedge ,\to \}$$
And as I had mentioned, these sublanguages are strictly less expressive than the full language, because these four connectives are all truth-preserving and therefore unable to express negation.

The set $\{\wedge ,\vee \}$, I claim, is unable to express any of the other fundamental connectives, because $\wedge$ and $\vee$ are each false-preserving, and so any logical expression built from $\wedge$ and $\vee$ will have $F$ on the bottom row of the truth table, where all atoms are false. Meanwhile, $\to ,\leftrightarrow$ and $\mathrm{\neg }$ are not false-preserving, since they each have $T$ on the bottom row of their defining tables. Thus, $\{\wedge ,\vee \}$ lies strictly below the languages mentioned in the previous paragraph in terms of logical expressivity.

Meanwhile, using only $\wedge$ we cannot express $\vee$, since any expression in $p$ and $q$ using only $\wedge$ will have the property that any false atom will make the whole expression false (this uses the associativity of $\wedge$), and $p\vee q$ does not have this feature. Similarly, $\vee$ cannot express $\wedge$, since any expression using only $\vee$ is true if any one of its atoms is true, but $p\wedge q$ is not like this. For these reasons, $\{\wedge \}$ and $\{\vee \}$ are both strictly weaker than $\{\wedge ,\vee \}$ in logical expressivity.

Next, I claim that $\{\vee ,\to \}$ cannot express $\wedge$, and the reason is that the logical operations of $\vee$ and $\to$ each have the property that any expression built from that has at least as many $T$’s as $F$’s in the truth table. This property is true of any propositional atom, and if $\phi$ has the property, so does $\phi \vee \psi$ and $\psi \to \phi$, since these expressions will be true at least as often as $\phi$ is. Since $\{\vee ,\to \}$ cannot express $\wedge$, this language is strictly weaker than $\{\wedge ,\vee ,\to ,\leftrightarrow \}$ in logical expressivity. Actually, since as we noted above $$p\vee q\equiv ((p\to q)\to q),$$ it follows that $\{\vee ,\to \}$ is expressively equivalent to $\{\to \}$.

Meanwhile, since $\vee$ is false-preserving, it cannot express $\to$, and so $\{\vee \}$ is strictly less expressive than $\{\vee ,\to \}$, which is expressively equivalent to $\{\to \}$.

Consider next the language corresponding to $\{\leftrightarrow ,\mathrm{\neg }\}$. I claim that this set is not complete. This argument is perhaps a little more complicated than the other arguments we have given so far. What I claim is that both the biconditional and negation are parity-preserving, in the sense that any logical expression using only $\mathrm{\neg }$ and $\leftrightarrow$ will have an even number of $T$’s in its truth table. This is certainly true of any propositional atom, and if true for $\phi$, then it is true for $\mathrm{\neg }\phi$, since there are an even number of rows altogether; finally, if both $\phi$ and $\psi$ have even parity, then I claim that $\phi \leftrightarrow \psi$ will also have even parity. To see this, note first that this biconditional is true just in case $\phi$ and $\psi$ agree, either having the pattern T/T or F/F. If there are an even number of times where both are true jointly T/T, then the remaining occurrences of T/F and F/T will also be even, by considering the T’s for $\phi$ and $\psi$ separately, and consequently, the number of occurrences of F/F will be even, making $\phi \leftrightarrow \psi$ have even parity. If the pattern T/T is odd, then also T/F and F/T will be odd, and so F/F will have to be odd to make up an even number of rows altogether, and so again $\phi \leftrightarrow \psi$ will have even parity. Since conjunction, disjunction and the conditional do not have even parity, it follows that $\{\leftrightarrow ,\mathrm{\neg }\}$ cannot express any of the other fundamental connectives.

Meanwhile, $\{\leftrightarrow \}$ is strictly less expressive than $\{\leftrightarrow ,\mathrm{\neg }\}$, since the biconditional $\leftrightarrow$ is truth-preserving but negation is not. And clearly $\{\mathrm{\neg }\}$ can express only unary truth functions, since any expression using only negation has only one propositional atom, as in $\mathrm{\neg }\mathrm{\neg }\mathrm{\neg }p$. So both $\{\leftrightarrow \}$ and $\{\mathrm{\neg }\}$ are strictly less expressive than $\{\leftrightarrow ,\mathrm{\neg }\}$.

Lastly, I claim that $\leftrightarrow$ is not expressible from $\to$. If it were, then since $\vee$ is also expressible from $\to$, we would have that $\{\vee ,\leftrightarrow \}$ is expressible from $\to$, contradicting our earlier observation that $\{\to \}$ is strictly less expressive than $\{\vee ,\leftrightarrow \}$, as this latter set can express $\wedge$, but $\to$ cannot, since every expression in $\to$ has at least as many $T$’s as $F$’s in its truth table.

These observations altogether establish the hierarchy of logical expressivity shown in the diagram displayed above.

It is natural, of course, to want to extend the hierarchy of logical expressivity beyond the five classical connectives. If one considers all sixteen binary logical operations, then Greg Restall has kindly produced the following image, which shows how the hierarchy we discussed above fits into the resulting hierarchy of expressivity. This diagram shows only the equivalence classes, rather than all $65536=2^{16}$ sets of connectives.

If one wants to go beyond merely the binary connectives, then one lands at Post’s lattice, pictured below (image due to Emil Jeřábek), which is the countably infinite (complete) lattice of logical expressivity for all sets of truth functions, using any given set of Boolean connectives. Every such set is finitely generated.