"The poet only asks to get his head into the heavens. It is the logician who seeks to get the heavens into his head. And it is his head that splits." G.K. Chesterton

Wednesday, August 27, 2014

Explicit solution (formula) to the "truth table" recurrence relation.

If anyone has done any introductory logic, or has been introduced to representing sets in terms of their characteristic function, then the following binary matrix will look familiar. Each row is a distinct combination of the elements of some set. This is the matrix for a three element set. Call it matrix A.

1 1 1 ...
0 1 1
1 0 1
0 0 1
1 1 0
0 1 0
1 0 0
0 0 0

Some of the most common applications/interpretations of this matrix are:

i) For any natural number N (of columns), the rows of the matrix (of which there is 2N) represent the set of all functions N→{0,1}., were N is a finite subset of the Natural numbers.

ii) The rows of a table thus generated, exhaust all truth value assignments to a propositional variable appearing in a formula of Propositional Calculus.

iii) Equivalently each row can be interpreted as the image of the characteristic function of a power set of some set S (we don't need to assume the axiom of countable choice since here we're dealing with finite sets). In other words each row of the matrix corresponds to a distinct combination of the elements of S. In fact the map : (S)→ ROWS (of the matrix) is a bijection: f(X)=r iff r(i)=1 iff i∈X, where we identify the matrix column indecies with the wellordering of the elements of S.

So clearly this matrix is a big deal, and subsequently the result here is an important one, since it basically compresses the entire matrix to a simple function of its rows and columns.

The way to generate the matrix in a way to ensure that all combinations are exhausted, is to follow the obvious pattern for column generation --- single iteration, double iteration, quadruple iteration, etc. In general, each column i has a 2i-1  iteration of 1's and 0's (starting with 1's in each column).

Below is the proof for the explicit formula of such matrices recurrence relations, i.e. as a function of the matrix'  row and column number. That is, given only the row and column numbers, the formula gives the value that appears in the matrix on those 'coordinates'. That is, the formula takes the following functional form:

                                                                       θ : 2n×→ {0,1}

EXAMPLE: θ(k,i), where the row number is = 7 and column number is= 2, i.e. θ(7,2) = 0.
Now for the proof, which I have only given a sketch of in a previous post. Subsequently I lost the proof, and only had the formula, which bothered me, so I re-proved it last week. So here we go. Most of the pattern recognition which underlies the solution is obviously to be found in the matrix itself, and the diagram below intends to capture and make salient those patterns which may not be so obvious at first glance. The integer numbered columns, i.e. columns 1, 2, 3, 4,..., are the actual columns of the matrix A. 
To the right of each actual matrix column i, I list k(mod 2i), which is the first pattern that ought to be observed. Can you see how a single cycle of k(mod 2i) matches the length of the pair of iterated 1's and 0's, in column i? The next key observation, and perhaps the crucial one, is that the pattern of out actual matrix columns is basically a function of k(mod 2i). More precisely, note how each i'th actual column has the same pattern as k(mod 2i)k(mod 2i-1), with the exception of being slightly 'misaligned' and having some product of 2 in the place there 1's ought to be. I have indicated the k(mod 2i)k(mod 2i-1) rows with a yellow heading. Have a look for a while, and the pattern* should 'jump out'. Once you're convinced that it is so, all we need to do is (i) to rectify the 'misalignment', and (ii) the multiples of 2 integers instead of 1's. By noting that the 'misalignment' is also a function of column number, we see that adding 2i-11 to k, does the trick. Finally divide all values in each i'th column by 2i-1 and we're basically done. That is, our formula can be expressed as the function:
This formula is good enough and does the trick, but using the identity below, relating the mod and floor functions, it can make it more concise.
Giving the formula its final form. I guess it could be rendered even more concise and elegant with further algebraic fiddling, but I shall leave it there.

*Admittedly, a more rigorous proof is required than merely conjecturing that this pattern ought to hold in general. I may get around to it soon. But it does seem obvious that the proof is correct, since no surprises will arise in the relationship of the values of k(mod 2i) and k(mod 2i-1as both k and i increase.

If we switch the order of 1's and 0's in the table, i.e. if we let 0's precede 1's, like so (call this matrix B):

Then the same reasoning yields a more elegant formula:

No comments: