 Application Center - Maplesoft

# Prime Implicants of Boolean Expression by Concensus method

You can switch back to the summary page by clicking here. 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,boolean) and args);    # 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; j := pair;      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,pair)) then          # May take consensus of terms, useful if consensus is not already a term in e          t := takeConsensus(pair,pair);          if not `subset`({t},e) then            moreToCheck := true;            consensus_printf("Adding consensus term of %s and %s --> %s\n",                             externalTerm(pair),externalTerm(pair),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); 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. 