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” true.

Similarly, we have the law

We can also verify this law by constructing a truth table. This time, there are four entries in the table, one for each of the 2×2 different combinations of the values of p and q.

Note how the first two columns in the truth table enumerate the four different combinations of the values of p and q. Because the evaluation of the expression (p = q) = (q = p) is more complicated, the values of each subexpression have been detailed to the right of the vertical line. The first and third column show the truth value of p = q and q = p, respectively. Note that these are sometimes true and sometimes false but, in each row, their values are always equal. The value of (p = q) = (q = p) given in the middle column is thus always true. In words, the expression (p = q) = (q = p) is “everywhere” true.

Reflexivity and symmetry of boolean equality are unsurprising. Much more interesting is that boolean equality is associative:

We recommend the reader to check the validity of this law by constructing a truth table. The table will have eight rows, corresponding to the 2×2×2 different combinations of the values of p, q and r. In order to avoid mistakes, list the truth values of each subexpression under the principal operator of the expression. Once this has been done, try to identify a general rule, based on how many of p, q and r are true, that predicts when the two expressions ((p = q) = r) and (p = (q = r)) are true.

As discussed in Section 5.3, we use both the symbol “=” and the symbol “≡” for boolean equality. The use of “=” emphasises the transitivity of equality. A continued equality of the form

p₁ = p₂ = . . . = p_n

means that all of p₁, p₂, . . ., p_n are equal. A typical use of “=” for boolean equality is in the steps of a calculation on boolean expressions; if all steps in a calculation are equality steps, we conclude that the first and the last expressions are equal. The use of “≡” emphasises the associativity of boolean equality. A continued equivalence of the form

p₁ ≡ p₂ ≡ . . . ≡ p_n

has the meaning given by fully parenthesising the expression (in any way whatsover, since the outcome is not affected) and then evaluating the expression as indicated by the chosen parenthesisation.

When a boolean equality has just two boolean subexpressions, we choose to write p ≡ q whenever p and/or q involves other relations, in particular equality or inequality in some other domain. For example, a simple law of arithmetic is the cancellation law:

[ x = y   ≡   x+z = y+z ]

The two occurrences of the “=” symbol denote equality of real numbers. Note that “≡” has lower precedence than “=”.

The rule (5.2) was our first example of how the associativity of boolean equality is exploited. For convenience, here is the rule again:

The rule is a definition of true if we read it as true = (p = p); in this form, it states that any instance of the expression “p = p” can be replaced by “true” (or vice versa, any instance of “true” can be replaced by any instance of the expression “p = p”). But it can also be read as (true = p) = p; in this form, it states that true is the unit of boolean equality.

13.2 NEGATION

Negation is discussed in detail in Section 5.4, so this section is very brief.

Negation is a unary operator (meaning that it is a function with exactly one argument) mapping a boolean to a boolean, and is denoted by the symbol “¬”, written as a prefix to its argument. If p is a boolean expression, “¬p” is pronounced “not p”. The law governing ¬p is:

The law introduces both a new unary operator “¬” and a new constant “false”.

See Sections 5.4.1 and 5.4.3 for the rule of contraposition and properties of boolean inequality.

13.3 DISJUNCTION

The disjunction p ∨ q is the (inclusive) “or” of p and q. Stating that p ∨ q is true means that one or more of p and q is true.

Disjunction has three obvious properties, namely idempotence, symmetry and associativity. Idempotence of disjunction is the rule

Note that, for convenience, we assume that the operator “∨” takes precedence over the operator “≡”. Fully parenthesised, (13.6) reads (p ∨ p) ≡ p and not p ∨ (p ≡ p).

The symmetry and associativity of disjunction are expressed as follows:

The associativity of disjunction allows us to omit parentheses in continued disjunctions, as in, for example,

p ∨ q ∨ p ∨ r ∨ q ∨ q.

The symmetry and associativity of disjunction mean that the terms in such a continued disjunction can be rearranged at will, and the idempotence of disjunction means that multiple occurrences of the same term can be reduced to one. So the above expression would be simplified as follows:

        p ∨ q ∨ p ∨ r ∨ q ∨ q

=               {            rearranging terms - allowed beacuse

                              disjunction is symmetric and associative }

        p ∨ p ∨ r ∨ q ∨ q ∨ q

=               {            idempotence of disjunction (applied three times) }

       p ∨ r ∨ q.

The fourth law governing disjunction is not so obvious. Disjunction distributes through equivalence:.

The fifth and final law is called the rule of the excluded middle; it states that, for each proposition p, either p or its negation is true. These are the only two possibilities and a third “middle” possibility is excluded.

Using this basis, we can derive many other laws. Here is how to show that false is a unit of disjunction:

          p ∨false

=                  {         definition of false (5.3)   }

          p ∨ (¬p ≡ p)

=                 {         disjunction distributes over equivalence (13.9)   }

          p ∨ ¬p ≡ p ∨ p

=                {         excluded middle (13.10) and

                             idempotence of disjunction   }

        true ≡ p

=                {         unit of equivalence (5.2)   }

       p.

Similarly, it is easy to show that true is the zero of disjunction. In summary, we have the following theorem.

Theorem 13.11 The booleans form a semiring (Bool, false, true, ∨, ≡) with unit false, zero true, product operator ∨ and addition operator ≡.

13.4 CONJUNCTION

In this section, we define conjunction (logical “and”) in terms of disjunction and equivalence. We show how to use the definition to derive the basic properties of conjunction.

The definition of conjunction uses the so-called golden rule:

The convention is that the conjunction operator (“∧”, read “and”) has the same precedence as disjunction (“∨”) which is higher than the precedence of equivalence.

Giving conjunction and disjunction the same precedence means that an expression like p∧q∨r is ambiguous. It is not clear whether it means (p∧q)∨r or p∧(q∨r). You should, therefore, always parenthesise, so that the meaning is clear. (Giving conjunction precedence over disjunction, as is often done, is bad practice, because it obscures symmetries in their algebraic properties.)

The golden rule can be seen as a definition of conjunction in terms of equivalence and disjunction if we read it as

[ (p∧q) = (p ≡ q ≡ p∨q)].

But it can also be read in other ways. For example, the golden rule asserts the equality

[ (p∧q ≡ p) = (q ≡ p∨q)].

This reading will be used later when we define logical implication. It can also be read as a definition of disjunction in terms of conjunction:

[ (p∧q ≡ p ≡ q) = (p∨q) ].

This reading is sometimes useful when, in a calculation, it is expedient to replace disjunctions by conjunctions.

The golden rule is so named because it can be used in so many different ways. Its beauty comes from exploiting the associativity and symmetry of equivalence. Here is how it is used to prove that conjunction is symmetric:

          p∧q

=              {          golden rule }

        p ≡ q ≡ p ∨ q

=              {          equivalence and disjunction are symmetric }

       q ≡ p ≡ q∨p

=             {          golden rule, p,q := q,p }

        q∧p.

So-called absorption of conjunctions by disjunctions is derived as follows:

          p∨(p ∧ q)

=               {          golden rule }

         p∨(p ≡ q ≡ p∨q)

=               {         disjunction distributes over equivalence }

        p∨p ≡ p ∨ q ≡ p ∨ (p∨q)

=               {         idempotence and associativity of disjunction }

        p ≡ p ∨q ≡ p∨q

=               {         reflexivity of equivalence (5.2) }

        p.

Thus,

In a similar way, we can prove that conjunction is associative. An outline of the calculation is shown below. (The first and third steps are not given in full.)

          p ∧ (q ∧ r)

=                  {       expand the definition of ∧

                             and use distributivity of ∨ over ≡ }

          p ≡ q ≡ r ≡ q ∨ r ≡ p ∨ q ≡ p ∨ r ≡ p ∨ q ∨ r

=                 {        equivalence is symmetric, disjunction is symmetric }

         r ≡ p ≡ q ≡ p ∨ q ≡ r ∨ p ≡ r ∨ q ≡ r ∨ p ∨ q

=                 {        reverse of first step with p,q,r := r,p,q }

        r ∧ (p ∧ q)

=                 {       conjunction is symmetric }

       (p ∧ q) ∧ r.

From now on, we often omit parentheses in continued conjunctions, silently exploiting the associativity property.

Below we list a number of additional properties of disjunction and conjunction. These can all be proved using the rules given above. Alternatively, they can be verified by constructing a truth table. (Note that in the case of the final law, this involves constructing a table with 32 entries!)

[Distributivity] [ p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) ].

[Distributivity] [ p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) ].

[Modus Ponens] [ p ∧ (p ≡ q) ≡ p ∧ q ].

[De Morgan] [ ¬(p ∧ q) ≡ ¬p ∨ ¬q ].

[De Morgan] [ ¬(p ∨ q) ≡ ¬p ∧ ¬q ].

[Contradiction] [ p ∧ ¬p ≡ false ].

[Distributivity] [ p ∧ (q ≡ r ≡ s) ≡ p ∧ q ≡ p ∧ r ≡ p ∧ s ].

A convenient way to summarise the interaction between disjunction and conjunction is to observe that both operators act like product and addition in a semiring:

Theorem 13.14  The booleans form a semiring (Bool, false, true, ∨, ∧) with unit false, zero true, product operator ∨ and addition operator ∧.

The booleans form a semiring (Bool, true, false, ∧, ∨) with unit true, zero false, product operator ∧ and addition operator ∨.

This is the basis for what is called a “duality” between the operators. Essentially, many properties can be “dualised” by interchanging true and false, and ∧ and ∨. We do not go into details, but this is the reason for choosing not to give either operator precedence over the other.

13.5 IMPLICATION

Many constructions and proofs involve a logical implication rather than a logical equivalence. Put simply, implications are “if” statements rather than “is” statements. An example is: John and Sue are cousins if their fathers are brothers. This is an if statement because the condition given for John and Sue to be cousins is not exhaustive. Another condition is, for example, that their mothers are sisters.

Confusingly, in normal conversation the English word “if” is often used when an equivalence is meant. For instance we might say, Ann and Bob are siblings if they have the same father or the same mother. What is meant here, however, is that the definition of sibling is having the same father or mother. That is, Ann and Bob are siblings is they have the same father or the same mother. In mathematical texts, the distinction between “if” and “is” is often made by writing “iff” when the equality is intended. Often “iff” is pronounced “if and only if” but sometimes it is pronounced “if”, as in normal conversation.

The notation we use for the statement “p if q” is p⇐q. The notation we use for “p only if q” is p⇒q. The expression p⇐q is often verbalised as “p follows from q” and p⇒q is verbalised as “p implies q”.

The statements p⇐q and q⇒p mean the same thing. It is useful to use both notations. Sometimes an argument can be easier to construct in one direction than in the other.

13.5.1 Definitions and Basic Properties

Implications are defined equationally. One definition of p⇐q is as follows:

Note that the precedence of “⇐” is higher than the precedence of “≡” as suggested by the spacing. Henceforth, we give “⇐” and “⇒” lower precedence that “∨” and “∧”.

This defines “⇐” in terms of equivalence and disjunction. Alternatively, in terms of equivalence and conjunction,

The two definitions are the same because, by the golden rule, p ≡ p ∨ q and q ≡ p ∧ q are the same.

Turning the arrows around, we get two definitions of p⇒q:

Immediate consequences of these definitions are obtained by suitable instantiations of the variables p and q. For example, (13.15) gives us

The specific details of the calculation are as follows:

          p ∨ q ⇐ q

=                 {       (13.15), p,q := p ∨ q, q }

         p ∨ q ≡ (p ∨ q) ∨ q

=                {        associativity and idempotence of disjunction }

         p ∨ q ≡ p ∨ q

=                {        reflexivity of ≡ }

        true.

The rule is called “strengthening” because boolean expressions are often viewed as requirements on the free variables; the rule is used to replace a proof requirement p ∨ q by the stronger requirement q. For example, m ≤ n is the same as m < n ∨ m = n. The requirement m = n is “stronger” than the requirement m ≤ n.

A second immediate consequence of the definitions is another strengthening rule:

This is obtained by instantiating q to p ∧ q in (13.15). Other immediate consequences are the following:

[Absurdity] [p ⇐ false];

[Reflexivity] [p ⇐ p];

[De Morgan]: [p⇐q ≡ p ∨ ¬q];

[Contraposition] [p ⇐ q ≡ ¬p ⇒ ¬q];

[Contradiction] [ ¬p ≡ p⇒false];

[Distributivity] [ (p ≡ q)⇐r ≡ p ∧ r ≡ q ∧ r ];

[Distributivity] [ (p ≡ q)⇐r ≡ p⇐r ≡ q⇐r ];

[Shunting] [ p ⇐ q ∧ r ≡ (p ⇐ q) ⇐ r ].

The names of these rules are commonly used. For example, a proof that p follows from q (for some properties p and q) is sometimes turned into a proof of the so-called contrapositive: a proof that ¬p implies ¬q. “Proof by contradiction” indicates the combined use of the two rules of contradiction we have given, the one above and the one in Section 13.4: to prove that some property p does not hold one shows that p implies false, where the false statement is a “contradiction” of the form q ∧ ¬q for some q.

13.5.2 Replacement Rules

The advantage of using equations over other methods for defining the logical connectives is the opportunity to substitute equals for equals. The definition of p⇐q provides good examples of this.

An important rule of logic is called modus ponens. It is the rule that

[ (p⇐q) ∧ q ≡ p ∧ q ].

Here is one way of proving it. The important step is the middle step, the first step paving the way for this step.

          (p⇐q) ∧ q

=                {        true is the unit of equivalence }

          (p⇐q) ∧ (q ≡ true)

=                {        substitution of equals for equals:

                            specifically the value true is substituted for q

                            in the term p⇐q }

          (p⇐true) ∧ (q ≡ true)

=                 {       [ p⇐true ≡ p ], true is the unit of equivalence }

          p ∧ q.

The middle step uses the intuition that, if we know that q is true, we can substitute true for q in any expression in which it appears. The rule is called a meta-rule because it cannot be expressed in the form of an algebraic law, and we need additional language outwith the language of the propositional calculus to explain how the rule is used. A way of expressing the rule is as follows:

The rule expresses the idea that if e and f are equal then e may be replaced by f (and vice versa) in any logical expression E.

Note that the rule does not depend on the type of e and f – they could be numbers, strings, booleans, or whatever. Equivalence of propositions is just equality of boolean values, so the rule applies to equivalences e ≡ f just as well. The types of e, f and x do, however, have to be the same.

The introduction of the variable x in the rule allows the possibility that not every occurrence of e and f is interchanged. For example,

         (a² = b) ∧ (a²+1 = 2a² + 3) ≡ (a² = b) ∧ (a²+1 = 2b + 3)

is an instance of the rule. It is so because

(a²+1 = 2x + 3)[x := a²] ≡ a²+1 = 2a² + 3

(a²+1 = 2x + 3)[x := b] ≡ a²+1 = 2b + 3.

Thus, although the subexpression a² is repeated, the replacement rule allows a substitution of a value equal to a² in selected occurrences of the expression.

Substitution of equals for equals is, in fact, an instance of the rule, first formulated by Leibniz, that application of a function to equal values gives equal results: an expression E parameterised by a variable x is a function of x, and E[x := e] and E[x := f] simply denote the result of applying the function to e and to f, respectively. Sometimes, for brevity and to give credit to Leibniz, we use “Leibniz” as the hint when we mean “substitution of equals for equals”.

A more direct formulation of Leibniz’s rule is the following. Suppose E is an arbitrary expression. Then, assuming e, f and x all have the same type,

(Rule (13.22) is a consequence of rule (13.21) because e = f is equivalent to (e = f) ∧ (E = E), to which (13.21) can be applied.)

We use both rules (13.21) and (13.22). Which of the two is being used can be recognised by whether a step does not or does change the number of conjuncts, respectively.

Returning to the properties of logical implication, here is how substitution (of equals for equals) is used to prove that implication is transitive.

          (p⇐q) ∧ (q⇐r)

=               {        definition }

          (p ≡ p ∨ q) ∧ (q ≡ q ∨ r)

=               {        substitution of equals for equals (13.22),

                           applied to 2nd term with E = (p ∨ x) }

          (p ≡ p ∨ q) ∧ (q ≡ q ∨ r) ∧ (p ∨ q ≡ p ∨ q ∨ r)

=               {        substitution of equals for equals (13.21):

                           the two rightmost occurrences of p ∨ q

                           are replaced by p }

          (p ≡ p ∨ q) ∧ (q ≡ q ∨ r) ∧ (p ≡ p ∨ r)

=              {         definition }

          (p⇐q) ∧ (q⇐r) ∧ (p⇐r)

⇒              {       weakening }

          p⇐r.

The following rules can all be proved using substitution of equals for equals:

[Mutual Implication (Iff)]   [ p ≡ q ≡ (p⇐q) ∧ (p⇒q) ];

[Distributivity]   [ p ⇐ q ∨ r ≡ (p⇐q) ∧ (p⇐r) ];

[Distributivity]   [ p ∧ q ⇐ r ≡ (p⇐r) ∧ (q⇐r) ].

The rule of mutual implication expresses the anti-symmetry of the follows-from relation on booleans. It is comparable to the anti-symmetry of the at-most relation on numbers:

[ x = y  ≡   x ≤ y ∧ x ≥ y ].

For some problems involving the calculation of a number x, say, one is forced to calculate a so-called upper bound y, say, on the number. That is, we establish x ≤ y. Then, in a second step, we establish that y is also a lower bound on x, that is, that x ≥ y. (This often occurs in optimisation problems where the problem is to determine the minimum number x having a certain property: the first step is to exhibit a number y having the desired property and then show that y cannot be reduced without violating the desired property.) In the same way, sometimes one is forced to simplify a given boolean expression p to boolean expression q by first establishing that p follows from q and, separately, that p implies q. This is a commonly used proof technique but which can often be avoided using equational reasoning.

13.6 SET CALCULUS

Sets were introduced in Chapter 12. Set comprehension was introduced in Section 12.2.5 as a common way to define sets. The use of set comprehension entails using boolean expressions to identify a set’s elements. As a result, there is a precise connection between boolean algebra and set algebra. In this section, we introduce set algebra via this connection.

We begin with the definition of set equality. Two sets S and T are equal exactly when they have the same elements:

The rule (13.23) turns reasoning about the equality of two sets into reasoning about the boolean expressions x∈S and x∈T for some arbitrary x. On the right side of the equivalence is a so-called universal quantification. The symbol “∀” is read as “for all” and the entire expression is read as “for all x, x is in S equivales x is in T”. We discuss universal quantification in detail in Chapter 14; for the moment, the only rule we need is that if we prove some property P that is predicated on x but the proof does not make any assumption about x then we can conclude ∀x :: P.

Here is an example. The unionT of two sets S and T is defined formally by the rule

Using this definition, we show that S∪T and T∪S are equal sets:

           x ∈ S∪T

=                    {          definition of set union: (13.24) }

          x∈S ∨ x∈T

=                    {          disjunction is symmetric }

          x∈T ∨ x∈S

=                   {           definition of set union: (13.24) }

        x ∈ T∪S.

We have thus proved that

∀x :: x ∈ S∪T ≡ x ∈ T∪S.

It follows from (13.23) that [ S∪T = T∪S ].

Note that the core of this calculation is that disjunction is symmetric. Set union inherits the properties of disjunction because the rule (13.24) provides a simple way of rewriting a union of two sets as a disjunction of two booleans, and vice versa. Thus set union is also idempotent and associative. Its unit is the empty set because

and false is the unit of disjunction.

Similarly, set intersection T is defined in terms of the conjunction of boolean expressions:

Consequently, set intersection inherits the properties of conjunction: it is idempotent, symmetric and associative. Also, union distributes through intersection and intersection distributes through union:

[Distributivity]     [ R∪(S∩T) = (R∪S) ∩ (R∪T) ],

[Distributivity]     [ R∩(S∪T) = (R∩S) ∪ (R∩T) ].

The proofs of all these properties are simple: apply the definition of equality of sets to turn the property into an equality of booleans, then apply the relevant property of the boolean operators and, finally, apply the definition of equality of sets once more.

Formally, this duality between set algebra and boolean algebra is captured by two simple rules of set comprehension. Suppose S is a set-valued expression and P is a boolean-valued expression (typically parameterised by variable x). Then

[Set Comprehension]     [ e ∈ {x | P} ≡ P[x := e] ],

[Set Comprehension]     [ S = {x | x ∈ S} ].

13.7 EXERCISES

¹The most common formulation of this property is that the booleans form something called a field, called GF(2): the “Galois field” of order 2. Several additional properties are required for a structure to be a field but, in the case of the booleans, the additional properties are trivial and add nothing to our understanding of their algebraic properties. The significance of identifying the booleans as a field is that they form the simplest possible example of a (Galois) field and the concept of a field is important to the understanding more complex mathematical structures.