"A Relationship Between CNF and DNF Systems Derivable from Examples"

ORSA Journal on Computing, Vol. 7, No. 3, pp. 283-285.

Evangelos Triantaphyllou and Allen L. Soyster

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.

Key Words:
Artificial intelligence, learning from examples, satisfiability problem, Boolean expressions, CNF/DNF form.

Download this paper as a PS (PostScript) file (size = 508 KB).

Download this paper as a PDF file (size = 230KB).

Return to Dr. Triantaphyllou's Homepage.