In
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas ...
, 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
Insley may refer to:
*John Insley Blair (1802–1899), American entrepreneur, railroad magnate, philanthropist
* Deborah Ann Insley Dingell (born 1953), Democratic Party politician
* Earl Insley (1911–1958), American football coach and player
* ...
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
,
,
,
, etc.
# Form a logical function
which is true when all the columns are covered. ''P'' consists of a product of sums where each sum term has the form
, where each
represents a row covering column
.
# Reduce
to a minimum sum of products by multiplying out
and applying the
absorption law
In algebra, the absorption law or absorption identity is an identity linking a pair of binary operations.
Two binary operations, ¤ and ⁂, are said to be connected by the absorption law if:
:''a'' ¤ (''a'' ⁂ ''b'') = ''a'' ⁂ (''a'' ¤ '' ...
.
# 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.
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:
:
Based on the ✓ marks in the table above, build a product of sums of the rows where each row is added, and columns are multiplied together:
(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
Choose term or terms with fewest total literals. In our example, the two products both expand to six literals total each:
KNP expands to a'b' + bc' + ac
LMQ expands to a'c' + b'c + ab
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
*
*
* (xiv+379+1 pages)
External links
Tutorial on Quine-McCluskey and Petrick's method!-- https://web.archive.org/web/20170412071609/https://d403fe19-a-62cb3a1a-s-sites.googlegroups.com/site/simpogical/download/qm.pdf?attachauth=ANoY7cqOUBAsLO6wiVSQKsBj0PGW5k-UaTWzufvjC0SUONIEnUE_ryij-m2BfvpSVWnKIX5c1rWlsESb0duGmCWcm0EN8o4me1ABMVlQEeru5-UuWNnEoTEnJcAPAMf9YBtKc_9-C_2EI4N0mE5kUfxiqdoLOS20oS7VLDNQPzbZA6WLetW25rG17B1voUQBZekKpQ3_cpz51xd9sxOH_YlswqUm4htfpg%3D%3D&attredirects=0&d=1 -->
PetrickC++ implementation based on the tutorial above
{{DEFAULTSORT:Petrick's Method
Boolean algebra