 Application Center - Maplesoft

# Finding Minimal Sum for Boolean Expression

You can switch back to the summary page by clicking here. 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

(c) 1987, ISBN 0-07-037990-4
Chapter 8 - Simplification of Logic Circuits, problems 8.3 : 8.6, pages 201-202.

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