Boolean functions (more)

[N. J. A. Sloane]

More about minimizing Boolean functions.

Concerning the (correct version of) Shannon's problem, 
the sequence stands at 1, 4, 13, <=28, ...
This is A058759 in the EIS and all progress will be reported there.

Concerning the question that I originally posed:

"Consider all 2^2^n Boolean functions f of n variables
X_1, ..., X_n.  You have available the X_i's and their negated values
X_1', ..., X_n', and you must realize f using AND's and OR's
of these 2n variables, using the smallest total number of AND's and OR's.
Call the minimal total number of AND's and OR's used G(f).
What is a(n) = max G(f) over all functions f of n variables?"

Clearly a(1) = 1, and Marc LeBrun in his posting showed that  a(2) = 3.

Several people said that it would not be difficult
to work out a few more terms.  It would be nice
if this could be done!  (Of course the sequence may then
turn out to be in the EIS already.)

Neil Sloane