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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Received: 03.10.2019

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}


Linking options:
  • http://mi.mathnet.ru/eng/dm1592
  • https://doi.org/10.4213/dm1592
  • http://mi.mathnet.ru/eng/dm/v32/i2/p32

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретная математика
    Number of views:
    This page:52
    References:5
    First page:5

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020