DNF minimization

From a table of values for a Boolean function one can immediately get a DNF representation just by listing cases where the value is 1. For one step in rule 30, for example, this yields {{1, 0, 0}, {0, 1, 1}, {0, 1, 0}, {0, 0, 1}}, as shown on page 616. One can think of this as specifying corners that should be colored on an n-dimensional Boolean hypercube. To reduce the representation, one must introduce "don't care" elements _; in this example the final minimal form consists of the list of 3 so-called implicants {{1, 0, 0}, {0, 1, _}, {0, _, 1}}. In general, an implicant with m _'s can be thought of as corresponding to an m-dimensional hyperplane on the Boolean hypercube. The problem of minimization is then to find the minimal set of hyperplanes that will cover the corners for a particular Boolean function. The first step is to work out so-called prime implicants corresponding to hyperplanes that cannot be contained in higher-dimensional ones. Given an original DNF list s, this can be done using PI[s, n]:

PI[s_, n_] := Union[Flatten[FixedPointList[f[Last[#], n] &, {{}, s}]〚All, 1〛, 1]]

g[a_, b_] := With[{i = Position[Transpose[{a, b}], {0,1}]}, If[Length[i]  1 && Delete[a, i] === Delete[b, i], {ReplacePart[a, _, i]}, {}]]

f[s_, n_] := With[{w = Flatten[Apply[Outer[g, #1, #2, 1] &, Partition[Table[Select[s, Count[#, 1]  i &], {i, 0, n}], 2, 1], {1}], 3]}, {Complement[s, w, SameTest  MatchQ], w}]

The minimal DNF then consists of a collection of these prime implicants. Sometimes it is all of them, but increasingly often when n ≥ 3 it is only some. (For example, in {{0, 0, _}, {0, _, 1}, {_, 0, 0}} the first prime implicant is covered by the others, and can therefore be dropped.) Given the original list s and the complete prime implicant list p the so-called Quine–McCluskey procedure can be used to find a minimal list of prime implicants, and thus a minimal DNF:

QM[s_, p_] := First[Sort[Map[p〚#〛 &, h[{}, Range[Length[s]], Outer[MatchQ, s, p, 1]]]]]

h[i_, r_, t_] := Flatten[Map[h[Join[i, r〚#〛], Drop[r, #],Delete[Drop[t, {}, #], Position[t〚All, #〛], {True}]]] &, First[Sort[Position[#, True] &, t]]]], 1]

h[i_, _, {}] := {i}

The number of steps required in this procedure can increase exponentially with the length of p. Other procedures work slightly more efficiently, but in general the problem of finding the minimal DNF for a Boolean function of n variables is NP-complete (see page 768) and is thus expected to grow in difficulty faster than any polynomial in n. In practice, however, cases up to about n = 12 are nevertheless currently handled quite routinely.