Полином Жегалкина многоместного самодостаточного оператора

Среди полных систем булевых функций особый интерес представляют самодостаточные операторы. Они обладают широкой областью применимости и не ограничиваются двухместным случаем. В данной работе формулируются условия, накладываемые на коэффициенты полинома Жегалкина, необходимые и достаточные для того, чтобы полином соответствовал самодостаточному оператору. Рассмотрено полиномиальное представление булевых функций, сохраняющих константу. Показано, что свойства монотонности и линейности не требуют специального рассмотрения при описании самодостаточного оператора. Вводится понятие полинома двойственного остатка, значение которого позволяет определить самодвойственность булевой функции. Доказано, что сохраняющая 0 и 1 или не сохраняющая ни 0, ни 1 булева функция является самодвойственной тогда и только тогда, когда двойственный остаток соответствующего ей полинома Жегалкина равен 0 для любых наборов значений переменных функции. На основании этого факта получена система ведущих коэффициентов. Решение данной системы позволило сформулировать критерий самодвойственности булевой функции, представленной полиномом Жегалкина, накладывающий необходимые и достаточные условия на коэффициенты полинома. Таким образом, показано, что полиномы Жегалкина являются достаточно удобным инструментом при исследовании предполных классов булевых функций.

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

2. N. M. Martin, Systems of Logic. Cambridge University Press, 1989.

3. R. L. Graham, “On n-Valued Functionally Complete Truth Functions,” The Journal of Symbolic Logic, vol. 32, no. 2, pp. 190–195, 1967.

4. T. C. Wesselkamper, “A sole sufficient operator,” NDJFAM, vol. 16, no. 1, pp. 86–88, 1975.

5. S. N. Selezneva, “O slozhnosti raspoznavaniya polnoty mnozhestv bulevyh funkcij, realizovannyh polinomami Zhegalkina,” DMA, vol. 9, no. 4, pp. 24–31, 1997.

6. S. S. Marchenkov, Zamknutye klassy bulevyh funkcij. Fizmatlit, 2000.

7. V. P. Barashev and S. A. Unuchek, Diskretnaya matematika. RTU MIREA, 2012.

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

9. N. V. Nikonov, “O svyazyah i otlichiyah poluzapretov I, II-go roda i zapretov K-znachnyh funkcij,” Forestry bulletin, no. 1, pp. 124–133, 2006.

10. S. S. Marchenkov, Osnovy teorii bulevyh funkcij. Fizmatlit, 2014.

11. L. Y. Bystrov and V. S. Rublev, “Bulevy funkcii, ne prinadlezhashchie predpolnym klassam,” in Zametki po informatike i matematike, vol. 13, Yaroslavl: P.G. Demidov Yaroslavl State University, 2021, pp. 22–26.

12. A. I. Kostrikin, Vvedenie v algebpu. Chast' 1. Osnovy algebpy. Fizmatlit, 2000.