How to reduce multivariate boolean expressions

Question

I need to model a system of several boolean expressions in 512 variables. Due to the number of variables, I found the expressions are way too large to handle normally, which is why I need a way to reduce them that's both time and space efficient.

Since raw logical expressions are harder to solve and simplify I considered using a simple isomorphism to boolean algebra in Z2:

false -> 0

true -> 1

AND -> xy

XOR -> x + y

OR -> xy + x + y

NOT -> x + 1

This system has a few pretty important properties:

1. there are no coefficients, since every coefficient is equivalent to either 0 or 1 (2nx = 0, (2n + 1)x = x)

2. anything summed to itself is equal to zero

3. there are no exponents (when n >= 1, x^n = x)

In this system, the worst case has a normal form composed of 2^512 elements: (1 + x1 + x2 + x2*x1 + x3 + x3*x1 ... + x512*x511*x510...*x1)

The best way I could think to simplify it is factoring, which would turn it into the product of just 512 factors: (x1 + 1)(x2 + 1)...(x512 + 1)

The spacial improvement is logarithmic, but of course, since it's a low complexity expression, I can't expect a similar improvement for the average case, and in fact I think most expressions wouldn't even be reducible.

I also need to have the ability to sum or multiply two expressions without having to expand them (since expanding would easily overcome any computer's storage's capacity).

Is there an algorithm that's suited for my case? I also accept suggestions acting on raw boolean expressions, modular algebra isn't a requirement.

Answer 1

There's no guaranteed generic way of representing a boolean function of N variables in less than O(2^N) parameters due to pigeonhole principle. The only exception is to exploit some regularities in the data, if there are any.

Another approach is to use Karnaugh_maps, a greedy merge of "islands of truth" in the truth table. This will reduce the number of parameters for simple functions, but the worst case is still 2^N parameters.

Answer 2

This is a common problem in the EDA domain, where such circuits get "minimized" for synthesis purposes. I use the word "minimized" in quotation marks, because there's no fast algorithm to solve it. However, practical instances can be handled fairly efficiently with a variety of heuristics.

In early 90s, Prof. Brayton at Berkeley came up with the Espresso algorithm, which is still in use (with modifications) in modern commercial systems. It's described in this paper. See https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer for details. You can still get the code for espresso at https://ptolemy.berkeley.edu/projects/embedded/pubs/downloads/espresso/ and install it for yourself.