|
Prikladnaya Diskretnaya Matematika, 2008, Number 1(1), Pages 7–9
(Mi pdm2)
|
|
|
|
This article is cited in 1 scientific paper (total 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.
Citation:
S. P. Gorshkov, “On the complexity of weakly positive and weakly negative boolean functions reducing”, Prikl. Diskr. Mat., 2008, no. 1(1), 7–9
Linking options:
https://www.mathnet.ru/eng/pdm2 https://www.mathnet.ru/eng/pdm/y2008/i1/p7
|
Statistics & downloads: |
Abstract page: | 364 | Full-text PDF : | 145 | First page: | 2 |
|