Algorithmic Problem Solving

This chapter is about the algebra of booleans, which is the basis of logical reasoning. As discussed in Chapter 5, our focus is on equational reasoning. Because equational reasoning is unusual – most introductions to logic focus on implicational reasoning – there is some overlap between Sections 13.1 and 13.2 in this chapter and sections of Chapter 5. This chapter can be read independently, but occasionally we refer the reader to sections of Chapter 5 for further clarification.

13.1 BOOLEAN EQUALITY

Equality – on any domain of values – has a number of characteristic properties. It is reflexive, symmetric and transitive. Most importantly, equal things are indistinguishable in Leibniz’s sense of being able to substitute one for the other in any context: the so-called rule of substitution of equals for equals or Leibniz’s rule.

These rules apply, of course, to equality of booleans. So, with variable p ranging over the booleans, we have the law

We can verify this law by constructing a truth table. There are two entries in the table, one for each of the two possibilities for the value of p:

The truth table for p = p is true irrespective of the value of p. That is, p = p is “everywhere” ...