Disjunctive and conjunctive normal forms of pseudo-Boolean functions

AbstractAfter showing that every pseudo-Boolean function (i.e. real-valued function with binary variables) can be represented by a disjunctive normal form (essentially the maximum of several weighted monomials), the concepts of implicants and of prime implicants are analyzed in the pseudo-Boolean context, and a consensus-type method is presented for finding all the prime implicants of a pseudo-Boolean function. In a similar way the concepts of conjunctive normal form, implicates and prime implicates, as well as the resolution method are examined in the case of pseudo-Boolean functions