Boolean functions

[N. J. A. Sloane]

In 1949 Shannon considered the following question.

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 max G(f) over all f?
For n = 1, 2, 3, 4, Shannon claims that max G(f) is
        1  4  8 14

For example, when n=3, the function X XOR Y XOR Z requires 8 elements
in its most economical realization, which is

    X(YZ + Y'Z') + X'(YZ' + Y'Z)

(where * means AND, + means OR and ' = NOT).

Does anyone recall if this question is discussed in any
of those old books on switching circuit design (Caldwell,
Harrison, McCluskey, Phister, etc.)?

Are any more terms known?

Here's the entry from the EIS:

%I A058759
%S A058759 1,4,8,14
%N A058759 Least number a(n) such that any switching (or Boolean) function of n variables can be realized as a two-terminal network with no more than a(n) AND's and OR's of the variables and their complements.
%C A058759 The variables X_1, ..., X_n and their negated values X_1', ..., X_n' are available, we only use AND's and OR's, and we wish to minimize the total number of AND's and OR's.
%C A058759 Shannon only states a(4) = 14 implicitly, and it is possible that he proved only that a(4) <= 14 and conjectured a(4) = 14.
%D A058759 C. E. Shannon, The synthesis of two-terminal switching networks, Bell Syst. Tech. J., 28 (Jan. 1949), pp. 59-98. Reprinted in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 588-627.
%H A058759 <a href="http://www.research.att.com/~njas/sequences/Sindx_B.html#Boolean">Index entries for sequences related to Boolean functions</a>
%O A058759 1,2
%e A058759 The function X XOR Y XOR Z requires 8 elements in its most economical realization, which is  X(YZ + Y'Z') + X'(YZ' + Y'Z) (where ' = NOT).
%F A058759 For any epsilon > 0, a(n) > (1-epsilon)*2^n/n for large n. For all n, a(n) <2^(n+3)/n.
%K A058759 nonn,bref,nice,more
%A A058759 njas, Jan 01 2001
%E A058759 a(5) <= 30 (Shannon).

Neil Sloane