Disjunctive and conjunctive normal forms of pseudo-Boolean functions

After showing that every pseudo-Boolean function (i.e. real-valued function with binary variables) can be represented by a disjunctive normal form (es sentially the maximum of several weighted monomials), the concepts of impli cants and of prime implicants are analyzed in the pseudo-Boolean context, a nd a consensus-type method is presented for finding all the prime implicant s of a pseudo-Boolean function, in a similar way the concepts of conjunctiv e normal form, implicates and prime implicates, as well as the resolution m ethod are examined in the case of pseudo-Boolean functions. (C) 2000 Elsevi er Science B.V. All rights reserved.