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)

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.