Tue Jun 9 14:55:19 CEST 2009

Symmetries of boolean functions

Inspired by the idea from the Sheep synth that only XOR and AND are
interesting ways of combining oscillators, here is some investigation
of the why of that.

There are 2^4 boolean functions that map 2 inputs to one.  There are
only a couple of interesting ones after you remove 0/1 morphism.  In
the following, the squares indicate their Karnaugh maps[1].

    |  A
    |  0 1 
B 0 |  . .
  1 |  . .

Simply looking at the Karnaugh maps already suggests a number of
equivalence classes:

Select class: 1/3

NAND  OR    =>    <=   
1 1   0 1   1 0   1 1  
1 0   1 1   1 1   0 1  

AND   NOR   N=>   N<=
0 0   1 0   0 1   0 0
0 1   0 0   0 0   1 0

Transform class: 2/2 diag

XOR   <=>
1 0   0 1
0 1   1 0

Drop class: 2/2 non-diag

A     B     !A    !B
0 1   0 0   1 0   1 1
0 1   1 1   1 0   0 0

Ignore class: 4/0

0     1
0 0   1 1
0 0   1 1

Each class is a set of boolean function which is closed under
inversion of one of the 2 inputs, or the output of the function.  The
classes can be constructed from a single representative f.  With i_o,
i_a, and i_b inversion or identitiy, the functions 

  g(a,b) = i_o(f(i_a(a), i_b(b)))

make up the class.  The maximum number of elements is 2^(n+1), which
occurs when all combinations of inversion and identitiy yield
a distinct function.

Let's define an "interesting" function to be the ones that belong to
large equivalence classes.  In this sense only AND and its symmetries
are interesting.  Note that this is => (implication).  Putting it as
"only implication is interesting" makes it sound a bit more profound.

Instead of looking at inversions, it's also possible to look at input
permutations.  For the 2->1 case this seems to be a closed operation
in all the classes (mirror around the diagonal).  In fact, in the 3->1
case we need to include permutation symmetry.

So what about 3->1 functions.  Is there a similar way to classify them
as interesting/boring using the same classification (inversion +

There are 2^(2^3) = 256 such boolean functions.  They can be
visualized as 2x2x2 Karnaugh cubes or folded open to one side as a
flat map:

    |  AB    :
    | 00 10  : 11 10 
C 0 |  .  .  :  .  .
  1 |  .  .  :  .  .

For 3->1 functions one just needs to look at the morphisms of the
2x2x2 binary cube.  With what we find from the 2->1 case, there are
some things we can expect:

1. single select (3AND, 3OR, ...)
2. embeddings of the 2->1 functions
3. irreducible structures

Here 3. is expected to be an analogue of non-separable convolution
kernels: increasing dimensionality introduces new structures that
can't be written simply in terms of lower-dimensional ones.

Looking at the 2x2x2 binary cube and trying to fill it with a pattern
that can be oriented in many different ways makes me think of an
L-shape like this:

x x . .
x . . .

It can be placed in one of 8 corners, with each taking 3 possible
orientations, leading to 24 symmetries.  However, this one is "flat".
It is independent of one of the inputs.  Rotating one plane of the the
2x2x2 cube 90 degrees wrt to another one (like you would do with a
rubik's cube) gives this configuration:

. x x .
x . . .

Which is no longer flat.  It is like an L that maximally occupies
space in the cube.  This turns out to be the function (class) that's
used in Wolfram's rule 110[2].

These two functions are in distinct classes (they difference is
_essential_ as the former doesn't use one of the inputs, while the
latter does).  However, they have the same number of symmetries:

       8 x 3 x 2 = 48

This follows from 8 different positions (the corners of the cube), 3
different orientations to fix one of the other 3 points at, and the
inversion of the pattern.

This might not be a coincidence.  Are they maybe lines and planes of a
projective plane, thereby being dual?

For 3-input, binary, 1D CAs, Wolfram identifies 88[3] fundamentally
different rules.  Why are there so many?  For CAs the order and
polarity matters a great deal.  Due to recursive application, there is
little more than left-right symmetry (256->128) + some symmetry in
degenerate cases.

Anyways.  How to look for such "interesting" functions automatically?

Let's look at the interpretation of functions in this class.  After
all, this is simple logic, so there is natural-language intuition to
connect to.

       _ __ _
C   .  x  x  . 
C   x  .  .  .

(A & B & C) | ((~B & ~C))
            | ~(B | C)

Hmm not much there..

What practical predictions to make?  Not more than hunches really.  I
suspect that a representative of this function will lead to an
interesting modulation scheme for a 3-oscillator synth.  This can
probably be generalized to higer dimensional functions.

Does giving up permutation give special status to the individual
functions?  This might also be usable in sound synthesis, where one of
the modulators has a different function than the other sounds.

[1] http://en.wikipedia.org/wiki/Karnaugh_map
[2] http://mathworld.wolfram.com/Rule110.html
[3] http://www.wolframscience.com/nksonline/page-57-text?firstview=1