Horn extensions of a partially defined Boolean function

Given a partially defined Boolean function (pdBf) (T, F), we investigate in this paper how to find a Horn extension f : {0, 1}(n) bar right arrow {0, 1}, which is consistent with (T, F), where T subset of or equal to {0, 1}(n ) denotes a set of true Boolean vectors (or positive examples) and F subset of or equal to {0, 1}(n) denotes a set of false Boolean vectors (or negati ve examples). Given a pdBf (T;F), it is known that the existence of a Horn extension can be checked in polynomial time. As there are many Horn extensi ons, however, we consider those extensions f which have maximal and minimal sets T(f) of the true vectors of f, respectively. For a pdBf (T, F), there always exists the unique maximal (i.e., maximum) Horn extension, but there are in general many minimal Horn extensions. We first show that a polynomi al time membership oracle can be constructed for the maximum extension, eve n if its disjunctive normal form (DNF) can be very long. Our main contribut ion is to show that checking if a given Horn DNF represents a minimal exten sion and generating a Horn DNF of a minimal Horn extension can both be done in polynomial time. We also can check in polynomial time if a pdBf (T, F) has the unique minimal Horn extension. However, the problems of finding a H orn extension f with the smallest \T(f)\ and of obtaining a Horn DNF, whose number of literals is smallest, are both NP-hard.