Boolean Expansion as Linear Interpolation

Given a set of n independent logical variables X1,X2,...,Xn, each of
which may be either TRUE or FALSE, let xj = P{Xj} denote the probability
that Xj is TRUE.  Consequently 1 - xj is the probability that Xj is 
FALSE.

Now consider some arbitrary Boolean function F(X1,X2,..,Xn) of these 
n logical vairables.  Thus for any specified truth values of the n
variables the function f is assigned a particular value, either TRUE 
or FALSE.  In his "Investigation of the Laws of Thought" George Boole
described (Chapter V, Prop II) how the probability f of the function F
can be expanded into its mutually exclusive components.  This expansion
is just an application of the conditional probability formula for an
arbitrary event E and logical variable X

               P{E}  =  P{E|X} P{X}  +  P{E|X'} P{X'}

where X' denotes "not X", and the vertical line "|" signifies "given".
Applying this repeatedly to the event F and the logical variables Xj
gives the expansion formula


 f(X1,X2,..,Xn)

       1     1        1    /                 n                      \
    = SUM   SUM  ... SUM  ( f(i1,i2,..,in) PROD[(1-ij)xj + ij(1-xj)] )
      i1=0  i2=0     in=0  \                j=1                     /


where the indices ij, j=1,2,..,n signify truth values (0=FALSE,1=TRUE).
Also, recall that f is the probability of F being TRUE.

For example, we can expand the function F in terms of two independent
logical variables X and Y, whose probabilities of being TRUE are x
and y respectively, as follows

     f(X,Y) = f(0,0) [1-x][1-y] + f(0,1) [1-x][y]

                   + f(1,0) [x][1-y]  +  f(1,1) [x][y]

It's interesting that the general formula for Boolean decomposition of
probabilities in terms of n independent variables is identical to the 
formula for n-dimensional orthogonal linear interpolation.  Suppose we
have an orthogonal n-dimensional table that specifies the value of a 
scalar field f(x1,x2,..,xn) at discrete points.  To interpolate the
value of f at some specific point in this n-dimensional space using
linear interpolation, we need to first find the particular "cell" of
the table where the point falls.  Once we have done this, we can
normalize the spatial coordinates along each axis such that the next
lower table ordinate is 0 and the next higher table ordinate is 1.
Then the values of f(i1,i2,..,in) in the above general formula for
the Boolean expansion represent the discrete table values at the 2^n
vertices of the relevant "cell" of the table, and the values of xj
for j=1 to n are the spatial coordinates of the particular point 
inside the cell that is to be interpolated.

The correspondence between interpolation in a Euclidean space and
the expansion of the probabilities of logical functions suggests some
interesting approaches to dealing with more challenging situations in 
which the logical variables are NOT independent.  We can express these 
in terms of the non-independence of a putative set of "basis vectors" 
for the space.  However, it's important to keep in mind that the 
general locus given by n-dimensional linear interpolation actually
possesses intrinsic curvature, and isn't linear with respect to 
arbitrary independent basis vectors.  For a discussion of this
intrinsic curvature, see Curvature of Linear Interpolation.

Return to MathPages Main Menu