ДЕКОМПОЗИЦИЯ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ - ПРОВЕРКА НА РАЗДЕЛИМОСТЬ ПО ЗАДАННОМУ РАЗБИЕНИЮ
Abstract
Рассматривается задача последовательной двухблочной декомпозиции частичных булевых функций по нестрогому разбиению на множестве аргументов. Предлагаются метод и алгоритм проверки функции на разделимость по заданному разбиению. При решении этой задачи используется аппарат булевых и троичных векторов и матриц с эффективными комбинаторными операциями над ними.
References
1. Perkowski, M.A. A survey of literature on function decomposition, Version IV / M.A. Perkowski, Grigiel. – Portland State University, 1995.
2. Поваров, Г.Н. О функциональной разделимости булевых функций / Г.Н. Поваров // Доклады АН СССР. – Т. 94, № 5. – 1954.
3. Ashenhurst, R.L. The decomposition of switching functions / R.L. Ashenhurst // Proc. International Symposium on the Theory of Switching: Part 1. – Cambridge: Harward University Press, 1959. – P. 75–116.
4. Curtis, H.A. Design of switching circuits / H.A. Curtis. – Van Nostrand, Princeton, N. J., 1962.
5. Закревский, А.Д. Алгоритм разделения булевой функции / А.Д. Закревский // Тр. Сибирского физико-технического института. – 1964. – Т. 44. – С. 5-16.
6. Закревский, А.Д. Векторный алгоритм анализа булевой функции на декомпозируе-мость по заданному разбиению / А.Д. Закревский // Доклады НАН Беларуси. – 2006. – Т. 50, № 5. – С. 28–29.
7. Харари, Ф. Теория графов / Ф. Харари. – М.: Мир, 1973.
Review
For citations:
. Informatics. 2007;(1(13)):16-21. (In Russ.)
Views: 491
Email this article 