{{Short description|Standard form of Boolean function}} {{Use dmy dates|date=April 2020|cs1-dates=y}} {{Use list-defined references|date=May 2023}} [[File:Karnaugh map KV 4mal4 Gruppe01a.svg|thumb|Karnaugh map of {{color|green|''{{overline|A}}B''}} + {{color|red|''{{overline|BC}}''}} + {{color|blue|''{{overline|AC}}''}}, a sum of all prime implicants (each rendered in a different color). Deleting {{color|blue|''{{overline|AC}}''}} results in a minimal sum.]] {{multiple image|perrow=2|caption_align=center |image1=Karnaugh map KV 4mal4 18.svg |caption1={{color|red|''{{overline|ABD}}''}} + {{color|blue|''{{overline|A}}BC''}} + {{color|green|''ABD''}} + {{color|magenta|''A{{overline|BC}}''}} |image2=Karnaugh map KV 4mal4 19.svg |caption2={{color|magenta|''{{overline|A}}C{{overline|D}}''}} + {{color|green|''BCD''}} + {{color|blue|''A{{overline|C}}D''}} + {{color|red|''{{overline|BCD}}''}} |footer=Boolean function with two different minimal forms. The Blake canonical form is the sum of the two. }} In Boolean logic, a formula for a Boolean function ''f'' is in '''Blake canonical form''' ('''BCF'''),<ref name="Brown_2012"/> also called the '''complete sum of prime implicants''',<ref name="Sasao_1996"/> the '''complete sum''',<ref name="Kandel_1998"/> or the '''disjunctive prime form''',<ref name="Knuth_2011"/> when it is a disjunction of all the prime implicants of ''f''.<ref name="Brown_2012"/>
==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.<ref name="Kandel_1998"/> 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,<ref name="Feldman_2009"/> so is NP-hard.<ref name="Gimpel_1965"/><ref name="Paul_1974"/>
==History== Archie Blake presented his canonical form at a meeting of the American Mathematical Society in 1932,<ref name="Blake_1932"/> and in his 1937 dissertation. He called it the "simplified canonical form";<ref name="Blake_1937"/><ref name="Blake_1938_1"/><ref name="Blake_1938_2"/><ref name="Kinsey_1938"/> it was named the "Blake canonical form" by {{ill|Frank Markham Brown|d|Q112500339}} and {{ill|Sergiu Rudeanu|d|Q64217563}} in 1986–1990.<ref name="Brown_1986"/><ref name="Brown_2012"/> Together with Platon Poretsky's work<ref name="Poretsky_1884"/> it is also referred to as "Blake–Poretsky laws".<ref name="Vasyukevich_2011"/>{{Clarify|reason=What exactly is referred to as Blake-Poretsky laws?|date=December 2023}}
==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<ref name="Brown_2012"/> by Edward W. Samson and Burton E. Mills,<ref name="Samson_1954"/> Willard Quine,<ref name="Quine_1955"/> and Kurt Bing.<ref name="Bing_1955"/><ref name="Bing_1956"/> In 2022, Milan Mossé, Harry Sha, and Li-Yang Tan discovered a near-optimal algorithm for computing the Blake canonical form of a formula in conjunctive normal form.<ref>{{Cite journal |last1=Mossé |first1=Milan |last2=Sha |first2=Harry |last3=Tan |first3=Li-Yang |date=2022 |title=A Generalization of the Satisfiability Coding Lemma and Its Applications |journal=DROPS-IDN/V2/Document/10.4230/LIPIcs.SAT.2022.9 |series=Leibniz International Proceedings in Informatics (LIPIcs) |volume=236 |pages=9:1–9:18 |language=en |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |doi=10.4230/LIPIcs.SAT.2022.9|doi-access=free |isbn=978-3-95977-242-6 }}</ref>
==See also== * Poretsky law * Horn clause * Quine–McCluskey algorithm
==References== <references>
<ref name="Brown_2012">{{cite book |title=Boolean Reasoning - The Logic of Boolean Equations |chapter=Chapter 3: The Blake Canonical Form |author-first=Frank Markham |author-last=Brown |author-link=:d:Q112500339 |edition=<!-- 2012 -->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}} [<!-- 1st edition -->https://www2.fiit.stuba.sk/~kvasnicka/Free%20books/Brown_Boolean%20Reasoning.pdf<!-- https://web.archive.org/web/20170416231752/https://www2.fiit.stuba.sk/~kvasnicka/Free%20books/Brown_Boolean%20Reasoning.pdf -->]</ref> <ref name="Sasao_1996">{{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}}</ref> <ref name="Kandel_1998">{{cite book |author-first=Abraham |author-last=Kandel |title=Foundations of Digital Logic Design |page=177 |isbn=978-9-81023110-1 |date=1998 |publisher=World Scientific |url=https://books.google.com/books?id=4sX9fTGRo7QC}}</ref> <ref name="Knuth_2011">{{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}}</ref> <ref name="Feldman_2009">{{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 [13–14] |date=2009 |doi=10.1016/j.jcss.2008.07.007|doi-access=free }}</ref> <ref name="Gimpel_1965">{{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}}</ref> <ref name="Paul_1974">{{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}}</ref> <ref name="Blake_1932">{{cite journal |author-first=Archie |author-last=Blake |author-link=Archie Blake (mathematician) |title=Canonical expressions in Boolean algebra |series=Abstracts of Papers |journal=Bulletin of the American Mathematical Society |date=November 1932 |page=805}}</ref> <ref name="Blake_1937">{{cite book |title=Canonical expressions in Boolean algebra |author-first=Archie |author-last=Blake |author-link=Archie Blake (mathematician) |type=Dissertation |publisher=University of Chicago Libraries |location=Department of Mathematics, University of Chicago |date=1937}}</ref> <ref name="Blake_1938_1">{{cite journal |title=Canonical expressions in Boolean algebra |author-first=Archie |author-last=Blake |author-link=Archie Blake (mathematician) |journal=The Journal of Symbolic Logic |volume=3 |number=2 |date=1938}}</ref> <ref name="Blake_1938_2">{{cite journal |author-first=Archie |author-last=Blake |author-link=Archie Blake (mathematician) |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|s2cid=5810863 }}</ref> <ref name="Kinsey_1938">{{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 |s2cid=122640691 |url=https://www.researchgate.net/publication/275744873}}</ref> <ref name="Samson_1954">{{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}}</ref> <ref name="Quine_1955">{{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}}</ref> <ref name="Bing_1955">{{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}}</ref> <ref name="Bing_1956">{{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|s2cid=37877557 }}</ref> <ref name="Brown_1986">{{citation |author-first1=Frank Markham |author-last1=Brown |author-link1=:d:Q112500339 |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 |pages=[http://elib.mi.sanu.ac.rs/files/journals/publ/60/n054p023.pdf 23–32]}}</ref> <ref name="Poretsky_1884">{{cite journal |script-title=ru:О способах решения логических равенств и об обратном способе |title=O sposobach reschenija lopgischeskich rawenstw i ob obrathom spocobe matematischeskoi logiki |language=ru |trans-title=On methods of solving logical equalities and the inverse method of mathematical logic. An essay in construction of a complete and accessible theory of deduction on qualitative forms |author-first=Platon Sergeevich |author-last=Poretsky |author-link=Platon Sergeevich Poretsky |journal=Collected Reports of Meetings of Physical and Mathematical Sciences Section of Naturalists' Society of Kazan University |issue<!-- or volume? -->=2 |date=1884}} (NB. This publication is also referred to as "On methods of solution of logical equalities and on inverse method of mathematical logic".)</ref> <ref name="Vasyukevich_2011">{{cite book |author-first=Vadim O. |author-last=Vasyukevich |title=Asynchronous Operators of Sequential Logic: Venjunction & Sequention — Digital Circuits Analysis and Design |chapter=1.10 Venjunctive Properties (Basic Formulae) |publisher=Springer-Verlag |publication-place=Berlin / Heidelberg, Germany |location=Riga, Latvia |date=2011 |edition=1 |series=Lecture Notes in Electrical Engineering (LNEE) |volume=101 |isbn=978-3-642-21610-7 |doi=10.1007/978-3-642-21611-4 |issn=1876-1100 |lccn=2011929655 |page=20 |quote-page=20 |quote=}} (xiii+1+123+7 pages) (NB. The back cover of this book erroneously states volume 4, whereas it actually is volume 101.)</ref>
</references>
Category:Normal forms (logic) {{Normal forms in logic}}