Many times a Boolean equation quickly becomes large, complex, and even unmanageable. You need a way to manage this complexity while at the same time verifying that your logic works as designed.
To fix this situation, try applying the theorems shown in Table 3-1 to minimize these types of equations.
Table 3-1. Boolean theorems
In Table 3-1, assume that w
,
x
, y
, and z
are all variables of type bool
. The
Theorem
ID
column in this table
allows easy identification of which theorems are being used in the
Boolean equations that are being minimized in the Discussion section.
Simplifying your Boolean logic will benefit your code by making it less cluttered and making its logic clearer and more readily understood. This simplification will lessen the number of potential locations in your logic where bugs can hide and at the same time improve maintainability.
Let’s walk through several examples to show how the
process of minimizing your logic works. These examples use the three
Boolean variables X
, Y
, and
Z
. The names have been kept simple so that we can
concentrate on minimizing the logic and not have to worry about what
the code is trying to do.
The first example uses only the X
and
Y
Boolean variables:
if (!X & !Y) {...}
From this if
statement, we extract the following
Boolean logic:
!X & !Y
Using theorem T6, we can eliminate one operator from this equation:
!(X | Y)
Now this equation only requires two Boolean operators to be evaluated
instead of three. By the way, you might notice that this equation is
a logical NOR
operation.
The second example uses the X
and
Y
Boolean variables in a seemingly complex
equation:
if ((!X & Y) | (X & !Y) | (X & Y)){...}
From this if
statement, we extract the Boolean
logic:
(!X & Y) | (X & !Y) | (X & Y)
Using theorem T11, we can simplify the last two parenthesized expressions into the following:
(!X & Y) | X
This equation is much simpler than the initial equation. In fact, we reduced the number of operators from 7 to 3, which is greater than a 2:1 ratio.
Some equations might not seem like they can be simplified very much, but looks can be deceiving. Let’s try to simplify the following equation:
(!X & Y) | (X & !Y)
Using theorem T24, we can derive the following expression:
(!X + X) & (!X | !Y) & (Y | X) & (Y | !Y)
Using theorem T2, we can remove the first and last parenthesized expressions:
(!X | !Y) & (Y | X)
Finally, using theorem T3, we can minimize the equation once again to the following form:
!(X & Y) & (Y | X)
We were only able to remove a single operator from this equation. This optimization might or might not improve the performance and readability of your code, since it is such a minor change that requires some effort.
You may think that this expression is in its most reduced form.
However, if you examine this expression more closely, you may notice
that it is the equation for the XOR
operator.
Knowing this, we can simplify the equation to the following:
X ^ Y
This technique really shines when you are faced with a large and complex Boolean expression, such as the one shown here:
(!X & !Y & !Z) | (!X & Y & Z) | (X & !Y & !Z) | (X & !Y & Z) | (X & Y & Z)
Using theorem T9, we get the following equation:
(!X & ((!Y & !Z) | (Y & Z))) | (X & ((!Y & !Z) | (!Y & Z) | (Y & Z)))
Notice that the equation (!Y & !Z) | (Y & Z)
is the equivalent of the NOT
XOR
operation on Y
and
Z
. So we can simplify this equation much further:
(!X & !(Y ^ Z)) | (X & ((!Y & !Z) | (!Y & Z) | (Y & Z)))
Using theorem T9, once again, we get the following equation:
(!X & !(Y ^ Z)) | (X & (!Y & (!Z | Z) | (Y & Z)))
Using theorem T2, we get the final equation:
(!X & !(Y ^ Z)) | (X & (!Y | (Y & Z)))
This equation is much simpler than the original and requires much less processing to evaluate, as well.
While it is unnecessary in most cases to commit all of these theorems to memory, you should try to understand them all. In addition, memorizing some of the simpler theorems can come in quite handy in many circumstances.
The theorems outlined in this recipe should be complete enough to allow you to play around with minimizing your Boolean equations.