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:
= is shorthand for ==.
in list, where
list is a comma-separated list of expressions, evaluates
to 1 if expr is equal to any of the expressions in list, 0 otherwise.
This makes it easy to describe symmetric functions: x+y+z in 1,2.
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.
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.