quine-mccluskey's Introduction

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