In Boolean algebra, Petrick's method (also known as Petrick function or branch-and-bound method) is a technique described by Stanley R. Petrick (1931–2006) in 1956 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. The method was improved by Insley B. Pyne and Edward Joseph McCluskey in 1962.

Algorithm

Example of Petrick's method

Following is the function we want to reduce: The prime implicant chart from the Quine-McCluskey algorithm is as follows: ! || 0 || 1 || 2 || 5 || 6 || 7 || ⇒ || A || B || C Based on the ✓ marks in the table above, build a product of sums of the rows. Each column of the table makes a product term which adds together the rows having a ✓ mark in that column: (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) Use the distributive law to turn that expression into a sum of products. Also use the following equivalences to simplify the final expression: X + XY = X and XX = X and X + X = X = (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) = (K+LM)(N+LQ)(P+MQ) = (KN+KLQ+LMN+LMQ)(P+MQ) = KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ Now use again the following equivalence to further reduce the equation: X + XY = X = KNP + KLPQ + LMNP + LMQ + KMNQ Choose products with fewest terms, in this example, there are two products with three terms: KNP LMQ Referring to the prime implicant table, transform each product by replacing prime implicants with their expression as boolean variables, and substitute a sum for the product. Then choose the result which contains the fewest total literals (boolean variables and their complements). Referring to our example: KNP expands to A'B' + BC' + AC where K converts to A'B', N converts to BC', etc. LMQ expands to A'C' + B'C + AB Both products expand to six literals each, so either one can be used. In general, application of Petrick's method is tedious for large charts, but it is easy to implement on a computer.