Стукртура сигнатурного кубу булевих алгебр
DOI:
https://doi.org/10.24144/2616-7700.2021.38(1).149-156Ключові слова:
сигнатурний куб, граничні алгебриАнотація
Дана робота є продовженням досліджень, розпочатих в [1], у яких теорія булевих функцій розглядається з точки зору універсальних алгебр. У цій роботі описано клас функціонально неповних алгебр, проведено дослідження основних типів алгебр і розташування їх по ярусах сигнатурного кубу. У даних дослідженнях універсальні булеві алгебри утворюють 11-мірний сигнатурний куб, до складу якого входять 2048 алгебр. Запропоновано нумерацію (кодифікацію) цих алгебр. Вводиться поняття суміжних, граничних, внутрішніх класів функціонально повних і функціонально неповних алгебр.
Булеві алгебри досліджуваного класу поділяють на чотири підкласи: клас внутрішніх функціонально неповних алгебр, клас граничних функціонально неповних алгебр, клас граничних функціонально повних алгебр, клас внутрішніх функціонально повних алгебр. У даній роботі пропонується алгоритм знаходження граничних функціонально повних алгебр на основі розширення сигнатури функціонально неповних алгебр булевими операціями. Побудовані підкласи граничних алгебр для кожної з одинадцяти операцій. Вказано ізоморфізм графів деяких класів граничних алгебр. На основі об’єднання графів отримали -граф граничних функціонально повних алгебр.
Посилання
- Mych, I. A., Nykolenko, V. V., & Vartsaba, O. V. (2020). Investigation of signature cube ofuniversal boolean algebra. Scientific Bulletin of Uzhhorod University. Series of Mathematics and Informatics, 2(37), 157-167. https://doi.org/10.24144/2616-7700.2020.2(37).157-167 [in Ukrainian].
- Zhuravlev, Yu. I. (1964). Otsenka slozhnosti lokal’nykh algoritmov dlya nekotorykh ekstremal’nykh zadach na konechnykh mnozhestvakh. AN USSR, 5, 1018-1021 [in Russian].
- Yablonskiy, S. V. (1959). Ob algoritmicheskikh trudnostyakh sistem minimal’nykh skhem. Sbornik «Problemy kibernetiki». Moskva: Fizmalit, 75-121 [in Russian].
- Zykov, A. A. (1969). Teoriya konechnykh grafov. Moskva: Nauka, 554 [in Russian].
- Uilson, R. J. (2019). Vvedenie v teoriyu grafov. Spb: OOO «Dialektika», 240 [in Russian].
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2021 І. А. Мич , В. В. Ніколенко, О. В. Варцаба
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.