Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Quine-McCluskey Algorithm

A systematic, tabular algorithm for minimizing Boolean functions. It identifies prime implicants and selects the essential prime implicants to achieve the minimal SOP form.
📜

The statement of the theorem

Let ff be a Boolean function defined by a set of minterms MM. The algorithm proceeds by: \n1. Initial Grouping: Partition MM into groups GkG_k based on the number of '1's (Hamming weight kk).\n2. Iterative Combination: Repeatedly combine terms Ta,Tb∈GkT_a, T_b \in G_k if they differ in exactly one position jj. The resulting term TabT_{ab} is formed by replacing the differing variable with a dash (wildcard). The new set of terms Gk−1G_{k-1} is formed by these combinations.\n3. Prime Implicant Identification: The set of prime implicants PI\text{PI} consists of all terms generated in the final iteration that cannot be combined further. The minimal SOP form is found by selecting the essential prime implicants (EPIs) using a covering matrix approach.