Solving ANF equations

Question

Can anyone suggest a method of solving a system of boolean equations in ANF form? Boolean equations in ANF form (Algebraic Normal Form ) are equations of the form of xor of products of boolean variables. For example (($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$)$)=1$

Answer 1

It's impossible. ANF uses functions like $f:\{0,1\}\times \{0,1\} \to \{0,1\}$, and this has the effect of destroying information, i.e. the function doesn't have an inverse, so an algebraic solution is impossible. Use truth tables instead.

Answer 2

What about one variable at a time?

Let Z be your equation in ANF form, made up of variables A,B,C, etc.

Now convert Z AND A back into ANF form. If you end up with the same equation as Z then A must be true. Otherwise try converting Z AND NOT A into ANF to see if A is false.

Lets try your example:

let Z = (($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$))

lets try (Z and $x_1$) first

(Z and $x_1$) = (($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$)) and $x_1$

(Z and $x_1$) = ($x_1$ and $x_2$) xor ($x_1$ and $x_2$ and $x_3$) xor ($x_1$ and $x_3$)

(Z and $x_1$) does not equal Z, so $x_1$ could either be false or have more than one solution.

now lets try (Z and not $x_1$)

(Z and not $x_1$) = (($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$)) and (not $x_1$)

(Z and not $x_1$) = (($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$)) and (true xor $x_1$)

(Z and not $x_1$) = ($x_1$ and $x_2$) xor ($x_2$ and $x_3$) xor ($x_1$ and $x_3$) xor ($x_1$ and $x_2$) xor ($x_1$ and $x_2$ and $x_3$) xor ($x_1$ and $x_3$)

(Z and not $x_1$) = ($x_2$ and $x_3$) xor ($x_1$ and $x_2$ and $x_3$)

(Z and not $x_1$) also does not equal Z. So it is likely there is more than 1 solution if there are any solutions. So to grab just one possible solution, pick any value for $x_1$ and simplify.

lets try $x_1$ = false

Z = ((false and $x_2$) xor ($x_2$ and $x_3$) xor (false and $x_3$))

Z = false xor ($x_2$ and $x_3$) xor false

Z = $x_2$ and $x_3$

leading to $x_2$ = true and $x_3$ = true, if $x_1$ = false

so ($x_1$, $x_2$, $x_3$) = (false, true, true) is one possible solution. And by backtracking and choosing a different substitution for $x_1$ you can get the other solution(s).

Now let $x_1$ = true to grab the other solutions.

Z = ((true and $x_2$) xor ($x_2$ and $x_3$) xor (true and $x_3$))

Z = $x_2$ xor ($x_2$ and $x_3$) xor $x_3$

Z = $x_2$ xor $x_3$ xor ($x_2$ and $x_3$)

Z = $x_2$ or $x_3$

leading to ($x_2$,$x_3$) = (false,true), (true,false) or (true,true), if $x_1$ = true.

So all the solutions to ($x_1$, $x_2$, $x_3$) are (false, true, true), (true, false, true), (true, true, false) and (true, true, true).