Version Spaces and Generalized Monotone Boolean Functions

We consider generalized monotone functions f: X --> {0,1} defined for an arbitrary binary relation <= on X by the property x <= y implies f(x) <= f(y). These include the standard monotone (or positive) Boolean functions, regular Boolean functions and other interesting functions as special cases. It is shown that a class of functions is closed under conjunction and disjunction (i.e., a distributive lattice) if and only if it is the class of monotone functions with respect to some quasi-order. Subsequently, we consider the monoid of all conjunctive operators on a set and show that this monoid is algebraically isomorphic to the monoid of all binary relations on this set. In this development, two operators, positive content and positive closure, play an important role. The results are then applied to the version space of all monotone hypotheses of a set of binary examples also called the class of all monotone extensions of a partially defined Boolean function, to clarify its lattice theoretic properties.