On quadratic Boolean equations (Q1920323): Difference between revisions

Let \(F(x_1, \dots, x_n)\) be a Boolean function and \(F\) a disjunction of terms of the form \(xy\) (i.e. \(F\) is a quadratic truth function). The author presents an algorithm for the solution of the quadratic Boolean equation \(F(x_1, \dots, x_n) = 0\). In a first step a prime-implicant approach is used which determines all possible unknowns \(x_i\) and \(x_j\) such that \(x_i = 0\) and \(x_j = 1\) in every solution, as well as all possible couples of unknowns \(x_h\), \(x_k\) and \(x_r\), \(x_s\) such that \(x_h = x_k\) and \(x_r = \neg x_s\) in every solution. After all these reductions have been performed, the remainder equation, if any, is solved in a second step by a process which yields all families (or hyperplanes) of solutions.