Heuristic Approach to Minimizing Boolean Functions Using Binary Trees

Abstract

Simplifying Boolean functions before implementation gives cheaper, faster hardware, but almost no algorithm handles functions of more than six variables well. This project's heuristic method builds a Boolean binary tree, overfits it to the minterm data, and reads the tree back out as a simplified Boolean function.

Introduction

Design complexity scales with the number of terms and literals in a Boolean function. Using a Boolean binary tree, expressions with more than 15 variables can be handled even in the worst case for minterms. The approach draws loose inspiration from the Shannon-Fano lossless compression method.

Related work

The model is a form of decision tree, a machine learning concept that splits input data on a chosen parameter until reaching an outcome. Two classical points of comparison: the Espresso algorithm, which minimizes two-level logic by manipulating cubes representing minterms, and the Quine-McCluskey algorithm, which finds all prime implicants of a function and then the essential ones.

How it works

Definitions

A Boolean binary tree is a data structure where each node splits its children on one bit. Every node checks one bit and returns the literal X or !X depending on the result. Once a leaf is reached, the tree unwinds back up.

Algorithm

A greedy approach. Minterms are converted to binary, then the entropy of each variable is calculated to find the best splitting point, entropy here meaning how often a variable switches between 0 and 1 across the minterms. The variable with the lowest entropy separates the most minterms and becomes the next node. For example, in the minterms Σ(1,3,5,7), variable C has the lowest entropy, so splitting on C produces a single true node and the tree does not grow wider. The chosen variable is set aside, and the same process recurses on the rest. At a leaf, the literal is returned, negated if reached through the false branch.

Leaf conditions

• A single remaining minterm converts directly to its literal form.
• If the left and right groups are equal in size after picking the minimum-entropy variable, that node is treated as a leaf and the tree stops growing.
• The tree caches minterm and solution pairs, so a repeated set of minterms returns the cached solution instead of recomputing.
• (Not implemented) a sequence classification model to predict upfront whether a set of minterms can be grouped, cutting complexity further even if occasionally wrong, since the fallback solution stays correct.

Intuition

Boolean minimization can be pictured as a hypercube lattice, a 3D lattice for 3 variables, extendable to higher dimensions. A random-forest-style extension, running multiple binary trees with different cut choices, could give multiple perspectives on the same minterms, from which the essential implicants can be picked out of the full implicant list.

Complexity

The problem is NP-hard. Even with 6 variables there are roughly 1.84×10¹⁹ possible functions. The algorithm runs in O(2ⁿ) time, where n is the number of minterms rather than variables, and O(n) space, though safety nets keep the typical solve time well below the worst case. With respect to variable count the complexity is O(n): each new variable adds one more pass.

Performance evaluation

Measured by increasing the variable count and doubling the minterm count, using 50 random minterm sets per variable count drawn from a uniform distribution via numpy.

Discussion

The algorithm handles any variable count a modern computer can process. In the worst case, where minterms cannot be grouped at all, complexity is 2ⁿ, but the algorithm checks for that worst case upfront and returns the input directly rather than letting the problem scale exponentially.

Limitations

Quine-McCluskey remains more accurate, since it guarantees the minimum number of terms needed to stay logically equivalent to the input.

Conclusions and future work

For large variable counts Quine-McCluskey is fast, but the Boolean tree keeps pace while trading perfect minimization for speed via the heuristic. Ideas borrowed from random forests and sequence classification could tighten the accuracy further.

References

• Kernighan, B. W. and Lin, S. "An efficient heuristic procedure for partitioning graphs." The Bell System Technical Journal, 1970, pages 291-307.
• Oliveira, Arlindo L. "Inductive Learning by Selection of Minimal Representations." PhD thesis, UC Berkeley, 1994.
• Quinlan, J. R. "Induction of decision trees." Machine Learning, 1:81-106, 1986.

← Back to all projects