This article is cited in 1 paper

Theoretical Foundations of Applied Discrete Mathematics

On the complexity of weakly positive and weakly negative boolean functions reducing

S. P. Gorshkov

Institute of Cryptography, Communications and Informatics, Academy of Federal Security Service of Russian Federation

Abstract: Boolean function $f(x_1,\dots,x_k)$ is called weakly positive (weakly negative) if $f$ may be represented by CNF such as $f\equiv\bigwedge\limits_{i=1}^t(x_{s_{i1}}^{\alpha_i}\lor x_{s_{i2}}\lor\dots\lor x_{s_{ik_i}})$, where $\alpha_i\in\{0,1\}$, $i=1,\dots,t$, (respectively by CNF such as $f\equiv\bigwedge\limits_{i=1}^t(\overline x_{s_{i1}}^{\alpha_i}\lor\overline x_{s_{i2}}\lor\dots\lor\overline x_{s_{ik_i}})$, where $\alpha_i\in\{0,1\}$, $i=1,\dots,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 algebraic normal form is evaluated in this paper.

UDC: 519.7