Application Center - Maplesoft

Contact Maplesoft Request Quote

Submit your work

Application Center Applications Finding Minimal Sum for Boolean Expression Preview

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
E-mail: jayped007@gmail.com
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): with(combinat,choose):

Warning, the assigned name Group now has a global binding

References

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

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 Format 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
     printf("%s\n",e);
     return;
   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));

   return;

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
     printf("%s\n",e);
     return;
   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));

   return;

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
     printf(seq(args[i],i=1..nargs));
   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;
   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");
          break;
       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;
            break;
         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"} };
         break;
       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);
   end:
   # 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;

   return(result);
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 };
   else
      # 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;
   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;
       break;
     end if;

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

   end do; # while not all_done

   return(e);

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
           break;
       else
           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
                   break;
               end if;
           end if;
           result := result union { v };
       end if;
   end do:
   # verbose_printf("simplifyTerm output : %A\n",result);

   return(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)");
     else
       s := `if`(not (member(c, {$"a".."z"})), cat(s,c), cat(s,UpperCase(c),"'"));
     end if;
   end;

   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)
   ASSERT(length(v)=1);
   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)
   ASSERT(length(v)=1);
   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)
   ASSERT(nops(t)=1);
   # 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;
   end;

   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;
     else
       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;
   end;

   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",
                          externalTerm(e[i]),externalTerm(e[j]),externalTerm(e[k]));
       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",
                            externalTerm(pair[1]),externalTerm(pair[2]),externalTerm(t));
           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

with(Minimize_Boolean_Expression);

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.

Maple

Maple Add-Ons

Student Success Platform

Improving Retention Rates

MapleSim

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

App Preview:

Finding Minimal Sum for Boolean Expression

Maple

Powerful math software that is easy to use

Maple Add-Ons

Student Success Platform

Improving Retention Rates

MapleSim

Advanced System Level Modeling

MapleSim Add-Ons

Systems Engineering

Consulting Services

Maple T.A. and Möbius

Education

Industries

Automotive and Aerospace

Robotics

Machine Design & Industrial Automation

Other

Application Areas

Product Pricing

Purchasing

Institutional Student Licensing

Maplesoft Elite Maintenance (EMP)

Support

Product Training

Online Product Help

Webinars & Events

Publications

Content Hubs

Examples & Applications

Community

About Maplesoft

Media Center

User Community

Contact

App Preview:

Finding Minimal Sum for Boolean Expression