I’ve recently been working on a qualitative modelling project where I am trying to uncover “truths” about the response of species in an ecosystem to control of invasive species. Long story short, I’ve been looking into various boolean minimisation techniques. I’ve been playing with Python EDA, a Python library that I think provides a front-end to the Robert Brayton and Richard Rudell espresso heuristic logic minimiser, developed at University of California, Berkeley.

I was trying out the examples on the Two-level Logic Minimisation docs page, and I had no issues with the second ‘Minimise truth tables’ example. However for the first example, where we’re trying to minimise a boolean expression, I kept on getting the following error

---> 11 f1m, = espresso_exprs(f1)

ValueError: expected a DNF expression

I’m not real clear yet on what the various types of expressions are yet[1], but converting f1 was a simple enough thing, and the espresso algorithm for expressions worked after that.

I’ve written out a minimal script that gets it going below.

from pyeda.inter import *
from pyeda.boolalg.expr import exprvar

a, b, c = map(exprvar, 'abc')
f1 = ~a & ~b & ~c | ~a & ~b & c | a & ~b & c | a & b & c | a & b & ~c
f1dnf = f1.to_dnf()

f1m, = espresso_exprs(f1dnf)
f1m
  • [1] update: DNF stands for Disjunctive Normal Form, which is an or-sum of boolean ands. It’s basically what you’d have your UPCs table as. This function is also good for making the result of a fold more readable. For example,
# ors is the result of some loop that has 
# ors.append( fp.reduce(lambda x, y: x & y, ands) )
# where ands was a list of boolean variables for 
# that iteration like 
# ands = [~cat_frugivores, ~cat_flyingFox, ~cat_rat]

In [122]: ors
Out[122]: 
[And(~rat_cat, ~rat_brownBooby),
 And(~rat_brownBooby, ~rat_cat),
 And(And(~rat_cat, ~rat_gecko), ~rat_hawkOwl),
...

In [123]: f1 = fp.reduce(lambda x,y: x | y, ors)

In [124]: f1
Out[124]: Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(Or(And(~rat_cat,~rat_brownBooby), And(~cat_rat, ~cat_brownBooby)), And(~cat_brownBooby, ~cat_rat)), And(~rat_brownBooby, ~rat_cat)), And(And(~rat_cat, ~rat_gecko), ~rat_hawkOwl)), And(And(~rat_cat, #... 

# Awful!

In [125]: f1.to_dnf()
Out[125]: Or(And(~rat_brownBooby, ~rat_cat), And(~cat_brownBooby, ~cat_rat), And(~rat_gecko, ~rat_hawkOwl, ~rat_cat), And(~rat_cat, ~rat_goshawk, ~rat_tropicBird), 
... 
# Much nicer
  • Update (22 July 2015)

Using a fold to do a boolean product or sum, like I did above, is an ungainly way of going about it. Much better to do something like this:

from pyeda.boolalg.expr import And, Or

# ... some code here ...

# Where BoolList is a list of boolean variables
myBoolProduct = And(*BoolList)
myBoolSum = Or(*BoolList)

The boolean sum and product above are DNFs, so no need to do .to_dnf().

  • Other keywords to help Googlers find this post, particularly sociologists: boolean analysis of questionnaire data, Quinne-McCluskey, Alain Degenne, Marie-Odile Lebeaux, ultimate canonical projections, UCP, Flament, Peter Theuns, Guttman analysis, Projection Canonique Ultime, PCU, prime implicant Martin Schrepp, Ragin, qualitative comparative analysis.