|
This article is cited in 2 scientific papers (total in 2 papers)
Functions without short implicents.Part I: lower estimates of weights
Pavel V. Roldugin, Alexey V. Tarasov Moscow State Institute of Radio-Engineering, Electronics and Automation (Technical University)
Abstract:
The paper is concerned with $n$-place Boolean functions not admitting implicents of $k$ variables, $1\le k<n$. Estimates for the minimal possible weight $w\left( {n,\;k} \right)$ of such functions are obtained. It is shown that $w\left( {n,\;1} \right) = 2$, $n = 2,3,...$, and $w\left( {n,\;2} \right)\sim{\log _2}n$ as $n \to \infty$, and moreover, for $k > 2$ there exists ${n_0}$ such that $w\left( {n,\;k} \right) > {2^{k - 2}} \cdot {\log _2}n$ for all $n > {n_0}$.
Keywords:
Boolean function, implicent, combinatorially complete matrix.
Received: 27.01.2015
Citation:
Pavel V. Roldugin, Alexey V. Tarasov, “Functions without short implicents.Part I: lower estimates of weights”, Diskr. Mat., 27:2 (2015), 94–105; Discrete Math. Appl., 26:1 (2016), 41–50
Linking options:
https://www.mathnet.ru/eng/dm1327https://doi.org/10.4213/dm1327 https://www.mathnet.ru/eng/dm/v27/i2/p94
|
Statistics & downloads: |
Abstract page: | 431 | Full-text PDF : | 175 | References: | 44 | First page: | 35 |
|