Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Blake canonical form
open-in-new
<h2 id="relation-to-other-forms">Relation to other forms</h2> <p>The Blake canonical form is a special case of <a href="/facts/Disjunctive_normal_form/hsw2pRPu">disjunctive normal form</a>. </p><p>The Blake canonical form is not necessarily <a href="/facts/Boolean_minimization/7wSV4nut">minimal</a> (upper diagram), however all the terms of a minimal sum are contained in the Blake canonical form.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> On the other hand, the Blake canonical form is a <a href="/facts/Canonical_form/K2jhB44k">canonical form</a>, that is, it is unique <a href="/facts/Up_to/ydz4ztzX">up to</a> 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 <a href="/facts/Set_cover_problem/MVzyBYs1">set cover problem</a>,<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> so is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a><a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> </p> <h2 id="history">History</h2> <p><a href="/facts/Archie_Blake_(mathematician)/mWbn52zY">Archie Blake</a> presented his canonical form at a meeting of the <a href="/facts/American_Mathematical_Society/fr5gotCt">American Mathematical Society</a> in 1932,<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> and in his 1937 dissertation. He called it the "simplified canonical form";<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a><a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a><a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a><a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> it was named the "Blake canonical form" by Frank Markham Brown [d] and Sergiu Rudeanu [d] in 1986–1990.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a><a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> Together with <a href="/facts/Platon_Poretsky/upBjL5lJ">Platon Poretsky</a>'s work<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> it is also referred to as "Blake–Poretsky laws".<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> </p> <h2 id="methods-for-calculation">Methods for calculation</h2> <p>Blake discussed three methods for calculating the canonical form: exhaustion of implicants, iterated <a href="/facts/Consensus_(boolean_algebra)/D3g60g8a">consensus</a>, and multiplication. The iterated consensus method was rediscovered<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> by Edward W. Samson and Burton E. Mills,<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> <a href="/facts/Willard_van_Orman_Quine/2RrhATxa">Willard Quine</a>,<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a> and Kurt Bing.<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a><a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a> 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 <a href="/facts/Conjunctive_normal_form/B3sY1lTW">conjunctive normal form</a>.<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Poretsky_law/X13du6fa">Poretsky law</a></li> <li><a href="/facts/Horn_clause/3IRKqnp1">Horn clause</a></li> <li><a href="/facts/Quine%E2%80%93McCluskey_algorithm/pXl5Ezor">Quine–McCluskey algorithm</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Brown, Frank Markham [at Wikidata] (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. 4, 77ff, 81. ISBN 978-0-486-42785-0. [1] <a href="978-0-486-42785-0" target="_blank">978-0-486-42785-0</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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 href="978-0792397205" target="_blank">978-0792397205</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Kandel, Abraham (1998). Foundations of Digital Logic Design. World Scientific. p. 177. ISBN 978-9-81023110-1. <a href="978-9-81023110-1" target="_blank">978-9-81023110-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Knuth, Donald Ervin (2011). Combinatorial Algorithms, Part 1. The Art of Computer Programming. Vol. 4A. p. 54. <a href="/wiki/Donald_Ervin_Knuth" target="_blank">/wiki/Donald_Ervin_Knuth</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Brown, Frank Markham [at Wikidata] (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. 4, 77ff, 81. ISBN 978-0-486-42785-0. [1] <a href="978-0-486-42785-0" target="_blank">978-0-486-42785-0</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Kandel, Abraham (1998). Foundations of Digital Logic Design. World Scientific. p. 177. ISBN 978-9-81023110-1. <a href="978-9-81023110-1" target="_blank">978-9-81023110-1</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Feldman, Vitaly [at Wikidata] (2009). "Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries". Journal of Computer and System Sciences. 75: 13–25 [13–14]. doi:10.1016/j.jcss.2008.07.007. <a href="https://www.wikidata.org/wiki/Q102311396" target="_blank">https://www.wikidata.org/wiki/Q102311396</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Gimpel, James F. (1965). "A Method for Producing a Boolean Function Having an Arbitrary Prescribed Prime Implicant Table". IEEE Transactions on Computers. 14: 485–488. <a href="/wiki/IEEE_Transactions_on_Computers" target="_blank">/wiki/IEEE_Transactions_on_Computers</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Paul, Wolfgang Jakob [in German] (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (in German). 4 (4): 321–336. doi:10.1007/BF00289615. S2CID 35973949. <a href="https://de.wikipedia.org/wiki/Wolfgang_Paul_(Informatiker)" target="_blank">https://de.wikipedia.org/wiki/Wolfgang_Paul_(Informatiker)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Blake, Archie (November 1932). "Canonical expressions in Boolean algebra". Bulletin of the American Mathematical Society. Abstracts of Papers: 805. <a href="/wiki/Archie_Blake_(mathematician)" target="_blank">/wiki/Archie_Blake_(mathematician)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Blake, Archie (1937). Canonical expressions in Boolean algebra (Dissertation). Department of Mathematics, University of Chicago: University of Chicago Libraries. <a href="/wiki/Archie_Blake_(mathematician)" target="_blank">/wiki/Archie_Blake_(mathematician)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Blake, Archie (1938). "Canonical expressions in Boolean algebra". The Journal of Symbolic Logic. 3 (2). <a href="/wiki/Archie_Blake_(mathematician)" target="_blank">/wiki/Archie_Blake_(mathematician)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Blake, Archie (September 1938). "Corrections to Canonical Expressions in Boolean Algebra". The Journal of Symbolic Logic. 3 (3): 112–113. doi:10.2307/2267595. JSTOR 2267595. S2CID 5810863. <a href="/wiki/Archie_Blake_(mathematician)" target="_blank">/wiki/Archie_Blake_(mathematician)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>McKinsey, John Charles Chenoweth, ed. (June 1938). "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. S2CID 122640691. <a href="/wiki/John_Charles_Chenoweth_McKinsey" target="_blank">/wiki/John_Charles_Chenoweth_McKinsey</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Brown, Frank Markham [at Wikidata]; Rudeanu, Sergiu [at Wikidata] (1986), A Functional Approach to the Theory of Prime Implicants, Publication de l'institut mathématique, Nouvelle série, vol. 40, pp. 23–32 <a href="https://www.wikidata.org/wiki/Q112500339" target="_blank">https://www.wikidata.org/wiki/Q112500339</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Brown, Frank Markham [at Wikidata] (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. 4, 77ff, 81. ISBN 978-0-486-42785-0. [1] <a href="978-0-486-42785-0" target="_blank">978-0-486-42785-0</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Poretsky, Platon Sergeevich (1884). "O sposobach reschenija lopgischeskich rawenstw i ob obrathom spocobe matematischeskoi logiki" О способах решения логических равенств и об обратном способе [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]. Collected Reports of Meetings of Physical and Mathematical Sciences Section of Naturalists' Society of Kazan University (in Russian) (2). (NB. This publication is also referred to as "On methods of solution of logical equalities and on inverse method of mathematical logic".) <a href="О способах решения логических равенств и об обратном способе" target="_blank">О способах решения логических равенств и об обратном способе</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Vasyukevich, Vadim O. (2011). "1.10 Venjunctive Properties (Basic Formulae)". Written at Riga, Latvia. Asynchronous Operators of Sequential Logic: Venjunction & Sequention — Digital Circuits Analysis and Design. Lecture Notes in Electrical Engineering (LNEE). Vol. 101 (1 ed.). Berlin / Heidelberg, Germany: Springer-Verlag. p. 20. doi:10.1007/978-3-642-21611-4. ISBN 978-3-642-21610-7. ISSN 1876-1100. LCCN 2011929655. (xiii+1+123+7 pages) (NB. The back cover of this book erroneously states volume 4, whereas it actually is volume 101.) <a href="978-3-642-21610-7" target="_blank">978-3-642-21610-7</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Brown, Frank Markham [at Wikidata] (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. 4, 77ff, 81. ISBN 978-0-486-42785-0. [1] <a href="978-0-486-42785-0" target="_blank">978-0-486-42785-0</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Samson, Edward Walter; Mills, Burton E. (April 1954). Circuit Minimization: Algebra and Algorithms for New Boolean Canonical Expressions (Technical Report). Bedford, Massachusetts, USA: Air Force Cambridge Research Center. AFCRC TR 54-21. <a href="/wiki/Air_Force_Cambridge_Research_Center" target="_blank">/wiki/Air_Force_Cambridge_Research_Center</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Quine, Willard Van Orman (November 1955). "A Way to Simplify Truth Functions". The American Mathematical Monthly. 62 (9): 627–631. doi:10.2307/2307285. hdl:10338.dmlcz/142789. JSTOR 2307285. <a href="/wiki/Willard_Van_Orman_Quine" target="_blank">/wiki/Willard_Van_Orman_Quine</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Bing, Kurt (1955). "On simplifying propositional formulas". Bulletin of the American Mathematical Society. 61: 560. <a href="/wiki/Bulletin_of_the_American_Mathematical_Society" target="_blank">/wiki/Bulletin_of_the_American_Mathematical_Society</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Bing, Kurt (1956). "On simplifying truth-functional formulas". The Journal of Symbolic Logic. 21 (3): 253–254. doi:10.2307/2269097. JSTOR 2269097. S2CID 37877557. <a href="/wiki/The_Journal_of_Symbolic_Logic" target="_blank">/wiki/The_Journal_of_Symbolic_Logic</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>Mossé, Milan; Sha, Harry; Tan, Li-Yang (2022). "A Generalization of the Satisfiability Coding Lemma and Its Applications". DROPS-IDN/V2/Document/10.4230/LIPIcs.SAT.2022.9. Leibniz International Proceedings in Informatics (LIPIcs). 236. Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 9:1–9:18. doi:10.4230/LIPIcs.SAT.2022.9. ISBN 978-3-95977-242-6. <a href="978-3-95977-242-6" target="_blank">978-3-95977-242-6</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> </ol>