Many learning systems use the space of logic formulas as the search space of hypotheses. To build efficient systems, the set of first order logic formulas can be reduced in many ways. Most systems restrict themselves to (subsets of) Horn clauses. In this paper we investigate the space of reduced first order sentences, which has the same expressive power as an arbritrary first order logic. Shapiro [1981] has used the subset of reduced first order sentences to define a most general refinement operator. His operator is claimed to be complete, i.e., all reduced sentences are derivable from the empty sentence. In this article we will show that his operator is not complete and propose a new, complete refinement operator for reduced first order sentences.

Horn clauses, learning systems, reduced sentences
Erasmus School of Economics

van der Laag, P.R.J. (1992). A most general refinement operator for reduced sentences. Retrieved from