Modelirovanie i Analiz Informatsionnykh Sistem
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






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


Modelirovanie i Analiz Informatsionnykh Sistem, 2022, Volume 29, Number 2, Pages 78–91
DOI: https://doi.org/10.18255/1818-1015-2022-2-78-91
(Mi mais768)
 

Discrete mathematics in relation to computer science

Application of election functions to estimate the number of monotone self-dual boolean functions

L. Yu. Bystrov, E. V. Kuz'min

P.G. Demidov Yaroslavl State University, 14 Sovetskaya str., Yaroslavl 150003, Russia
References:
Abstract: One of the problems of modern discrete mathematics is R. Dedekind problem on the number of monotone boolean functions. For other precomplete classes, general formulas for the number of functions of the classes had been found, but it has not been found so far for the class of monotone boolean functions. Within the framework of this problem, there are problems of a lower level. One of them is the absence of a general formula for the number of boolean functions of intersection $MS$ of two classes — the class of monotone functions and the class of self-dual functions. In the paper, new lower bounds are proposed for estimating the cardinality of the intersection for both an even and an odd number of variables. It is shown that the election function of an odd number of variables is monotone and self-dual. The election function of an even number of variables is determined. Free election functions, which are functions with fictitious variables similar in properties to election functions, are introduced. Then the union of a set of election functions and a set of free election functions is considered, and the cardinality of this union is calculated. The resulting value of the cardinality is proposed as a lower bound for $|MS|$. For the class $MS$ of monotone self-dual functions of an even number of variables, the lower bound is improved over the bounds proposed earlier, and for functions of an odd number of variables, the lower bound for $|MS|$ is presented for the first time.
Keywords: functions of election, self-dual boolean functions, monotone boolean functions, the Dedekind problem, boolean functions with fictitious variables, functions of free election, equilibrium sets, disjunctive normal form.
Funding agency
This work was supported by P.G. Demidov Yaroslavl State University Project № VIP-016.
Received: 04.05.2022
Revised: 28.05.2022
Accepted: 01.06.2022
Bibliographic databases:
Document Type: Article
UDC: 510.6
MSC: 06E30
Language: Russian
Citation: L. Yu. Bystrov, E. V. Kuz'min, “Application of election functions to estimate the number of monotone self-dual boolean functions”, Model. Anal. Inform. Sist., 29:2 (2022), 78–91
Citation in format AMSBIB
\Bibitem{BysKuz22}
\by L.~Yu.~Bystrov, E.~V.~Kuz'min
\paper Application of election functions to estimate the number of monotone self-dual boolean functions
\jour Model. Anal. Inform. Sist.
\yr 2022
\vol 29
\issue 2
\pages 78--91
\mathnet{http://mi.mathnet.ru/mais768}
\crossref{https://doi.org/10.18255/1818-1015-2022-2-78-91}
\mathscinet{https://mathscinet.ams.org/mathscinet-getitem?mr=4456623}
Linking options:
  • https://www.mathnet.ru/eng/mais768
  • https://www.mathnet.ru/eng/mais/v29/i2/p78
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Моделирование и анализ информационных систем
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025