NAME

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

SYNOPSIS

    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();

or

    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')".

DESCRIPTION

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

Object Methods

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

Creates the QuineMcCluskey object. The attributes are:

'width'

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

This is a required attribute.

'minterms'

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

'maxterms'

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.

'dontcares'

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.

'columnstring'

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".

'dc'

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.

'title'

A title for the problem you are solving.

'vars'

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']

solve()

Returns a string of the Boolean equation.

complement()

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')".

dual()

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)".

to_columnstring()

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

to_boolean()

Generating Boolean expressions

AUTHOR

Darren M. Kulp <darren@kulp.ch>