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

Одной из проблем современной дискретной математики является проблема Р. Дедекинда о числе монотонных булевых функций. Если для прочих предполных классов были найдены общие формулы числа функций этих классов, то для класса монотонных булевых функций этого сделать пока не удалось. В рамках этой проблемы существуют проблемы меньшего уровня, одной из которых является отсутствие общей формулы числа булевых функций пересечения $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.