On symmetric boolean functions invariant under the Möbius transform
- Authors: Zubkov O.V.1
-
Affiliations:
- Иркутский государственный университет
- Issue: Vol 224 (2023)
- Pages: 71-79
- Section: Статьи
- URL: https://journals.rcsi.science/2782-4438/article/view/271275
- DOI: https://doi.org/10.36535/0233-6723-2023-224-71-79
- ID: 271275
Cite item
Full Text
Abstract
The work is devoted to the study of the class of Boolean functions that are invariant under the Möbius transform. In the first part of the paper, we systematize general information on the Möbius transform and its fixed points. In the second part, we consider a class of symmetric Boolean functions that are invariant under the Möbius transform. The relationship of these functions with columns of the Sierpinski triangle is shown. We propose a method for obtaining masks of all such functions as sums of columns of the Sierpinski triangle. For the case , we proved that a symmetric function is invariant if and only if its mask is invariant.
About the authors
O. V. Zubkov
Иркутский государственный университет
Author for correspondence.
Email: oleg.zubkov@mail.ru
Russian Federation, Иркутск
References
- Бухман А. В. О распознавании функций, инвариантных относительно преобразования Мёбиуса, и чёт-ных функций, заданных в форме полиномов// в кн.: Прикладная математика и информатика / Тр. ф-та ВМК МГУ им. М. В. Ломоносова. — М.: МАКС Пресс, 2012. — С. 105–112.
- Зубков О. В. Представление полиномиально устойчивых функций суммами бесповторных в элемен-тарном базисе слагаемых// Мат. 6 Междунар. школы-семинара «Синтаксис и семантика логических систем» (Монголия, Ханх, 11-16 августа 2019 г.). — Иркутск: Изд-во ИГУ, 2019. — С. 48–52.
- Зубков О. В. О классе полиномиально устойчивых булевых функций// Итоги науки техн. Совр. мат. прилож. Темат. обзоры. — 2022. — 214. — С. 37–43.
- Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии.— М.: МЦНМО, 2004.
- Яблонский С. В. Введение в дискретную математику. — M.: Высшая школа, 2001.
- MacWilliams F. J., Sloane N. J. A. The theory of Error-Correcting Codes. — Amsterdam–New York–Oxford: Noth-Holland, 1978.
- Pieprzyk J., Zhang X.-M. Computing Möbius transform of boolean functions and characterising coincident boolean functions// in: Boolean Functions: Cryptography and Applications. — Rouen, France: Publications des Univercites de Rouen et du Havre, 2007. — P. 135–151.
- Sloane N. J. A. Rows of Sierpinski’s triangle// http://oeis.org/A006943/b006943.txt.
Supplementary files
