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

Автор(и)

DOI:

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

Ключові слова:

сигнатурний куб, граничні алгебри

Анотація

Дана робота є продовженням досліджень, розпочатих в [1], у яких теорія булевих функцій розглядається з точки зору універсальних алгебр. У цій роботі описано клас функціонально неповних алгебр, проведено дослідження основних типів алгебр і розташування їх по ярусах сигнатурного кубу. У даних дослідженнях універсальні булеві алгебри утворюють 11-мірний сигнатурний куб, до складу якого входять 2048 алгебр. Запропоновано нумерацію (кодифікацію) цих алгебр. Вводиться поняття суміжних, граничних, внутрішніх класів функціонально повних і функціонально неповних алгебр.

Булеві алгебри досліджуваного класу  поділяють на чотири підкласи: клас внутрішніх функціонально неповних алгебр, клас граничних функціонально неповних алгебр, клас граничних функціонально повних алгебр, клас внутрішніх функціонально повних алгебр. У даній роботі пропонується алгоритм знаходження граничних функціонально повних алгебр на основі розширення сигнатури функціонально неповних алгебр булевими операціями. Побудовані підкласи граничних алгебр для кожної з одинадцяти операцій. Вказано ізоморфізм графів деяких класів граничних алгебр. На основі об’єднання графів отримали -граф граничних функціонально повних алгебр.

Біографії авторів

І. А. Мич , ДВНЗ «Ужгородський національний університет»

доцент кафедри кібернетики і прикладної математики, кандидат фізико-математичних наук

В. В. Ніколенко, ДВНЗ «Ужгородський національний університет»

доцент кафедри інформаційних управляючих систем та технологій, кандидат фізико-математичних наук

О. В. Варцаба, ДВНЗ «Ужгородський національний університет»

аспірант кафедри кібернетики і прикладної математики

Посилання

  1. 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].
  2. Zhuravlev, Yu. I. (1964). Otsenka slozhnosti lokal’nykh algoritmov dlya nekotorykh ekstremal’nykh zadach na konechnykh mnozhestvakh. AN USSR, 5, 1018-1021 [in Russian].
  3. Yablonskiy, S. V. (1959). Ob algoritmicheskikh trudnostyakh sistem minimal’nykh skhem. Sbornik «Problemy kibernetiki». Moskva: Fizmalit, 75-121 [in Russian].
  4. Zykov, A. A. (1969). Teoriya konechnykh grafov. Moskva: Nauka, 554 [in Russian].
  5. 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

Номер

Розділ

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