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.

artificial intelligence, machine learning, operations research, ordinal classification, partially defined Boolean functions
Mathematical Methods and Programming: Other (jel C69), Business Administration and Business Economics; Marketing; Accounting (jel M), Production Management (jel M11), Transportation Systems (jel R4)
Erasmus Research Institute of Management
ERIM Report Series Research in Management
Copyright 2002, J.C. Bioch, T. Ibaraki, This report in the ERIM Report Series Research in Management is intended as a means to communicate the results of recent research to academic colleagues and other interested parties. All reports are considered as preliminary and subject to possibly major revisions. This applies equally to opinions expressed, theories developed, and data used. Therefore, comments and suggestions are welcome and should be directed to the authors.
Erasmus Research Institute of Management

Bioch, J.C, & Ibaraki, T. (2002). Version Spaces and Generalized Monotone Boolean Functions (No. ERS-2002-34-LIS). ERIM Report Series Research in Management. Erasmus Research Institute of Management. Retrieved from http://hdl.handle.net/1765/187