#algorithm #boolean #expression #automatic #minimize #petrick #quine

quine-mc_cluskey

Rust implementation of the Quine-McCluskey algorithm and Petrick's method

7 releases

Uses old Rust 2015

0.2.4 Aug 3, 2016
0.2.3 Aug 3, 2016
0.2.2 Mar 29, 2016
0.1.1 Mar 22, 2016

#1686 in Algorithms

Download history 7214/week @ 2024-03-14 7610/week @ 2024-03-21 7261/week @ 2024-03-28 6929/week @ 2024-04-04 7007/week @ 2024-04-11 7190/week @ 2024-04-18 6625/week @ 2024-04-25 6642/week @ 2024-05-02 6885/week @ 2024-05-09 6772/week @ 2024-05-16 7006/week @ 2024-05-23 6375/week @ 2024-05-30 6944/week @ 2024-06-06 7330/week @ 2024-06-13 7085/week @ 2024-06-20 5873/week @ 2024-06-27

28,296 downloads per month
Used in 82 crates (2 directly)

MIT license

18KB
461 lines

Clippy Linting Result Build Status

An algorithm to automatically minimize boolean expressions.

Example

extern crate quine_mc_cluskey;

use quine_mc_cluskey::*;
use quine_mc_cluskey::Bool::{And, Or, Not, True, False};

fn main() {
    // !false => true
    assert_eq!(
        Not(Box::new(False)).simplify(),
        vec![True]
    );

    // a && (b || a) => a
    assert_eq!(
        And(vec![Bool::Term(0),
        Or(vec![Bool::Term(1), Bool::Term(0)])]).simplify(), vec![Bool::Term(0)]
    );
}

Obtaining a minimal "and of or" form

Sometimes an expression of the form a && (b || c) is shorter than the a && b || a && c form. We can simply negate the original expression and negate all the resulting simplified expressions to obtain that form.

extern crate quine_mc_cluskey;
use quine_mc_cluskey::Bool;

fn main() {
    let a: Bool = Bool::And(vec![Bool::True, Bool::True]);
    let simplified: Vec<Bool> = Bool::Not(Box::new(a)).simplify()
        .iter().map(simple_negate).collect();
}

fn simple_negate(b: &Bool) -> Bool {
    use quine_mc_cluskey::Bool::*;
    let b = b.clone();

    match b {
        True => False,
        False => True,
        t @ Term(_) => Not(Box::new(t)),
        And(mut v) => {
            for el in &mut v {
                *el = simple_negate(el);
            }
            Or(v)
        },
        Or(mut v) => {
            for el in &mut v {
                *el = simple_negate(el);
            }
            And(v)
        },
        Not(inner) => *inner,
    }
}

Dependencies

~0–260KB