Blake canonical form: Difference between revisions
move diagram to more appropriate place |
The page is already in the footnote: 77ff. |
||
| Line 8: | Line 8: | ||
==History== |
==History== |
||
It was introduced in 1937 by Archie Blake, who called it the "simplified canonical form";<ref name="Blake_1937"/><ref name="Kinsey_1938"/> it was named in honor of Blake by Frank Markham Brown in 1990.<ref name="Brown_2012"/> |
It was introduced in 1937 by Archie Blake, who called it the "simplified canonical form";<ref name="Blake_1937"/><ref name="Kinsey_1938"/> it was named in honor of Blake by Frank Markham Brown in 1990.<ref name="Brown_2012"/> |
||
==Methods for calculation== |
==Methods for calculation== |
||
Revision as of 18:22, 30 December 2019
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, 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 unique, whereas there can be multiple minimal forms.
History
It was introduced in 1937 by Archie Blake, who called it the "simplified canonical form";[5][6] it was named in honor of Blake by Frank Markham Brown in 1990.[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 by Samson and Mills, Quine, and Bing.[1]
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. 77ff. 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 9789810231101.
- ^ Donald E. Knuth, The Art of Computer Programming 4A: Combinatorial Algorithms, Part 1, 2011, p. 54
- ^ Blake, Archie (1937). Canonical expressions in Boolean algebra (Dissertation). Department of Mathematics, University of Chicago: University of Chicago Libraries.
- ^ McKinsey, J. C. C. (June 1938). McKinsey, J. C. C. (ed.). "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.