Application of Election Functions to Estimate the Number of Monotone Self-Dual Boolean functions
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 functio...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2022-06-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/1647 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1839573148680323072 |
|---|---|
| author | Leonid Y. Bystrov Egor V. Kuzmin |
| author_facet | Leonid Y. Bystrov Egor V. Kuzmin |
| author_sort | Leonid Y. Bystrov |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-2c60fa9a019f44e3b19192b1df69d67d |
| institution | Matheson Library |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2022-06-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-2c60fa9a019f44e3b19192b1df69d67d2025-08-04T14:06:43ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172022-06-01292789110.18255/1818-1015-2022-2-78-911265Application of Election Functions to Estimate the Number of Monotone Self-Dual Boolean functionsLeonid Y. Bystrov0Egor V. Kuzmin1P.G. Demidov Yaroslavl State UniversityP.G. Demidov Yaroslavl State UniversityOne 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.https://www.mais-journal.ru/jour/article/view/1647functions of electionself-dual boolean functionsmonotone boolean functionsthe dedekind problemboolean functions with fictitious variablesfunctions of free electionequilibrium setsdisjunctive normal form |
| spellingShingle | Leonid Y. Bystrov Egor V. Kuzmin Application of Election Functions to Estimate the Number of Monotone Self-Dual Boolean functions Моделирование и анализ информационных систем 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 |
| title | Application of Election Functions to Estimate the Number of Monotone Self-Dual Boolean functions |
| title_full | Application of Election Functions to Estimate the Number of Monotone Self-Dual Boolean functions |
| title_fullStr | Application of Election Functions to Estimate the Number of Monotone Self-Dual Boolean functions |
| title_full_unstemmed | Application of Election Functions to Estimate the Number of Monotone Self-Dual Boolean functions |
| title_short | Application of Election Functions to Estimate the Number of Monotone Self-Dual Boolean functions |
| title_sort | application of election functions to estimate the number of monotone self dual boolean functions |
| topic | 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 |
| url | https://www.mais-journal.ru/jour/article/view/1647 |
| work_keys_str_mv | AT leonidybystrov applicationofelectionfunctionstoestimatethenumberofmonotoneselfdualbooleanfunctions AT egorvkuzmin applicationofelectionfunctionstoestimatethenumberofmonotoneselfdualbooleanfunctions |