# 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

## Syntax

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

• There is no assignment; `=` is shorthand for `==`.
• There is no comma operator.
• The new syntax expr `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.

## 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.