Boolean functions (original question)

[Russ Cox]

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

(And the example was a*b+!a*!b = a XOR b).

I wrote a program to search out the next two.
I believe that a(3) = 9 and a(4) = 15.

A formula over 3 variables that requires
9 operations is
  (a*!c+!a*c+!b)*(a*c+!a*!c+b)
which is really just a XOR b XOR c.

A formula over 4 variables that requires
15 operations is
  (b*!d+!b*d+!a*c+a*!c)*(b*d+!b*!d+a*c+!a*!c)
which is, of course, 
  (!(b XOR d)+!(a XOR c))*((b XOR d)+(a XOR c))
which is a XOR b XOR c XOR d.

It is tempting to guess that a(5) = 33 and
a(6) = 63.

Perhaps someone else can see an argument why
chains of XOR should be the hardest function?

Russ