Application Center - Maplesoft
  Submit your work
Application Center Applications Prime Implicants of Boolean Expression by Concensus method Preview

App Preview:

Prime Implicants of Boolean Expression by Concensus method

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

Learn about Maple
Download Application

 

Image 

A Maple Package Implementing the
Consensus Method of finding Prime Implicants 

of boolean expressions 

Jay Pedersen
University of Nebraska at Omaha Student
E-mail: jayped007@gmail.com
Version 3, 2007-05-19, use combinat:-choose
Version 2, 2007-05-17, use Maple package
Version 1, 2002-07-07

Project: Use the consensus method to find the prime implicants of
              boolean expressions in sum of products form (eg: XY + X'Y + XY'). 

> restart;
with (StringTools):
with(combinat,choose):
 

Warning, the assigned name Group now has a global binding
 

References 

The consensus method for determining prime implicants, as implemented by this program, 

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. 

Input Format (boolean expressions) 

Input to the consensus routine is a character-string containing a boolean expression; 

whose prime-implicants are 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".

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)".

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

Whitespace is ignored (spaces and tabs). 

Algorithm Code (Module) 

> Consensus_Method := module()

 option package;

 # interface routines
 export consensus;

 # local support routines:
 local consensus_printf,compressAndUpcase, makeInternalForm,
       externalTerm, externalExpression, negateVbl, hasVbl, sameTerm,
       consensusPossible, takeConsensus, termContained,
       consensusStep1, consensusStep2, consensusList;

 global verboseMode;

 # 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:  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
   consensusList(e);

 end proc: # consensus

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

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

   if (verboseMode) then
     printf(seq(args[i],i=1..nargs));
   end if;

 end proc: # consensus_printf

 # Routine: consensusList
 # Abstract: Given expression (list), 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;
   consensus_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

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

 end proc: # consensusList

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

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

   s := "";
   s1 := UpperCase(s_in);
   n := length(s1);
   for i to n do;
     # remove blanks, tabs and newlines
     c := s1[i];
     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,e,i,n,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 := "";
   n := length(s1);
   e := {}; # output expression
   term := {}; # next term
   termCount := 0;
   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;
       termCount := termCount + 1;
       e := e union {term};
       term := {};
     end if;
   end do;

   # append trailing term
   if nops(term) > 0 then
     termCount := termCount + 1;
     e := e union {term};
   end if;

   return e;
 end proc: # makeInternalForm

 # 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, i, n, s;

   s := "";
   n := nops(elem);
   for i to n do;
     c := elem[i];
     s := `if`(not (member(c, {$"a".."z"})), cat(s,c), cat(s,UpperCase(c),"'"));
   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 i,s;

   s := "";
   for i to nops(expr) do;
     s := `if`(i = 1, externalTerm(expr[i]), cat(s," + ",externalTerm(expr[i])));
   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 contained in term.
 # Returns:  boolean result

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

 # 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 i, n, flips;

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

   flips := 0;
   n := nops(t1);
   for i to n do;
     if (hasVbl(t2,negateVbl(t1[i]))) 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, c, cnot, e, i, n, negatedVbl;

   # Process flipped variables, must be exactly 1
   flips := 0;
   e := {};
   n := nops(t1);
   for i to n do;
     c := t1[i];
     cnot := negateVbl(c);
     if (hasVbl(t2,cnot)) then
       flips      := flips + 1;
       negatedVbl := cnot;
     else
       e := e union {c};
     end if;
   end do;
   ASSERT(flips=1,"Bad call to takeConsensus, flips not 1");

   # add any vbls from t2 that are not in t1
   n := nops(t2);
   for i to n do;
     c := t2[i];
     if (c <> negatedVbl) then
       e := e union {c};
     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;
   # consensus_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};
         consensus_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;
     consensus_printf("Result: %s\n", externalExpression(e));
   end if;

   # consensus_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;
   # consensus_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;
           consensus_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
     consensus_printf("Result: %s\n",externalExpression(e));
   end if;

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

   return e;
 end proc: # consensusStep2

end module: # Consensus_Method

with(Consensus_Method);
 

[consensus]
 

Example Usage 

> consensus(" XY + X'Y + Z");
 

Prime implicants: Z + Y
 

> consensus("XY + Y'T + X'YZ' + XY'ZT' + X'YZ");
 

Prime implicants: T + ZX + Y
 

> consensus("A'B' + AB + A'B' + AB'");
 

Prime implicants: A + B'
 

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

Initial: AB + AB'
Adding consensus term of AB and AB' --> A
Result: A + AB + AB'
Simplify: combine terms A + AB --> A
Simplify: combine terms A + AB' --> A
Result: A
Prime implicants: A
 

> consensus("X' + X'Y' + Y'Z' + X'Y'Z' + X'A'B'C' + X'D'E'F'G' + Y'");
 

Prime implicants: X' + Y'
 

> consensus("X + XY");
 

Prime implicants: X
 

> consensus("xy' + xyz' + x'yz'");
 

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

> consensus("xy + y't +x'yz' + xy'zt'");
 

Prime implicants: Z'Y + Y'T + Z'T + XT + ZX + XY
 

> consensus("xyz + x'z' + xyz' + x'y'z + x'yz'");
 

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

> consensus("xy' + xyz' + x'yz'");
 

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

> consensus("xy + y't + x'yz' + xy'zt'");
 

Prime implicants: Z'Y + Y'T + Z'T + XT + ZX + XY
 

> consensus("x + x'",true);
 

Initial: X' + X
Prime implicants: X' + X
 

> consensus("a'b'c'd' + a'cd + abc' + abd' + bcd",false);
 

Prime implicants: A'CD + AB + A'B'C'D' + BCD
 

> consensus("a + + b");
 

*** Missing boolean term before + operator ***
 

Prime Implicants vs Minimal Sum 

Prime implicants are not necessarily the minimal boolean expression.
 

A second algorithm must be applied to the prime-implicants to obtain 

the minimal form.  Some prime implicants may prove to be superfluous 

and would be removed in minimal form. 

 

That step requires multiplying 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 would need to be 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. 

 

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.
 

Image