Blake canonical form: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
→‎See also: not quite relevant here, and linked from Poretsky law
CE, added ref
Line 1: Line 1:
{{Short description|Standard form of Boolean function}}
{{Short description|Standard form of Boolean function}}
{{Use dmy dates|date=April 2020|cs1-dates=y}}[[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.]]
{{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
{{multiple image|perrow=2|caption_align=center
|image1=Karnaugh map KV 4mal4 18.svg
|image1=Karnaugh map KV 4mal4 18.svg
Line 11: Line 13:


==Relation to other forms==
==Relation to other forms==

The Blake canonical form is a special case of [[disjunctive normal form]].
The Blake canonical form is a special case of [[disjunctive normal form]].


Line 17: Line 18:


==History==
==History==
[[Archie Blake (mathematician)|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"/><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"/>
[[Archie Blake (mathematician)|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 groundlaying work<ref name="Poretsky_1884"/> it is also referred to as "Blake–Poretsky laws".<ref name="Vasyukevich_2011"/>


==Methods for calculation==
==Methods for calculation==
Line 39: Line 40:
<ref name="Blake_1932">{{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}}</ref>
<ref name="Blake_1932">{{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}}</ref>
<ref name="Blake_1937">{{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}}</ref>
<ref name="Blake_1937">{{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}}</ref>
<ref name="Blake_1938">{{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}}</ref>
<ref name="Blake_1938_1">{{cite journal |title=Canonical expressions in Boolean algebra |author-first=Archie |author-last=Blake |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 |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}}</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 |url=https://www.researchgate.net/publication/275744873}}</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 |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="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>
Line 46: Line 48:
<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}}</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}}</ref>
<ref name="Brown_1986">{{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 |pages=[http://elib.mi.sanu.ac.rs/files/journals/publ/60/n054p023.pdf 23–32]}}</ref>
<ref name="Brown_1986">{{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 |pages=[http://elib.mi.sanu.ac.rs/files/journals/publ/60/n054p023.pdf 23–32]}}</ref>
<ref name="Poretsky_1884">{{cite journal |title= |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>
}}
}}


Revision as of 19:24, 18 May 2023

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 + ABC
ACD + BCD + ACD + BCD
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),[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]

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.[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

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 "simplified canonical form";[9][10][11][12] it was named the "Blake canonical form" by Frank Markham Brown [d] and Sergiu Rudeanu [d] in 1986–1990.[13][1] Together with Platon Poretsky's groundlaying work[14] it is also referred to as "Blake–Poretsky laws".[15]

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[1] by Edward W. Samson and Burton E. Mills,[16] Willard Quine,[17] and Kurt Bing.[18][19]

See also

References

  1. ^ a b c d Brown, Frank Markham (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]
  2. ^ 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.
  3. ^ a b Kandel, Abraham (1998). Foundations of Digital Logic Design. p. 177. ISBN 978-9-81023110-1.
  4. ^ Knuth, Donald Ervin (2011). Combinatorial Algorithms, Part 1. The Art of Computer Programming. Vol. 4A. p. 54.
  5. ^ 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.
  6. ^ 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.
  7. ^ Paul, Wolfgang Jakob [in German] (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (in German). 4 (4): 321–336. doi:10.1007/BF00289615. S2CID 35973949.
  8. ^ Blake, Archie (November 1932). "Canonical expressions in Boolean algebra". Bulletin of the American Mathematical Society. Abstracts of Papers: 805.
  9. ^ Blake, Archie (1937). Canonical expressions in Boolean algebra (Dissertation). Department of Mathematics, University of Chicago: University of Chicago Libraries.
  10. ^ Blake, Archie (1938). "Canonical expressions in Boolean algebra". The Journal of Symbolic Logic. 3 (2).
  11. ^ 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.
  12. ^ 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.
  13. ^ Brown, Frank Markham; 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
  14. ^ Poretsky, Platon Sergeevich (1884). [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). {{cite journal}}: |trans-title= requires |title= or |script-title= (help) (NB. This publication is also referred to as "On methods of solution of logical equalities and on inverse method of mathematical logic".)
  15. ^ 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.)
  16. ^ 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.
  17. ^ 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.
  18. ^ Bing, Kurt (1955). "On simplifying propositional formulas". Bulletin of the American Mathematical Society. 61: 560.
  19. ^ Bing, Kurt (1956). "On simplifying truth-functional formulas". The Journal of Symbolic Logic. 21 (3): 253–254. doi:10.2307/2269097. JSTOR 2269097.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Blake_canonical_form&oldid=1155571414"