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.