login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058759 Shannon switching function: least number a(n) such that any switching (or Boolean) function of n variables can be realized as a two-terminal network of AND's and OR's in which the total number of occurrences of the variables X_1, X_1', ..., X_n, X_n' is no more than a(n) (where the primes indicate complements). 3
1, 4, 8, 13 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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 two-terminal 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 n-variable Boolean functions.

REFERENCES

M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965; see especially pp. 230-235 and 408 (for a(4)=13).

O. B. Lupanov, On the synthesis of contact networks, Dokl. Akad. Nauk SSSR, vol. 119, no. 1, pp. 23-26, 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, Addison-Wesley, 1961; see p. 247.

C. E. Shannon, The synthesis of two-terminal switching networks, Bell Syst. Tech. J., 28 (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.

Y. L. Vasilev, Minimal contact networks for 4-variable Boolean functions, Dokl. Akad. Nauk SSSR, vol. 127 (no. 2, 1959), pp. 242-245 [shows that a(4) = 13].

LINKS

Table of n, a(n) for n=1..4.

N. J. A. Sloane, Illustration of initial terms

Index entries for sequences related to Boolean functions

FORMULA

For any epsilon > 0, a(n) > (1-epsilon)*2^n/n for sufficiently large n (Shannon). For any epsilon > 0, a(n) <= (1+epsilon)*2^n/n for sufficiently large n (Lupanov). Hence a(n) ~ 2^n/n as n tends to infinity.

CROSSREFS

Cf. A056287, A057241.

Sequence in context: A083492 A137337 A061517 * A237519 A032474 A222304

Adjacent sequences:  A058756 A058757 A058758 * A058760 A058761 A058762

KEYWORD

nonn,nice,more,hard

AUTHOR

N. J. A. Sloane, Jan 01 2001

EXTENSIONS

Additional comments from Vladeta Jovovic, Jan 01 2001

a(5) <= 28 (Povarov)

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 23 14:53 EDT 2017. Contains 289688 sequences.