Про один підхід до розв'язання проблеми Дедекінда

Автор(и)

DOI:

https://doi.org/10.24144/2616-7700.2024.45(2).223-229

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

монотонні функції, проблема Дедекінда, класи Поста, одноярусні монотонні функції

Анотація

У даній роботі показано, що клас монотонних функцій співпадає з класом тупикових диз'юнктивних нормальних форм (ТДНФ). Монотонні функції від n змінних можна задати на вершинах n-мірного кубу. У роботі знаходяться всі монотонні функції від n змінних (n = 1, 2, ..., 13), які є одноярусними ТДНФ. У даній роботі запропонований алгоритм для знаходження монотонних функцій, які є одноярусними тупиковими диз'юнктивними нормальними формами для n змінних.

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

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

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

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

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

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

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

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

Магістр факультету математики та цифрових технологій

Посилання

  1. Van Hirtum, L., De Causmaecker, P., Goemaere, J., & et al. (2023). A computation of D(9) using FPGA Supercomputing. Published online. https://doi.org/10.48550/arXiv.2304.03039
  2. Wiedemann, D. (1969). A computation of the eighth Dedekind number. Order, 8(1), 5–6. https://doi.org/10.1007/BF00385808
  3. Fidytek, R., Mostowski, A., Somla, R., & Szepietowski, A. (2011). Algorithms counting monotone Boolean functions. Inform. Process. Lett., 79(5) 203–209. https://doi.org/10.1016/S0020-0190(00)00230-1
  4. Bakoev, V. (June 15–21, 2012). On more way for counting monotone Boolean functions. Thirteenth International Workshop on Algebraic and Combinatorial Coding Theory. Pomorie: Bulgaria.
  5. Pawelski, B. (2021). On the number of inequivalent monotone Boolean functions of 8 variables. https://doi.org/10.48550/arXiv.2108.13997
  6. Mych, I. A., Nykolenko, V. V., & Vartsaba, O. V. (2022). Dedekind’s problem and Post’s classes. International Scientific Technical Journal "Problems of control and informatics", 67(5), 42–50. Retrieved from https://jnas.nbuv.gov.ua/article/UJRN-0001383907 [in Ukrainian].
  7. Szudzik, M. An Elegant Pairing Function. Retrieved from https://szudzik.com/ElegantPairing.pdf
  8. Kleitman, D. (1969). On Dedekind’s problem: the number of monotone Boolean functions. Proc. Amer. Math. Soc., 21, 677–682.
  9. Yusun, T. (2012). Counting inequivalent monotone Boolean functions. Retrieved from https://sfu.ca/∼tyusun/inequivalentMBF.html

##submission.downloads##

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

2024-11-21

Як цитувати

Мич, І. А., Ніколенко, В. В., Варцаба, О. В., & Когут, Н. І. (2024). Про один підхід до розв’язання проблеми Дедекінда. Науковий вісник Ужгородського університету. Серія «Математика і інформатика», 45(2), 223–229. https://doi.org/10.24144/2616-7700.2024.45(2).223-229

Номер

Том 45 № 2 (2024)

Розділ

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

Ліцензія

Авторське право (c) 2024 І. А. Мич, В. В. Ніколенко, О. В. Варцаба, Н. І. Когут

Creative Commons License

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

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