Sept. 19, 2002

Workshop on
Boolean Problems

Quine-McCluskey
type exact ND SOP relation minimization

Given an ND relation, e.g. the complete
flexibility, its *i*-set is the set of input minterms that can produce output value *i*.

•For each *i*-set,
generate all its primes, *P**i
*

•Form
covering table with

–one
column for each *p**j* in *P**i* for all *i
*

–one row
for each minterm in the input space

•Solve minimum covering problem

–Primes
chosen from *P**k** ** *is the cover for kth *i*-set.