HOM FUNCTIONS AND SUBMODULAR BOOLEAN FUNCTIONS

After providing a simple characterization of Horn functions (i.e., tho se Boolean functions that have a Horn DNF), we study in detail the spe cial class of submodular functions. Every prime implicant of such a fu nction involves at most one complemented and at most one uncomplemente d variable, and based on this we give a one-to-one correspondence betw een submodular functions and partial preorders (reflexive and transiti ve binary relations), and in particular between the nondegenerate acyc lic submodular functions and the partially ordered sets. There is a on e-to-one correspondence between the roots of a submodular function and the ideals of the associated partial preorder. There is also a one-to -one correspondence between the prime implicants of the dual of the su bmodular function and the maximal antichains of the associated partial preorder. Based on these results, we give graph-theoretic characteriz ations for all minimum prime DNF representations of a submodular funct ion. The problem of recognizing submodular functions in DNF representa tion is coNP-complete.