Disjunctive and conjunctive normal forms of pseudo-Boolean functions

被引：12

作者：

Foldes, S ^{[1
]}

Hammer, PL ^{[1
]}

机构：

[1] Rutgers State Univ, RUTCOR, Piscataway, NJ 08844 USA

来源：

DISCRETE APPLIED MATHEMATICS | 2000年 / 107卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/S0166-218X(00)00276-6

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

After 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. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：1 / 26

页数：26

共 24 条

[1]

ALEXE G, 232000 RUTCOR RRR

[2]

Baccelli F, 1992, SYNCHRONIZATION LINE

[3] DECOMPOSITIONS OF POSITIVE SELF-DUAL BOOLEAN FUNCTIONS [J].