Logic as algebra

In classical propositional logic, proofs are often made using the rules of inference, or using the tableaux and resolution methods. However, there is another way to construct proofs: one that treats logic as algebra.

The algebraic method treats logic like high school algebra, where the values are limited to \(\{0, 1\}\) instead of \(\mathbb{C}\), and the operators are the boolean operators. Premises are written out as equations, and solving those equations is the same as constructing a proof.

Proving statements algebraically

Let’s start with an example. Starting with a set of premises, we’ll construct a proof without using any of the traditional methods of proving theorems. Instead, we’ll treat the premises a system of equations, which we’ll solve.

Example 1. Given the premises \(\lnot P\), \(Q \supset P\), and \(Q \lor R\), can we infer \(R\)?

Let’s start by writing the premises as a system of equations:

1.\(\lnot p = 1\)Premise
2.\(q \supset p = 1\)Premise
3.\(q \lor r = 1\)Premise

Here we’re using lowercase letters to represent variables: if \(R\) is a predicate, then we write \(R\) as “\(r = 1\),” and \(\lnot R\) as “\(r = 0\).” The predicate and variable forms are equivalent, but the variable form is more convenient for algebra.

Now let’s find the solutions:

1.\(\lnot p = 1\)Premise
\(p = 0\)Simplification
2.\(q \supset p = 1\)Premise
\(q \supset 0 = 1\)Substitution (\(p = 0\))
\(q = 0\)Simplification
3.\(q \lor r = 1\)Premise
\(0 \lor r = 1\)Substitution (\(q = 0\))
\(r = 1\)Simplification

We can see that \(p = 0\), \(q = 0\), \(r = 1\). So there is one solution:
\((p, q, r) = (0, 0, 1)\)

Can we infer \(R\) from the premises? Yes, because \(r = 1\) for every solution \((p, q, r) \in \{(0, 0, 1)\}\).

We have proved \(R\), but we’ve gained something far more valuable: the full set of solutions to the system of equations. With this information, we can trivially prove or disprove any statement about \(P\), \(Q\), and \(R\).

For example: Can we infer \(P \lor Q\) from the premises? No, because \(p \lor q \neq 1\) at the solution \((p, q, r) = (0, 0, 1)\). This solution is a counterexample (\(\lnot P\), \(\lnot Q\), and \(R\)) which satisfies the premises (\(\lnot P\), \(Q \supset P\), \(Q \lor R\)), but not the conclusion (\(P \lor Q\)).

Note that we could have found the full set of solutions by searching for literals in the branches of a tableau, or by reading the rows in a truth table that are consistent with all of the premises. The algebraic method is only superficially different from the other methods of inference.

Branching

So far, we’ve been able to solve equations through substitution and simplification alone. But there is one more tool in our toolbox: branching.

Example 2. Given the premises \(P \lor Q\) and \(Q \supset P\), can we infer \(Q\)?

First, the premises:

1.\(p \lor q = 1\)Premise
2.\(q \supset p = 1\)Premise

This time, we cannot perform any substitutions or simplifications. Instead, we’ll create a branch around the first premise (\(p \lor q = 1\)): We’ll consider the possibility that \(p = 1\), and the possibility that \(q = 1\), in alternate realities.

1.\(p = 1\)Premise
2.\(q \supset p = 1\)Premise
\(q \supset 1 = 1\)Substitution (\(p = 1\))
\(q \in \{0, 1\}\)Simplification
1.\(q = 1\)Premise
2.\(q \supset p = 1\)Premise
\(1 \supset p = 1\)Substitution (\(q = 1\))
\(p = 1\)Simplification

In the \(p = 1\) reality, there are two solutions:
\((p, q) \in \{(1, 0), (1, 1)\}\).

In the \(q = 1\) reality, there is one solution:
\((p, q) \in \{(1, 1)\}\).

Any of these solutions will solve the original system of equations, so the complete solution set is \(\{(1, 0), (1, 1)\}\).

Can we infer \(Q\) from the premises? No, because \(q \neq 1\) at the solution \((p, q) = (1, 0)\).

Can we infer \(P\) from the premises? Yes, because \(p = 1\) for every solution \((p, q) \in \{(1, 0), (1, 1)\}\).

In this example, we were able to branch on a disjunctive premise (\(p \lor q = 1\)). If none of the premises had been disjunctive, then we’d have converted a premise to disjunctive form (e.g. \(x \supset y\) becomes \(y \lor \lnot x\)), or we’d have branched on a tautology instead (e.g. \(p \lor \lnot p = 1\)).

Special case: tautologies

Example 3. Given no premises, can we infer \(P \lor \lnot P\)?

Yes, because \(p \lor \lnot p = 1\) for every \(p \in \{0, 1\}\).

This is the degenerate case where there’s nothing to solve. We simply move on to the final verification step.

Special case: paradoxes

Example 4. Given the premises \(P\) and \(\lnot P\), can we infer \(X\)?

Here, \(X\) could represent absolutely any statement, so we certainly hope this not a valid argument.

After listing the premises:

1.\(p = 1\)Premise
2.\(p = 0\)Premise

We immediately reach a contradiction:

1.\(p = 1\)Premise
2.\(p = 0\)Premise
\(1 = 0\)Substitution (\(p = 1\))

So there are no solutions:
\((p, x) \in \{\}\)

Can we infer \(X\) from the premises? No, because there is no solution for which \(x = 1\).

Can we infer \(\lnot X\) from the premises? No, because there is no solution for which \(\lnot x = 1\).

We simply cannot make any inferences about \(X\)—which is just as it should be, considering that \(X\) could represent any statement whatsoever.