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.

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

share|improve this question
4  
Subject to what constraints? –  Qiaochu Yuan May 17 '11 at 12:29
1  
What do you mean by a boolean function? –  AD. May 17 '11 at 12:49
    
Ah... so your only possible values for the $x_i$ are 0 and 1 then? –  J. M. May 17 '11 at 13:16
    
@J. M.: Might be, but then the problem went away... poof! –  AD. May 17 '11 at 14:15

3 Answers 3

up vote 0 down vote accepted

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.

share|improve this answer

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}$$

share|improve this answer

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.

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.