Blake canonical form

In Boolean logic, a formula for a Boolean function f is in Blake canonical form, also called the complete sum of prime implicants,[1] the complete sum,[2] or the disjunctive prime form,[3] when it is a disjunction of all the prime implicants of f.[4] Blake canonical form is a 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.[2]

It was introduced in 1937 by Archie Blake, who called it the "simplified canonical form";[5] it was named in honor of Blake by Frank Markham Brown in 1990.[4]

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.[4]

See also

Notes

  1. Tsutomu Sasao, "Ternary Decision Diagrams and their Applications", in Tsutomu Sasao, Masahira Fujita, eds., Representations of Discrete Functions ISBN 0792397207, 1996, p. 278
  2. 1 2 Abraham Kandel, Foundations of Digital Logic Design, p. 177
  3. Donald E. Knuth, The Art of Computer Programming 4A: Combinatorial Algorithms, Part 1, 2011, p. 54
  4. 1 2 3 Frank Markham Brown, "The Blake Canonical Form", chapter 4 of Boolean Reasoning: The Logic of Boolean Equations, ISBN 0486427854, 2nd edition, 2012, p. 77ff (first edition, 1990)
  5. "Canonical expressions in Boolean algebra", Dissertation, Dept. of Mathematics, U. of Chicago, 1937, reviewed in J. C. C. McKinsey, The Journal of Symbolic Logic 3:2:93 (June 1938) doi:10.2307/2267634 JSTOR 2267634


This article is issued from Wikipedia - version of the 11/17/2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.