Preview

Моделирование и анализ информационных систем

Расширенный поиск

Применение функций голосования для оценки числа монотонных самодвойственных булевых функций

https://doi.org/10.18255/1818-1015-2022-2-78-91

Аннотация

Одной из проблем современной дискретной математики является проблема Р. Дедекинда о числе монотонных булевых функций. Если для прочих предполных классов были найдены общие формулы числа функций этих классов, то для класса монотонных булевых функций этого сделать пока не удалось. В рамках этой проблемы существуют проблемы меньшего уровня, одной из которых является отсутствие общей формулы числа булевых функций пересечения $MS$ двух классов --- класса монотонных функций и класса самодвойственных функций. В данной работе предлагаются новые нижние границы для оценки мощности этого пересечения как для чётного, так и для нечётного количества переменных. Показывается, что функция голосования от нечётного числа переменных является монотонной и самодвойственной. Определяется функция голосования от чётного числа переменных. Вводятся функции свободного голосования --- функции с фиктивными переменными, близкие по свойствам к функциям голосования. Рассматривается объединение множества функций голосования и множества функций свободного голосования. Вычисляется мощность этого объединения. Полученное значение мощности предлагается в качестве нижней границы для $|MS|$. Для класса $MS$ монотонных самодвойственных функций от чётного числа переменных нижняя граница была улучшена по сравнению с границами, предложенными ранее, а для функций от нечётного числа переменных нижняя граница для $|MS|$ представлена впервые.

Об авторах

Леонид Юрьевич Быстров
Ярославский государственный университет им. П.Г. Демидова
Россия


Егор Владимирович Кузьмин
Ярославский государственный университет им. П.Г. Демидова
Россия


Список литературы

1. D. J. Kleitman, “On Dedekind’s Problem: The Number of Monotone Boolean Functions”, Proceedings of the American Mathematical Society, vol. 21, no. 3, pp. 677-682, 1969.

2. L. Y. Bystrov and V. S.Rublev, “Bulevy funkcii, ne prinadlezhashchie predpolnym klassam”, Zametki po informatike i matematike, vol. 13, pp. 22-26, 2021.

3. L. Haviarova and E. Toman, “The Number of Monotone and Self-Dual Boolean Functions”, JAMSI, vol. 10, no. 2, pp. 93-111, 2014.

4. S. V. Yablonskiy, Introduction into discrete mathematics, 5th ed. HSE, 2008.

5. G. P. Gavrilov and A. A. Sapozhenko, Zadachi i uprazhneniya po diskretnoj matematike. Fizmatlit, 2005.

6. A. A.Rubchinskiy, Diskretnye matematicheskie modeli. Nachal’nye ponyatiya i standartnye zadachi: uchebnoe posobie. Direct-Media, 2014.

7. D. N. Zhuk, “Ot dvuznachnoj k k-znachnoj logike”, Intellektual’nye sistemy. Teoriya i prilozheniya, vol. 22, no. 1, pp. 131-149, 2018.

8. V. N. Semenchuk, Diskretnaya matematika. Kurs lekcij. Francysk Skaryna Homiel State University, 2007.

9. A. D. Korshunov, “Reshenie problemy dedekinda o chisle monotonnyh bulevyh funkcij”, Doklady Akademii Nauk SSSR, vol. 233, no. 4, pp. 543-546, 1977.


Рецензия

Для цитирования:


Быстров Л.Ю., Кузьмин Е.В. Применение функций голосования для оценки числа монотонных самодвойственных булевых функций. Моделирование и анализ информационных систем. 2022;29(2):78-91. https://doi.org/10.18255/1818-1015-2022-2-78-91

For citation:


Bystrov L.Y., Kuzmin E.V. Application of Election Functions to Estimate the Number of Monotone Self-Dual Boolean functions. Modeling and Analysis of Information Systems. 2022;29(2):78-91. (In Russ.) https://doi.org/10.18255/1818-1015-2022-2-78-91

Просмотров: 528


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)