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
use Algorithm::QuineMcCluskey;
my $q = Algorithm::QuineMcCluskey>new(
width => 5,
columnstring => '10001011011000111001110000'
);
my $result = $q>solve();
In either case $result
will be "(AC') + (A'BDE) + (B'CE) + (C'E')"
.
The strings that represent the covered terms are also viewable:
use Algorithm::QuineMcCluskey;
#
# Fivebit, 12minterm Boolean expression test with don'tcares
#
my $q = Algorithm::QuineMcCluskey>new(
width => 4,
minterms => [ 1, 6, 7, 8, 11, 13, 15],
);
my @covers = $q>get_covers();
print $q>solve(), "\n", join(", ", @covers[0];
Will print out
'0001', '011', '111', '1000', '111'
(A'B'C'D) + (A'BC) + (ACD) + (AB'C'D') + (ABD)
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 minterms
attribute as far as solve() is concerned.
It is possible that there will be more than one equation that solves the boolean expression. Therefore solve() can return a different (but equally valid) equation on separate runs. You can have the full list of possible equations by using "all_solutions()". Likewise, the terms that describe the solution (before they are converted with the variable names) are returned with "get_covers()", described below.
all_solutions()
Return an array of strings that represent the Boolean equation.
It is often the case that there will be more than one equation that covers the terms.
my @sol = $q>all_solutions();
print " ", join("\n ", @sol), "\n";
The first equation in the list will be the equation returned by "solve".
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 function "chart()" 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.
The implicants are in a form that combines 1, 0, and the don'tcare character (found and set with the dc
attribute). These are used by "solve()" to create a boolean equation that solves the set of minterms
or maxterms
.
It is possible that there will be more than one equation that solves a boolean expression. The solve() method returns a minimum set, and all_solutions() show the complete set of solutions found by the algorithm.
But if you want to see how the solutions match up with their associated covers, you may use this:
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 = sort @{$covers>[$idx]};
#
# The raw ones, zeroes, and dontcare characters.
#
print "'", join("', '", @cvs), "' => ";
#
# And the resulting boolean equation.
#
print $q>to_boolean(\@cvs), "\n";
}
prints
'010', '10', '000', '001', '11' => (B'CD') + (BC') + (A'B'D') + (A'B'C) + (AB)
'10', '000', '001', '110', '11' => (BC') + (A'B'D') + (A'B'C) + (ACD') + (AB)
'010', '10', '000', '001', '11' => (B'CD') + (BC') + (A'C'D') + (A'B'C) + (AB)
'10', '000', '001', '110', '11' => (BC') + (A'C'D') + (A'B'C) + (ACD') + (AB)
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)
SEE ALSO
Introduction To Logic Design, by Sajjan G. Shiva, 1998.
Discrete Mathematics and its Applications, by Kenneth H. Rosen, 1995
LICENSE AND COPYRIGHT
Copyright (c) 2006 Darren Kulp. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
See http://dev.perl.org/licenses/ for more information.