Application Center - Maplesoft

App Preview:

Finding Minimal Sum for Boolean Expression

You can switch back to the summary page by clicking here.

Learn about Maple
Download Application



A Maple Package implementing
minimization of boolean expressions

Jay Pedersen
University of Nebraska at Omaha Student
Version 1.0, 2007-07-09,

Project: Finds the mimimal sum of boolean expressions in sum of products form (eg: XY + X'Y + XY').

The "consensus" routine finds prime-implicants.  The "minbool" routine finds minimal boolean sum. 

> restart;
with (StringTools):

Warning, the assigned name Group now has a global binding


The consensus method for determining prime implicants, is defined in: 


    Schaum's Outlines 

    Essential Computer Mathematics by Seymour Lipschutz Phd, Professor of Math, Temple University 

    (c) 1987, ISBN 0-07-037990-4
    Chapter 8 - Simplification of Logic Circuits, problems 8.3 : 8.6, pages 201-202.


After prime implicants are determined; a second algorithm is applied to the prime implicants; 

to remove any terms not needed for minimal form.  This is also defined by Lipschutz; 

in the same pages.  The algorithm is as follows: 


Multiply the prime implicant terms by the conjugate of each variable in 

the expression which is not involved in the term. 


For example, if the boolean expression involves XYZ; and a prime implicant is X; 

then the following would be calculated for prime implicant X: 


                  X(Y+Y')(Z+Z') --> XYZ + XYZ' +  XY'Z + XY'Z' 


Perform this operation for each prime implicant.  Compare the results. 

For any given prime implicant; if each term generated by the multiplication 

can be found in the multiplied terms of the other prime-implicants, then that 

prime implicant is superfluous and is removed from the minimal sum form. 

Input Format (boolean expressions) 

The input is a character-string containing a boolean expression; whose minimal boolean sum form 

is to be determined. 


The format of this string is to specify boolean variables as one-letter names; 

optionally followed by a single-quote to specify "negated" or "NOT".

Variables are concatenated to specify AND conditions;

eg: "XY'Z" means "X AND NOT-Y AND Z".

The "+" operator can be used to "OR" expressions together; eg: "XY + Z'"

is read "(X AND Y) OR (not Z)".

The variable T is reserved to mean TRUE, and T' means FALSE. 

So TT' = T', T + T' = T. 

Lowercase letters are converted to uppercase.  Eg: xy means "X AND Y".

Whitespace is ignored (spaces and tabs).

Algorithm Code (Module) 

> Minimize_Boolean_Expression := module()

 option package;

 # interface routines
 export consensus,minbool;

 # local support routines:
 local verbose_printf,compressAndUpcase, makeInternalForm,
       externalTerm, externalExpression, negateVbl, hasVbl, hasTerm,
       sameTerm, consensusPossible, takeConsensus, termContained,
       consensusStep1, consensusStep2, consensusList, determineVariables,
       minimalSum, superfluousTerm, mulTermByMissingVbls, simplifyTerm;

 global verboseMode, variableSet;

 # Note: The Internal Forma
t of a boolean expression is a set.
 #   1. Each term results in a set inside of the expression set.
 #   2. A variable is stored as its uppercase name.
 #   3. A negated variable is stored as its lowercase name.
 # Eg: "XY + X'Z" is stored as {{"X","Y"},{"x","Z"}};

 # Routine:  minbool
 # Abstract: Determine minimal boolean expression
 # Input:    boolstr - boolean expression in string form (see "Input Format" section)
 # Returns:  string - prime implicants of specified boolean expression

 minbool := proc (boolstr::string)
   local e, p, m;

   # verboseMode iff 2nd arg passed, and set true
   verboseMode := evalb(nargs = 2 and type(args[2],boolean) and args[2]);
   #printf("verboseMode = %A\n", verboseMode);

   # convert input string form of expression to internal form
   e := makeInternalForm(boolstr);

   if (type(e,string)) then # error
   end if;

   # Determine variable set
   variableSet := determineVariables(e);

   if (verboseMode) then
     printf("Variables in expression: %A\n", variableSet);
   end if;

   # Determine prime implicants by concensus method
   p := consensusList(e);
   verbose_printf("Prime implicants: %s\n",externalExpression(p));

   # Determine minimal sum
   m := minimalSum(p);

   # Display result
   printf("Minimal sum: %s\n",externalExpression(m));


 end proc: # minbool

 # Routine:  consensus
 # Abstract: Determine prime implicants for specified boolean expression
 # Input:    boolstr - boolean expression in string form (see "Input Format" section)
 # Returns:  string - prime implicants of specified boolean expression

 consensus := proc (boolstr::string)
   local e;

   # convert input string form of expression to internal form
   e := makeInternalForm(boolstr);

   if (type(e,string)) then # error
   end if;

   # verboseMode iff 2nd arg passed, and set true
   verboseMode := evalb(nargs = 2 and type(args[2],boolean) and args[2]);

   # perform consensus algorithm on internal-format expression
   e := consensusList(e);

   # Display result
   printf("Prime implicants: %s\n",externalExpression(e));


 end proc: # consensus

 # Routine: verbose_printf
 # Abstract: printf, but only if in verbose mode
 # Note:     uses args, nargs - to process argument list

 verbose_printf := proc()
   global verboseMode;
   local i;

   if (verboseMode) then
   end if;

 end proc: # verbose_printf

 # Routine: determineVariables
 # Abstract: Given expression, return set with all variables
 #           used in the expression

 determineVariables := proc(expr::set)
   local e, result, term, v, vbl;

   e := expr;
   result := {}; # empty

   # Step through the set, adding variables to the result set
   for term in e do;
     for v in term do;
       vbl := `if`(member(v,{$"a".."z"}),UpperCase(v),v);
       result := result union { vbl };
   end do;

   return(result); # set of all variables used in expression
 end proc: # determineVariables

 # Routine: minimalSum
 # Abstract: Given expression, which is a set of prime implicants;
 #           return the minimal sum (remove any superfluous implicants).

 minimalSum := proc(expr::set)
     local p, term, rem_terms, moreToCheck, loops;

     p := expr;

     if nops(p) > 1 then
       # FALSE + X = X, X + FALSE = X
       p := p minus {{"t"}}; # may do nothing, if FALSE in list, removes
       if (member({"T"},p)) then
         p := {{"T"}}; # X + TRUE + Y --> TRUE, regardless of X,Y
       end if;
     end if;

     moreToCheck := true;
     loops := 0;
     while moreToCheck do;
       moreToCheck := false; # assume no superfluous terms

       # sanity check
       loops := loops + 1;
       if (loops > 1500) then
          printf("*** Max loops in minimalSum reached, terminating ***\n");
       end if;

       for term in p do;
         # Determine if term is superfluous
         rem_terms := p minus { term };
         if (superfluousTerm(term, rem_terms)) then
            # Remove superfluous term, restart with smaller set of terms
            p := rem_terms;
            moreToCheck := true;
         end if;
       end do;

     end do; # while moreToCheck

     # Check for X + X' situations
     for term in p do;
       if (nops(term) = 1) and (hasTerm(p,{ negateVbl(term[1]) })) then
         # X + X' + whatever ---> TRUE
         p := { {"T"} };
       end if;
     end do;
     return (p);

 end proc: # minimalSum

 # Routine: superfluousTerm
 # Abstract: determine if specified prime implicant term is superfluous
 # Algorithm
 #    Multiply the prime implicant terms by the conjugate of each
 #    variable in the expression which is not involved in the term.
 #    For example, if the expression is for XYZ and a prime implicant
 #    is X then the following would be calculated:
 #      X(Y+Y')(Z+Z') --> XYZ + XYZ' +  XY'Z + XY'Z'
 #    This is performed on each prime implicant; and the results
 #    are then compared.  If each and every term generated by this
 #    multiplication is found in the multiplied terms from other
 #    prime-implicants, then this prime implicant is superfluous
 #    and is removed from the minimal sum form.

 superfluousTerm := proc(term::set, other_terms::set)
   local term_set, other_terms_set, t, result;

   term_set := mulTermByMissingVbls(term);
   other_terms_set := {};
   for t in other_terms do;
       other_terms_set := other_terms_set union mulTermByMissingVbls(t);
   # verbose_printf("checkset = %s\n", externalExpression(term_set));
   # verbose_printf("ocheckset = %s\n", externalExpression(other_terms_set));
   result := `if`(`subset`(term_set,other_terms_set),true,false);

   if (result) then
       verbose_printf("Superfluous term: %s\n",externalTerm(term));
   end if;

 end proc: # superfluousTerm

 # Routine: mulTermByMissingVbls
 # Abstract: Given a term, determine what variables it is missing from the
 #           global variableSet.  Multiply the term by the conjugates of
 #           of those variables.  Return the expression that is the
 #           the result of that multiplication.

 mulTermByMissingVbls := proc(term::set)
   local termVbls, missVbls, nVbls, result, i, j, n, s, binary_s, zeropad;

   termVbls := determineVariables({term});
   missVbls := variableSet minus termVbls;
   # printf("Missing variables = %A\n",missVbls);
   nVbls := nops(missVbls);
   if (nVbls = 0) then
      result := { term };
      # multiply by conjugates, done by generating every combination
      # of each missing variable with every other missing variable;
      # and appending.  Use binary counting to obtain all possibilities.
      result := {}; # empty
      zeropad := cat("0"$nVbls);
      n := 2^nVbls - 1; # zero-relative
      for i from 0 to n do;
         # generate next possibility
         binary_s := substring(cat(zeropad, convert(i,compose,binary,string)),-nVbls..-1);
         s := {};
         for j from 1 to nVbls do;
             s := s union `if`(binary_s[j] = "1",{missVbls[j]},{negateVbl(missVbls[j])});
         end do;
         result := result union { term union s };
   end if;

   return (result);

 end proc: # mulTermByMissingVbls

 # Routine: consensusList
 # Abstract: Given expression, return simplified form
 #           after applying consensus method to it.
 #           Displays simplified expression in external-form.
 #           Eg: {{"X"}, {"X","Y"}} -> X

 consensusList := proc(expr::set)
   local e, saved_e, all_done, loops;

   e := expr;
   # verbose_printf("Initial: %s\n",externalExpression(e));

   all_done := false;
   loops := 0;
   while (not all_done) do;

     # Step 1.  Look for elements contained in other elements.
     #          Eg: AB + ABCDEF --> AB, AB is implicant of ABCDEF
     e := consensusStep1(e);

     saved_e := e;  # save state, so we can see if step 2 makes any change

     # Step 2. Looking for removable elements
     e := consensusStep2(e);

     # If nothing added in step 2, we are done
     if evalb(e=saved_e) then
       all_done := true;
     end if;

     # Guard against infinite loop
     loops := loops + 1;
     if (loops > 1500) then
       printf("*** Max loops in concensusList reached, terminating ***\n");
     end if;

   end do; # while not all_done


 end proc: # consensusList

 # Routine:  compressAndUpcase
 # Abstract: Remove whitespace from string, convert to uppercase
 # Returns:  converted string

 compressAndUpcase := proc (s_in::string)
   local c,s,s1;

   s := "";
   s1 := UpperCase(s_in);
   for c in s1 do;
     # remove blanks, tabs and newlines
     if not (member(c,{" ","\t","\n"})) then
       s := cat(s, c);
     end if;
   end do;

   return s;
 end proc: # compressAndUpcase

 # Routine: makeInternalForm
 # Abstract: Given a sum of products boolean expression string
 #           eg: "XY+Y'Y", convert to internal list form with
 #           single-character variables; lowercase if negated.
 #           (eg: "XY + X'Y" -> {{"X","Y"},{"x","Y"}}
 # Returns: internal form boolean expression (set)

 makeInternalForm := proc (s_in::string)
   local c,i,n,e,s,s1,term,termCount;

   # remove spaces and tabs, convert to uppercase
   s1 := compressAndUpcase(s_in);

   # check for empty expression
   if (length(s1)=0) then
     return "*** Empty Expression ***";
   end if;

   s := "";
   e := {}; # output expression
   term := {}; # next term
   termCount := 0;
   n := length(s1);
   for i to n do;
     c := s1[i];
     if (not member(c, {"+", "'", $"A".."Z"})) then
       return cat("*** Invalid Character: <", c, "> ***");
     end if;
     if (member(c, {$"A".."Z"})) then
       # lookahead for negation indicator
       if (i < n) then
         if (s1[i+1] = "'") then # negated => lowercase
           i := i + 1;
           c := LowerCase(c);
         end if;
       end if;
       term := term union {c};
     elif (c = "'") then
       # Only valid after variable (see above)
       return "*** Invalid negation operation ***";
     elif (c = "+") then
       # Add term
       if (nops(term) = 0) then
         return "*** Missing boolean term before + operator ***";
       end if;
       term := simplifyTerm(term); # Handle T or T' in term
       termCount := termCount + 1;
       e := e union {term};
       term := {};
     end if;
   end do;

   # append trailing term
   if nops(term) > 0 then
     term := simplifyTerm(term); # Handle T or T' in term
     termCount := termCount + 1;
     e := e union {term};
   end if;

   return e;
 end proc: # makeInternalForm

 # Routine: simplifyTerm
 # Abstract: Handle special variable T and T'.
 #           T' makes entire term false.
 #           T  can be removed from term, if more than T in term
 #           AA' makes entire term false (A is any variable)
 #           eg: {"X","T"} -> "X"
 #           eg: {"A", "B", "T", "t"} -> "t" (false)
 # Returns: internal form boolean expression (set)

 simplifyTerm := proc (term::set)
   local result, n, v;

   # verbose_printf("simplifyTerm input : %A\n",term);
   n := nops(term);
   result := {};
   for v in term do;
       if ((v = "T") and (n > 1)) then
           ; # ignore
       elif (v = "t") then
           result := { "t" }; # entire expression false
           if (nops(result) > 0) then
               # see if negated form of vbl already in result -> AA' -> FALSE!
               if (hasVbl(result,negateVbl(v))) then
                   result := { "t" }; # entire expression false
               end if;
           end if;
           result := result union { v };
       end if;
   end do:
   # verbose_printf("simplifyTerm output : %A\n",result);

 end proc: # simplifyTerm

 # Routine: externalTerm
 # Abstract: Given a term in internal format
 #           return an external-format string.
 #           For example: {"A","b","C"} -> AB'C

 externalTerm := proc(elem::set)
   local c, s;

   s := "";
   for c in elem do;
     if (c = "T") then
       s := cat(s, "(TRUE)");
     elif (c = "t") then
       s := cat(s, "(FALSE)");
       s := `if`(not (member(c, {$"a".."z"})), cat(s,c), cat(s,UpperCase(c),"'"));
     end if;

   return s;
 end proc: # externalTerm

 # Routine:  externalExpression
 # Abstract: Given an expression, convert to external format
 # Example:  {{"A","b"},{"C","D"}} --> AB' + CD

 externalExpression := proc(expr::set)
   local s,term;

   s := "";
   for term in expr do;
     s := cat(s,`if`(length(s) = 0,""," + "),externalTerm(term));
   end do;

   return s;
 end proc: # externalExpression

 # Routine: negateVbl
 # Abstract: Given a variable in internal format, return
 #           a variable in internal format that is its
 #           negation.  For example: v -> V, V -> v

 negateVbl := proc (v::string)
   return `if`(member(v,{$"a".."z"}),UpperCase(v),LowerCase(v));
 end proc: # negateVbl

 # Routine:  hasVbl
 # Abstract: Determine if variable v contained in term t
 # Returns:  boolean result

 hasVbl := proc (t::set, v::string)
   return `subset`({v},t);
 end proc: # hasVbl

 # Routine:  hasTerm
 # Abstract: Determine if expression e has term t
 # Returns:  boolean result

 hasTerm := proc(e::set, t::set)
   # verbose_printf("hasTerm t=%A e=%A\n",t,e);
   return `subset`({t},e);
 end proc: # hasTerm

 # Routine:  sameTerm
 # Abstract: Determine if 2 terms are equal.  Eg: XY and YX are equal
 # Returns:  boolean result

 sameTerm := proc (t1::set, t2::set)
   return evalb(t1=t2); # could do: `subset`(t1,t2) and `subset`(t2,t1)
 end proc: # sameTerm

 # Routine:  consensusPossible
 # Abstract: Determine if consensus of 2 given terms is possible.
 #           This is true if a single variable is in negated form
 #           in comparison of t1's variables and t2's variables.
 #           Eg1: "ABC" and "ABc" -> true.
 #           Eg2: "ABC" and "aBc" -> false (2 vbl flips)
 #           Eg3: "X" and "x"     -> false (no consensus of X and X')
 # Note:     Concensus also possible if one term completely contained
 #           within another.  This is handled in consensusStep1
 # Returns:  boolean result

 consensusPossible := proc (t1::set, t2::set)
   local v, flips;

   # Note: no consensus of X+X', inserting
   # TRUE would not work properly -> X T X'

   if nops(t1)=1 and nops(t2)=1 then
       return false; # no consensus of X,X', etc
   end if;

   flips := 0;
   for v in t1 do;
     if (hasVbl(t2,negateVbl(v))) then
       flips := flips + 1;
     end if;

   return evalb(flips = 1);
 end proc: # consensusPossible

 # Routine:  takeConsensus
 # Abstract: Given 2 terms which should be consensus-able;
 #           return the consensus.  Eg: "ABC" and "ABc" -> "AB"
 # Returns:  consensus of 2 terms

 takeConsensus := proc(t1::set, t2::set)
   local flips, e, negatedVbl, v, vnot;

   # Process flipped variables, must be exactly 1
   flips := 0;
   e := {}; negatedVbl := "";
   for v in t1 do;
     vnot := negateVbl(v);
     if (hasVbl(t2,vnot)) then
       flips      := flips + 1;
       negatedVbl := vnot;
       e := e union {v};
     end if;
   end do;
   ASSERT(flips=1,"Bad call to takeConsensus, flips not 1");

   # add any vbls from t2 that are not in t1
   for v in t2 do;
     if (v <> negatedVbl) then
       e := e union {v};
     end if;

   return e;
 end proc: # takeConsensus

 # Routine:  termContained
 # Abstract: Determine if one term contained in another.
 #           Eg: AB and ABC --> true
 #               ABC and ABD --> false
 #               AB and AB --> false
 # Returns:  boolean result

 termContained := proc(t1::set, t2::set)
   return (`subset`(t1,t2) or `subset`(t2,t1)) and evalb(t1<>t2);
 end proc: # termContained

 # Routine: consensusStep1
 # Abstract: Remove superfluous terms which are supersets of
 #           other terms in the expression.
 #           Eg: AB and ABCDE --> AB
 # Returns:  Reduced expression (set)

 consensusStep1 := proc(expr::set)
   local e, i, j, k, n, t, dropset, newset, allpairs, pair;

   e := expr;
   # verbose_printf("Step1 start: %s\n", externalExpression(e));

   dropset   := {};
   n := nops(e);
   allpairs := combinat:-choose(n,2): # all combos of 2 indexes into e
   for pair in allpairs do;
     i := pair[1]; j := pair[2];
     if termContained(e[i],e[j]) then
       # Contained term!
       if (nops(e[i]) < nops(e[j])) then # e[i] contained in e[j] => drop e[j]
         t := j;  k := i; # drop e[j]
       else # e[j] contained in e[i] => drop e[i]
         t := i;  k := j; # drop e[i]
       end if;
       if (not member(t, dropset)) then
         dropset := dropset union {t};
         verbose_printf("Simplify: combine terms %s + %s --> %s\n",
       end if;
     end if; # termContained
   end do; # for pair in allpairs

   if (nops(dropset) > 0) then
     newset := {};
     for i to n do;
       if (not member(i, dropset)) then
         newset := newset union {e[i]};
       end if;
     end do;
     e := newset;
     # verbose_printf("Result: %s\n", externalExpression(e));
   end if;

   # verbose_printf("Step1 end: %s\n", externalExpression(e));

   return e;
 end proc: # consensusStep1

 # Routine: consensusStep2
 # Abstract: Given expression (list), perform consensus on
 #           terms which have a single variable changed.
 #           Eg: XY, XY'Z -> XZ
 # Returns: expression with consensus terms added (set)

 consensusStep2 := proc(expr::set)
   local e, t, loops, moreToCheck, allpairs, pair, added;

   e := expr;
   # verbose_printf("Step2 start: %s\n", externalExpression(e));
   moreToCheck := true;
   loops := 0; added := 0;
   while moreToCheck do;
     moreToCheck := false; # assume no more consensus terms

     allpairs := combinat:-choose(e,2): # all combos of 2 terms of e
     for pair in allpairs do;

       if (consensusPossible(pair[1],pair[2])) then
         # May take consensus of terms, useful if consensus is not already a term in e
         t := takeConsensus(pair[1],pair[2]);
         if not `subset`({t},e) then
           moreToCheck := true;
           verbose_printf("Adding consensus term of %s and %s --> %s\n",
           e := e union {t}; # add consensus term - modifies e, breaks indexes into e
           added := added + 1;
           break;  # added term -- break from while i loop
         end if; # not subset
       end if; # consenusPossible

     end do; # for nextpair

     # Guard against infinite loop
     loops := loops + 1;
     if (loops >= 1500) then
         printf("*** Max loops in concensusStep2, terminating ***\n"); return(e);
     end if;

   end do; # while moreToCheck

   if (added > 0) then
     verbose_printf("Result: %s\n",externalExpression(e));
   end if;

   # verbose_printf("Step2 end: %s\n", externalExpression(e));

   return e;
 end proc: # consensusStep2

end module: # Minimize_Boolean_Expression


[consensus, minbool]

Example Usage 

> # Examine standard boolean expression properties

> minbool("A + T"); # A + 1

Minimal sum: (TRUE)

> minbool("A + T'"); # A * 0

Minimal sum: A

> minbool("A + A"); # (Idempotent)

Minimal sum: A

> minbool("AA"); # A AND A (Idempotent)

Minimal sum: A

> minbool("A + A'"); # A + NOT A (Complement)

Minimal sum: (TRUE)

> minbool("AA'"); # A * not A (Complement)

Minimal sum: (FALSE)

> minbool("A + AB"); # (Absorption)

Minimal sum: A

> # Determine prime-implicants using "consensus"
consensus("xyz + x'z' + xyz' + x'y'z + x'yz'");

Prime implicants: X'Y' + Z'X' + XY + Z'Y

> # Same example with minbool to find minimal sum
minbool("xyz + x'z' + xyz' + x'y'z + x'yz'");

Minimal sum: X'Y' + XY + Z'Y

> # 4 variable example, could be solved with a Karnaugh map
minbool("xyza' + xy'za + xy'za' + xy'z'a' + xy'z'a + x'y'za + x'y'za' + x'y'z'a' + x'y'z'a");

Minimal sum: Y' + A'ZX

> # More complex absorption
minbool("X + XYZABC");

Minimal sum: X

> # Show verbose mode, where 2nd argument specified as true
minbool("AB + AB'",true);

Variables in expression: {A, B}
Adding consensus term of AB' and AB --> A
Result: AB' + A + AB
Simplify: combine terms AB' + A --> A
Simplify: combine terms A + AB --> A
Prime implicants: A
Minimal sum: A

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.