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