Conference rusure::math

    re .0
    
    The way you stated the problem m must = n. Is that correct?
    

re .1:
    
>    The way you stated the problem m must = n. Is that correct?

No; n and m are arbitrary and unrelated.  In my example, n = m = 3
coincidentally.

However, a solution that works only for n = m would still be of interest.
In fact, I think if the solution works for n = m, all the other cases are
degenerate (gotten by making n = m = max( n_given, m_given)).

n is the number of boolean variables; m is the number of functions of these
variables.  In the most general case, each function will depend upon all of the
boolean variables.

Another interesting question: is the set of gk unique for a given set of
fk ?

>[2]

>z1 = g1(y1, y2, ... , yn)
>z2 = g2(y1, y2, ... , yn)
>.
>.
>zn = gm(y1, y2, ... , yn)

The 'zn' above should be a 'zm'.

    re .0

Let us define some notation that will save room. 
B_N = {<x_1,..,x_i,..,x_N> | x_i in [0,1] the simple Boolean Lattice}

BF_N = { functions f | f : B_N -> [0,1]} i.e. the N_addic Boolean Functions

BF_2^N = { functions f | f :B_N -> B_N}

NxBF_N = BF_N X ... X BF_N ( The N-fold cartesian prod of BF_N with itself}

Thus if g in NxBF_N then g = <g_1,...,g_N> where g_1,...g_N in BF_N

Let g = <g_1,...,g_N>. Let x in B_N, where x = <x_1,...,x_N>

Define g * x = <g_1(x_1,...,x_N),...,g_N(x_1,...,x_N)> 
thus for x in B_N, g*x in B_N

Your question can now be stated as follows. If f in BF_2^N, does there exist
g in BF_2^N such that f*x = g*(g*x) for all x in B_N.

How many elements in BF_2^N?  Answer: (2^N)^(2^N)

Maximum number of values the functional g*(g*x) can have? Answer:

Cardinality of NxBF_N which is (2^(2^N))^N which = (2^(N*(2^N)) = (2^N)^(2^N)

Thus your problem has an affirmative answer if it can be shown that
the functional g*(g*x) is a 1-1 mapping from BF_2^N onto BF_2^N.
That is for each distinct choice of g_1,....,g_N, plugging the N_tuple
g=<g_1,...,g_N> gives distinct values for g*(g*x), x runs thru B_N, which is
equivalent to saying that if g # g' then for some N tuple x, we have
g*(g*x) # g'*(g'*x). 

I am currently working on this reduction of the problem.
 

re .0, .4

Bad news. Not all boolean functions have sqare roots. Simple counter example:

	There are four possible function of a single variable:
	1. ALL_TRUE where ALL_TRUE (x) = TRUE (or 1)
	2. ALL_FALSE where ALL_FALSE (x) = FALSE (or 0)
	3. IDENT where IDENT (x) = x
	4. NEG   where NEG (x) = ~x

	ALL_TRUE*ALL_TRUE = ALL_TRUE
	ALL_FALSE*ALL_FALSE = ALL_FALSE
	IDENT*IDENT = IDENT
	NEG*NEG = IDENT

	The function NEG has no boolean square root.

I have not yet shown this for numbers of variables > 1, but I am working on
it. Amusing side light.  You can't compute the square root of minus 1 in the 
domain of Boolean Functional :8>).

More results as I derive them.

    Re .5:
    
    Hmmm, guess we should be looking for something like imaginary roots
    for boolean operations huh?  Sounds like something I read ever so
    long ago in "Laws of Form" by G. Spencer Brown.
    
    
    --  Barry

I've made some progress towards getting an algorithm for the Boolean
square root algorithm.  What I have is a hand procedure for doing this
that I'll describe.  I think this procedure might be easy to
implement in something like Prolog because it's a 'cut and try'
algorithm with occasional backtracking needed.  I'm just a neophyte
Prolog programmer, so I may need some help.

Incidentally, the procedure I came up with is relatively simple and
is probably easily extensible to higher order 'roots'.

Here goes:

First, make a truth table of the functions to be computed.
I'll use the following as an example (I'm an engineer, so I understand
things best by example).


z2 = x2 + x0
z1 = x2' + x1
z0 = x0

x2 x1 x0 | z2 z1 z0
---------|---------
0  0  0  | 0  1  0
0  0  1  | 1  1  1
0  1  0  | 0  1  0
0  1  1  | 1  1  1
1  0  0  | 1  0  0
1  0  1  | 1  0  1
1  1  0  | 1  1  0
1  1  1  | 1  1  1

Add a middle column for the 'square root' (y) and convert to decimal:

x	y	z
-----------------	Any entry made in the 'y' column will be used
0	-	2	as an index into the table to locate the value
1	-	7	of y that must correspond to z in the original
2	-	2	entry.  The constraint is y(y(x)) = z(x).
3	-	7	So we start by assigning y(0) arbitrarily and
4	-	4	proceed until we encounter a contradiction
5	-	5	or produced a self consistent subgrouping.
6	-	6	If we encounter a contradiction, then we
7	-	7	backtrack and reassign y(0).  If we produce
			a self consistent subgrouping, then we find
the next unassigned y and make an arbitrary assignment, repeating the
above process.  This is not a great explanation, so I'll work the
example:

0	0	2
; assigned y(0)=0 and encountered a contradiction,
; since y(y(0))=y(0)=0 <> z(0), so we try a new assignment for y(0)

0	1	2
1	2	7
; with y(0) = 1, we must have y(1) = 2 so that y(y(0)) = z(0).  We continue.

0	1	2
1	2	7
2	7	2
; with y(1) = 2, we must have y(2) = 7 so that y(y(1)) = z(1).  We continue.

0	1	2
1	2	7
2	7	2
7	2	7
; with y(2) = 7, we must have y(7) = 2 so that y(y(2)) = z(2).  We continue.

0	1	2
1	2	7
2	7	2
7	2	7
; with y(7) = 2, we must have y(2) = 7, so that y(y(7)) = z(7).  At this point,
; we can no longer follow the 'chain' of constraints, but must arbitrarily
; assign a new one.  We'll try y(3) = 0.

0	1	2
1	2	7
2	7	2
7	2	7
3	0	7
; y(3) = 0 doesn't work, because y(y(3)) = y(0) = 1 <> z(3) = 7, so we must
; try something else.  y(3) = 1 obviously doesn't go either, so try y(3) = 2.

0	1	2
1	2	7
2	7	2
7	2	7
3	2	7
; y(3) = 2 does work because y(y(3)) = y(2) = 7 does equal z(3). There is
; no new constraint to chain to, so we arbitrarily assign y(4).  The first
; assignment that works is y(4) = 4.

0	1	2
1	2	7
2	7	2
7	2	7
3	2	7
4	4	4
; There is no chain to follow, so we next arbitrarily assign y(5).
; y(5) = 5 is the first assignment that works.

0	1	2
1	2	7
2	7	2
7	2	7
3	2	7
4	4	4
5	5	5
; Again, there is no chain, so arbitrarily assign y(6).  y(6) = 6 is
; the only one that works.

0	1	2
1	2	7
2	7	2
7	2	7
3	2	7
4	4	4
5	5	5
6	6	6
; Now we should convert back to binary and identify the boolean function.
x	y	z
000	001	010
001	010	111
010	111	010
011	010	111
100	100	100
101	101	101
110	110	110
111	010	111

y2 = x1.x0' + x2.x1'
y1 = x1 + x2'.x0
y0 = x2'.x0' + x2.x1'.x0


I know that the square root is not unique (I know this because my sample
z functions were generated by squaring a different function of y).

It's also easy to show that there are functions that do not have square
roots.

I'd like to get this written as a program so that I can play with it some
more.
------------------------------------------------------------------------
It seems that the problem may be isomorphic to one that may be amenable to
results from abstract algebra on finite sets.

For given mapping z: { 0..2^n ) --> { 0..2^n },
find another mapping y: { 0..2^n } --> { 0..2^n }
such that For_all x | (x is_in { 0..2^n }) implies z( x ) = y( y( x ) )

This almost looks like permutation groups may be applicable.

Does THIS problem look familiar to anyone ?

What branch of algebra studies this kind of problem ? 

The following Pascal program should suffice.  When you run it, the input
would be something like:

	$ RUN SQX
	2 7 2 7 4 5 6 7
	1 3 2 2

It only displays the first 50 square roots.

program sqx (input, output);

const
    k_n = 6;			{ up to 6 variables }
    k_twon = 64;		{ 2**n }

type
    bfunc = array [0..k_twon-1] of integer;

procedure dump_bfunc (twon: integer; f: bfunc);
    var
	i:	integer;
    begin
    write ('(');
    for i := 0 to twon-1 do
	begin
	if i <> 0 then write (',');
	write (f[i]:0);
	end;
    write (')');
    end;

function init (var twon: integer; var f: bfunc): boolean;
    var
	i,j:	integer;
	b:	boolean;
    begin

    twon := 0;
    while (not eoln) and (twon < k_twon) do
	begin
	read (f[twon]);
	while (not eoln) and not (input^ in ['0'..'9']) do get (input);
	twon := twon + 1;
	end;
    readln;

    b := true;
    for i := 0 to twon-1 do
	if (0 <= f[i]) and (f[i] < twon) then else b := false;

    if not b then writeln ('an input error occurred')
    else if twon = 0 then b := false
    else
	begin
	dump_bfunc (twon, f);
	writeln (' <-');
	end;

    init := b;
    end;

function sqrt_x (
		twon:	integer;
	    var	x:	bfunc;
		f:	bfunc;
		limit:	integer
	): integer;
    var
	xxx:	integer;

    procedure recurse (var x: bfunc);
	var
	    i,j,ii,jj,m,tt:	integer;
	    any:	boolean;
	begin
	any := false;
	{ }
	{   Find an entry to set
	{ }
	for i := 0 to twon-1 do if x[i] < 0 then if not any then
	    begin
	    any := true;
	    for j := 0 to twon-1 do
		begin
		{ Assert that x[i] = j }
		ii := i;
		jj := j;
		m := 0;			{ no implications yet }
		while x[ii] < 0 do
		    begin
		    x[ii] := jj;	{ assert that x[ii] = jj }
		    jj := f[ii];	{ and assert that x[jj] = f[ii] }
		    ii := x[ii];	{ next time through the loop }
		    m := m + 1;
		    end;
		if x[ii] = jj then	{ if no contradiction }
		    recurse (x);
		ii := i;
		jj := j;
		while m > 0 do
		    begin
		    tt := x[ii];	{ fetch as a temporary }
		    x[ii] := -1;
		    jj := f[ii];
		    ii := tt;
		    m := m - 1;
		    end;
		end;
	    end;
	if not any then
	    begin
	    if xxx < limit then
		begin
		dump_bfunc (twon, x);
		writeln;
		end;
	    xxx := xxx + 1;
	    end;
	end;

    begin

    for xxx := 0 to twon-1 do x[xxx] := -1;
    xxx := 0;
    recurse (x);
    sqrt_x := xxx;

    end;

procedure main;
    var
	i,twon:	integer;
	x,f:	bfunc;
    begin
    while init (twon, f) do
	begin
	i := sqrt_x (twon, x, f, 50);
	dump_bfunc (twon, f);
	writeln (' has ', i:0, ' square roots ***');
	end;
    end;

begin
main;
end.

  Thank you (extensively) !

I've tried this program and it seems to run flawlessly.  Oh, how I wish
I could program that quickly and effectively !

re .5

	The following demonstrates that some sets of functions don't
	have square roots.  It does this by demonstrating two square
    	roots for a single set of functions.

	Note .5 showed this for functions of a single variable.

	Let
	    f (x , x , ... , x ) = x .
	     i  1   2         n     i

	Then the set of functions has (at least) 4 square roots, viz:

	    g (x , x , ... , x ) = x ,
	     i  1   2         n     i

	    g (x , x , ... , x ) = not x ,
	     i  1   2         n         i

	    g (x , x , ... , x ) = x     ,
	     i  1   2         n     n+1-i
	and
	    g (x , x , ... , x ) = not x     .
	     i  1   2         n         n+1-i


	Here's a question -- how many square roots does the set of identity
	functions (the f's above) have?  What is the general formula?
	The program in .8 gives:

		 n	# of square roots
		 1	     1
		 2	     2
		 3	     4
		 4	    10
		 5	    26
		 6	    76
		 7	   232
		 8	   764
		 9	  2620
		10	  9496
		11	 35696
		12	140152
		13	568504

None of the replies have addressed the rest of the problem in .0:

>                       What is really wanted is a way to split f into a pair
>of identical g's, but the outputs from the first g stage can be PERMUTED
>in passing to the second stage.

re .11:

The restricted procedure generated so many roots for some of
the functions that I was interested in that I thought it might be beneficial
to see if any of roots were easily reduced to simpler functions than
the original Boolean function before enlarging the number of possibilities
combinatorially ! (pardon the length of that last sentence).

Some interesting observations:
Z = X + 1 has 0 roots
Z = X + 2, Z = X + 4, ... have monotonically increasing numbers of roots.

Note: Z is the decimal interpretation of bit vector Z and X is the decimal
interpretation of bit vector X.

I have been dragged off this problem temporarily, but I will take a
shot at the second part sometime soon.

There are yet two other parts:
(1) The reduction of the boolean g vector function generated by SQX to minimal
realisations.  But that's a standard problem and I'm sure there are scads of
algorithms around to do it (Socrates can probably do this).
(2) The evaluation of the reduced g realisation against some criterion of
maximum path delay.  This requires specific knowledge of the implementation
technology (AUTODLY maybe ?).

One more brief qualitative observation:

I've tried hand reducing several of the candidate g functions
(individually, not sharing terms) and the results are somewhat
disappointing.  All of the ones examined have equal or greater
'complexity' than the original boolean function.

By 'complexity' I mean my seat of the pants estimate of the
worst case path length from any gate input to any network output.
In other words, g seems to require more gates and longer path
lengths than Z.

A proviso: I only did a few and I haven't tried reducing with
shared terms, so I wouldn't necessarily rule out possibilities for
this method yet.

Nonetheless, I wonder if there is some kind of a 'general systems'
theorem at work here.  Maybe something like:

'Breaking things up introduces additional overhead or the parts
sum up to more than the whole.'

Just for fun, I'm going to post a pointer to the hand procedure and
Mr. Gilbert's Pascal in the Prolog conference to see if someone can generate
a really compact elegant implementation.

Afterthought: by 'g' I mean the boolean vector square root of the original
function Z.  I hope the change in terminology didn't confuse anybody.

PROBLEM STATEMENT.  Given f = (f1, f2, ..., fn), find a g = (g1, g2,
..., gn) such that g*g = f.  Each fi, and gi are functions of n
boolean variables.  Operator "*" means composition.  g will be called
a square root of f.

It is not clear if one can provide a general closed form solution
when f is arbitrary.  However, we do have a solution when we
restrict f to a class of functions, to be defined later.  First,
however, we need some properties of permutaions.

Every permutation can be expressed as compositions of cycles.  A
permutation (cycle) Q is called a "square-root permutation (cycle)"
of P if Q*Q = P.  That is to say, composition of two Q's produces
P.  Composition of cycles is commutative.  Length of a cycle is the
number of elements in it.

LEMMA1.  If C = (c  c  c  ....   c  ) is a cycle of ODD length m, then
		  0  1  2         m-1
the square-root cycle of C also has the length m, and is given by,

	(c   c   c     .....  c   )  where  k = ceiling(m/2).
	  0   k  (2k)mod m    (jk)mod m


LEMMA2.  No cycle of even length has a square-root cycle.

LEMMA3.  A composition of two cycles (c11 c12 c13 ...  c1n) and
(c21 c22 c23 ...  c2n) with equal lengths and no common elements
has the square-root cycle (c11 c21 c12 c22 c13 c23 ....  c1n c2n).


From the above lemmas, we can show:

THEOREM1.  A permutation P has a square-root permutation if and only
if either of the following is true:
	(a) every cycle in P is odd
	(b) number of even cycles of equal lengths are even.


Now, we return to the original square-root function problem.

DEFINITION.  A set of n functions {g1, g2, ..., gn} is called a
"basis set" of all n-variable functions iff any h(x1,x2,...,xn) can
be synthesized starting from the gi's, by using a collection of
complete primitives (eg., NAND).

LEMMA4:  A set {g1, g2, ..., gn} is a basis iff the implied mapping
(x1,x2,...,xn) |---> (g1,g2,...,gn) is 1-1 and onto defined on the
2^n points of the n-cube.

For our purpose, we view the mapping in lemma4 as a permutation.
Theorem1 and lemma4 together solve the original problem of
square-root function when the components f1, f2, f3, ..., fn of f
are restricted to form a basis set.

ALGORITHM1:  Given a f = (f1,f2,...,fn) where the fi's form a
basis, the square-root of f can be found in the following way:

	(1) Let f be the 1-1 mapping from (x1,...,xn)  --> (f1,...,fn)
	    and let P be the permutation defined by f.  If P satisfies
	    theorem1, then apply step2.  Otherwise, there is NO
	    square-root function of f.

	(2) Obtain the square-root permutation Q of P by using Lemmas
	    1 and 3.  Q defines the 1-1 mapping (x1,...,xn)  ---->
	    (g1,...,gn).  The set of gi's so obtained defines the
	    square-root g for f.


EXAMPLE1:  Lets take f1 = x1 xor x2 xor x1x2 xor x2x3 xor x3x1,
		     f2 = x2 xor x3 xor x1x2 xor x2x3 xor x3x1,
		     f3 = 1 xor x2 xor x3x1.

Then, f = (f1,f2,f3) defines the 1-1 mapping,

     (x1,x2,x3) (f1,f2,f3)
	--------------------------
	(000)	(001)
	(001)   (011)	f1 = x1'x2x3' + x1x2'x3' + x1x2x3' + x1x2x3
	(010)	(110)	f2 = x1'x2'x3 + x1'x2x3' + x1'x2x3 + x1x2x3
	(011)	(010)	f3 = x1'x2'x3'+ x1'x2'x3 + x1x2'x3'+ x1x2x3
	(100)	(101)
	(101)	(000)
	(110)	(100)
	(111)	(111)

Converting 3-tuples to decimals, the map f can be viewed as a
permutation, P = (0 1 3 2 6 4 5)*(7).  P is a composition of
cycles of length 7 and 1.

The square-root permutation by using Lemma1,
	Q = (0 6 1 4 3 5 2)* (7).

Permutation Q defines (x1,x2,x3) --> (g1,g2,g3) as follows,

	(x1,x2,x3)	(g1,g2,g3)
	--------------------------
	(000)		(110)
	(001)		(100)
	(010)		(000)
	(011)		(101)
	(100)		(011)
	(101)		(010)
	(110)		(001)
	(111)		(111).

Expressing gi's in terms of xi's, we get,

	g1 = x1'x2' + x2x3, g2 = x2'x3' + x1x3, g3 = x2x3 + x1x3'.

Hence, g1(g1,g2,g3) = g1'g2' + g2g3
		    = x1'x2x3' + x1x2'x3' + x1x2x3' + x1x2x3
		    = f1.

Similarly, one can verify, g2(g1,g2,g3) = f2, and g3(g1,g2,g3) = f3.


EXTENSIONS
----------

While looking at the original square-root problem, it occurs that
our approach could be used for finding "r-th-root" g of f such that

	(g*g*....g) = f.
	 r-times.

The machinery to do so hinges on finding a r-th root of a cycle in
a way similar to finding a square-root of a cycle.  The results for
the r-th-root cycle are not reported here.

	Snehamay Kundu	(HPSRAD::KUNDU)
	Yu Wang		(HPSCAD::WANG)
	26-Feb-1988.

>From the above lemmas, we can show:
>
>THEOREM1.  A permutation P has a square-root permutation if and only
>if either of the following is true:
>	(a) every cycle in P is odd
>	(b) number of even cycles of equal lengths are even.

Note that (a) => (b), so (a) v (b) = (b); thus condition (b) is necessary 
and sufficient.