RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskr. Mat.: Year: Volume: Issue: Page: Find

 Diskr. Mat., 2020, Volume 32, Issue 2, Pages 32–43 (Mi dm1592)

On complexity of realization of Boolean functions with the small number of ones

N. P. Red'kin

Lomonosov Moscow State University

Abstract: The class of Boolean functions $F_{n,k}$, which consists of all the functions of $n$ variables each of those turns into one exactly at $k$ sets of variables values, is considered. When $k$ is little, class $F_{n,k}$ is divided into subclasses, and for each subclass the Shannon function asymptotic value for the complexity of realization of function from this subclass by schemes of functional elements in the basis $\{x&y,\overline x\}$ (or in the basis $\{x\vee y,\overline x\}$) is found. In that case, any rigorously positive numbers may be the weights of bases elements.

Keywords: Boolean function, scheme of functional elements, Shannon function.

 Funding Agency Grant Number Russian Foundation for Basic Research 18-01-00337

DOI: https://doi.org/10.4213/dm1592

Full text: PDF file (494 kB)
First page: PDF file
References: PDF file   HTML file

UDC: 519.714.4

Citation: N. P. Red'kin, “On complexity of realization of Boolean functions with the small number of ones”, Diskr. Mat., 32:2 (2020), 32–43

Citation in format AMSBIB
\Bibitem{Red20} \by N.~P.~Red'kin \paper On complexity of realization of Boolean functions with the small number of ones \jour Diskr. Mat. \yr 2020 \vol 32 \issue 2 \pages 32--43 \mathnet{http://mi.mathnet.ru/dm1592} \crossref{https://doi.org/10.4213/dm1592}