Boolean functions
Marc LeBrun
mlb at well.com
Tue Jan 2 18:26:56 CET 2001
>=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...
More information about the SeqFan
mailing list