О структуре, сложности и глубине схем в базисе {&,˅}, реализующих ступенчатые функции алгебры логики

С.А. Ложкин, Д.С. Кинжикеева

Московский государственный университет имени М.В. Ломоносова, г. Москва, 119991, Россия

Полный текст PDF
DOI: 10.26907/2541-7746.2020.3.335-349

Для цитирования: Ложкин С.А., Кинжикеева Д.С. О структуре, сложности и глубине схем в базисе {&, ∨} , реализующих ступенчатые функции алгебры логики // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2020. – Т. 162, кн. 3. – С. 335–349. – doi: 10.26907/2541-7746.2020.3.335-349.

For citation: Lozhkin S.A., Kinzhikeyeva D.S. On the structure, complexity, and depth of the circuits over the basis {&, ∨} realizing step Boolean functions. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 335–349. doi: 10.26907/2541-7746.2020.3.335-349. (In Russian)

Аннотация

Решается задача синтеза схем из функциональных элементов (СФЭ) в базисе {&, ∨}, реализующих ступенчатые функции алгебры логики (ФАЛ) от n , n = 1, 2,…, булевых переменных (БП), то есть ФАЛ, обращающиеся в единицу на всех наборах единичного куба размерности n , номера которых не меньше заданного числа – порога этой ФАЛ.

Ступенчатые ФАЛ часто встречаются в теоретических и прикладных исследованиях в качестве вспомогательных ФАЛ. Так, схемная реализация n-разрядного двоичного сумматора включает в себя подсхему, реализующую ступенчатую ФАЛ от n БП с порогом 2ⁿ/3, глубина которой составляет основную часть глубины всего сумматора.

С точностью до изоморфизма или подобия, то есть до изоморфизма и эквивалентных преобразований на основе тождеств коммутативности и ассоциативности, описана структура СФЭ, реализующих ступенчатые ФАЛ от n БП с минимальной сложностью, равной (n−1), или минимальным рангом, равным n . Установлено точное значение глубины указанных СФЭ. Исследована возможность оптимизации СФЭ, реализующих ступенчатые ФАЛ, как по сложности, так и по глубине.

Ключевые слова: схемы из функциональных элементов, базис {&, ∨}, ступенчатые функции алгебры логики, минимизация сложности и глубины, структура минимальных схем

Благодарности. Работа выполнена при поддержке гранта Московского центра фундаментальной и прикладной математики и РФФИ (проект № 18-01-00800).

Литература

1. Храпченко В.М. Об асимптотической оценке времени сложения параллельного сумматора // Проблемы кибернетики. – М.: Наука, 1967. – Вып. 19. – С. 107–122.
2. Гринчук М.И. Уточнение верхней оценки глубины сумматора и компаратора // Дискрет. анализ и исслед. операций. – 2008. – Т. 15, № 2. – С. 12–22.
3. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. – M.: Изд-во Моск. ун-та, 1989. – 138 с.
4. Ложкин С.А. Лекции по основам кибернетики. – М.: Изд. отд. фак. ВМиК МГУ, 2004. – 253 с.
5. Ложкин С.А., Кинжикеева Д.С. О структуре, сложности и глубине схем в базисе &, ∨ , реализующих ступенчатые функции алгебры логики // Проблемы теоретической кибернетики: Материалы заочного семинара XIX Междунар. конф. / Под ред. Ю.И. Журавлева. – Казань: Изд-во Казан. ун-та, 2020. – С. 72–75.
6. Кинжикеева Д.С. Методы синтеза схем из некоторых классов, реализующих функции ступенчатого типа, оценки их сложности и глубины: Магистерская дис. – М.: МГУ им. М.В. Ломоносова. Фак. вычисл. матем. и кибернетики. Каф. матем. кибернетики, 2020. – 27 с.
7. Власкин В.М. О сложности и глубине схем, реализующих ступенчатые функции: Дипл. работа. – М.: МГУ им. М.В. Ломоносова. Фак. вычисл. матем. и кибернетики. Каф. матем. кибернетики, 1995. – 13 с.

Поступила в редакцию 11.08.2020

Ложкин Сергей Андреевич, доктор физико-математических наук, заведующий кафедрой математической кибернетики факультета вычислительной математики и кибернетики

Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия

E-mail: lozhkin@cs.msu.ru

Кинжикеева Дина Сергеевна, аспирант кафедры математической кибернетики факультета вычислительной математики и кибернетики

Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия

E-mail: kinzhikeyeva@yandex.ru

Контент доступен под лицензией Creative Commons Attribution 4.0 License.