John Gamble
and 1 contributors


Algorithm::QuineMcCluskey - solve Quine-McCluskey set-cover problems


    use Algorithm::QuineMcCluskey;

    # Five-bit, 12-minterm Boolean expression test with don't-cares
    my $q = Algorithm::QuineMcCluskey->new(
        width => 5,
        minterms => [ 0, 5, 7, 8, 10, 11, 15, 17, 18, 23, 26, 27 ],
        dontcares => [ 2, 16, 19, 21, 24, 25 ]

    my $result = $q->solve();


    my $q = Algorithm::QuineMcCluskey->new(
        width => 5,
        columnstring => '10-0010110110001-11-0-01--110000'

In either case $result will be "(AC') + (A'BDE) + (B'CE) + (C'E')".


This module minimizes Boolean expressions using the Quine-McCluskey algorithm.

Object Methods

new([<attribute> => value, ...])

Creates the QuineMcCluskey object. The attributes are:


The number of variables (columns) in the Boolean expression.

This is a required attribute.


An array reference of terms representing the 1-values of the Boolean expression.


An array reference of terms representing the 0-values of the Boolean expression. This will also indicate that you want the expression in product-of-sum form, instead of the default sum-of-product form.


An array reference of terms representing the don't-care-values of the Boolean expression. These represent inputs that simply shouldn't happen (e.g., numbers 11 through 15 in a base 10 system), and therefore don't matter to the result.


Present the entire list of values of the boolean expression as a single string. The values are ordered from left to right in the string. For example, a simple two-variable AND equation would have a string "0001".


Default value: '-'

Change the representation of the don't-care character. The don't-care character is used both in the columnstring, and internally as a place holder for eliminated variables in the equation. Some of those internals may be examined via other methods.


A title for the problem you are solving.


Default value: ['A' .. 'Z']

The variable names used to form the equation. The names will be taken from the leftmost first:

    my $f1 = Algorithm::QuineMcCluskey->new(
        width => 4,
        maxterms => [1 .. 11, 13, 15],
        vars => ['w' .. 'z']

The names do not have to be single characters, e.g.:

        vars => ['a0', 'a1', 'b0', 'b1']


Returns a string of the Boolean equation.


Returns a new object that's the complement of the existing object:

    my $qc = $q->complement();
    print $qc->solve(), "\n";

Prints "(ABC) + (A'B'D'E) + (BD'E) + (CE')".


Returns a new object that's the dual of the existing object:

    my $qd = $q->dual();
    print $qd->solve(), "\n";

Prints "(ABCE') + (A'B'C') + (B'DE') + (C'E)".


Return a string made up of the function column. Position 0 in the string is the 0th row of the column, and so on.


Generating Boolean expressions


Darren M. Kulp <>