Finding Boolean/Logical Expressions for truth tables in algebraic normal form(ANF)

As Henning Makholm pointed out, the ANF is unique. I will illustrate how you determine the ANF given the truth table for the function for the case of three variables.

The ANF of $f(x_1,x_2,x_3)$ is $$\begin{align*} f(x_1,x_2,x_3) &= a_0\\ &\quad \oplus a_1x_1 \oplus a_2x_2 \oplus a_3x_3\\ &\quad \oplus a_{12}x_1x_2 \oplus a_{13}x_1x_3 \oplus a_{23}x_2x_3\\ &\quad \oplus a_{123}x_1x_2x_3 \end{align*}$$ and we need to determine the $a$'s. We proceed as follows (working exactly in reverse order of the method outlined by Henning) by determining $a_{123}$, the coefficient of highest degree term, first and working our way downwards.

• $a_{123}$ equals the parity of the Hamming weight of the function. That is, $a_{123}=1$ if the column labeled $f$ in the truth table has an odd number of $1$s in it, and $a_{123}=0$ if the column labeled $f$ in the truth table has an even number of $1$s in it.

• We obtain $a_{12}$ by considering the four rows corresponding to $x_3=0$ as the truth table of a function $$\begin{align*}f_{12}(x_1,x_2) &= f(x_1,x_2,0)\\ &= a_0\\ &\quad \oplus a_1x_1 \oplus a_2x_2\\ &\quad \oplus a_{12}x_1x_2 \end{align*}$$ and applying the same technique as in the previous step. $a_{12}$ is the parity of the Hamming weight of the column labeled $f_{12}$ in this shorter truth table.

• Similarly, we obtain $a_{13}$ and $a_{23}$ by considering truth tables for $f_{13}(x_1,x_3) = f(x_1,0,x_3)$ and $f_{23}(x_2,x_3) = f(0,x_2,x_3)$ respectively and finding the parity of the Hamming weights of the reduced functions.

• Similarly, we obtain $a_{1}$, $a_{2}$, and $a_3$ by considering truth tables for $f_{1}(x_1) = f(x_1,0,0)$,
  $f_{2}(x_2) = f(0,x_2,0)$, and $f_{3}(x_3) = f(0,0,x_3)$ respectively and finding the parity of the Hamming weights of the reduced functions

• Finally, $a_0 = f(0,0,0)$ can be just read off the truth table.

It is, of course possible to proceed in opposite order, but the method outlined above is related to Reed-Muller decoding for which you might find software available. Look also for canonical ring sum expansion.

The algebraic normal form is unique (which follows from a simple counting argument), so minimality is not an issue.

You can construct an ANF directly from a truth table by finding the coefficients for the terms of low degree first. The constant coefficient is just the value in the 000..0 line in the truth table, and once you know what that is you can find the coefficients for all of the lines with a single 1, and so forth until everything is filled out.

Mathematica command :

BooleanConvert[expr,form] converts the Boolean expression expr to the specified form.

For example :

input : BooleanConvert[(! x || y) && (x || ! y), "ANF"]

output : ! (x $\veebar$ y)