# Finding conjunctive normal form of a Boolean polynomial

I have to find the conjunctive normal form of the following Boolean Polynomial :

$(x_1+x_2+x_3)(x_1x_2+x_1'x_3)'$

I simplified this polynomial to get $x_1x_2'+x_1x_2x_3'$ for which i then formed the truth table and got the conjunctive normal form to be,

$(x_1+x_2+x_3)(x_1+x_2+x_3')(x_1+x_2'+x_3)(x_1+x_2'+x_3')(x_1'+x_2'+x_3')$

I just want to make sure that i am doing these problems correctly,so could someone please check my answer.

• Your CNF looks correct to me. I haven't generated the truth table myself to check all the cases, but the ones you picked are all maxterms. – ml0105 May 2 '14 at 13:51

For two of the eight possible cases, the original expression and your solution are different:

For $x_1' x_2 x_3'$, the original results in true while your solution yields false.

For $x_1 x_2 x_3'$ you are getting true instead of false.

WolframAlpha gives you a rather compact CNF:

$$(x_1' + x_2')(x_1 + x_2)(x_1 + x_3')$$

This minimized product-of-sums is not unique. An equivalent solution would be:

$$(x_1' + x_2')(x_1 + x_2)(x_2' + x_3')$$

Hint: To compare two expressions you can enter them in WolframAlpha separated by comma. This allows for a direct comparison of the truth tables. Another option would be to write an xor of the two expressions and look for lines with true (indicating different expressions).