Product form parametric representation of the solutions to a quadratic boolean equation

A parametric representation of the solutions to a consistent quadratic boolean equation in n variables is obtained. Each variable (or its complement) is expressed as a product of free boolean parameters or their complements. These expressions provide a complete description of the solution set of the equation. An O(n³) algorithm is proposed to produce such a representation. An application to the maximization of some classes of pseudoboolean functions is discussed.