![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/f/f2/QmcSearchGraph3_Ab%252Bc_svg.svg/640px-QmcSearchGraph3_Ab%252Bc_svg.svg.png&w=640&q=50)
Quine–McCluskey algorithm
Algorithm for the minimization of Boolean functions / From Wikipedia, the free encyclopedia
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]
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f2/QmcSearchGraph3_Ab%2Bc_svg.svg/320px-QmcSearchGraph3_Ab%2Bc_svg.svg.png)
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 F has been reached. It is sometimes referred to as the tabulation method.
The Quine-McCluskey algorithm works as follows:
- 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.