[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/2016\/07\/27\/blake-canonical-form-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki24\/2016\/07\/27\/blake-canonical-form-wikipedia\/","headline":"Blake canonical form &#8211; Wikipedia","name":"Blake canonical form &#8211; Wikipedia","description":"From Wikipedia, the free encyclopedia Standard form of Boolean function Karnaugh map of AB + BC + AC, a sum","datePublished":"2016-07-27","dateModified":"2016-07-27","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/1\/16\/Karnaugh_map_KV_4mal4_Gruppe01a.svg\/220px-Karnaugh_map_KV_4mal4_Gruppe01a.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/1\/16\/Karnaugh_map_KV_4mal4_Gruppe01a.svg\/220px-Karnaugh_map_KV_4mal4_Gruppe01a.svg.png","height":"220","width":"220"},"url":"https:\/\/wiki.edu.vn\/en\/wiki24\/2016\/07\/27\/blake-canonical-form-wikipedia\/","about":["Wiki"],"wordCount":3717,"articleBody":"From Wikipedia, the free encyclopediaStandard form of Boolean function  Karnaugh map of AB + BC + AC, a sum of all prime implicants (each rendered in a different color). Deleting AC results in a minimal sum.ABD + ABC + ABD + ABCACD + BCD + ACD + BCDBoolean 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),[1] also called the complete sum of prime implicants,[2] the complete sum,[3] or the disjunctive prime form,[4] when it is a disjunction of all the prime implicants of f.[1]Table of ContentsRelation to other forms[edit]History[edit]Methods for calculation[edit]See also[edit]References[edit]Relation to other forms[edit]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.[3] 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,[5] so is NP-hard.[6][7]History[edit]Archie Blake presented his canonical form at a meeting of the American Mathematical Society in 1932,[8] and in his 1937 dissertation. He called it the &#8220;simplified canonical form&#8221;;[9][10][11] it was named the &#8220;Blake canonical form&#8221; by Frank Markham Brown\u00a0[d] and Sergiu Rudeanu\u00a0[d] in 1986\u20131990.[12][1]Methods for calculation[edit]Blake discussed three methods for calculating the canonical form: exhaustion of implicants, iterated consensus, and multiplication. The iterated consensus method was rediscovered[1] by Edward W. Samson and Burton E. Mills,[13]Willard Quine,[14] and Kurt Bing.[15][16]See also[edit]References[edit]^ a b c d Brown, Frank Markham (2012) [2003, 1990]. &#8220;Chapter 3: The Blake Canonical Form&#8221;. Boolean Reasoning &#8211; The Logic of Boolean Equations (reissue of 2nd\u00a0ed.). Mineola, New York: Dover Publications, Inc. pp.\u00a04, 77ff, 81. ISBN\u00a0978-0-486-42785-0. [1]^ Sasao, Tsutomu (1996). &#8220;Ternary Decision Diagrams and their Applications&#8221;.  In Sasao, Tsutomu; Fujita, Masahira (eds.). Representations of Discrete Functions. p.\u00a0278. doi:10.1007\/978-1-4613-1385-4_12. ISBN\u00a0978-0792397205.^ a b Kandel, Abraham (1998). Foundations of Digital Logic Design. p.\u00a0177. ISBN\u00a0978-9-81023110-1.^ Knuth, Donald Ervin (2011). Combinatorial Algorithms, Part 1. The Art of Computer Programming. Vol.\u00a04A. p.\u00a054.^ Feldman, Vitaly [at Wikidata] (2009). &#8220;Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries&#8221;. Journal of Computer and System Sciences. 75: 13\u201325 [13\u201314]. doi:10.1016\/j.jcss.2008.07.007.^ Gimpel, James F. (1965). &#8220;A Method for Producing a Boolean Function Having an Arbitrary Prescribed Prime Implicant Table&#8221;. IEEE Transactions on Computers. 14: 485\u2013488.^ Paul, Wolfgang Jakob [in German] (1974). &#8220;Boolesche Minimalpolynome und \u00dcberdeckungsprobleme&#8221;. Acta Informatica (in German). 4 (4): 321\u2013336. doi:10.1007\/BF00289615. S2CID\u00a035973949.^ Blake, Archie (November 1932). &#8220;Canonical expressions in Boolean algebra&#8221;. Bulletin of the American Mathematical Society. Abstracts of Papers: 805.^ Blake, Archie (1937). Canonical expressions in Boolean algebra (Dissertation). Department of Mathematics, University of Chicago: University of Chicago Libraries.^ Blake, Archie (September 1938). &#8220;Corrections to Canonical Expressions in Boolean Algebra&#8220;. The Journal of Symbolic Logic. 3 (3): 112\u2013113. doi:10.2307\/2267595. JSTOR\u00a02267595.^ McKinsey, John Charles Chenoweth, ed. (June 1938). &#8220;Blake, Archie. Canonical expressions in Boolean algebra, Department of Mathematics, University of Chicago, 1937&#8221;. The Journal of Symbolic Logic (Review). 3 (2:93): 93. doi:10.2307\/2267634. JSTOR\u00a02267634.^ Brown, Frank Markham; Rudeanu, Sergiu [at Wikidata] (1986), A Functional Approach to the Theory of Prime Implicants, Publication de l&#8217;institut math\u00e9matique, Nouvelle s\u00e9rie, vol.\u00a040, pp.\u00a023\u201332^ 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.^ Quine, Willard Van Orman (November 1955). &#8220;A Way to Simplify Truth Functions&#8221;. The American Mathematical Monthly. 62 (9): 627\u2013631. doi:10.2307\/2307285. hdl:10338.dmlcz\/142789. JSTOR\u00a02307285.^ Bing, Kurt (1955). &#8220;On simplifying propositional formulas&#8221;. Bulletin of the American Mathematical Society. 61: 560.^ Bing, Kurt (1956). &#8220;On simplifying truth-functional formulas&#8221;. The Journal of Symbolic Logic. 21 (3): 253\u2013254. doi:10.2307\/2269097. JSTOR\u00a02269097."},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/2016\/07\/27\/blake-canonical-form-wikipedia\/#breadcrumbitem","name":"Blake canonical form &#8211; Wikipedia"}}]}]