Применение функций голосования для оценки числа монотонных самодвойственных булевых функций
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