About the Boolean Oracle

This web server computes the minimal Boolean formula for a given function using a “cheat sheet” generated during the search for the most complex minimal Boolean formula over five variables. The cheat sheet records how to generate each of the 616,126 distinct five-input Boolean formulas (modulo negation and permutation of the inputs and negation of the output). Given a function, the web server searches for a transformation that produces the equivalent canonical function and then applies the reverse transformation to the canonical function's subformulas. It must then recursively translate each of the subformulas, until it hits simple variables. This blog post explains more about the precomputation.

The problem of minimal Boolean formula complexity is inspired by a related circuit design problem first studied by Claude Shannon. This form is the OEIS sequences A056287 and A178939


The syntax accepted by the web server is C expressions over the variables v, w, x, y, and z with the following exceptions:

The function is the result of evaluating the C expression for each possible input setting. The function is false when the C expression evaluates to zero, true otherwise. As a special case, a hexadecimal constant, like 0xffff0000, is interpreted as the truth table value itself: each bit is a function output, as described in the blog post.

Source code

The source code for the search and the web app, both written in Go, are available from the boolean-oracle project on Google Code.


The tables that power the web site are available for download.

Powered by Go on Google App EnginePowered by Go on Google App Engine