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 theproperty x <= y implies f(x) <= f(y). These include thestandard monotone (or positive) Boolean functions, regular Booleanfunctions and other interesting functions as special cases. It isshown that a class of functions is closed under conjunction anddisjunction (i.e., a distributive lattice) if and only if it isthe 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 monotonehypotheses of a set of binary examples also called the class ofall monotone extensions of a partially defined Boolean function,to clarify its lattice theoretic properties