Description of the package "boolmin.m"

How to use the package "boolmin.m"

The package "boolmin.m" needs the package "boolean.m" from Charles Wells.

Step 1: Copy the files "boolmin.nb", "boolmin.m" and "boolean.m" in your favourite directory (lets say <directory>) for packages. Here <directory> stands for an arbitrary path. The path should be in the list $Path.

If <directory> is not in $Path, append <directory> to the list $Path with the command

$Path=Append[$Path, "<directory>"]

Or you could overwrite the source code of "boolmin.nb" as follows:
Search the command

<< boolean`

in "boolmin.nb" and subsitute it by the command

<< "<directory>\boolean.m"

Of course after that you have to save "boolmin.nb". The corresponding file "boolmin.m" is modified automaticly.

Step 2: Load the package "boolmin.m" with the command:

<< boolmin`

Or if  <directory> is not in $Path with the command

<< "<directory>\boolmin.m"

Specification of the implemented functions

Basic definitions

A boolean expression p is called a SOP-expression (Sum-Of-Products-expression), if p = False or if p has the form p = (Subscript[p, 1]) || (Subscript[p, 2]) ||  ...  || (Subscript[p, m]), where all (Subscript[p, i]) (i ∈ {1,  ... , m}) are product expressions. The (Subscript[p, i]) are called terms of p.

A boolean expression p is called a product expression, iff p = True or p has the form p = (Subscript[l, 1]) && (Subscript[l, 2]) &&  ...  && (Subscript[l, k]), where all (Subscript[l, i]) (i ∈ {1,  ... , k}) are literals. In addition we demand that (Subscript[l, i]) ≠ 
        (Subscript[l, j])  and  (Subscript[l, i]) ≠ ! (Subscript[l, j]) for i ≠ j.

A boolean expression p is called a literal, iff p is an atomic expression (such literals are called uncomplemented literals) or p = ! a, where a is an atomic expression (complemented literals).

Analogly we can define POS-expressions (Product-Of-Sums-expressions).

Let p be a boolean expression. If you reaplace simultaniously every occurence of " || " with "&&", every occurence of " && " with " || " and every complemented literal with the corresponding uncomplemented literal (and vice versa), you will obtain the dual boolean expression of p.

Let p = (Subscript[l, 1]) && (Subscript[l, 2]) &&  ...  && (Subscript[l, k]) and q = (Subscript[s, 1]) && (Subscript[s, 2]) &&  ...  && (Subscript[s, j]) be two product expressions, where the (Subscript[l, i]) and the (Subscript[s, j]) denote the literals of p respective q. If the set {(Subscript[l, 1]), (Subscript[l, 2]),  ... , (Subscript[l, k])} is a subset of {(Subscript[s, 1]), (Subscript[s, 2]),  ... , (Subscript[s, j])}, we say that p subsumes q.

If the boolean expression p logically implies the boolean expression q, we say that p is an implicant of q.

A product expression t is called a prime implicant of a boolean expression p, iff t is an implicant of p and t is not subsumed by another implicant of p.

A SOP-expression p is called irredundant, iff deleting any terms or literals leads to a SOP-expression, which is not aequivalent to p anymore.

Let p and q be SOP-expressions. We denote with (Subscript[t, p]) and (Subscript[t, q]) the number of terms of p respective q and with (Subscript[e, p]) and (Subscript[e, q]) the number of occurences of " && " in p respective q. Then p is simpler than q, iff

(Subscript[t, p]) < 
        (Subscript[t, q])  or  ((Subscript[t, p]) = (Subscript[t, q])  and  (Subscript[e, p]) < (Subscript[e, q])).

A SOP-expression p is called minimal, iff there is no simpler SOP-expression aequivalent to p.

Analog we can define irredundant and minimal for POS-expressions.

Let (Subscript[p, l]) and (Subscript[p, u]) be two boolean expressions such that (Subscript[p, l]) implies (Subscript[p, u]). Then we denote by I the set of all boolean expressions "between" (Subscript[p, l]) and (Subscript[p, u]):

I:={p | p is a boolean expression with ((Subscript[p, l]) implies p) and  (p implies (Subscript[p, u]))}

Then we call a SOP-expression p don´t-care-irredundant with respect to (Subscript[p, l]) and (Subscript[p, u]), iff deleting terms or literals from p leads to a SOP-expression, which is not in I anymore.

Specification of nice

Let p be a boolean expression, then nice[p] gives p in "nice" form (i.e. " || " is replaced by "+", " && " is replaced by "·" and "! " is replaced by "\(TraditionalForm\`□\&_\)"):

nice[(a || b) && (c || ! d) || ! a]

Specification of unnice

unnice[p] replaces "+" by " || ", "·" by " && " and "\(TraditionalForm\`□\&_\)" by "! ":

\(unnice[a\&_ + \((a + b)\)\ \((c + d\&_)\)]\)

Specification of dual

Let p be a boolean expression. Then dual[p] gives the dual boolean expression of p:

dual[! a || (a || 
              b) && (c || ! d)]

Specification of apiQuine

Let p be a SOP-expression. Then apiQuine[p] gives the conjunction of all prime implicants, which is computed by the Quine-McCluskey method:

\(apiQuine[
        x1\ x2\&_\ x3\&_\ x4\  + \ x1\&_\ x2\ x3\&_\ x4\  + 
            x1\ x2\&_\ x3\&_\ x4\&_\  + \ x1\&_\ x2\ x3\ x4\  + 
            x1\&_\ x2\&_\ x3\&_\ x4\&_\  + \ x1\ x2\ x3\ x4\  + \ 
            x1\ x2\&_\ x3\ x4\  + \ x1\&_\ x2\ x3\ x4\&_\  + 
            x1\&_\ x2\&_\ x3\ x4\  // unnice]\  // \ nice\)

Specification of apiReusch

Let p be a SOP-expression. Then apiReusch[p] gives the conjunction of all prime implicants, which is computed by the Reusch method:

\(apiReusch[
        x1\ x2\&_\ x3\&_\ x4\  + \ x1\&_\ x2\ x3\&_\ x4\  + 
            x1\ x2\&_\ x3\&_\ x4\&_\  + \ x1\&_\ x2\ x3\ x4\  + 
            x1\&_\ x2\&_\ x3\&_\ x4\&_\  + \ x1\ x2\ x3\ x4\  + \ 
            x1\ x2\&_\ x3\ x4\  + \ x1\&_\ x2\ x3\ x4\&_\  + 
            x1\&_\ x2\&_\ x3\ x4\  // unnice]\  // \ nice\)

Specification of apiConsensus

Let p be a SOP-expression. Then apiConsensus[p] gives the conjunction of all prime implicants, which is computed by the Consensus method:

\(apiConsensus[
        x1\ x2\&_\ x3\&_\ x4\  + \ x1\&_\ x2\ x3\&_\ x4\  + 
            x1\ x2\&_\ x3\&_\ x4\&_\  + \ x1\&_\ x2\ x3\ x4\  + 
            x1\&_\ x2\&_\ x3\&_\ x4\&_\  + \ x1\ x2\ x3\ x4\  + \ 
            x1\ x2\&_\ x3\ x4\  + \ x1\&_\ x2\ x3\ x4\&_\  + 
            x1\&_\ x2\&_\ x3\ x4\  // unnice]\  // \ nice\)

Specification of apiNelson

Let p be an arbitrary boolean expression. Then apiNelson[p] gives the conjunction of all prime implicants, which is computed by the method of direct multiplication:

\(apiNelson[
        x1\ x2\&_\ x3\&_\ x4\  + \ x1\&_\ x2\ x3\&_\ x4\  + 
            x1\ x2\&_\ x3\&_\ x4\&_\  + \ x1\&_\ x2\ x3\ x4\  + 
            x1\&_\ x2\&_\ x3\&_\ x4\&_\  + \ x1\ x2\ x3\ x4\  + \ 
            x1\ x2\&_\ x3\ x4\  + \ x1\&_\ x2\ x3\ x4\&_\  + 
            x1\&_\ x2\&_\ x3\ x4\  // unnice]\  // \ nice\)

Specification of amsReusch

Let PI(p) be the list or conjunction of all prime implicants of a boolean expression p. Let q be a SOP-expression aequivalent to p. Then amsReusch[PI(p), q] gives the list of all (of course just up to permutations of terms and literals) irredundant SOP-expressions which are aequivalent to p. This is done by the method of Reusch for finding all irredundant SOP-expression. All Boolean expressions can also be representet in a "nice" form.

\(amsReusch[
        x3\ x4 + x1\ x4\ x2\&_ + x1\ x2\&_\ x3\&_ + x2\ x3\ x1\&_ + 
          x2\ x4\ x1\&_ + x2\&_\ x3\&_\ x4\&_, 
        x1\ x2\&_\ x3\&_\ x4\  + x1\&_\ x2\ x3\&_\ x4\  + 
          x1\ x2\&_\ x3\&_\ x4\&_\  + \ x1\&_\ x2\ x3\ x4\  + 
          x1\&_\ x2\&_\ x3\&_\ x4\&_\  + \ x1\ x2\ x3\ x4\  + \ 
          x1\ x2\&_\ x3\ x4\  + \ x1\&_\ x2\ x3\ x4\&_\  + 
          x1\&_\ x2\&_\ x3\ x4\ ]\  // \ nice\)

Specification of minDisForm

Let p be a boolean expression. Then minDisForm[p] gives a minimal SOP-expression aequivalent to p:

\(minDisForm[
        x1\ x2\&_\ x3\&_\ x4\  + \ x1\&_\ x2\ x3\&_\ x4\  + 
            x1\ x2\&_\ x3\&_\ x4\&_\  + \ x1\&_\ x2\ x3\ x4\  + 
            x1\&_\ x2\&_\ x3\&_\ x4\&_\  + \ x1\ x2\ x3\ x4\  + \ 
            x1\ x2\&_\ x3\ x4\  + \ x1\&_\ x2\ x3\ x4\&_\  + 
            x1\&_\ x2\&_\ x3\ x4\  // unnice]\  // \ nice\)

\(minDisForm[\((a\&_ + 
                a\ b\ d\&_)\)\ \((\((a + b\&_ + 
                    c\ d\&_)\) + \(a\ e\)\&_\ )\)\  // \ unnice]\  // \ 
      nice\)

Specification of minConForm

Let p be a boolean expression. Then minConForm[p] gives a minimal POS-expression aequivalent to p:

\(minConForm[
        x1\ x2\&_\ x3\&_\ x4\  + \ x1\&_\ x2\ x3\&_\ x4\  + 
            x1\ x2\&_\ x3\&_\ x4\&_\  + \ x1\&_\ x2\ x3\ x4\  + 
            x1\&_\ x2\&_\ x3\&_\ x4\&_\  + \ x1\ x2\ x3\ x4\  + \ 
            x1\ x2\&_\ x3\ x4\  + \ x1\&_\ x2\ x3\ x4\&_\  + 
            x1\&_\ x2\&_\ x3\ x4\  // unnice]\  // \ nice\)

\(minConForm[\((a\&_ + 
                a\ b\ d\&_)\)\ \((\((a + b\&_ + 
                    c\ d\&_)\) + \(a\ e\)\&_\ )\)\  // \ unnice]\  // \ 
      nice\)

Specification of dontCareMin

Let p and q be two SOP-expressions, such that p locically implies q. Then dontCareMin[p,q] gives the list of all (of course just up to permutations of terms and literals) don´t-care-irredundant SOP-expressions with respect to p and q:

\(dontCareMin[
        x1\ x2\ x3\  + \ x1\ x2\&_\ x3\  + \ x1\ x2\&_\ x3\&_ + 
            x1\&_\ x2\&_\ x3\  // \ unnice, 
        x1\ x2\ x3 + x1\ x2\ x3\&_\  + x1\ x2\&_\ x3\  + \ x1\ x2\&_\ x3\&_ + 
            x1\&_\ x2\ x3\&_ + x1\&_\ x2\&_\ x3 + x1\&_\ x2\&_\ x3\&_\  // \ 
          unnice]\  // \ nice\)

Example:

The functions in "boolmin.m" are not quite useless. The next expamle shoes that the Mathematica command LogicalExpand gives not always a minimal form:

\(\(p = \((a\ b\&_ + a\&_\ b + b\ c\&_ + b\&_\ c // \ 
            unnice)\);\)\)
minDisForm[p]  //  nice

LogicalExpand[p]  //  nice