Стукртура сигнатурного кубу булевих алгебр

І. А. Мич; В. В. Ніколенко; О. В. Варцаба

doi:10.24144/2616-7700.2021.38(1).149-156

Стукртура сигнатурного кубу булевих алгебр

Автор(и)

І. А. Мич ДВНЗ «Ужгородський національний університет», Ukraine https://orcid.org/0000-0002-3392-1442
В. В. Ніколенко ДВНЗ «Ужгородський національний університет», Ukraine https://orcid.org/0000-0003-0071-6896
О. В. Варцаба ДВНЗ «Ужгородський національний університет», Ukraine https://orcid.org/0000-0001-9158-2365

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##

Опубліковано

2021-05-27

Як цитувати

Мич , І. А., Ніколенко, В. В., & Варцаба, О. В. (2021). Стукртура сигнатурного кубу булевих алгебр. Науковий вісник Ужгородського університету. Серія «Математика і інформатика», 38(1), 149–156. https://doi.org/10.24144/2616-7700.2021.38(1).149-156

Завантажити посилання

Номер

Том 38 № 1 (2021)

Розділ

Iнформатика, комп’ютернi науки та прикладна математика

Ліцензія

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.