ERROR-FREE AND BEST-FIT EXTENSIONS OF PARTIALLY DEFINED BOOLEAN FUNCTIONS

In this paper, we address a fundamental problem related to the inducti on of Boolean logic: Given a set of data, represented as a set of bina ry ''true n-vectors'' (or ''positive examples'') and a set of ''false n-vectors'' (or ''negative examples''), we establish a Boolean functio n (or an extension) f, so that f is true (resp., false) in every given true (resp., false) vector. We shall further require that such an ext ension belongs to a certain specified class of functions, e.g., class of positive functions, class of Horn functions, and so on. The class o f functions represents our a priori knowledge or hypothesis about the extension f, which may be obtained from experience or from the analysi s of mechanisms that may or may not cause the phenomena under consider ation. The real-world data may contain errors, e.g., measurement and c lassification errors might come in when obtaining data, or there may b e some other influential factors not represented as variables in the v ectors. In such situations, we have to give up the goal of establishin g an extension that is perfectly consistent with the given data, and w e are satisfied with an extension f having the minimum number of miscl assifications. Both problems, i.e., the problem of finding an extensio n within a specified class of Boolean functions and the problem of fin ding a minimum error extension in that class, will be extensively stud ied in this paper. For certain classes we shall provide polynomial alg orithms, and for other cases we prove their NP-hardness. (C) 1998 Acad emic Press.