Quine–McCluskey algorithm: Difference between revisions

Revision as of 05:59, 5 October 2022

Revision as of 01:00, 30 November 2022

Line 202:

<ref name="Quine_1952">{{cite journal |last=Quine |first=Willard Van Orman |author-link=Willard Van Orman Quine |date=October 1952 |title=The Problem of Simplifying Truth Functions |jstor=2308219 |journal=[[The American Mathematical Monthly]] |volume=59 |issue=8 |pages=521–531 |doi=10.2307/2308219}}</ref>

<ref name="Quine_1955">{{cite journal |last=Quine |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="McCluskey_1956">{{cite journal |last=McCluskey |first=Edward Joseph Jr.|author-link=Edward Joseph McCluskey, Jr. |date=November 1956 |title=Minimization of Boolean Functions |journal=[[Bell System Technical Journal]] |volume=35 |issue=6 |pages=1417–1444 |doi=10.1002/j.1538-7305.1956.tb03835.x |url=https://archive.org/details/bstj35-6-1417 |access-date=2014-08-24 |hdl=10338.dmlcz/102933}}</ref>

<ref name="Nelson_1995">{{cite book |last1=Nelson |first1=Victor P. |first2=H. Troy |last2=Nagle |first3=Bill D. |last3=Carroll |first4=J. David |last4=Irwin |author-link4=J. David Irwin |date=1995 |title=Digital Logic Circuit Analysis and Design |url=https://books.google.com/books?id=8V5TAAAAMAAJ |publisher=[[Prentice Hall]] |page=234 |edition=2 |access-date=2014-08-26 |isbn=978-0-13463894-2}}</ref>

<ref name="Logic_Friday">[[Logic Friday]] program</ref>

Line 216:

<ref name="Mullin_Kellner_1958">{{cite journal |title=A Residue Test for Boolean Functions |first1=Albert Alkins |last1=Mullin |author-link1=Albert Alkins Mullin |first2=Wayne G. |last2=Kellner |journal=Transactions of the Illinois State Academy of Science |volume=51 |number=3–4 |date=1958<!-- |orig-date=November 1955 According to Caldwell --> |publication-place=Springfield, Illinois, USA |___location=University of Illinois, Urbana, USA and Electrical Engineering Department, [[Massachusetts Institute of Technology]], Massachusetts, USA |type=Teaching memorandum |s2cid=125171479 |pages=14–19 |url=https://ilacadofsci.com/wp-content/uploads/2016/03/051-16-print.pdf |access-date=2020-05-05 |url-status=live |archive-url=https://web.archive.org/web/20200505163915/https://ilacadofsci.com/wp-content/uploads/2016/03/051-16-print.pdf |archive-date=2020-05-05}} [https://ilacadofsci.com/archives/9279] (6 pages) (NB. In {{citeref|Caldwell|1958|his book|style=plain}}, Caldwell dates this to November 1955 as a teaching memorandum. Since Mullin dates their work to 1958 in {{citeref|Mullin|1960|another work|style=plain}} and Abrahams/Nordahl's {{citeref|Abrahams|Nordahl|1955|class memorandum|style=plain}} is also dated November 1955, this could be a copy error.)</ref>

<ref name="Mullin_1959">{{cite journal |title=Two Applications of Elementary Number Theory |first=Albert Alkins |last=Mullin |author-link=Albert Alkins Mullin |journal=Transactions of the Illinois State Academy of Science |volume=52 |number=3–4 |date=1960-03-15 |orig-date=1959-09-19 |___location=University of Illinois, Urbana, USA |publication-place=Springfield, Illinois, USA |editor-first1=Harvey I. |editor-last1=Fisher |editor-first2=George E. |editor-last2=Ekblaw |editor-first3=F. O. |editor-last3=Green |editor-first4=Reece |editor-last4=Jones |editor-first5=Francis |editor-last5=Kruidenier |editor-first6=John |editor-last6=McGregor |editor-first7=Paul |editor-last7=Silva |editor-first8=Milton |editor-last8=Thompson |pages=102–103 |url=https://ilacadofsci.com/wp-content/uploads/2016/03/052-15-print.pdf |access-date=2020-05-05 |url-status=live |archive-url=https://web.archive.org/web/20200505143916/https://ilacadofsci.com/wp-content/uploads/2016/03/052-15-print.pdf |archive-date=2020-05-05}} [https://ilacadofsci.com/archives/9203][https://archive.org/details/transactionsofil5219unse][https://archive.org/stream/transactionsofil5219unse/transactionsofil5219unse_djvu.txt] (2 pages)</ref>

<ref name="McCluskey_1960">{{cite journal |title=Albert A. Mullin and Wayne G. Kellner. A residue test for Boolean functions. Transactions of the Illinois State Academy of Science, vol. 51 nos. 3 and 4, (1958), pp. 14–19. |type=Review |last=McCluskey |first=Edward Joseph Jr.|author-link=Edward Joseph McCluskey, Jr. |journal=[[The Journal of Symbolic Logic]] |volume=25 |issue=2 |date=June 1960 |doi=10.2307/2964263 |page=185 |jstor=2964263 |s2cid=123530443 |quote-page=185 |quote=[...] The results of this paper are presented in the more readily available {{citeref|Caldwell|1958|book|style=plain}} by S. H. Caldwell [...<!-- XXIII 433 -->]. In this book, the author gives credit to {{citeref|Mullin|Kellner|1958|Mullin and Kellner|style=plain}} for development of the manipulations with the decimal numbers.}} (1 page)</ref>

<ref name="Kämmerer_1969">{{cite book |title=Digitale Automaten – Theorie, Struktur, Technik, Programmieren |language=de |chapter=I.12. Theorie: Minimierung Boolescher Funktionen |first=Wilhelm |last=Kämmerer |author-link=:de:Wilhelm Kämmerer |editor-first1=Hans |editor-last1=Frühauf |editor-link1=:de:Hans Frühauf |editor-first2=Wilhelm |editor-last2=Kämmerer |editor-first3=Kurz |editor-last3=Schröder |editor-first4=Helmut |editor-last4=Winkler |edition=1 |date=May 1969 |publisher=[[Akademie-Verlag GmbH]] |publication-place=Berlin, Germany |___location=Jena, Germany |volume=5 |id=License no. 202-100/416/69. Order no. 4666 ES 20 K 3. |series=Elektronisches Rechnen und Regeln |pages=98, 103–104 |url=https://books.google.com/books?id=jkcgAQAAIAAJ&q=P.+W.+Abraham+I.+G.+Nordahl |quote-page=98 |quote=[...] 1955 wurde das Verfahren auf die bequemere dezimale Schreibweise umgestellt ({{citeref|Abrahams|Nordahl|1955|P. W. Abraham und I. G. Nordahl|style=plain}} in [<nowiki/>{{citeref|Caldwell|1958|Caldwell|style=plain}}<nowiki/>]). [...]}} (NB. A second edition 1973 exists as well.<!-- where the relevant quote is located on page 99 rather than 98 -->)</ref>

<ref name="McColl_1878">{{cite journal |first=Hugh |last=McColl |author-link=Hugh McColl (mathematician) |date=1878-11-14 |title=The Calculus of Equivalent Statements (Third Paper) |journal=[[Proceedings of the London Mathematical Society]] |volume=s1-10<!-- or 10? --> |issue=1 |doi=10.1112/plms/s1-10.1.16 |pages=16–28 |url=https://academic.oup.com/plms/article-abstract/s1-10/1/16/1503062}}</ref>

<ref name="Blake_1932">{{cite journal |first=Archie |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 |last=Blake |first=Archie |date=1938 |orig-date=1937 |title=Canonical Expressions in Boolean Algebra |type=Dissertation |publisher=[[University of Chicago Libraries]] |___location=Chicago, Illinois, USA |edition=Lithographed |page=36 |url=https://books.google.com/books?id=gqRYAAAAMAAJ |quote-page=36 |quote=[...] this method was known to [[Charles Sanders Peirce|Peirce]] and his students [...] It is mentioned at several places in Studies in Logic, by members of the [[Johns Hopkins University]], 1883 [...]}} (ii+60 pages)</ref>

<ref name="Blake_1938">{{cite journal |first=Archie |last=Blake |title=Corrections to ''Canonical Expressions in Boolean Algebra'' |journal=[[The Journal of Symbolic Logic]] |issn=0022-4812 |publisher=[[Association for Symbolic Logic]] |volume=3 |issue=2 |date=June 1938 |doi=10.2307/2267595 |jstor=2267595 |url=https://projecteuclid.org/euclid.jsl/1183385465 |pages=112–113|s2cid=5810863 }}</ref>

<ref name="Samson_1954">{{cite book |last1=Samson |first1=Edward Walter |last2=Mills |first2=Burton E. |date=April 1954 |title=Circuit Minimization: Algebra and Algorithms for New Boolean Canonical Expressions |publisher=[[Air Force Cambridge Research Center]] |id=Technical Report AFCRC TR 54-21 |___location=Bedford, Massachusetts, USA}}</ref>

<ref name="Nelson_1955">{{cite journal |last=Nelson |first=Raymond J. |date=June 1955 |title=Simplest Normal Truth Functions |journal=[[The Journal of Symbolic Logic]] |publisher=[[Association for Symbolic Logic]] |volume=20 |issue=2 |doi=10.2307/2266893 |jstor=2266893 |pages=105–108|s2cid=32920372 }} (4 pages)</ref>

<ref name="Ladd_1883">{{cite book |last=Ladd |first=Christine |author-link=Christine Ladd |date=1883 |chapter=On the algebra of logic |editor-first=Charles Sanders |editor-last=Peirce |editor-link=Charles Sanders Peirce |title=Studies in Logic |___location=Boston, USA |publisher=[[Little, Brown & Company]] |pages=17–71 |quote-page=23 |quote=[...] If the reduction [of an expression to simplest form] is not evident, it may be facilitated by taking the negative of the expression, reducing it, and then restoring it to the positive form. [...]}}</ref>

<ref name="Fielder_1966">{{cite journal |title=Classroom Reduction of Boolean Functions |first=Daniel C. |last=Fielder |journal=[[IEEE Transactions on Education]] |publisher=[[IEEE]] |volume=9 |issue=4 |date=December 1966 |issn=0018-9359 |eissn=1557-9638 |doi=10.1109/TE.1966.4321989 |bibcode=1966ITEdu...9..202F |pages=202–205}}</ref>

<ref name="Brown_2010">{{cite journal |title=McColl and Minimization |journal=History and Philosophy of Logic |volume=31 |number=4 |pages=337–348 |publisher=[[Taylor & Francis]] |issn=1464-5149 |date=November 2010 |orig-date=2010-10-27 |doi=10.1080/01445340.2010.517387 |first=Frank Markham |last=Brown<!-- |author-link=Frank Markham Brown --> |s2cid=216590641 |url=https://www.researchgate.net/publication/233139704 |access-date=2020-04-15 |url-status=live |archive-url=https://web.archive.org/web/20200415201838/https://www.researchgate.net/publication/233139704_McColl_and_Minimization |archive-date=2020-04-15}}</ref>

<ref name="Majumder_2015">{{cite conference |title=Investigation on Quine McCluskey Method: A Decimal Manipulation Based Novel Approach for the Minimization of Boolean Function |first1=Alak |last1=Majumder |first2=Barnali |last2=Chowdhury |first3=Abir J. |last3=Mondal |first4=Kunj |last4=Jain |___location=Department of Electronics & Communication, Engineering National Institute of Technology, Arunachal Pradesh Yupia, India |date=2015-01-30 |orig-date=2015-01-09 |type=Conference paper |conference=2015 International Conference on Electronic Design, Computer Networks & Automated Verification (EDCAV), Shillong, India |doi=10.1109/EDCAV.2015.7060531 |pages=18–22 |url=https://www.researchgate.net/publication/301408055 |access-date=2020-05-08 |url-status=live |archive-url=https://web.archive.org/web/20200508200648/https://www.researchgate.net/publication/301408055_Investigation_on_Quine_McCluskey_method_A_decimal_manipulation_based_novel_approach_for_the_minimization_of_Boolean_function

|archive-date=2020-05-08}} [https://www.researchgate.net/profile/Alak_Majumder2/publication/301408055_Investigation_on_Quine_McCluskey_method_A_decimal_manipulation_based_novel_approach_for_the_minimization_of_Boolean_function/links/5948a1bba6fdcc70635a3706/Investigation-on-Quine-McCluskey-method-A-decimal-manipulation-based-novel-approach-for-the-minimization-of-Boolean-function.pdf] (NB. This work does not cite the prior art on decimal methods.) (5 pages)</ref>

<ref name="Holdsworth_2002">{{cite book |title=Digital Logic Design |chapter=3.17 Decimal approach to Quine–McCluskey simplification of Boolean algebra |first1=Brian |last1=Holdsworth |first2=Clive |last2=Woods |edition=4 |date=2002 |publisher=[[Newnes Books]] / [[Elsevier Science]] |isbn=((0-7506-4588-2))<!-- this ISBN is faulty, but actually printed in the book --> |pages=65–67 |chapter-url=https://books.google.com/books?id=o7enSwSVvgYC&pg=PA65 |url=https://books.google.com/books?id=o7enSwSVvgYC |access-date=2020-04-19}} (519 pages) [https://web.archive.org/web/20200419213939/http://s2.bitdownload.ir/Ebook/Electronics/Holdsworth%20-%20Digital%20Logic%20Design%204e%20HQ%20(Newnes,%202002).pdf]</ref>

<ref name="ChandraMarkowsky_1978">{{cite journal |title=On the number of prime implicants |first1=Ashok K. |last1=Chandra |first2=George |last2=Markowsky |journal=Discrete Mathematics |volume=24 |number=1 |date=1978 |pages=7-117–11 |doi=10.1016/0012-365X(78)90168-1 |url=https://wwwdx.sciencedirectdoi.comorg/science10.1016/article/pii/0012365X789016810012-365X%2878%2990168-1}}</ref>

}}