Recipe 3.12 Minimizing (Reducing) Your Boolean Logic

Problem

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.

Solution

To fix this situation, try applying the theorems shown in Table 3-1 to minimize these types of equations.

Table 3-1. Boolean theorems

Theorem ID	Theorem definition
T0	!(!x) == x
T1	x | x == x
T2	x | !x == true
T3 (DeMorgan's Theorem)	!x | !y == !(x & y)
T4	x & x == x
T5	x & !x == false
T6 (DeMorgan's Theorem)	!x & !y == !(x | y)
T7 (Commutative Law)	x | y == y | x
T8 (Associative Law)	(x | y) | z == x | (y | z)
T9 (Distributive Law)	x & y | x & z == x & (y | z)
T10	x | x & y = x
T11	x & y | x & !y = x
T12	(x & y) | (!x & z) | (y & z) == (x & y) | (!x & z)
T13 (Commutative Law)	x & y == y & x
T14 (Associative Law)	(x & y) & z == x & (y & z)
T15 (Distributive Law)	(x | y) & (x | z) == x | (y & z)
T16	x & (x | y) = x
T17	(x | y) & (x | !y) = x
T18	(x | y) & (!x | z) & (y | z) == (x | y) & (!x | z)
T19	x | x | x | ... | x == x
T20	!(x | x | x | ... | x) == !x & !x & !x & ... & !x
T21	x & x & x & ... & x == x
T22	!(x & x & x & ... & x) == !x | !x | !x | ... | !x
T23	(x | y) & (w | z) == (x & w) | (x * z) | (y & w) | (y * z)
T24	(x & y) | (w & z) == (x | w) & (x | z) & (y | w) & (y | z)

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.

Discussion

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.

See Also

See the "C# Operators" topic in the MSDN documentation.