Computing the Minimum DNF Representation of Boolean Functions Defined by Intervals

For any two n-bit numbers define the Boolean function to be the function for which if and only if x is the binary representation of a number in the interval [a, b]. We consider the disjunctive normal form representation of such functions, and show how to compute such a representation with a minimum number of disjuncts in linear time. We also show how to compute a minimum ¡°disjoint¡± representation; i.e., a representation in which the domains of the disjuncts are mutually disjoint. The minimum disjunctive normal form can be applied to devise efficient constraint satisfaction systems for automatic generation of test patterns.

By: Baruch Schieber, Daniel Geist, Ayal Zaks

Published in: Discrete Applied Mathematics, volume 149, (no 1-3), pages 154-73 in 2005

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .