Jump to content

Blake canonical form

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Jochen Burghardt (talk | contribs) at 19:01, 18 May 2023 (→See also: not quite relevant here, and linked from Poretsky law). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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] it was named the "Blake canonical form" by Frank Markham Brown [d] and Sergiu Rudeanu [d] in 1986–1990.[12][1]

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,[13] Willard Quine,[14] and Kurt Bing.[15][16]

See also

References

  1. ^ a b c d Brown, Frank Markham (2012) [2003, 1990]. "Chapter 3: The Blake Canonical Form". Boolean Reasoning - The Logic of Boolean Equations (reissue of 2nd ed.). Mineola, New York: Dover Publications, Inc. pp. 4, 77ff, 81. ISBN 978-0-486-42785-0. [1]
  2. ^ Sasao, Tsutomu (1996). "Ternary Decision Diagrams and their Applications". In Sasao, Tsutomu; Fujita, Masahira (eds.). Representations of Discrete Functions. p. 278. doi:10.1007/978-1-4613-1385-4_12. ISBN 978-0792397205.
  3. ^ a b Kandel, Abraham (1998). Foundations of Digital Logic Design. p. 177. ISBN 978-9-81023110-1.
  4. ^ Knuth, Donald Ervin (2011). Combinatorial Algorithms, Part 1. The Art of Computer Programming. Vol. 4A. p. 54.
  5. ^ Feldman, Vitaly [at Wikidata] (2009). "Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries". Journal of Computer and System Sciences. 75: 13–25 [13–14]. doi:10.1016/j.jcss.2008.07.007.
  6. ^ Gimpel, James F. (1965). "A Method for Producing a Boolean Function Having an Arbitrary Prescribed Prime Implicant Table". IEEE Transactions on Computers. 14: 485–488.
  7. ^ Paul, Wolfgang Jakob [in German] (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (in German). 4 (4): 321–336. doi:10.1007/BF00289615. S2CID 35973949.
  8. ^ Blake, Archie (November 1932). "Canonical expressions in Boolean algebra". Bulletin of the American Mathematical Society. Abstracts of Papers: 805.
  9. ^ Blake, Archie (1937). Canonical expressions in Boolean algebra (Dissertation). Department of Mathematics, University of Chicago: University of Chicago Libraries.
  10. ^ Blake, Archie (September 1938). "Corrections to Canonical Expressions in Boolean Algebra". The Journal of Symbolic Logic. 3 (3): 112–113. doi:10.2307/2267595. JSTOR 2267595.
  11. ^ 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 (Review). 3 (2:93): 93. doi:10.2307/2267634. JSTOR 2267634.
  12. ^ Brown, Frank Markham; Rudeanu, Sergiu [at Wikidata] (1986), A Functional Approach to the Theory of Prime Implicants, Publication de l'institut mathématique, Nouvelle série, vol. 40, pp. 23–32
  13. ^ Samson, Edward Walter; Mills, Burton E. (April 1954). Circuit Minimization: Algebra and Algorithms for New Boolean Canonical Expressions (Technical Report). Bedford, Massachusetts, USA: Air Force Cambridge Research Center. AFCRC TR 54-21.
  14. ^ Quine, Willard Van Orman (November 1955). "A Way to Simplify Truth Functions". The American Mathematical Monthly. 62 (9): 627–631. doi:10.2307/2307285. hdl:10338.dmlcz/142789. JSTOR 2307285.
  15. ^ Bing, Kurt (1955). "On simplifying propositional formulas". Bulletin of the American Mathematical Society. 61: 560.
  16. ^ Bing, Kurt (1956). "On simplifying truth-functional formulas". The Journal of Symbolic Logic. 21 (3): 253–254. doi:10.2307/2269097. JSTOR 2269097.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Blake_canonical_form&oldid=1155567784"