Blake canonical form

From HandWiki
Short description: Standard form of Boolean function

Karnaugh map of AB + BC + AC, a sum of all prime implicants (each rendered in a different color). Deleting AC results in a minimal sum.
ABD + ABC + ABD + ABC
ACD + BCD + ACD + BCD
Boolean function with two different minimal forms. The Blake canonical form is the sum of the two.

In Boolean logic, a formula for a Boolean function f is in Blake canonical form (BCF),[1] also called the complete sum of prime implicants,[2] the complete sum,[3] or the disjunctive prime form,[4] when it is a disjunction of all the prime implicants of f.[1]

Relation to other forms

The Blake canonical form is a special case of disjunctive normal form.

The Blake canonical form is not necessarily minimal (upper diagram), however all the terms of a minimal sum are contained in the Blake canonical form.[3] On the other hand, the Blake canonical form is a canonical form, that is, it is unique up to reordering, whereas there can be multiple minimal forms (lower diagram). Selecting a minimal sum from a Blake canonical form amounts in general to solving the set cover problem,[5] so is NP-hard.[6][7]

History

Archie Blake presented his canonical form at a meeting of the American Mathematical Society in 1932,[8] and in his 1937 dissertation. He called it the "simplified canonical form";[9][10][11][12] it was named the "Blake canonical form" by Frank Markham Brown (d) and Sergiu Rudeanu (d) in 1986–1990.[13][1] Together with Platon Poretsky's work[14] it is also referred to as "Blake–Poretsky laws".[15][clarification needed]

Methods for calculation

Blake discussed three methods for calculating the canonical form: exhaustion of implicants, iterated consensus, and multiplication. The iterated consensus method was rediscovered[1] by Edward W. Samson and Burton E. Mills,[16] Willard Quine,[17] and Kurt Bing.[18][19]

See also

References

  1. ↑ 1.0 1.1 1.2 1.3 "Chapter 3: The Blake Canonical Form". Boolean Reasoning - The Logic of Boolean Equations (reissue of 2nd ed.). Mineola, New York: Dover Publications, Inc.. 2012. pp. 4, 77ff, 81. ISBN 978-0-486-42785-0.  [1]
  2. ↑ "Ternary Decision Diagrams and their Applications". Representations of Discrete Functions. 1996. p. 278. doi:10.1007/978-1-4613-1385-4_12. ISBN 978-0792397205. 
  3. ↑ 3.0 3.1 Foundations of Digital Logic Design. 1998. p. 177. ISBN 978-9-81023110-1. https://books.google.com/books?id=4sX9fTGRo7QC. 
  4. ↑ Combinatorial Algorithms, Part 1. The Art of Computer Programming. 4A. 2011. p. 54. 
  5. ↑ "Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries". Journal of Computer and System Sciences 75: 13–25 [13–14]. 2009. doi:10.1016/j.jcss.2008.07.007. 
  6. ↑ "A Method for Producing a Boolean Function Having an Arbitrary Prescribed Prime Implicant Table". IEEE Transactions on Computers 14: 485–488. 1965. 
  7. ↑ "Boolesche Minimalpolynome und Überdeckungsprobleme" (in de). Acta Informatica 4 (4): 321–336. 1974. doi:10.1007/BF00289615. 
  8. ↑ "Canonical expressions in Boolean algebra". Bulletin of the American Mathematical Society. Abstracts of Papers: 805. November 1932. 
  9. ↑ Canonical expressions in Boolean algebra (Dissertation). Department of Mathematics, University of Chicago: University of Chicago Libraries. 1937. 
  10. ↑ "Canonical expressions in Boolean algebra". The Journal of Symbolic Logic 3 (2). 1938. 
  11. ↑ "Corrections to Canonical Expressions in Boolean Algebra". The Journal of Symbolic Logic 3 (3): 112–113. September 1938. doi:10.2307/2267595. 
  12. ↑ McKinsey, John Charles Chenoweth, ed (June 1938). "Blake, Archie. Canonical expressions in Boolean algebra, Department of Mathematics, University of Chicago, 1937". The Journal of Symbolic Logic 3 (2:93): 93. doi:10.2307/2267634. https://www.researchgate.net/publication/275744873. 
  13. ↑ A Functional Approach to the Theory of Prime Implicants, Publication de l'institut mathématique, Nouvelle série, 40, 1986, pp. 23–32 
  14. ↑ "O sposobach reschenija lopgischeskich rawenstw i ob obrathom spocobe matematischeskoi logiki" (in ru). Collected Reports of Meetings of Physical and Mathematical Sciences Section of Naturalists' Society of Kazan University (2). 1884.  (NB. This publication is also referred to as "On methods of solution of logical equalities and on inverse method of mathematical logic".)
  15. ↑ "1.10 Venjunctive Properties (Basic Formulae)". written at Riga, Latvia. Asynchronous Operators of Sequential Logic: Venjunction & Sequention — Digital Circuits Analysis and Design. Lecture Notes in Electrical Engineering (LNEE). 101 (1 ed.). Berlin / Heidelberg, Germany: Springer-Verlag. 2011. p. 20. doi:10.1007/978-3-642-21611-4. ISBN 978-3-642-21610-7.  (xiii+1+123+7 pages) (NB. The back cover of this book erroneously states volume 4, whereas it actually is volume 101.)
  16. ↑ Circuit Minimization: Algebra and Algorithms for New Boolean Canonical Expressions (Technical Report). Bedford, Massachusetts, USA: Air Force Cambridge Research Center. April 1954. AFCRC TR 54-21. 
  17. ↑ "A Way to Simplify Truth Functions". The American Mathematical Monthly 62 (9): 627–631. November 1955. doi:10.2307/2307285. 
  18. ↑ "On simplifying propositional formulas". Bulletin of the American Mathematical Society 61: 560. 1955. 
  19. ↑ "On simplifying truth-functional formulas". The Journal of Symbolic Logic 21 (3): 253–254. 1956. doi:10.2307/2269097. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Blake_canonical_form&oldid=3374701"