Characterization of Linearly Separable Boolean Functions: A Graph-Theoretic Perspective

In this paper, we present a novel approach for studying Boolean function in a graph-theoretic perspective. In particular, we first transform a Boolean function $f$ of $n$ variables into an induced subgraph $H_{f}$ of the $n$ -dimensional hypercube, and then, we show the properties of linearly separable Boolean functions on the basis of the analysis of the structure of $H_{f}$ . We define a new class of graphs, called hyperstar, and prove that the induced subgraph $H_{f}$ of any linearly separable Boolean function $f$ is a hyperstar. The proposal of hyperstar helps us uncover a number of fundamental properties of linearly separable Boolean functions in this paper.