Petrick's method
From Wikipedia, the free encyclopedia
In Boolean algebra, Petrick's method (also known as the branch-and-bound method) is a technique for determining all minimum sum-of-products solutions from a prime implicant chart. Petrick's method is very tedious for large charts, but it is easy to implement on a computer.
- Reduce the prime implicant chart by eliminating the essential prime implicant rows and the corresponding columns.
- Label the rows of the reduced prime implicant chart P1, P2, P3, P4, etc.
- Form a logical function P which is true when all the columns are covered. P consists of a product of sums where each sum term has the form (Pi0 + Pi1 +
+ PiN), where each Pij represents a row covering column i. - Reduce P to a minimum sum of products by multiplying out and applying X + XY = X.
- Each term in the result represents a solution, that is, a set of rows which covers all of the minterms in the table. To determine the minimum solutions, first find those terms which contain a minimum number of prime implicants.
- Next, for each of the terms found in step five, count the number of literals in each prime implicant and find the total number of literals.
- Choose the term or terms composed of the minimum total number of literals, and write out the corresponding sums of prime implicants.
