Blake Canonical Form

In Boolean logic, a formula for a Boolean function ''f'' is in Blake canonical form (BCF), also called the complete sum of prime implicants, the complete sum, or the disjunctive prime form, when it is a disjunction of all the prime implicants of ''f''.

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. 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, so is NP-hard.

History

Archie Blake presented his canonical form at a meeting of the American Mathematical Society in 1932, and in his 1937 dissertation. He called it the "simplified canonical form"; it was named the "Blake canonical form" by and in 1986–1990.

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 Edward W. Samson and Burton E. Mills, Willard Quine, and Kurt Bing.

See also

* Horn clause
* Consensus theorem
* Quine–McCluskey algorithm

References

{{reflist, refs=
{{cite book , title=Boolean Reasoning - The Logic of Boolean Equations , chapter=Chapter 3: The Blake Canonical Form , author-first=Frank Markham , author-last=Brown , edition=reissue of 2nd , publisher=Dover Publications, Inc. , location=Mineola, New York , date=2012 , orig-date=2003, 1990 , isbn=978-0-486-42785-0 , pages=4, 77ff, 81}
https://web.archive.org/web/20170416231752/http://www2.fiit.stuba.sk/~kvasnicka/Free%20books/Brown_Boolean%20Reasoning.pdf -->
/ref>
{{cite book , author-first=Tsutomu , author-last=Sasao , chapter=Ternary Decision Diagrams and their Applications , editor-first1=Tsutomu , editor-last1=Sasao , editor-first2=Masahira , editor-last2=Fujita , title=Representations of Discrete Functions , isbn=978-0792397205 , date=1996 , page=278 , doi=10.1007/978-1-4613-1385-4_12
{{cite book , author-first=Abraham , author-last=Kandel , title=Foundations of Digital Logic Design , page=177 , isbn=978-9-81023110-1 , date=1998 , url=https://books.google.com/books?id=4sX9fTGRo7QC
{{cite book , author-first=Donald Ervin , author-last=Knuth , author-link=Donald Ervin Knuth , series=The Art of Computer Programming , volume=4A , title=Combinatorial Algorithms, Part 1 , date=2011 , page=54
{{cite journal , author-first=Vitaly , author-last=Feldman , author-link=:d:Q102311396 , title=Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries , journal=Journal of Computer and System Sciences , volume=75 , pages=13–25 3–14, date=2009 , doi=10.1016/j.jcss.2008.07.007, doi-access=free
{{cite journal , author-first=James F. , author-last=Gimpel , title=A Method for Producing a Boolean Function Having an Arbitrary Prescribed Prime Implicant Table , journal=IEEE Transactions on Computers , volume=14 , date=1965 , pages=485–488
{{cite journal , author-first=Wolfgang Jakob , author-last=Paul , author-link=:de:Wolfgang Paul (Informatiker) , title=Boolesche Minimalpolynome und Überdeckungsprobleme , language=de , journal=Acta Informatica , volume=4 , issue=4 , date=1974 , doi=10.1007/BF00289615 , pages=321–336 , s2cid=35973949
{{cite journal , author-first=Archie , author-last=Blake , title=Canonical expressions in Boolean algebra , series=Abstracts of Papers , journal=Bulletin of the American Mathematical Society , date=November 1932 , page=805
{{cite book , title=Canonical expressions in Boolean algebra , author-first=Archie , author-last=Blake , type=Dissertation , publisher= University of Chicago Libraries , location=Department of Mathematics, University of Chicago , date=1937
{{cite journal , author-first=Archie , author-last=Blake , title=Corrections to ''Canonical Expressions in Boolean Algebra'' , journal=The Journal of Symbolic Logic , volume=3 , number=3 , date=September 1938 , pages=112–113 , doi=10.2307/2267595 , jstor=2267595
{{cite journal , title=Blake, Archie. Canonical expressions in Boolean algebra, Department of Mathematics, University of Chicago, 1937 , type=Review , editor-first=John Charles Chenoweth , editor-last=McKinsey , editor-link=John Charles Chenoweth McKinsey , journal=The Journal of Symbolic Logic , volume=3 , pages=93 , number=2:93 , date=June 1938 , doi=10.2307/2267634 , jstor=2267634 , url=https://www.researchgate.net/publication/275744873
{{cite book , author-last1=Samson , author-first1=Edward Walter , author-last2=Mills , author-first2=Burton E. , date=April 1954 , title=Circuit Minimization: Algebra and Algorithms for New Boolean Canonical Expressions , publisher= Air Force Cambridge Research Center , type=Technical Report , id=AFCRC TR 54-21 , location=Bedford, Massachusetts, USA
{{cite journal , author-last=Quine , author-first=Willard Van Orman , author-link=Willard Van Orman Quine , date=November 1955 , title=A Way to Simplify Truth Functions , jstor=2307285 , journal=The American Mathematical Monthly , volume=62 , issue=9 , pages=627–631 , doi=10.2307/2307285 , hdl=10338.dmlcz/142789
{{cite journal , author-first=Kurt , author-last=Bing , title=On simplifying propositional formulas , journal=Bulletin of the American Mathematical Society , volume=61 , date=1955 , pages=560
{{cite journal , author-first=Kurt , author-last=Bing , title=On simplifying truth-functional formulas , journal=The Journal of Symbolic Logic , volume=21 , date=1956 , issue=3 , pages=253–254 , doi=10.2307/2269097 , jstor=2269097
{{citation , author-first1=Frank Markham , author-last1=Brown , author-first2=Sergiu , author-last2=Rudeanu , author-link2=:d:Q64217563 , title=A Functional Approach to the Theory of Prime Implicants , series=Publication de l'institut mathématique, Nouvelle série , volume=40 , number=54 , date=1986 , page
23–32
}

Normal forms (logic)