Limiting Negations in Formulas

Negation-limited circuits have been studied as a circuit model between general circuits and monotone circuits. In this paper, we consider limiting negations in formulas. The minimum number of NOT gates in a Boolean circuit computing a Boolean function

f

is called the inversion complexity of

f

. In 1958, Markov determined the inversion complexity of every Boolean function and particularly proved that ⌈log

2

(

n

 + 1) ⌉ NOT gates are sufficient to compute any Boolean function on

n

variables. We determine the inversion complexity of every Boolean function in formulas, i.e., the minimum number of NOT gates (NOT operators) in a Boolean formula computing (representing) a Boolean function, and particularly prove that ⌈

n

/2 ⌉ NOT gates are sufficient to compute any Boolean function on

n

variables. Moreover we show that if there is a polynomial-size formula computing a Boolean function

f

, then there is a polynomial-size formula computing

f

with at most ⌈

n

/2 ⌉ NOT gates. We consider also the inversion complexity in formulas of negation normal form and prove that the inversion complexity is at most polynomials of

n

for every Boolean function on

n

variables.