# 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}