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 instead of , and the operators are the boolean operators. Constructing a proof amounts to solving a system of equations.

Algebraic proofs

Let’s start with an example. Given a set of premises, we’ll construct a proof without using any of the traditional methods of proving theorems. Instead, we’ll construct the proof algebraically.

Example 1. Given the premises , , and , can we infer ?

First, we’ll express the premises algebraically:

1.Premise
2.Premise
3.Premise

Here we use lowercase letters to represent the variables: If is a propositional variable, then is the corresponding algebraic variable, and if is a propositional statement, then is the corresponding algebraic equation.

The premises give us a system of equations, which we can solve through substitution and simplification:

1.Premise
Simplification
2.Premise
Substitution
Simplification
3.Premise
Substitution
Simplification

From this, we see that , , and . So there is one solution:

Can we infer from the premises? Every solution satisfies , so yes, we can infer .

This proves . But it gives us 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 , , and . For example:

Can we infer from the premises? There is a solution for which . This is a counterexample (, , and ) which satisfies the premises (, , ), but not the conclusion (). So no, we cannot infer .

Can we infer from the premises? Every solution satisfies , so yes, we can infer .

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 and , can we infer ?

1.Premise
2.Premise

This time, the equations are already in their simplest form, and we cannot perform any substitutions. To make progress, we’ll consider the first premise () in two small steps: we’ll branch into alternate realities, one where , and another where . Together, they represent the full premise, , but individually we can tackle them.

A.1.Premise
2.Premise
Substitution
Simplification
B.1.Premise
2.Premise
Substitution
Simplification

In branch A, there are two solutions:
.

In branch B, there is one solution:
.

These solutions all satisfy the original system of equations, so the complete solution set is: .

Can we infer from the premises? There is a solution for which , so no, we cannot infer .

In this example, one of the premises was disjunctive (), which allowed us to branch. But what if none of the premises are disjunctive? In that case, we’ll either convert a premise to disjunctive form (e.g. becomes ), or we’ll branch on a tautology instead (e.g. ).

Special case: tautology

Example 3. Given no premises, can we infer ?

This is the degenerate case where there’s nothing to solve. We simply start with , and move on to the final verification step: Every solution satisfies , so yes, we can infer .

Special case: paradox

Example 4. Given the premises and , can we infer ?

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

We start by listing the premises:

1.Premise
2.Premise

And we immediately reach a contradiction:

1.Premise
2.Premise
Substitution

So there are no solutions:

Can we infer from the premises? There is no solution for which , so no, we shouldn’t infer .

Can we infer from the premises? There is no solution for which , so no, we shouldn’t infer .

We simply have no basis for making an inference about .