| > |
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);
|
