Проблема Дедекінда та класи Поста

• Datum: 2023
• Hauptverfasser: Nikolenko, Volodymyr, Mych, Ihor, Vartsaba, Olena
• Format: Artikel
• Sprache: Ukrainian
• Veröffentlicht: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2023
• Schlagworte: класи Поста; решітка Поста; базиси булевих функцій; проб¬лема Дедекінда
• Online Zugang: https://jais.net.ua/index.php/files/article/view/16
• Назва журналу: Problems of Control and Informatics

У роботі за допомогою класів Поста вивчаються булеві функції. Введено поняття характеристики Поста булевої функції та еквівалентних функцій за характеристикою Поста. На основі відношення еквівалентності за характеристикою Поста розглядаються 32 замкнені класи, які утворюють куб Поста. У цьому кубі 17 класів є порожніми, а решта 15 непорожніх утворюють решітку Поста. У роботі виведено формули для обчислення кількості функцій у класах Поста в залежності від числа змінних  Такі формули знайдено для 11 з 15 класів. Проблема обчислення потужностей непорожніх класів тісно повʼязана з проблемою Дедекінда. Задачу знаходження кількості монотонних функцій в залежності від числа змінних називають проблемою Дедекінда. У 1897 році цю задачу розвʼязав Дедекінд для n=4; у 1940 році Черч — для n=5; Вард — для n=6; для n=7 є розходження в отриманих оцінках. Найбільше значення числа Дедекінда відомо для n=8. Знайдено оцінки потужностей класів Поста, які дають можливість інакше підійти до розвʼязання проблеми Дедекінда. У даній роботі проведено аналітичні дослідження, за допомогою яких можна для довільної системи булевих функцій від довільної кількості змінних, для яких знайдено характеристики Поста, знайти всі можливі одно-, дво-, три- та чотирифункціональні базиси. Знайдено розподіли булевих функцій від трьох, чотирьох і пʼяти змінних за непорожніми класами Поста. Використовуючи приведений аналітичний апарат, можна обчислити число всіх можливих базисів. У роботі наведено приклад знаходження всіх базисів для булевих функцій, арність яких не перевищує пʼяти. У цьому прикладі знайдена кількість одно-, дво-, три- та чотирифункціональних базисів.