We continue the study of binary threshold substitutions - bijective transformations of the set of binary vectors whose coordinate functions are threshold functions. It is proven that the set of binary threshold substitutions generates an imprimitive group, which acts on the set of 2n-1 blocks {a, a} permutationally similar to the wreath product S2 ≀ S2n-1. It is shown that, within the class of {0,1}-matrices, only permutation matrices realize threshold substitutions. A recursive method for constructing a class of full-cycle threshold substitutions is proposed. The possibility of practical applications of such substitutions is investigated.
- Title Binary treshold substitutions
- Headline Binary treshold substitutions
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 71
- Date:
- DOI 10.17223/20710410/71/1
Keywords
binary threshold functions, binary bijective transformations, threshold substitutionsAuthors
References
Дертоузос М. Пороговая логика. М.: Мир, 1967.
Бутаков Е. А. Методы синтеза релейных устройств из пороговых элементов. М.: Энергия, 1970.
Зуев Ю. А. Пороговые функции и пороговые представления булевых функций // Математические вопросы кибернетики. Вып.5. М.: Наука, 1994.
Никонов В. Г., Сидоров Е. С. О способе построения взаимно однозначных отображений при помощи квазиадамаровых матриц // Лесной вестник. 2009. №2. С. 155-158.
Никонов В. Г., Литвиненко В. С. Геометрический подход к доказательству биективности одного координатно-порогового отображения // Comp. Nanotechnol. 2015. No. 1. Р. 26-31.
Никонов В. Г., Литвиненко В. С. О биективности преобразований, задаваемых квазиа-дамаровыми матрицами // Comp. Nanotechnol. 2016. No. 1. P.6-13.
Никонов В. Г., Кононов С. А. О некоторых свойствах квазиадамаровых матриц, задающих биективнвіе преобразования // Comp. Nanotechnol. 2022. V. 9. No. 1. P.32-38.
Никонов В. Г., Зобов А. И. Построение обратимого полноциклового преобразования в пороговом базисе // Comp. Nanotechnol. 2023. V. 10. No. 2. P.36-41.
Шурупов A. H. Критерии функционалвной разделимости квадратичных булевых пороговых функций // Прикладная дискретная математика. 2015. №2(28). С. 37-45.
Шурупов А. Н. Некоторые структурные свойства квадратичных булевых пороговых функций // Прикладная дискретная математика. Приложение. 2015. №8. С. 48-51.
Логачев О. А., Сальников А. А., Смышляев С. В., Ященко В. В. Булевы функции в теории кодирования и криптологии. 2-е изд. М.: МЦНМО, 2012. 584с.
Carey М. R. and Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness. N.Y.: W. H. Freeman and Company, 1979.
MacWilliams F. J. and Sloane N. J.A. The Theory of Error-Correcting Codes. Amsterdam: Elsevier, 1977.
Лидл P., Нидерайтер Г. Конечные поля. Т. 1. М.: Мир, 1988. 430 с.
Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра: учебник для вузов. 5-е изд. СПб.: Лани, 2024. 608 с.
Binary treshold substitutions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2026. № 71. DOI: 10.17223/20710410/71/1
Download full-text version
Counter downloads: 45