On: How many ANDs and ORs does it take... Low-level bi...

[ableal]

[...] after hearing the problem from Neil Sloane, who suggested it as a variant of a similar problem first studied by Claude Shannon.

It figures ;-)

The web site http://boolean-oracle.swtch.com lets you type in a Boolean expression and gives back the minimal formula for it.

Nice, thanks. I'd suggest adding that example inputs can be had from the column at right (took me a bit to notice).