Disjunctive Normal Form with Minimum variables

Question

I am trying reduce this DNF function to minimal variables. $f(a,b,c,d)=(ac’+c)(a’bc+d’)+(cd’+b)(cd’+c)+abd’+abc’d$

I have reduced to $ac'd+bc+cd'+abc'$ but I know it can be reduced down to $ab +ad'+bc+ cd'$

I am stuck and don't know where to continue from to get final solution.

Answer 1

Actually, you can't reduce it to $ab + ad' + bc + cd'$. Take $a = 1, b = c = d = 0$. Your reduced expression equals $0$, while that expression equals $1$ (because of the $ad'$ term).

However, using the absorption law $A + AB = A$ you can reduce it a little: $$ac'd + bc + cd' + abc' = ac'd + cd' + (bc + abc) + abc'$$ $$= ac'd + cd' + bc + ab(c+c') = ac'd + cd' + bc + ab.$$

Updated: I think you've made a mistake while reducing $f(a, b, c, d)$. Using absorption, complementation $A = xA + x'A$ and $x + x'y = x + y$ we have $$(ac'+c)(a'bc+d') + (cd'+b)(cd'+c) + abd' + abc'd = ac'd' + a'bc + cd' + bc + abd' +abc'd = ac'd' + cd' + bc + abcd' + abc'd' + abc'd = ac'd' + cd' + bc + abc'd = ac'd' + cd' + b(c + ac'd) = ac'd' + cd' + b(c+ad) = ac'd' + cd' + bc + abd = (ac' + c)d' + bc + abd = (a + c)d' + bc + abd = ad' + cd' + bc + abd = cd' + bc + a(d' + bd) = cd' + bc + a(d' + b) = ab + ad' + bc + cd'.$$

So this minimal form is correct, but you can't obtain it from your reduced expression since you've made a mistake.

Answer 2

I do not have enough rep to comment, but I would suggest trying Shannon cofactor expansion because this is a relatively small Boolean function (only $2^{4}=$16 possible assignments). You essentially break up the function into two separate pieces (recursively). For example,

$f_{1}=f(1,b,c,d)$

$f_{0}=f(0,b,c,d)$

$f_{10}=f(1,0,c,d)$

$f_{11}=f(1,1,c,d)$ . . .

you can work this out (in any order, it is not necessary to start with a, in your case I think starting with c would be best) and then see what settings of variables force he function to be true/false and make those your new clauses... For more straight forward minimization rules you can check out http://www.allaboutcircuits.com/textbook/digital/chpt-7/boolean-rules-for-simplification/ This is what I used in my computer architecture class for similar problems.

(I will take this down in a few minutes) Hope this helps.