#boolean #minimize #algorithm

quine-mccluskey

Boolean function minimizer based on Quine–McCluskey algorithm

1 stable release

1.0.0 Mar 15, 2024

#839 in Algorithms

MIT license

48KB
1K SLoC

Quine-McCluskey

crates.io docs.rs

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 the Serialize and Deserialize traits for structs and enums.

Dependencies

~0.3–0.8MB
~20K SLoC