# 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.