2.4 Two-column proofs

If you’ve ever spent much time trying to check someone else’s work in solving an algebraic problem, you’d probably agree that it would be a help to know what they were trying to do in each step. Most people have this fairly vague notion that they’re allowed to “do the same thing on both sides” and they’re allowed to simplify the sides of the equation separately — but more often than not, several different things get done on a given line, mistakes get made, and it can be nearly impossible to figure out what went wrong and where.

Now, after all, the beauty of math is supposed to lie in its crystal clarity, so this sort of situation is really unacceptable. It may be an impossible goal to get “the average Joe” to perform algebraic manipulations with clarity, but those of us who aspire to become mathematicians must certainly hold ourselves to a higher standard.

Two-column proofs are usually what is meant by a “higher standard” when we are talking about relatively mechanical manipulations — like doing algebra, or more to the point, proving logical equivalences. Now don’t despair! You will not, in a mathematical career, be expected to provide two-column proofs very often. In fact, in more advanced work, one tends to not give any sort of proof for a statement that lends itself to a two-column approach. But, if you find yourself writing “As the reader can easily verify, Equation 17 holds…” in a paper, or making some similar remark to your students, you are morally obligated to being able to produce a two-column proof.

So, what exactly is a two-column proof? In the left column, you show your work, being careful to go one step at a time. In the right column, you provide a justification for each step.

We’re going to go through a couple of examples of two-column proofs in the context of proving logical equivalences. One thing to watch out for: if you’re trying to prove a given equivalence, and the first thing you write down is that very equivalence, it’s wrong! This would constitute the logical error known as “begging the question” also known as “circular reasoning.” It’s clearly not okay to try to demonstrate some fact by first asserting the very same fact. Nevertheless, there is (for some unknown reason) a powerful temptation to do this very thing. To avoid making this error, we will not put any equivalences on a single line. Instead we will start with one side or the other of the statement to be proved, and modify it using known rules of equivalence, until we arrive at the other side.

Without further ado, let’s provide a proof of the equivalence \(A \land (B \lor {\lnot}A) \; \cong \; A \land B\).22

\[\begin{array}{rll} &A \land (B \lor {\lnot}A) & \\ && \text{distributive law}\\ \cong & (A \land B) \lor (A \land {\lnot}A) & \\ && \text{complementarity}\\ \cong & (A \land B) \lor \bot & \\ & & \text{identity law}\\ \cong & (A \land B) & \\ \end{array}\]

We have assembled a nice, step-by-step sequence of equivalences — each justified by a known law — that begins with the left-hand side of the statement to be proved and ends with the right-hand side. That’s an irrefutable proof!

In the next example, we’ll highlight a slightly sloppy habit of thought that tends to be problematic. People usually (at first) associate a direction with the basic logical equivalences. This is reasonable for several of them because one side is markedly simpler than the other. For example, the domination rule would normally be used to replace a part of a statement that looked like \[A \land \bot\] with the simpler expression \[\bot.\] There is a certain amount of strategization necessary in doing these proofs, and I usually advise people to start with the more complicated side of the equivalence to be proved. It just feels right to work in the direction of making things simpler, but there are times when one has to take one step back before proceeding two steps forward…

Let’s have a look at another equivalence: \(A \land (B \lor C) \cong (A \land (B \lor C)) \lor (A \land C)\). There are many different ways in which valid steps can be concatenated to convert one side of this equivalence into the other, so a subsidiary goal is to find a proof that uses the least number of steps. Following my own advice, I’ll start with the right-hand side of this one.

\[\begin{array}{rll} & (A \land (B \lor C)) \lor (A \land C) & \\ & & \text{distributive law}\\ \cong & ((A \land B) \lor (A \land C)) \lor (A \land C) & \\ & & \text{associative law}\\ \cong & (A \land B) \lor ((A \land C) \lor (A \land C)) & \\ & & \text{idempotence} \\ \cong &(A \land B) \lor (A \land C) & \\ & & \text{distributive law}\\ \cong &A \land (B \lor C) & \\ \end{array}\]

Note that in the example we’ve just done, the two applications of the distributive law go in opposite directions as far as their influence on the complexity of the expressions are concerned.

2.4.1 Exercises

Write two-column proofs that verify each of the following logical equivalences.

  1. \(A \lor (A \land B) \; \cong \; A \land (A \lor B)\)

  2. \((A \land {\lnot}B) \lor A \; \cong \; A\)

  3. \(A \lor B \; \cong \; A \lor ({\lnot}A \land B)\)

  4. \({\lnot}(A \lor {\lnot}B) \lor ({\lnot}A \land {\lnot}B) \; \cong \; {\lnot}A\)

  5. \(A \; \cong \; A \land ((A \lor {\lnot}B) \lor (A \lor B))\)

  6. \((A \land {\lnot}B) \land ({\lnot}A \lor B) \; \cong \; c\)

  7. \(A \; \cong \; A \land (A \lor (A \land (B \lor C)))\)

  8. \({\lnot}(A \land B) \land {\lnot}(A \land C) \; \cong \; {\lnot}A \lor ({\lnot}B \land {\lnot}C)\)

  1. This equivalence should have been verified using truth tables in the exercises from the previous section.↩