RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2015 Volume 27, Issue 2, Pages 94–105 (Mi dm1327)

This article is cited 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.

UDC: 519.571

Received: 27.01.2015

DOI: 10.4213/dm1327


 English version:
Discrete Mathematics and Applications, 2016, 26:1, 41–50

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024