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
