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

## Tables

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