Boolean Algebra to the Rescue: Using Maths to Write Better Code

Wagner is a former theoretical physicist turned iOS developer. He loves teaching, likes to juggle, and thinks that he can do close-up magic.

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:

custom view

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:

exploded custom view highlighting vertical dividers between the buttons

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:

and/or truth table 1

Now imagine that false is represented by 0 and true is represented by 1. Then we have

and/or truth table 2

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:

partial truth table

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 (0s in the first three columns) then none of the dividers should be present, giving 0s for the last two columns. Also, if all three buttons are present (1s in the first three columns) then both dividers should be present, so we should have 1s 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:

full truth table

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.

showRightDivider

In other words, showRightDivider is true/1 when either of these happen:

But these can be written like so as well:

or, more simply,

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 ored 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:

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:

where A is any boolean variable or expression. The last one simply says that oring 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:

showLeftDivider

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,

(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:

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

About Novoda

We plan, design, and develop the world’s most desirable Android products. Our team’s expertise helps brands like Sony, Motorola, Tesco, Channel4, BBC, and News Corp build fully customized Android devices or simply make their mobile experiences the best on the market. Since 2008, our full in-house teams work from London, Liverpool, Berlin, Barcelona, and NYC.

Let’s get in contact