Boolean functions

[Marc LeBrun]

 >=karttu
 >>=Neil
 >> In 1949 Shannon considered the following question...

Hard to imagine that this hasn't been completely solved by now.  I can't 
help but think it must be in Knuth's long-awaited volume 4.  But it's fun 
to think about anyhow.

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

You're counting that expression right.  And I think we can assume Shannon's 
question would involve only the familiar Boolean operations, without 
extraneous switchery.  Perhaps there's another expression for "XOR[3]" that 
takes only 8 operations.

But I don't understand the sequence as given, either.  You can get all 16 
2-variable functions with no more than 3 operations:

# 1s in
output    Expressions

0         0

1         XY X'Y XY' X'Y'

2         X Y X' Y' XY+X'Y' XY'+X'Y

3         X+Y X'+Y X+Y' X'+Y'

4         X+X'+Y+Y'

1+4+6+4+1=16.  The hardest are XOR, EQV and 1, each taking only 3 operations.

So perhaps there's something about Shannon's question we're missing?

 > Shouldn't we able to compute this ... 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)

Well, very naively we can bound it because we can surely write every 
function as a "sub sum" of the tautological expression

   XYZ + X'YZ + XY'Z + X'Y'Z + XYZ' + ... = 1

which takes about n 2^n operations.

But of course there's LOTS of symmetry to remove.  Take some expression E, 
and make F from E by X swapping with X'.  Then if E=F they're independent 
of X.  So X could be removed, thus reducing E to only n-1 variables.  So we 
can consider just the cases where the output depends on all n 
inputs.  These must partition into families of equivalent complexity, where 
each is computable via the same expression with the variables inverted in 
every possible way.  (Generally these will have 2^n members, reduced by any 
algebraic subexpression symmetry).

A fruitful approach might be: for each n, try to find a construction for a 
function which always yields one of the hardest expressions.  It would 
probably strive to be something like the minimal case with maximal asymmetry...