<Text-field style="Heading 1" layout="Heading 1"><Font family="Arial">References</Font></Text-field>

<Text-field style="Heading 1" layout="Heading 1"><Font family="Arial">Algorithm Code (Module)</Font></Text-field>

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\134n", verboseMode); # convert input string form of expression to internal form e := makeInternalForm(boolstr); if (type(e,string)) then # error printf("%s\134n",e); return; end if; # Determine variable set variableSet := determineVariables(e); if (verboseMode) then printf("Variables in expression: %A\134n", variableSet); end if; # Determine prime implicants by concensus method p := consensusList(e); verbose_printf("Prime implicants: %s\134n",externalExpression(p)); # Determine minimal sum m := minimalSum(p); # Display result printf("Minimal sum: %s\134n",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\134n",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\134n",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 ***\134n"); 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\134n", externalExpression(term_set)); # verbose_printf("ocheckset = %s\134n", externalExpression(other_terms_set)); result := `if`(`subset`(term_set,other_terms_set),true,false); if (result) then verbose_printf("Superfluous term: %s\134n",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\134n",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\134n",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 ***\134n"); 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,{" ","\134t","\134n"})) 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\134n",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\134n",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\134n",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\134n", 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\134n", 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\134n", externalExpression(e)); end if; # verbose_printf("Step1 end: %s\134n", 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\134n", 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\134n", 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 ***\134n"); return(e); end if; end do; # while moreToCheck if (added > 0) then verbose_printf("Result: %s\134n",externalExpression(e)); end if; # verbose_printf("Step2 end: %s\134n", externalExpression(e)); return e; end proc: # consensusStep2 end module: # Minimize_Boolean_Expression with(Minimize_Boolean_Expression);

NiM3JEkqY29uc2Vuc3VzRzYiSShtaW5ib29sRzYi