Quine–McCluskey algorithm
Algorithm for the minimization of Boolean functions / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Quine–McCluskey algorithm?
Summarize this article for a 10 year old
The Quine–McCluskey algorithm (QMC), also known as the method of prime implicants, is a method used for minimization of Boolean functions that was developed by Willard V. Quine in 1952[1][2] and extended by Edward J. McCluskey in 1956.[3] As a general principle this approach had already been demonstrated by the logician Hugh McColl in 1878,[4][5][6] was proved by Archie Blake in 1937,[7][8][9][6] and was rediscovered by Edward W. Samson and Burton E. Mills in 1954[10][6] and by Raymond J. Nelson in 1955.[11][6] Also in 1955, Paul W. Abrahams and John G. Nordahl[12] as well as Albert A. Mullin and Wayne G. Kellner[13][14][15][16] proposed a decimal variant of the method.[17][14][15][16][18][19][20][21]
The Quine–McCluskey algorithm is functionally identical to Karnaugh mapping, but the tabular form makes it more efficient for use in computer algorithms, and it also gives a deterministic way to check that the minimal form of a Boolean function has been reached. It is sometimes referred to as the tabulation method.
The method involves two steps:
- Finding all prime implicants of the function.
- Use those prime implicants in a prime implicant chart to find the essential prime implicants of the function, as well as other prime implicants that are necessary to cover the function.