src/vendor/quine-mc_cluskey/README.md

   1 [![Clippy Linting Result](https://clippy.bashy.io/github/oli-obk/quine-mc_cluskey/master/badge.svg)](https://clippy.bashy.io/github/oli-obk/quine-mc_cluskey/master/log)
   2 [![Current Version](http://meritbadge.herokuapp.com/quine-mc_cluskey)](https://crates.io/crates/quine-mc_cluskey)
   3 [![Build Status](https://travis-ci.org/oli-obk/quine-mc_cluskey.svg?branch=master)](https://travis-ci.org/oli-obk/quine-mc_cluskey)
   4
   5 An algorithm to automatically minimize boolean expressions.
   6
   7 # Example
   8
   9 ```rust
  10 extern crate quine_mc_cluskey;
  11
  12 use quine_mc_cluskey::*;
  13 use quine_mc_cluskey::Bool::{And, Or, Not, True, False};
  14
  15 fn main() {
  16     // !false => true
  17     assert_eq!(
  18         Not(Box::new(False)).simplify(),
  19         vec![True]
  20     );
  21
  22     // a && (b || a) => a
  23     assert_eq!(
  24         And(vec![Bool::Term(0),
  25         Or(vec![Bool::Term(1), Bool::Term(0)])]).simplify(), vec![Bool::Term(0)]
  26     );
  27 }
  28 ```
  29
  30 # Obtaining a minimal "and of or" form
  31
  32 Sometimes an expression of the form `a && (b || c)` is shorter than the `a && b || a && c` form.
  33 We can simply negate the original expression and negate all the resulting simplified expressions to obtain that form.
  34
  35 ```rust
  36 extern crate quine_mc_cluskey;
  37 use quine_mc_cluskey::Bool;
  38
  39 fn main() {
  40     let a: Bool = Bool::And(vec![Bool::True, Bool::True]);
  41     let simplified: Vec<Bool> = Bool::Not(Box::new(a)).simplify()
  42         .iter().map(simple_negate).collect();
  43 }
  44
  45 fn simple_negate(b: &Bool) -> Bool {
  46     use quine_mc_cluskey::Bool::*;
  47     let b = b.clone();
  48
  49     match b {
  50         True => False,
  51         False => True,
  52         t @ Term(_) => Not(Box::new(t)),
  53         And(mut v) => {
  54             for el in &mut v {
  55                 *el = simple_negate(el);
  56             }
  57             Or(v)
  58         },
  59         Or(mut v) => {
  60             for el in &mut v {
  61                 *el = simple_negate(el);
  62             }
  63             And(v)
  64         },
  65         Not(inner) => *inner,
  66     }
  67 }
  68 ```