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.
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
or boolean operators. Imagine that we have two boolean variables,
B. The truth tables for
A and B and for
A or B are:
Now imagine that
false is represented by
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
We can then use
or, which will not just make the expressions I'm about to write simpler, but also more intuitive and easier to understand.
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
hasRightButton are called input variables and the boolean variables
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:
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
showRightDivider as boolean expressions in terms of the input variables
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.
How do we do that, though? How do we write expressions for
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.
showRightDivider, for instance. What we really want to know is: when is that value
1)? Well, looking at the table, we see that it's
1 when either of the rows below happens.
In other words,
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
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.
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
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
0. It's actually easier to do that if we think of
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
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.
So now let's get back to the problem at hand and let's simplify the expressions for
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
(!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
Similarly, the last two terms in
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
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,
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
A + (!A * B) has the value
1 regardless of the value of
B and when
A has the value
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 = 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)
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:
and) of the input variables, making sure that variables which have a value of
or) all those expressions together; That is the raw (i.e., not yet simplified) result for the output variable in question.
A + (!A * B).
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