Programming, automation, algorithms, macOS, and more.

Simplifying Boolean Expressions

I recently had a boolean expression of the following form:

a || (x && b) || (x && y && c) || (x && y && z && d)

It looked redundant with 10 instances of only 7 different variables.

Pretty much the only rule I know for manipulating boolean logic is how to change AND to OR so I didn’t have much luck working on the above until I realized that AND can be seen as multiply and OR as plus (with false being 0 and everything else being true).

Using that insight we instead have:

a + (x · b) + (x · y · c) + (x · y · z · d)

It is now possible to use the algebraic properties with which most of us should be somewhat familiar. For example we can use the distributivity property to only have one instance of x:

a + x · (b + y · c + y · z · d)

We can do exactly the same with y:

a + x · (b + y · (c + z · d))

We now only list each variable once, so this is optimal (assuming that all variables can affect the result of the expression). Going back to boolean operations we end with:

a || x && (b || y && (c || z && d))

Another thing I gained from this exercise is that now I will always be able to remember that AND has higher precedence than OR which is useful if you want to cut down on your use of parenthesis.

{{ numberOfCommentsTitle }}

{{ submitComment.success }}

Error Posting Comment

{{ submitComment.error }}