1 stable release
1.0.0 | Mar 15, 2024 |
---|
#839 in Algorithms
48KB
1K
SLoC
Quine-McCluskey
Boolean function minimizer based on Quine-McCluskey algorithm.
Example
Given the boolean function expressed by the following truth table:
A | B | C | Output |
---|---|---|---|
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | X |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | X |
We can minimize it in Sum of Products form using minimize
with minterms and maxterms and Form::SOP
:
use quine_mccluskey as qmc;
let mut solutions = qmc::minimize(
&qmc::DEFAULT_VARIABLES[..3],
&[0, 5], // minterms
&[1, 3, 4, 6], // maxterms
qmc::SOP,
false,
None
)
.unwrap();
assert_eq!(
solutions.pop().unwrap().to_string(),
"(A ∧ C) ∨ (~A ∧ ~C)"
);
or using minimize_minterms
with minterms and don't cares:
let mut solutions = qmc::minimize_minterms(
&qmc::DEFAULT_VARIABLES[..3],
&[0, 5], // minterms
&[2, 7], // don't cares
false,
None
)
.unwrap();
assert_eq!(
solutions.pop().unwrap().to_string(),
"(A ∧ C) ∨ (~A ∧ ~C)"
);
And in Product of Sums form using minimize
with minterms and maxterms and Form::POS
:
let mut solutions = qmc::minimize(
&qmc::DEFAULT_VARIABLES[..3],
&[0, 5], // minterms
&[1, 3, 4, 6], // maxterms
qmc::POS,
false,
None
)
.unwrap();
assert_eq!(
solutions.pop().unwrap().to_string(),
"(A ∨ ~C) ∧ (~A ∨ C)"
);
or using minimize_maxterms
with maxterms and don't cares:
let mut solutions = qmc::minimize_maxterms(
&qmc::DEFAULT_VARIABLES[..3],
&[1, 3, 4, 6], // maxterms
&[2, 7], // don't cares
false,
None
)
.unwrap();
assert_eq!(
solutions.pop().unwrap().to_string(),
"(A ∨ ~C) ∧ (~A ∨ C)"
);
Feature flags
serde
– Derives theSerialize
andDeserialize
traits for structs and enums.
Dependencies
~0.3–0.8MB
~20K SLoC