Abstract:
Multiaffine, bijunctive ($2$-CNF), weakly positive and weakly negative (Horn's) Boolean functions generates polynomially solvable systems of equations. These sets of Boolean functions are called the Schaefer classes. We describe sets of Boolean functions $f$ from any Schaefer class such that $f$ belongs to another Schaefer class. The results obtained may be applied to the solution of systems of Boolean equations.
Key words:multiaffine Boolean functions, $2$-CNF, Horn's Boolean functions, systems of Boolean equations.