How to minimize a painstakingly large amount of conditions by using good old-fashioned Boolean algebra

As developers, all of us will sometimes come along with a problem that will make you think out of the box. For me, one of such problems was a situation where I had to get a valid response based on six different variables that depended on each other’s state and were on top of some logic that was already complicated. At that point, I didn’t even know how to begin to write conditions. I knew even less how to ensure that the result was always correct. I did solve the problem in the end, and explained below is the process how.

For the sake of the example, let’s say I walk into an imaginary library where the only possible genres of books are fantasy and romance. I want to choose some books to read, but I have my standards:

  • I like romance books only if they are also fantasy books, but I don’t want to read a book that is shorter than 200 pages or longer than 800 pages,
  • I like fantasy books and I don’t care about their length, but I don’t want romance in that case,
  • If a book is shorter than 200 pages or longer than 800 pages, I want it to be of the romance genre.

Since there are a lot of books to go through, I want to create a program which will filter out all of the books to my liking. Shown below is the list of conditions each book has to pass to be declared as a book that I would like to read:

if (
($book->isFantasy() && $book->isRomance() &&
$book->getLength()>200 && $book->getLength()<800)
||
($book->isFantasy() && !$book->isRomance())
||
($book->isRomance() && ($book->getLength()<200 || $
book->getLength()>800))) {
return $book;
}

Well, this looks overly complicated. Imagine just what it would look like if we added a third genre with its own constraints…

At this point we could shape all the conditions in the way that they are represented with a boolean value, which would then shorten the code a bit. Keeping that in mind, we could change the book length constraints to look like this:

$isLengthWithinRange = 
$book->getLength() > 200 && $book->getLength() < 800;
if (
($book->isFantasy() && $book->isRomance() && $isLengthWithinRange)
||
($book->isFantasy() && !$book->isRomance())
||
($book->isRomance() && !$isLengthWithinRange)) {
return $book;
}

This is a bit easier to understand, but it would still be a nightmare to maintain. On the bright side, all of our constraints are now represented by a boolean variable. This reminded me of Boolean algebra and minimizing boolean functions that I learned at college and thought I would never really use.

After changing the conditions, the book’s validity depends on 3 boolean variables. This leads to 2³ = 8 different combinations. The next step is to draw a truth table and fill in all the combinations and the output function (you can find more on boolean logic and truth tables here). The combinations of variables that indicate that the book passes all the conditions should be marked with 1, while invalid combinations should be marked with 0. If you have some combinations that are impossible to happen in real life (or code), like a book that is neither of romance nor fantasy genre, you can mark them with R or X (redundant/“don’t care”). Marking some combinations as redundant can shorten or lengthen your minimized function, so you can experiment with this one.

Here is the truth table written based on constraints in the library example:

From the table we can see four valid situations:

  • the book is of the fantasy genre, everything else is false
  • the book is of the fantasy genre and valid in length
  • the book is of the romance genre and is valid in length
  • the book is of romance and fantasy genre and is valid in length.

The case where all the variables are false is impossible, and is marked as redundant. The same goes for the case where both book genres are false. Every other outcome is not valid. After the whole table is filled in, you will get your output function (marked with F in the table). As you can see, we still have 4 different conditions, so the next step is to minimize the output function.

There are a number of different ways which you can use to minimize the function, but I prefer using the Karnaugh-Veitch map. If you are not familiar with Veitch diagram or other minimizing algorithms, do not worry because the Internet is your savior. I find this tool really easy to use, since it tells you where every value of the output function goes and it’s pretty straight-forward. If you use redundant output function values, make sure to mark “Allow don’t care” checkbox.

In Karnaugh-Veitch map, every row from a truth table is represented by a cell position in a two-dimensional grid. The value of the cell is the output function value of the corresponding row in the truth table. To minimize the output function, we have to find optimal groups of valid results. Redundant values can be grouped either with valid or invalid results. What you basically do here is group the valid conditions in a way that each group covers the most surface it can, while containing only valid or redundant values. After the optimal groups are found, we can read out the minimal function from the diagram by checking which value do the variables have for the circled areas.

After filling in the output function from the table above, the Karnaugh-Veitch diagram looks like this:

The circled areas represent the minimized function, which is:

F = (x̄2) ∨ (x0), where x2 is $book->isRomance() and x0 is $isLengthWithinRange.

This can easily be translated into conditions, like so:

$isLengthWithinRange = 
$book->getLength() > 200 && $book->getLength() < 800;
if (!$book->isRomance() || $isLengthWithinRange) {
return $book;
}

Now you have your minimal set of conditions that will always provide you with a valid result. If you were to sit and think hard about the constraints we had in the beginning, you would probably come to a solution similar to the resulting minimized function after some time, but why waste your time and brain cells when you can use existing algorithms and techniques that will save you a lot of time?