Boolean functions

[karttu at megabaud.fi]

Neil wrote:
> 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
>
> (where * means AND, + means OR and ' = NOT).
> 
>     X(YZ + Y'Z') + X'(YZ' + Y'Z)
       ^ ^ ^   ^   ^   ^ ^  ^   ^

I get 6 AND's and 3 OR's. What I am counting wrong?
I guess there is an identity that allows eliminating one of
the operations above when one constructs a corresponding
circuit?

Anyways, an interesting question. Shouldn't we able to compute
this upto n=5 (resulting 2^32 =~ 4*10^9 different boolean functions)
with the modern hardware? (And maybe more if there's some hidden
symmetry to be exploited.)

I'm thinking of what kind of search technique to apply here.
E.g., is there some guaranteed upper limit for G(f) for arbitrary/any
boolean function f? I.e. the minimum number of AND/OR-ports in the
Universal Turing/computing machine capable of handling n-bit words.
Something simpler I presume. ;->


Terveisin,

Antti Karttunen

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