С.А. Ложкин, Д.С. Кинжикеева
Московский государственный университет имени М.В. Ломоносова, г. Москва, 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 БП с порогом 2n/3, глубина которой составляет основную часть глубины всего сумматора.
С точностью до изоморфизма или подобия, то есть до изоморфизма и эквивалентных преобразований на основе тождеств коммутативности и ассоциативности, описана структура СФЭ, реализующих ступенчатые ФАЛ от n БП с минимальной сложностью, равной (n−1), или минимальным рангом, равным n . Установлено точное значение глубины указанных СФЭ. Исследована возможность оптимизации СФЭ, реализующих ступенчатые ФАЛ, как по сложности, так и по глубине.
Ключевые слова: схемы из функциональных элементов, базис {&, ∨}, ступенчатые функции алгебры логики, минимизация сложности и глубины, структура минимальных схем
Благодарности. Работа выполнена при поддержке гранта Московского центра фундаментальной и прикладной математики и РФФИ (проект № 18-01-00800).
Литература
Поступила в редакцию 11.08.2020
Ложкин Сергей Андреевич, доктор физико-математических наук, заведующий кафедрой математической кибернетики факультета вычислительной математики и кибернетики
Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия
E-mail: lozhkin@cs.msu.ru
Кинжикеева Дина Сергеевна, аспирант кафедры математической кибернетики факультета вычислительной математики и кибернетики
Московский государственный университет имени М.В. Ломоносова Ленинские горы, д. 1, г. Москва, 119991, Россия
E-mail: kinzhikeyeva@yandex.ru
Контент доступен под лицензией Creative Commons Attribution 4.0 License.