Blake canonical form
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/16/Karnaugh_map_KV_4mal4_Gruppe01a.svg/220px-Karnaugh_map_KV_4mal4_Gruppe01a.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0c/Karnaugh_map_KV_4mal4_18.svg/200px-Karnaugh_map_KV_4mal4_18.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/Karnaugh_map_KV_4mal4_19.svg/200px-Karnaugh_map_KV_4mal4_19.svg.png)
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 and 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[]
- ^ 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]
- ^ 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.
- ^ a b Kandel, Abraham (1998). Foundations of Digital Logic Design. p. 177. ISBN 978-9-81023110-1.
- ^ Knuth, Donald Ervin (2011). Combinatorial Algorithms, Part 1. The Art of Computer Programming. Vol. 4A. p. 54.
- ^ Feldman, Vitaly (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.
- ^ 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.
- ^ Paul, Wolfgang Jakob (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (in German). 4 (4): 321–336. doi:10.1007/BF00289615. S2CID 35973949.
- ^ Blake, Archie (November 1932). "Canonical expressions in Boolean algebra". Bulletin of the American Mathematical Society. Abstracts of Papers: 805.
- ^ Blake, Archie (1937). Canonical expressions in Boolean algebra (Dissertation). Department of Mathematics, University of Chicago: University of Chicago Libraries.
- ^ 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.
- ^ 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.
- ^ Brown, Frank Markham; Rudeanu, Sergiu (1986), A Functional Approach to the Theory of Prime Implicants, Publication de l'institut mathématique, Nouvelle série, vol. 40, pp. 23–32
- ^ 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.
- ^ 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.
- ^ Bing, Kurt (1955). "On simplifying propositional formulas". Bulletin of the American Mathematical Society. 61: 560.
- ^ Bing, Kurt (1956). "On simplifying truth-functional formulas". The Journal of Symbolic Logic. 21 (3): 253–254. doi:10.2307/2269097. JSTOR 2269097.
- Normal forms (logic)