Minimize Boolean function

Question

I have got some silly task, but I am quite confused.

Need to minimize function.

$$f(x_1,x_2,x_3,x_4)=x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4.$$

Thanks.

Sorry for my English. Minimize Boolean function

Ah... so your only possible values for the $x_i$ are 0 and 1 then? — J. M. ain't a mathematician, May 17 '11 at 13:16
this is NP hard with constraints... otherwise every variables is zero. — D. Sikilai, Jul 08 '22 at 12:30

score 0 · Answer 1 · answered May 17 '11 at 12:43

Do you mean to reduce the form? i.e. something like $$ \begin{eqnarray} f(x_1,x_2,x_3,x_4) &=& x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4 \nonumber \\ &=& x_1(x_2+x_3+x_4)+x_2(x_3+x_4) \nonumber \\ &=& x_1x_2+(x_1+x_2)(x_3+x_4) \end{eqnarray}$$

score 0 · Answer 2 · answered May 17 '11 at 12:51

0

Type $$\rm minimize\ boolean$$ into a search engine and you'll be directed to lots of webpages that may help. Another keyphrase is $$\rm Karnaugh\ map$$ This will lead you to http://en.wikipedia.org/wiki/Karnaugh_map among other places.

answered May 17 '11 at 12:51

Gerry Myerson

179,216

score 0 · Accepted Answer · answered May 31 '11 at 00:01

If I understand the notation here correctly, a Karnaugh map looks something like this:

        x1x2  x1|x2  |x1|x2  |x1x2

x3x4     X      X              X
|x3x4    X      X              X
|x3|x4   X
x3|x4    X      X              X

where |xn indicates the negation of xn, and xnxm indicates the conjunction of xn and xm, and the X's represent where and only where such a conjunction evaluates to "1" (e. g. with the "X" at the intersection of x1x2 and x3x4, we have "x1x2x3x4" evaluating to "1"). If you want a minimal disjunctive normal form, you already have the unique disjunctive normal form right there, there doesn't exist anything to minimize, unless I've made a mistake here.

Minimize Boolean function

3 Answers3