NAME
Algorithm::QuineMcCluskey  solve QuineMcCluskey setcover problems
SYNOPSIS
use Algorithm::QuineMcCluskey;
#
# Fivebit, 12minterm Boolean expression test with don'tcares
#
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 => '10001011011000111001110000'
);
In either case $result
will be "(AC') + (A'BDE) + (B'CE) + (C'E')"
.
DESCRIPTION
This module minimizes Boolean expressions using the QuineMcCluskey 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 1values of the Boolean expression.
 'maxterms'

An array reference of terms representing the 0values of the Boolean expression. This will also indicate that you want the expression in productofsum form, instead of the default sumofproduct form.
 'dontcares'

An array reference of terms representing the don'tcarevalues 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 twovariable AND equation would have a string "0001".
 'dc'

Default value: ''
Change the representation of the don'tcare character. The don'tcare 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 => ['a1', 'a0', 'b1', 'b0']
solve()
Returns a string of the Boolean equation.
For now, the form of the equation is set by the choice of terms used to create the object. If you use the minterms attribute, the equation will be returned in sumofproduct form. If you use the maxterms attribute, the equation will be returned in productofsum form.
Using the columnstring attribute is the same as using the minterm attribute as far as solve() is concerned.
It is possible for solve() to return two different (but equally valid) equations on separate runs. You can have the full list of possible equations by using "get_covers()", described below.
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)
get_primes()
Returns the prime implicants of the boolean expression, as a hash reference. The keys of the hash are the prime implicants, while the values of the hash are arrays of the terms each implicant covers.
use Algorithm::QuineMcCluskey;
my $q = Algorithm::QuineMcCluskey>new(
width => 4,
minterms => [0, 2, 3, 4, 5, 10, 12, 13, 14, 15]
);
#
# Remember, get_primes() returns a hash reference.
#
my $prime_ref = $q>get_primes();
print join(", ", sort keys %{$prime_ref}), "\n";
prints
010, 10, 000, 000, 001, 110, 11
See the chart() function in Algorithm::QuineMcCluskey::Format for an example of the prime implicant/term chart.
get_essentials()
Returns the essential prime implicants of the boolean expression, as an array reference. The array elements are the prime implicants that are essential, that is, the only ones that happen to cover certain terms in the expression.
use Algorithm::QuineMcCluskey;
my $q = Algorithm::QuineMcCluskey>new(
width => 4,
minterms => [0, 2, 3, 4, 5, 10, 12, 13, 14, 15]
);
my $ess_ref = $q>get_essentials();
print join(", ", @{$ess_ref}), "\n";
prints
10, 001, 11
get_covers()
Returns all of the reduced implicant combinations that cover the booelan expression.
It is possible to have more than one possible equation solve a boolean expression. The solve() method returns a minimum set, but other sets are often generated too as part of the solving process. To see the other solutions, return them via get_covers().
use Algorithm::QuineMcCluskey;
my $q = Algorithm::QuineMcCluskey>new(
width => 4,
minterms => [0, 2, 3, 4, 5, 10, 12, 13, 14, 15]
);
#
# get_covers() returns an array ref of arrays.
#
my $covers = $q>get_covers();
for my $idx (0 .. $#{$covers})
{
my @cvs = @{$covers>[$idx]};
#
# The raw ones, zeroes, and dontcare characters.
#
print "'", join("', '", sort @cvs), "' => ";
#
# And the resulting boolean equation.
#
print $q>to_boolean(\@cvs), "\n";
}
prints
'010', '10', '000', '001', '11' => (AB) + (A'B'C) + (A'B'D') + (BC') + (B'CD')
'10', '000', '001', '110', '11' => (AB) + (ACD') + (A'B'C) + (A'B'D') + (BC')
'010', '10', '000', '001', '11' => (AB) + (A'B'C) + (A'C'D') + (BC') + (B'CD')
'10', '000', '001', '110', '11' => (AB) + (ACD') + (A'B'C) + (A'C'D') + (BC')
Note the use of the method to_boolean() in the loop. This is the method solve() uses to create its equation, by passing it the first of the list of covers.
to_columnstring()
Return a string made up of the function's column's values. Position 0 in the string is the 0th row of the column, and so on. The string will consist of zeros, ones, and the don'tcare character (which by default is '').
my $column = $self>to_columnstring();
AUTHOR
Darren M. Kulp darren@kulp.ch
John M. Gamble jgamble@cpan.org (current maintainer)