"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
Abstract:
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.
