Recipe3.11.Minimizing (Reducing) Your Boolean Logic

Recipe 3.11. 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 IDs allow 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 you 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, you extract the following Boolean logic:

 !X & !Y

Using theorem T6, you can eliminate one operator from this equation:

 !(X | Y)

Now this equation requires only 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, you extract the Boolean logic:

 (!X & Y) | (X & !Y) | (X & Y)

Using theorem T11, you can simplify the last two parenthesized expressions, yielding X, and obtain the following:

 (!X & Y) | X

This equation is much simpler than the initial equation. In fact, you reduced the number of operators from seven to three, which is greater than a 2:1 ratio.

Some equations might not seem as if 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, you can derive the following expression:

 (!X | X) & (!X | !Y) & (Y | X) & (Y | !Y)

Using theorem T2, you can remove the first and last parenthesized expressions:

 (!X | !Y) & (Y | X)

Finally, using theorem T3, you can minimize the equation once again to the following form:

 !(X & Y) & (Y | X)

You were able to remove only 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.

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, you 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, you 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 you can simplify this equation much further:

 (!X & !(Y ^ Z)) | (X & ((!Y & !Z) | (!Y & Z) | (Y & Z)))

Using theorem T9, once again, you get the following equation:

 (!X & !(Y ^ Z)) | (X & (!Y & (!Z | Z) | (Y & Z)))

Using theorem T2, you 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.