Впровадження методу образних перетворень для мінімізації функцій Шеффера

Autor: Solomko, Mykhailo, Khomiuk, Nataliia, Ivashchuk, Yakiv, Nazaruk, Vitalii, Reinska, Vikroriia, Zubyk, Liudmyla, Popova, Anzhela
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Zdroj: Eastern-European Journal of Enterprise Technologies; Том 5, № 4 (107) (2020): Математика та кібернетика-прикладні аспекти; 19-34
Eastern-European Journal of Enterprise Technologies; Том 5, № 4 (107) (2020): Математика и кибернетика-прикладные аспекты; 19-34
Eastern-European Journal of Enterprise Technologies; Том 5, № 4 (107) (2020): Mathematics and Cybernetics-applied aspects; 19-34
ISSN: 1729-3774
1729-4061
Popis: The studies have established the possibility of reducing computational complexity, higher productivity of minimization of the Boolean functions in the class of expanded normal forms of the Sheffer algebra functions by the method of image transformations.Expansion of the method of image transformations to the minimization of functions of the Sheffer algebra makes it possible to identify new algebraic rules of logical transformations. Simplification of the Sheffer functions on binary structures of the 2-(n, b)-designs) features exceptional situations. They are used both when deriving the result of simplification of functions from a binary matrix and introducing the Sheffer function to the matrix.It was shown that the expanded normal form of the n-digit Sheffer function can be represented by binary sets or a matrix. Logical operations with the matrix structure provide the result of simplification of the Sheffer functions. This makes it possible to concentrate the principle of minimization within the truth table of a given function and do without auxiliary objects, such as Karnaugh map, Weich diagrams, coverage tables, etc.Compared with the analogs of minimizing the Sheffer algebra functions, the method under the study makes the following to be possible:‒ reduce algorithmic complexity of minimizing expanded normal forms of the Sheffer functions (ENSF-1 and ENSF-2);‒ increase the productivity of minimizing the Sheffer algebra functions by 100‒150 %;‒ demonstrate clarity of the process of minimizing the ENSF-1 or ENSF-2;‒ ensure self-sufficiency of the method of image transformations to minimize the Sheffer algebra functions by introducing the tag of minimum function and minimization in the complete truth table of the ENSF-1 and ENSF-2.There are reasons to assert that application of the method of image transformations to the minimization of the Sheffer algebra functions brings the problem of minimization of the ENSF-1 and ENSF-2 to the level of a well-studied problem in the class of disjunctive-conjunctive normal forms (DCNF) of Boolean functions
Проведенными исследованиями установлена возможность уменьшения вычислительной сложности, увеличение производительности минимизации булевых функций в классе совершенных нормальных форм функций алгебры Шеффера методом образных преобразований.Распространение метода образных преобразований на минимизацию функций алгебры Шеффера позволяет выявлять новые алгебраические правила логических преобразований. Особенностью упрощения функций Шеффера на бинарных структурах 2-(n, b)-блок-схем (англ. 2-(n, b)-designs) является исключительные ситуации. Они имеют применение как при выводе результата упрощения функций из бинарной матрицы, так и при введении функции Шеффера в матрицу.Показано, что совершенную нормальную форму n-местной функции Шеффера можно подать бинарными наборами или матрицей. Логические операции над структурой матрицы обеспечивают результат упрощения функций Шеффера. Это позволяет сосредоточить принцип минимизации в пределах таблицы истинности заданной функции и обойтись без вспомогательных объектов, таких как карта Карно, диаграммы Вейча, таблицы покрытия и др.По сравнению с аналогами минимизации функций алгебры Шеффера рассмотренный метод позволяет:– уменьшить алгоритмическую сложность минимизации совершенных нормальных форм функций Шеффера (СНФШ-1 и СНФШ-2);– увеличить производительность минимизации функций алгебры Шеффера на 100–150 %;– демонстрировать наглядность процесса минимизации СНФШ-1 или СНФШ-2;– обеспечить самодостаточность метода образных преобразований для минимизации функций алгебры Шеффера за счет внедрения признака минимальной функции и минимизации на полной таблице истинности ДНФШ-1 и ДНФШ-2.Есть основания утверждать, что применение метода образных преобразований для минимизации функций алгебры Шеффера выводит проблему минимизации СНФШ-1 и СНФШ-2 на уровень хорошо исследованной задачи в классе дизъюнктивно-конъюнктивные нормальных форм (ДКНФ) булевых функций
Проведеними дослідженнями встановлена можливість зменшення обчислювальної складності, збільшення продуктивності мінімізації булевих функцій у класі досконалих нормальних форм функцій алгебри Шеффера методом образних перетворень.Поширення методу образних перетворень на мінімізацію функцій алгебри Шеффера дає змогу виявляти нові алгебричні правила логічних перетворень. Особливістю спрощення функцій Шеффера на бінарних структурах 2-(n, b)-блок-схем (англ. 2-(n, b)-designs) є виняткові ситуації. Вони мають застосування як при виведенні результату спрощення функцій з бінарної матриці, так і при введенні функції Шеффера до матриці.Показано, що досконалу нормальну форму n-містної функції Шеффера можна подати бінарними наборами або матрицею. Логічні операції над структурою матриці забезпечують результат спрощення функцій Шеффера. Це дозволяє зосередити принцип мінімізації у межах таблиці істинності заданої функції та обійтись без допоміжних об’єктів, як то карта Карно, діаграми Вейча, таблиці покриття та ін.Порівняно з аналогами мінімізації функцій алгебри Шеффера розглянутий метод дозволяє:– зменшити алгоритмічну складність мінімізації досконалих нормальних форм функцій Шеффера (ДНФШ-1 та ДНФШ-2);– збільшити продуктивність мінімізації функцій алгебри Шеффера на 100–150 %;– демонструвати наочність процесу мінімізації ДНФШ-1 або ДНФШ-2;– забезпечити самодостатність методу образних перетворень для мінімізації функцій алгебри Шеффера за рахунок впровадження ознаки мінімальної функції та мінімізації на повній таблиці істинності ДНФШ-1 і ДНФШ-2.Є підстави стверджувати, що застосування методу образних перетворень для мінімізації функцій алгебри Шеффера виводить проблему мінімізації ДНФШ-1 та ДНФШ-2 на рівень добре дослідженої задачі у класі диз’юнктивно-кон’юнктивних нормальних форм (ДКНФ) булевих функцій
Databáze: OpenAIRE
Externí odkaz: