Quine–McCluskey algorithm: Difference between revisions

Revision as of 11:32, 23 March 2025

Latest revision as of 04:02, 15 August 2025

(2 intermediate revisions by 2 users not shown)

Line 262:

==== Creating the prime implicant chart ====

The prime implicant chart can be represented by a dictionary where each key is a prime implicant and the corrrespondingcorresponding value is an empty string that will store a binary string once this step is complete. Each bit in the binary string is used to represent the ticks within the prime implicant chart. The prime implicant chart can be created using the following steps:

# Iterate through each key (prime implicant of the dictionary).

Line 337:

<ref name="Nordahl_2017">{{cite web |title=Welcome to the memorial page for John "Jack" G Nordahl June 14, 1933 ~ November 20, 2017 (age 84) |publisher=Jellison Funeral Home and Cremation Services |url=https://www.jellisonfuneralhome.com/obituary/JohnJack-Nordahl |access-date=2020-05-05 |url-status=live |archive-url=https://web.archive.org/web/20200505151004/https://www.jellisonfuneralhome.com/obituary/JohnJack-Nordahl |archive-date=2020-05-05}}</ref>

<ref name="Caldwell_1958">{{cite book |title=Switching Circuits and Logical Design |chapter=5.8. Operations Using Decimal Symbols |first=Samuel Hawks |last=Caldwell |author-link=Samuel Hawks Caldwell |version=5th printing September 1963 |date=1958-12-01 |orig-date=February 1958 |edition=1st |publisher=[[John Wiley & Sons Inc.]] |publication-place=New York, USA |___location=Watertown, Massachusetts, USA |isbn=0-47112969-0 |lccn=58-7896 |pages=162–169 |quote-page=166 |quote=[...] It is a pleasure to record that this treatment is based on the work of two students during the period they were studying Switching Circuits at the Massachusetts Institute of Technology. They discussed the method independently and then collaborated in preparing a class memorandum: {{citeref|Abrahams|Nordahl|1955|P. W. Abraham and J. G. Nordahl|style=plain}} [...]}} (xviii+686 pages) (NB. For the first major treatise of the decimal method in this book, it is sometimes misleadingly known as "Caldwell's decimal tabulation".)</ref>

<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] {{Webarchive|url=https://web.archive.org/web/20200817055259/https://ilacadofsci.com/archives/9279 |date=2020-08-17 }} (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] {{Webarchive|url=https://web.archive.org/web/20200817055316/https://ilacadofsci.com/archives/9203 |date=2020-08-17 }}[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|url-access=subscription }}</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 |url-access=subscription }}</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>