About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Discrete Applied Mathematics
Paper
Computing the minimum DNF representation of Boolean functions defined by intervals
Abstract
For any two n-bit numbers a≤b define the Boolean function f[a,b]:{0,1}n→{0,1} to be the function for which f[a,b](x)=1 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. © 2005 Elsevier B.V. All rights reserved.