Control Systems and Computers, N4, 2019, Статья 1
https://doi.org/10.15407/csc.2019.04.003
Rytsar B.Ye. A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. I. Control Systems and Computers. 2019. № 4. pp. 3-13.
УДК 519.713
Б.Е. Рыцар, доктор технических наук, профессор, кафедра радиоэлектронных устройств и систем
Национальный университет «Львівська політехніка», ул. С. Бандеры, 12, Львов, 79013, Украина, E-mail: bohdanrytsar@gmail.com
НОВЫЙ МЕТОД РАСПОЗНАВАНИЯ СИММЕТРИИ В БУЛЕВЫХ ФУНКЦИЯХ НА ОСНОВЕ ТЕОРЕТИКО-МНОЖЕСТВЕННОГО
ЛОГИЧЕСКОГО ДИФФЕРЕНЦИРОВАНИЯ. I
Введение. Симметричные булевые функции благодаря своим специфическим свойствам широко используются в проектировании цифровых устройств, телекоммуникациях, криптографии и т.п. Поскольку булевые функции могут иметь разные типы симметрии с присущими им особенностями, важно уметь их распознавать как можно простейшими способами. Но проблема усложняется тем, что, с одной стороны, функции могут быть как одного типа, так и смешанного, а также как полностью симметричными, так и частично симметричными, а с другой стороны, сама функция может быть не полностью определена, т.е. задана частично, или задана ДНФ. Современные методы распознавания типов симметрии основаны преимущественно на аналитическом подходе (разложении Шеннона), визуальном методе, аналитическом вычислении логических производных и др., слишком сложны в реализации и мало эффективны для функций больших размеров и особенно, когда они заданы частично.
Цель статьи — разработать простой в реализации метод распознавания разных типов полных и частичных симметрий, как в полных, так и частично заданных булевых функциях.
Методы. В статье предложен новый метод распознавания разных типов полных и частичных симметрий, таких как полисимметрия, простая симметрия и антисимметрия, как в полностью, так и частично заданных функциях на основе численного теоретико-множественного логического дифференцирования. Алгоритм метода основан на теореме распознавания разных типов частичных симметрий, который, в сравнении с известными, имеет относительно меньшую вычислительную сложность благодаря сравнительно меньшему количеству операций и процедур, необходимых для выполнения поставленной задачи.
Результат. Справедливость доказанной теоремы показывают примеры распознавания разных типов полных и частичных симметрий как в полностью заданных функциях (часть I), так и частично заданных функциях (часть II), в том числе заданных в ДНФ, которые с целью сравнения эффективности предложенного алгоритма взято из публикаций известных авторов.
Выводы. Предложенный новый метод распознавания разных типов полных и частичных симметрий (полисимметрии, простые симметрии и антисимметрии) как в полностью, так и частично заданных булевых функциях на основе числового теоретико-множественного логического дифференцирования отличается от известных относительно простейшей практической реализацией.
Загрузить полный текст в PDF (на английском).
Ключевые слова: распознавание полных и частичных симметрий, булевая функция, числовое теоретико-множественное логическое дифференцирование.
Поступила 22.07.2019
