Struct MinimumDisjunctiveNormalForm 

pub struct MinimumDisjunctiveNormalForm { /* private fields */ }

Minimum Disjunctive Normal Form problem.

Given a Boolean function by its truth table, find the minimum number of prime implicants whose disjunction (OR) is equivalent to the function.

The constructor computes all prime implicants via Quine-McCluskey. The configuration is a binary selection over prime implicants.

Example

use problemreductions::models::misc::MinimumDisjunctiveNormalForm;
use problemreductions::{Problem, Solver, BruteForce};

// f(x1,x2,x3) = 1 when exactly 1 or 2 variables are true
let truth_table = vec![false, true, true, true, true, true, true, false];
let problem = MinimumDisjunctiveNormalForm::new(3, truth_table);
let solver = BruteForce::new();
let value = solver.solve(&problem);

Implementations

impl MinimumDisjunctiveNormalForm

pub fn new(num_variables: usize, truth_table: Vec<bool>) -> Self

Create a new MinimumDisjunctiveNormalForm problem.

Panics

• If truth_table length != 2^num_variables
• If the function is identically false (no minterms)

pub fn num_variables(&self) -> usize

Get the number of variables.

pub fn truth_table(&self) -> &[bool]

Get the truth table.

pub fn prime_implicants(&self) -> &[PrimeImplicant]

Get the prime implicants.

pub fn num_prime_implicants(&self) -> usize

Get the number of prime implicants.

pub fn minterms(&self) -> &[usize]

Get the minterms.

Trait Implementations

impl Clone for MinimumDisjunctiveNormalForm

fn clone(&self) -> MinimumDisjunctiveNormalForm

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for MinimumDisjunctiveNormalForm

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for MinimumDisjunctiveNormalForm

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for MinimumDisjunctiveNormalForm

const NAME: &'static str = "MinimumDisjunctiveNormalForm"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Value = Min<usize>

The evaluation value type.

fn dims(&self) -> Vec<usize>

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> Min<usize>

Evaluate the problem on a configuration.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl Serialize for MinimumDisjunctiveNormalForm

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl DeclaredVariant for MinimumDisjunctiveNormalForm