Karnaugh map is a method to simplify Boolean algebra expressions in two different notations sum-of-products(DNF) and product-of-sums(CNF). I need to find a minimized boolean expression in algebraic normal form (ANF) for a truth table. Is there a solution?
A solution is simplifying the boolean algebra expression in CNF or DNF then converting it to ANF. But is it minimized?
Is there a software to convert CNF boolean algebra expressions to 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)
