A Relationship Between CNF and DNF Systems Derivable from Examples

In learning from examples, the main goal is to use a collection of positive examples and a collection of negative examples to derive a Boolean expression which satisfies the requirements imposed by the examples. In order to represent such a Boolean expression, the conjunctive normal form (CNF) and the disjunctive normal form (DNF) have been proposed. This paper makes two contributions. First it shows how to use any DNF algorithm to derive a CNF formula (or vice-versa). Furthermore, it demonstrates how to make efficient use of DNF algorithms which cannot handle a large number of positive (or negative) examples by using them as negative (or positive) examples and deriving CNF (or vice-versa). Therefore, the findings of this paper can be used to solve efficiently large scale learning problems. Two learning algorithms are used to illustrate the above issues.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.