Petrick's Method
   HOME

TheInfoList



OR:

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 variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...
, 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, P_2, P_3, P_4, 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 (P_ + P_ + \cdots + P_), where each P_ represents a row covering column i. # Apply
De Morgan's Laws In propositional calculus, propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both Validity (logic), valid rule of inference, rules of inference. They are nam ...
to expand P into a sum of products and minimize by 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'' ¤ '' ...
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: private string DoPetriksMethod( Dictionary PIchart, List epis, List primeImplicants, List minterms) private static Dictionary MapTermsToImplicants(List primeImplicants) private static List GetProductOfSums(Dictionary termToImplicantMap, Dictionary primeImplicantChart) private static void AddSumsToList(List productOfSums, List sumsToAdd) private static List GetSumsToAdd(Dictionary PIchart, Dictionary termToImplicantMap, string key, int positionWithinKey) private static char GetTermFromImplicant(Dictionary termToImplicantMap, string implicant) private static string[] GetSumOfProducts(List productOfSums) private static Bracket MergeBrackets(Bracket b1, Bracket b2) private static List> ConvertBracketsToString(List brackets) private static List> RecursiveDistributiveLaw(List> brackets) private static List SingleDistributiveLaw(List b1, List b2) private static string ApplyDistributiveLaw(string a, string b) private static string GetMinProduct(string[] sumOfProducts) private string GetFinalExpression(Dictionary termToImplicantMap, string minProduct) The following code snippet assumes access to the bracket struct. struct Bracket


Example of Petrick's method

Following is the function we want to reduce: :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

* * * (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 -->
Petrick
C++ implementation based on the tutorial above {{DEFAULTSORT:Petrick's Method Boolean algebra