Boolean functions, corrected version

[N. J. A. Sloane]

[This is a postscript to my original posting, and does not replace it.]

Apologies, I misread Shannon's paper.
Here is the real problem:

We build f(X_1, ..., X_n) with a two-terminal network
using AND's and OR's applied to the variables X_1, X_1',
..., X_n, X_n', but what we count is the total number
of times the variables X_1, X_1', ..., X_n, X_n' are used.

For n=1 the worst case is f = X, circuit is

         o----- X ----o

requiring 1 variable.

For n=2 it is X XOR Y, circuit is


         X    X'
        / \  / \
    o -     o   ----o
        \  / \ /
         Y    Y'

requiring 4 uses of the variables

For n=3 the worst is X XOR Y XOR Z, circuit is


             Y 
            / \
           o   ---------- Z --
          / \           (P)   \
         X    Y'               \---------- o
        /      \               /
    o -         o---Z' -------/
        \       /
         X'    Y
          \   /
           \ /  / (join to P)
            \  /
             Y'

requiring 8 uses of the variables.

So far we have   1 2 3
  worst case     1 4 8
and Shannon asserts the next term is 14

However, Vladeta Jovovic <vladeta at EUnet.yu>,
replying to my original message, said:

Lupanov O. B.  in  On the synthesis of contact networks, Dokl. Akad. Nauk
SSSR, vol 119, no. 1, pp. 23-26, 1958" proved :

For any epsilon > 0, a(n) <= (1+epsilon)*2^n/n for sufficiently  large n.
This with Shannon's result gives a(n)~2^n/n, as n tends infinity.

The proof also can be find in   M. A. Harrison, Introduction to Switching
and Automata Theory. McGraw Hill, NY, 1965.

Vasilev Y. L. in  Minimal contact networks for 4-variable Boolean
functions, Dokl . Akad. Nauk SSSR, vol 127, no. 2, p. 242, 1959" showed
that a(4)=13.

Povarov G. N. in   Investigation of contact networks with minimal number of
contacts, Ph. D. thesis, Moscow, 1954   proved that a(5)<=28.

(end of quotation)

---------
I assume this means the next terms are 13 (not 14), and <= 28.
(But i'm not 100% certain her references refer to the same problem,
since I had misstated it in my original posting)

Neil Sloane