
COMMENTS

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 appearances of X_1, X_1', ..., X_n, X_n'. What is the worst case?
To describe this another way: X_i and X_i' are the (front and back) contacts (or elements) of a twoterminal network. Let L(S) be the number of contacts in a network S and L(f) = min L(S), where minimum is taken over all networks S which realize the Boolean function f. Then a(n) = max L(f), where maximum is taken over all nvariable Boolean functions.


REFERENCES

M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965; see especially pp. 230235 and 408 (for a(4)=13).
O. B. Lupanov, On the synthesis of contact networks, Dokl. Akad. Nauk SSSR, vol. 119, no. 1, pp. 2326, 1958.
G. N. Povarov, Investigation of contact networks with minimal number of contacts, Ph. D. thesis, Moscow, 1954.
S. Seshu and M. B. Reed, Linear Graphs and Electrical Networks, AddisonWesley, 1961; see p. 247.
C. E. Shannon, The synthesis of twoterminal switching networks, Bell Syst. Tech. J., 28 (1949), pp. 5998. Reprinted in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 588627.
Y. L. Vasilev, Minimal contact networks for 4variable Boolean functions, Dokl. Akad. Nauk SSSR, vol. 127 (no. 2, 1959), pp. 242245 [shows that a(4) = 13].
