The Nice Properties of a New Boolean Function

\begin{abstract} We work in $B^n$ and consider sets of $2^m$ points, $m \leq n$, represented in binary {\em balanced} matrices, whose columns contain half 0's and half 1's, and this property repeats recursively in proper submatrices. We introduce the concept of {\em pseudo-cube} of order $m$, that is a subset of $2^m$ points of $B^n$ whose matrix is balanced. A subcube $B^m \subseteq B^n$ is a special case of pseudo-cube and shares most of its properties. For a given pseudo-cube $P$ we define the class ${\cal P}(P)$ of the pseudo-cubes obtained from $P$ by complementing any subset of variables, and show that the elements of ${\cal P}(P)$ are disjoint and tessellate $B^n$. Furthermore, the union of any two pseudo-cube of the same class ${\cal P}$ is a pseudo-cube, and the intersection of two arbitrary pseudo-cubes is either empty or is a pseudo-cube. We then introduce {\em pseudo-products} as Boolean functions that have value 1 in the points of a pseudo-cube $P$. These functions inherit all the properties of pseudo-cubes, and have a compact expression EXP($P$). Given two pseudo-products $P_1$, $P_2$ belonging to the same class $\cal P$, we give an algorithm to construct in linear time the expression of the union EXP($P_1 \cup P_2$) from EXP($P_1$) and EXP($P_2$). Finally we show how a standard procedure to generate a minimal "sum of products" form for a Boolean function $f$ can be extended to generate a minimal "sum of pseudo-products" for $f$. This latter form, based on the representation EXP, is generally much shorter than the corresponding Boolean form. \end{abstract}