ON THE COMPLEXITY OF WEAKLY POSITIVE AND WEAKLY NEGATIVE BOOLEAN FUNCTIONSREDUCING | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2008. № 1(1).

Boolean function f (x1, ..., xk) is called weakly positive (weakly negative) if f may be represented by CNF such asf ≡1ti=∧ (1isixα ∨i2 sx ∨...∨ikisx ), where αi∈{0, 1}, i = 1, ..., t, (respectively by CNF such as f ≡1ti=∧ (1isixα ∨ xsi2 ∨...∨ ikis x ), whereαi∈{0, 1}, i = 1, ..., t). These formulas are called reduced representations of weakly positive and weakly negative functions accordingly.The complexity of reducing the weakly positive and weakly negative functions represented by perfect CNF or algebraicnormal form is evaluated in this paper.