Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Why is this tagged linear algebra? –  Doug Spoonwood Feb 14 '12 at 21:53
2  
@Doug: Probably because the ANF can be understood by viewing the set of Boolean functions of $n$ variables as a vector space over $\mathbb F_2$ considering the basis consisting of all conjunctions of (not negated) variables. –  Henning Makholm Feb 15 '12 at 1:11

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.