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
28,296 downloads per month
Used in 82 crates
(2 directly)
18KB
461 lines
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