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

Abstract

У роботі за допомогою класів Поста вивчаються булеві функції. Введено поняття характеристики Поста булевої функції та еквівалентних функцій за характеристикою Поста. На основі відношення еквівалентності за характеристикою Поста розглядаються 32 замкнені класи, які утворюють куб Поста. У цьому кубі 17 класів є порожніми, а решта 15 непорожніх утворюють решітку Поста. У роботі виведено формули для обчислення кількості функцій у класах Поста в залежності від числа змінних Такі формули знайдено для 11 з 15 класів. Проблема обчислення потужностей непорожніх класів тісно повʼязана з проблемою Дедекінда. Задачу знаходження кількості монотонних функцій в залежності від числа змінних називають проблемою Дедекінда. У 1897 році цю задачу розвʼязав Дедекінд для n=4; у 1940 році Черч — для n=5; Вард — для n=6; для n=7 є розходження в отриманих оцінках. Найбільше значення числа Дедекінда відомо для n=8. Знайдено оцінки потужностей класів Поста, які дають можливість інакше підійти до розвʼязання проблеми Дедекінда. У даній роботі проведено аналітичні дослідження, за допомогою яких можна для довільної системи булевих функцій від довільної кількості змінних, для яких знайдено характеристики Поста, знайти всі можливі одно-, дво-, три- та чотирифункціональні базиси. Знайдено розподіли булевих функцій від трьох, чотирьох і пʼяти змінних за непорожніми класами Поста. Використовуючи приведений аналітичний апарат, можна обчислити число всіх можливих базисів. У роботі наведено приклад знаходження всіх базисів для булевих функцій, арність яких не перевищує пʼяти. У цьому прикладі знайдена кількість одно-, дво-, три- та чотирифункціональних базисів.The paper studies Boolean functions using Post classes. The concept of Post's characteristic of a Boolean function and equivalent functions according to Post's characteristic is introduced. Based on the equivalence relation by Post's characteristic, 32 closed classes are considered, which form the Post cube. In this cube, 17 classes are empty, and the remaining 15 non-empty classes form the Post lattice. The paper derives formulas to calculate the number of functions in the Post classes depending on the number of variables. Such formulas have been found for 11 out of 15 classes. The problem of computing the powers of non-empty classes is closely related to Dedekind's problem. The task of finding the number of monotone functions depending on the number of variables is called Dedekind's problem. In 1897, Dedekind solved this problem for n=4; in 1940, Church solved it for n=5; Ward solved it for n=6; for n=7, there are discrepancies in the obtained estimates. The largest known value of the Dedekind number is for n=8. Estimates for the powers of Post's classes have been found, which provide an alternative approach to solving Dedekind's problem. In this paper, analytical studies are conducted, through which, for any system of Boolean functions with any number of variables for which Post's characteristics are found, all possible one-, two-, three-, and four-functional bases can be determined. Distributions of Boolean functions with three, four, and five variables are found across the non-empty Post classes. Using the analytical apparatus presented, it is possible to calculate the number of all possible bases. The paper presents an example of finding all bases for Boolean functions with an arity of up to five. In this example, the number of one-, two-, three-, and four-functional bases is determined.