Example boolean algebra proofs

The three absorption laws in question are those on the boolean laws handout, and the problem posed here is to prove them using other (earlier) laws on the boolean laws handout.

In general in this course, you only need cite a law if it's not obvious what you're doing. The lines in a proof have to follow from each other in accordance with these laws, but usually it will be obvious to the reader what laws you're using; you only need cite laws if clarification is needed. This principle is followed below. (If you're uncertain, feel free to cite more than you have to.)

Let us first prove the second absorption law, that a+ab = a.

One way to do this is to begin with one side of the equation, then argue that it is equal to something, which is equal to something else, and so on, eventually which is equal to the other side of the equation. By the transitivity of equality, this proves that the two sides of the equation are equal.

I'll sometimes use an asterisk ("*") here to indicate "multiplication", i.e. AND, where I would be using a raised dot to indicate ANDing in real life. But as usual, most ANDing is indicated with even less punctuation than that.

Proof:

  a + ab
= a*1 + ab
= a(1+b)
= a*1
= a

Now let us prove the first absorption law, that a(a+b) = a.

  a(a+b)
= a*a + a*b
= a + ab
= a  (by absorption law #2)

Finally, the third absorption law, that a+nota*b = a+b (to simplify this web page a bit, I'll use "nota" to mean not a, i.e. "a" with an overbar):

  a + nota*b
= (a+nota)(a+b)   (by the weirder distributive law: distribute OR over AND)
= 1(a+b)
= a+b

Note that proofs are much easier to read (verify) than to create. The verification of a boolean algebra proof can even be done mechanically, in fact. The formulation of the proof is a creative process and is considerably harder.

That is to say, the fact that you can understand a proof doesn't mean that you could have come up with one yourself. Make sure you get some practice in formulating boolean algebra proofs, not just in reading and understanding my proofs.