A few days ago I was fixing an auto-layout issue on a custom view in Novoda's first iOS app and it gave me a chance to play with some boolean algebra. This post gives an overview of the practical implications of boolean algebra for problem solving and shows how you can apply it in order to write correct and simpler code.

The custom view in question is a reusable component used to build custom alerts in the app, and has three buttons, like so: Sometimes, however, we only need to display one or two buttons so the remaining one(s) need to be constrained to have zero width. In itself that's not a particularly difficult auto-layout problem so that's not the focus of this post. Rather, I want to focus on the vertical dividers between the buttons. Here's an "exploded" view of the custom view so we can see more clearly the buttons and the dividers: The question, then, is: when should we show the left and/or the right vertical dividers?

This is also not a particularly difficult problem to solve but it provides a great opportunity to show how one can use a little boolean algebra to make sure the code that computes the hidden state of those dividers is not only correct but also the simplest possible. What I'm going to explain below is a general method that can be applied to any problem involving boolean variables and boolean expressions.

### Truth tables

We start by writing the so-called truth table that describes the problem at hand. A truth table lists all possible combinations of the boolean variables of interest and, for each such combination, shows the expected result.

Here we have 3 buttons, each of which may or may not be present, and 2 vertical dividers whose present/not-present state we want to compute in terms of the present/not-present state of each button.

Before I write that truth table, however, I want to talk about two other truth tables, those of the `and` and `or` boolean operators. Imagine that we have two boolean variables, `A` and `B`. The truth tables for `A and B` and for `A or B` are: Now imagine that `false` is represented by `0` and `true` is represented by `1`. Then we have and it becomes apparent that the logical `and` operator is like the multiplication of binary digits, in that the only way to get `1` out of the two variables is if both of them have the value `1`. Similarly, the logical `or` operator is like the addition of binary digits in that the only way to get `0` out of the two variables is if both of them have the value `0`.

We can then use `*` for `and` and `+` for `or`, which will not just make the expressions I'm about to write simpler, but also more intuitive and easier to understand.

### Back to the buttons and dividers

We have 3 buttons - each of which can be present or absent - so we have a total of 2^3 = 8 possible combinations. For each of those combinations, zero, one, or both of the dividers will be present. We then need to fill the truth table below: Incidentally, the boolean variables `hasLeftButton`, `hasMiddleButton`, and `hasRightButton` are called input variables and the boolean variables `showLeftDivider` and `showRightDivider` are called output variables.

Obviously, if none of the buttons are present (`0`s in the first three columns) then none of the dividers should be present, giving `0`s for the last two columns. Also, if all three buttons are present (`1`s in the first three columns) then both dividers should be present, so we should have `1`s in the last two columns. Yet another simple case is that if only one button is present then no dividers should appear.

Here's an interesting case, though: if we have the left and right buttons but not the middle button, then we need one divider to appear but... which one? If we make the convention that the left divider is associated with the left button and the right divider is associated with the middle button then not having the middle button means not having the right divider. Therefore, `101` (left and right but no middle) must result in `10` (left divider but no right divider).

Working our way through the entire table, we get: This table describes every possible situation that could happen in this problem, in a compact way. The problem now is how to express the output variables `showLeftDivider` and `showRightDivider` as boolean expressions in terms of the input variables `hasLeftButton`, `hasMiddleButton`, and `hasRightButton` so that we match the results of the table when we write those expressions in code.

Note that if the table is correct, the code will be correct. This shifts the problem from figuring out the logic as we code to figuring out the logic first and then having an almost automatic way to write the code, a way that is guaranteed to be correct.

We're also interested in getting the simplest possible expressions that are still correct so that our code is as simple as it can be.

### From truth tables to boolean expressions: concrete example

How do we do that, though? How do we write expressions for `showLeftDivider` and `showRightDivider` that are the simplest possible and also guaranteed to be correct? It's all in the truth table already! All we need to do is understand what the table is actually telling us.

Take `showRightDivider`, for instance. What we really want to know is: when is that value `true` (ie, `1`)? Well, looking at the table, we see that it's `true`/`1` when either of the rows below happens. In other words, `showRightDivider` is `true`/`1` when either of these happen:

• `hasLeftButton == 0 and hasMiddleButton == 1 and hasRightButton == 1`
• `hasLeftButton == 1 and hasMiddleButton == 1 and hasRightButton == 1`

But these can be written like so as well:

• `!hasLeftButton == 1 and hasMiddleButton == 1 and hasRightButton == 1`
• `hasLeftButton == 1 and hasMiddleButton == 1 and hasRightButton == 1`

or, more simply,

• `!hasLeftButton and hasMiddleButton and hasRightButton`
• `hasLeftButton and hasMiddleButton and hasRightButton`

Note the change from `hasLeftButton == 0` to `!hasLeftButton == 1`, which means exactly the same thing. Now, saying that either of these can happen is equivalent to saying that these possibilities are being `or`ed together:

``````showRightDivider = (!hasLeftButton and hasMiddleButton and hasRightButton)
or ( hasLeftButton and hasMiddleButton and hasRightButton)
``````

which translates directly into code as

``````showRightDivider = (!hasLeftButton && hasMiddleButton && hasRightButton)
|| (hasLeftButton && hasMiddleButton && hasRightButton)
``````

But this isn't the simplest possible expression we could write. In fact, the simplest expression is just

``````showRightDivider = hasMiddleButton && hasRightButton
``````

We'll see below how to simplify an expression arising from the truth table. First, I need to explain how to get an expression out of the table, in the general case.

### From truth tables to boolean expressions: general rule

The concrete example above shows that to get an expression for an output variable from a truth table we only need to focus on those rows for which the output variable in question has a value of `true`/`1`, and then we need to `or` those rows together, where each row is the `and` of the corresponding input variables, making sure to negate any input variable that has the value `false`/`0`. It's actually easier to do that if we think of `and` as `*` and `or` as `+`.

Once we have the expressions for the output variables in terms of the input variables, we can use some of the standard properties of addition and multiplication to simplify those expressions. The most commonly used property is the distributive nature of multiplication:

• `A * (B + C) = (A * B) + (A * C)`

except that we generally use it to go from the right-hand side to the left-hand side. The reason we can use this distributive law, of course, is that `and` itself is distributive with respect to `or` in the same way that multiplication is distributive with respect to addition.

Other useful simplification rules come from the identities:

• `A * 0 = 0`
• `A * 1 = A`
• `A + 0 = A`
• `A + 1 = 1`
• `A + !A = 1`

where `A` is any boolean variable or expression. The last one simply says that `or`ing a boolean variable with its negation always results in `1` which is, of course, correct.

### Back to the buttons and dividers

So now let's get back to the problem at hand and let's simplify the expressions for `showLeftDivider` and `showRightDivider` that arise from the truth table we built. First, we need to obtain the expression for `showLeftDivider`, which comes from: and results in

``````showLeftDivider = (hasLeftButton * !hasMiddleButton * hasRightButton)
+ (hasLeftButton * hasMiddleButton * !hasRightButton)
+ (hasLeftButton * hasMiddleButton * hasRightButton)
``````

The expression for the other output variable is that which we had obtained before:

``````showRightDivider = (!hasLeftButton * hasMiddleButton * hasRightButton)
+ (hasLeftButton * hasMiddleButton * hasRightButton)
``````

Let's start with the second one. Note that `hasMiddleButton * hasRightButton` appears in both terms being "added" so we can use the distributive property to write

``````showRightDivider = hasMiddleButton * hasRightButton *
(!hasLeftButton + hasLeftButton)
``````

Now we use the property that anything added to its negation equals `1`, so `(!hasLeftButton + hasLeftButton) = 1` and we have

``````showRightDivider = hasMiddleButton * hasRightButton * 1
``````

But "anything" times `1` equals the "anything" so

``````showRightDivider = hasMiddleButton * hasRightButton
``````

and that's the simplest expression we can get for `showRightDivider`.

Similarly, the last two terms in `showLeftDivider` have `hasLeftButton * hasMiddleButton` in common so

``````showLeftDivider = (hasLeftButton * !hasMiddleButton * hasRightButton)
+ hasLeftButton * hasMiddleButton * (!hasRightButton + hasRightButton)

showLeftDivider = (hasLeftButton * !hasMiddleButton * hasRightButton)
+ hasLeftButton * hasMiddleButton * 1

showLeftDivider = (hasLeftButton * !hasMiddleButton * hasRightButton)
+ hasLeftButton * hasMiddleButton
``````

But now `hasLeftButton` can be factored out as well and we get

``````showLeftDivider = hasLeftButton *
(!hasMiddleButton * hasRightButton + hasMiddleButton)
``````

As it turns out, the term in parenthesis can be simplified further because of another property of boolean algebra,

• `A + (!A * B) = A + B`

(where, in the example of this post, `A` is `hasMiddleButton` and `B` is `hasRightButton`).

We can see that this identity is true by comparing the truth table for `A + (!A * B)` with the truth table for `A + B` (an exercise left to the reader) or by noticing that when `A` has the value `1`, `A + (!A * B)` has the value `1` regardless of the value of `B` and when `A` has the value `0`, `A + (!A * B)` has the value `B`. But that's exactly the same behaviour as that of `A + B`. So, the simplest expression for `showLeftDivider` is:

``````showLeftDivider = hasLeftButton * (hasMiddleButton + hasRightButton)
``````

Does this make sense? Yes, since the left divider should indeed be present if we have the left and middle buttons, regardless of the state of the right button (the first term of the result) or if we have the left and right buttons, regardless of the state of the middle button (the second term of the result).

We then translate those expressions directly into code and we're done:

``````showRightDivider = hasMiddleButton && hasRightButton

showLeftDivider = hasLeftButton && (hasMiddleButton || hasRightButton)
``````

### Summary

Yes, of course using boolean algebra for such a simple problem is overkill. The point is, though, that it's there when we need it and can be very useful to make sure our code is correct and the simplest possible. All we need to do is write a truth table that correctly describes the problem we're trying to code and then apply what is mostly an automatic procedure. More specifically, the steps are:

• Write a truth table for the problem at hand; This is the only part of the problem that is domain-specific.
• For each output variable:
• Collect the rows in the table for which the output variable has the value `true`/`1`.
• For each such row, write an expression that is the product (`and`) of the input variables, making sure that variables which have a value of `false`/`0` are negated.
• Add (`or`) all those expressions together; That is the raw (i.e., not yet simplified) result for the output variable in question.
• Simplify the expression using the properties explained in this post. Alternatively, you can use Wolfram Alpha to do the simplification for you. Here is a particular example showing how to simplify `A + (!A * B)`.
• Convert the simplified expression into code.

Big thanks to Ataul, Ferran, Ryan, and Yvette for providing great feedback on earlier drafts of this post.