# 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

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

```