Petrick's method

Key takeaways

Petrick's method belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Petrick's method to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Petrick's method from memory before moving on to harder problems.

Reference excerpt

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 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 P 1 {\displaystyle P_{1}} , P 2 {\displaystyle P_{2}} , P 3 {\displaystyle P_{3}} , P 4 {\displaystyle P_{4}} , etc. Form a logical function P {\displaystyle P} which is true when all the columns are covered. P consists of a product of sums where each sum term has the form ( P i 0 + P i 1 + {\displaystyle (P_{i0}+P_{i1}+}

⋯ {\displaystyle \cdots }

+ P i N ) {\displaystyle +P_{iN})} , where each P i j {\displaystyle P_{ij}} represents a row covering column i {\displaystyle i} . Apply De Morgan's Laws to expand P {\displaystyle P} into a sum of products and minimize by applying the absorption law X + X Y = X {\displaystyle 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.

Pseudocode The algorithm above can be implemented with the C# as shown below:The following code snippet assumes access to the bracket struct.

Example of Petrick's method Following is the function we want to reduce:

f ( A , B , C ) = ∑ m ( 0 , 1 , 2 , 5 , 6 , 7 ) = A ′ B ′ C ′ + A ′ B ′ C + A ′ B C ′ + A B ′ C + A B C ′ + A B C {\displaystyle f(A,B,C)=\sum m(0,1,2,5,6,7)=A'B'C'+A'B'C+A'BC'+AB'C+ABC'+ABC}

The prime implicant chart from the Quine-McCluskey algorithm is as follows:

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.

Notes

References

Further reading Krambeck, Donald (2016-02-17). "Prime Implicant Simplification Using Petrick's Method". All About Circuits. EETech Media, LLC. Archived from the original on 2017-04-12. Retrieved 2020-04-03. Petrick, Stanley R. (1965). A Recognition Procedure for Transformational Grammars (PhD thesis). Massachusetts Institute of Technology. Bolton, Martin (1990). "4. Minimization". Written at University of Bristol, Bristol, UK. In Dagless, Erik L. (ed.). Digital Systems Design with Programmable Logic. Electronic Systems Engineering Series (1 ed.). Wokingham, UK: Addison-Wesley Publishers Ltd. pp. 100–101, 115. ISBN 0-201-14545-6. LCCN 90000007. ISBN 978-0-201-14545-8 ark:/13960/t2f83p38r. Retrieved 2021-04-17. (xiv+379+1 pages)

External links Tutorial on Quine-McCluskey and Petrick's method Petrick C++ implementation based on the tutorial above

Worked examples

Example 1 — a first encounter with Petrick's method

Start with the simplest possible case. Write down what Petrick's method claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Petrick's method before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Petrick's method ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Petrick's method

In research: Petrick's method appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Petrick's method in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Petrick's method is common in secondary-school and first-year university syllabi. It links to neighbouring topics Boolean algebra, so understanding it makes those chapters shorter.
In everyday life: Look for Petrick's method outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Petrick's method in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Petrick's method means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Petrick's method out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Petrick's method in simple terms?

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.

Why does Petrick's method matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Petrick's method?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Petrick's method.