Проблема Дедекінда та класи Поста
У роботі за допомогою класів Поста вивчаються булеві функції. Введено поняття характеристики Поста булевої функції та еквівалентних функцій за характеристикою Поста. На основі відношення еквівалентності за характеристикою Поста розглядаються 32 замкнені класи, які утворюють куб Поста. У цьому кубі 1...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2022 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2022
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/210910 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Проблема Дедекінда та класи Поста / І.А. Мич, В.В. Ніколенко, О.В. Варцаба // Проблеми керування та інформатики. — 2022. — № 5. — С. 42-50. — Бібліогр.: 6 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859502027410767872 |
|---|---|
| author | Мич, І.А. Ніколенко, В.В. Варцаба, О.В. |
| author_facet | Мич, І.А. Ніколенко, В.В. Варцаба, О.В. |
| citation_txt | Проблема Дедекінда та класи Поста / І.А. Мич, В.В. Ніколенко, О.В. Варцаба // Проблеми керування та інформатики. — 2022. — № 5. — С. 42-50. — Бібліогр.: 6 назв. — укр. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | У роботі за допомогою класів Поста вивчаються булеві функції. Введено поняття характеристики Поста булевої функції та еквівалентних функцій за характеристикою Поста. На основі відношення еквівалентності за характеристикою Поста розглядаються 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.
|
| first_indexed | 2026-03-12T23:47:12Z |
| format | Article |
| fulltext |
© І.А. МИЧ, В.В. НІКОЛЕНКО, О.В. ВАРЦАБА, 2022
42 ISSN 2786-6491
МЕТОДИ ОБРОБКИ ТА ЗАХИСТУ ІНФОРМАЦІЇ
УДК 519.7
І.А. Мич, В.В. Ніколенко, О.В. Варцаба
ПРОБЛЕМА ДЕДЕКІНДА ТА КЛАСИ ПОСТА
Мич Ігор Андрійович
Ужгородський національний університет,
ihor.mych@uzhnu.edu.ua
Ніколенко Володимир Володимирович
Ужгородський національний університет,
volodymyr.nikolenko@uzhnu.edu.ua
Варцаба Олена Василівна
Ужгородський національний університет,
olena.vartsaba@uzhnu.edu.ua
У роботі за допомогою класів Поста вивчаються булеві функції. Введено
поняття характеристики Поста булевої функції та еквівалентних функцій за
характеристикою Поста. На основі відношення еквівалентності за характе-
ристикою Поста розглядаються 32 замкнені класи, які утворюють куб Пос-
та. У цьому кубі 17 класів є порожніми, а решта 15 непорожніх утворюють
решітку Поста. У роботі виведено формули для обчислення кількості фун-
кцій у класах Поста в залежності від числа змінних 1 2, ,..., .nx x x Такі фор-
мули знайдено для 11 з 15 класів. Проблема обчислення потужностей не-
порожніх класів тісно повʼязана з проблемою Дедекінда. Задачу знахо-
дження кількості монотонних функцій в залежності від числа змінних
називають проблемою Дедекінда. У 1897 році цю задачу розвʼязав Деде-
кінд для n 4; у 1940 році Черч — для n 5; Вард — для n 6; для n 7 є
розходження в отриманих оцінках. Найбільше значення числа Дедекінда
відомо для n 8. Знайдено оцінки потужностей класів Поста, які дають
можливість інакше підійти до розвʼязання проблеми Дедекінда. У даній
роботі проведено аналітичні дослідження, за допомогою яких можна для
довільної системи булевих функцій від довільної кількості змінних, для
яких знайдено характеристики Поста, знайти всі можливі одно-, дво-, три-
та чотирифункціональні базиси. Знайдено розподіли булевих функцій від
трьох, чотирьох і пʼяти змінних за непорожніми класами Поста. Викорис-
товуючи приведений аналітичний апарат, можна обчислити число всіх мо-
жливих базисів. У роботі наведено приклад знаходження всіх базисів для
булевих функцій, арність яких не перевищує пʼяти. У цьому прикладі
знайдена кількість одно-, дво-, три- та чотирифункціональних базисів.
Ключові слова: класи Поста, решітка Поста, базиси булевих функцій, проб-
лема Дедекінда.
mailto:ihor.mych@uzhnu.edu.ua
mailto:volodymyr.nikolenko@uzhnu.edu.ua
mailto:olena.vartsaba@uzhnu.edu.ua
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 5 43
Вступ
Однією з важливих задач дискретної математики є задача знаходження потуж-
ності класу монотонних булевих функцій, яка відома як проблема Дедекінда [1–3].
Науковці багатьох країн продовжують роботу щодо розвʼязання цієї проблеми у
двох напрямках. Перший полягає у тому, щоб обчислити число монотонних функ-
цій для заданого n шляхом виведення відповідних формул або алгоритмів підра-
хунку, а другий — в оцінці цього числа [3]. У 1954 році Гільберт отримав першу
наближену оцінку числа монотонних функцій. В таких роботах, як [2–6], було по-
кращено цю оцінку. У [2] підраховано число монотонних функцій для восьми
змінних. Цей результат підтверджений у [4].
Основні означення і поняття
Позначимо 0A клас булевих функцій, які зберігають нуль; 1A — клас буле-
вих функцій, які зберігають одиницю, L — клас лінійних функцій; M — клас
монотонних функцій; S — клас самодвоїстих функцій.
Кожній булевій функції 1 2( , ,..., )nf x x x поставимо у відповідність пʼяти-
мірний булевий вектор 1 2 1 2 3 4 5( ( , ,..., )) ( , , , , ),nH f x x x де 1 0, якщо
0f A , і 1 1, якщо 0 ;f A 2 0, якщо 1f A , і 2 1, якщо 1;f A
3 0, якщо f L , і 3 1, якщо ;f L 4 0, якщо f M , і 4 1, якщо
0 ;f M 5 0, якщо f S , і 5 1, якщо .f S
Вектор 1 2( ( , ,..., ))nH f x x x назвемо характеристикою Поста булевої функції
1 2( , ,..., ),nf x x x що вказує на належність цієї функції класам Поста.
Означення 1. Дві булеві функції 1 1 2( , ,..., )nf x x x та 2 1 2( , ,..., )mf x x x нази-
ваються еквівалентними за характеристикою Поста, якщо 1 1 2( ( , ,..., ))nH f x x x
2 1 2( ( , ,..., )).mH f x x x
Відношення еквівалентності за характеристикою Поста розібʼє множину всіх
булевих функцій на 32 замкнені класи, які утворюють пʼятимірний куб. Далі бу-
демо називати його кубом Поста (рис. 1).
Рис. 1
44 ISSN 2786-6491
На рис. 1 зображено куб Поста, вершинами якого є класи еквівалентності, в
яких розміщуються еквівалентні за характеристикою Поста булеві функції. У ве-
ршинах позначено характеристику відповідного класу і номер вершини куба Поста.
Порожні класи та решітка Поста
У кубі Поста вершини можна розбити на два класи.
Означення 2. Клас еквівалентності куба Поста називається порожнім, якщо не
існує булевих функцій, які мають характеристики Поста цього класу.
Встановлено, що у кубі Поста порожніми є 17 класів, а саме n1, n2, n5–n7, n8,
n10, n11, n15, n16, n18–n22, n 27, n28, а решта 15 — непорожні, які утворюють решіт-
ку Поста (рис. 2).
Рис. 2
Вершини решітки Поста розташовані на шести ярусах. На першому знахо-
диться множина булевих функцій класу n0, на другому — множини двох класів:
n3 — функції, які не належать класу L, і n4 — функції, які не належать класу M.
На третьому ярусі знаходяться функції класів n9, n12–n14, функції яких не нале-
жать двом із п’яти класів Поста, на четвертому — класи n17, n23, n24, n25, на
п’ятому — класи n26, n29, n30 і на останньому — клас n31, функції якого не нале-
жать жодному класу Поста (шеферові функції). У решітці Поста можна виділити
п’ять класів функцій. Функції, які зберігають нуль , належать підкласам
0 3 4 12 13 14 15 16 30, , , , , , , , ;n n n n n n n n n функції класу 1A — підкласам 0 3 4, , ,n n n
9 13 14 23 25 29, , , , , ;n n n n n n лінійні функції — підкласам 0 4 9 12 17, , , , ,n n n n n 23 24, ;n n
монотонні — підкласам 0 3 9 12 14, , , ,n n n n n , самодвоїсті функції — підкласам
0 3 4 13 17 26, , , , , .n n n n n n Позначимо in кількість булевих функцій, які входять до
класу .in
Клас лінійних функцій
Із функцій замкнутих класів 0 ,n 4 ,n 9 ,n 12 ,n 17 ,n 23 ,n 24 ,n які утворюють під-
граф лінійних функцій решітки Поста (рис. 3), складається клас лінійних функцій.
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 5 45
Рис. 3
Клас функцій 0 1 2{ , ,..., }kn x x x — це функції змінних, які належать всім
п’яти класам Поста. Класу 9n належить функція-константа «одиниця», яка не
зберігає нуль і є монотонною. Класу 12n належить константа «нуль». Аналогічно
ця функція не зберігає одиницю і є монотонною. Зрозуміло, що 9 12 1.n n
Побудуємо дерево (рис. 4), яке розіб’є решту лінійних функцій за класами
Поста. Класи 17n і 23n містять у поліномах Жегалкіна одиницю, а класи 4n і 24n
її не містять. У класах 23n і 4n поліноми мають непарну кількість доданків, а в
класах 24n і 17n — парну.
Рис. 4
Клас лінійних функцій, які не зберігають нуль і одиницю, — це клас 17 .n
Цей клас утворюють функції, поліноми яких мають такий вигляд: 11 ,x
1 2 31 ,x x x 1 2 3 4 51 ,x x x x x …, 1 2 31 x x x … 2lx 2 1lx і т.д.
За допомогою наведених вище представлень функцій класу 17n обчислимо
його потужність за формулою
1 3 5 2 1
17
1 3 2 1
... , якщо 2 1,
... , якщо 2 .
l
n n n n
l
n n n
C C C C n l
n
C C C n l
Лінійні функції, які не зберігають нуль і зберігають одиницю, утворюють
клас 23.n Ці функції можна представити поліномами такого вигляду: 1 21 ,x x
1 31 ,x x 1 2 31 ,x x x …, 1 21 ... nх х x і т.д.
Аналогічно встановимо потужність класу 23 :n
2 4 2
23
2 4 2
... , якщо 2 1,
... , якщо 2 .
l
n n n
l
n n n
C C C n l
n
C C C n l
Клас лінійних функцій, які зберігають нуль і не зберігають одиницю ,
входять до класу 24 .n Функції цього класу представляються такими поліно-
мами:
1 2 2
... ,
lі і іx x x а отже:
2 4 2
24
2 4 2
... , якщо 2 1,
... , якщо 2 .
l
n n n
l
n n n
C C C n l
n
C C C n l
46 ISSN 2786-6491
Лінійні функції класу 4 ,n які зберігають нуль і одиницю, можуть бути пред-
ставлені такими поліномами:
1 2 2 1
... .
lі і іx x x
Тоді
2 4 2
4
3 5 2 1
... , якщо 2 1,
... , якщо 2 .
l
n n n
l
n n n
C C C n l
n
C C C n l
Співвідношення між потужностями класів Поста
Розіб’ємо множину булевих функцій від n змінних на чотири класи: 0 1,A A
0 1,A A 0 1,A A 0 1,A A тобто класи, які відповідно зберігають нуль і одиницю, зберіга-
ють нуль і не зберігають одиницю, не зберігають нуль і зберігають одиницю, не збері-
гають нуль і одиницю. В кожному з цих класів знаходиться четверта частина функцій.
З решітки Поста отримуємо такі формули:
2 2
25 13 14 3 4 0 2 ;
n
n n n n n n (1)
2 2
30 24 12 2 ;
n
n n n (2)
2 2
29 23 9 2 ;
n
n n n (3)
2 2
31 26 17 2 .
n
n n n (4)
Множину самодвоїстих функцій розіб’ємо за характеристиками 0A і 1A на два
підкласи 0 1A A і 0 1.A A Оскільки
122 ,
n
S
то мають місце такі співвідношення:
12
26 17
1
2 ;
2
n
n n
(5)
12
13 3 4 0
1
2 .
2
n
n n n n
(6)
Оскільки відома потужність класу лінійних функцій 17n , то з рівності (5)
отримуємо
12
26 17
1
2
2
n
n n
.
Використовуючи формули (4) і (5), знайдемо потужність класу 31 :n
12 2 2
31
1
2 2 .
2
n n
n
(7)
З (7) випливає, що кількість однофункціональних базисів (шеферових функ-
цій), арність яких не перевищує n , дорівнює
12 2 21
2 2 .
2
n n
Оскільки відомі потужності класів лінійних функцій 23 9,n n та 24 12, ,n n то з
рівностей (2) і (3) отримуємо формули для обчислення потужності двох класів:
22
30 24 122 ( );
n
n n n
(8)
22
29 23 92 ( ).
n
n n n
(9)
Не знайдено поки формули для обчислення 3 13 14 25, , ,n n n n . Число мо-
нотонних функцій від n змінних знаходиться за формулою 0 3 9nM n n n
12 14n n . Знаходження 3n і 14n веде до розв’язання проблеми Дедекінда.
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 5 47
Алгоритм знаходження базисів
Нехай система S складається з функцій 1 2, , ..., ,kf f f для кожної з яких
знайдено характеристики Поста 1 2 3 4 5( ) ( , , , , ),i i i i i
iH f 1, 2,..., .i k
Означення 3. Характеристикою Поста системи S називається вектор ( )H S
1 2 3 4 5( , , , , ),S S S S S де
1
k
S i
t t
i
— диз’юнкція відповідних координат харак-
теристики Поста ( ).iH f
Позначимо 1 1 2{ , , ..., }nS f f f і 2 1 2{ , ,..., }mS g g g дві системи булевих
функцій відповідно до характеристик Поста 1( )H S і 2( ).H S Утворимо з 1S і
2S множину 1 2 ,S S яка складається з впорядкованих пар функцій, тобто
1 2 {( , ), 1, 2,..., ; 1, 2,..., }.i jS S f g i n j m
Відомо, якщо 1 ,S n 2 ,S m то 1 2 ;S S n m 1 2 1( ) ( )H S S H S
2( ).H S
Приведені міркування поширюються на системи 1,S 2 ,S …, ,rS тому мають
місце твердження.
Твердження 1. Якщо 1 1,S n 2 2 ,S n …, ,r rS n то 1 2 rS S S
1 2 ,rn n n 1 2 1 2( ) ( ) ( ) ( ).r rH S S S H S H S H S
Твердження 2. Система булевих функцій 1 2{ , ,..., }kS f f f є функціонально
повною тоді і тільки тоді, коли 1 2 3 4 5 1.S S S S S
Означення 4. Функціонально повна система булевих функцій 1 2{ , ,...S f f
..., }kf називається базисом, якщо ,kS S ,kS S kS не є функціонально
повною.
Опишемо алгоритм знаходження базисів.
Нехай задана множина булевих функцій .S Для системи S побудуємо реші-
тку Поста (рис. 2), яка розіб’є S на 15 класів еквівалентності. У кожному класі
знаходяться усі функції S , еквівалентні за характеристикою Поста. У вершинах
решітки вказано номер класу in і характеристику Поста відповідного класу екві-
валентності.
Однофункціональні базиси утворюють функції, які належать класу 31,n оскі-
льки кожна функція цього класу є шеферовою.
Двофункціональні базиси утворюють функції класу 1 2S S такі, що
1 2( ) (1, 1, 1, 1, 1),H S S а 1( ) (1, 1, 1, 1, 1),H S 2( ) (1, 1, 1, 1, 1).H S Побудуємо
всі двофункціональні базиси.
Нехай 1S співпадає з класом 26 .n Тоді 2S може бути довільним класом екві-
валентності, пʼята координата характеристики Поста якого дорівнює одиниці. Та-
кими можуть бути класи 29 ,n 30 ,n 23 ,n 24 ,n 25 ,n 9 ,n 12 ,n 14 .n З твердження 2
випливає, що кількість двофункціональних базисів, до складу яких входять фу-
нкції класу 26 ,n знаходимо за формулою
2
26 26 29 30 23 24(N n n n n n
25 9 12 14 ).n n n n В інші двофункціональні базиси не потрапляють фун-
кції класу 26n . Аналогічно обчислимо
2
29 29 30 17 24 12( ),N n n n n n
2
30 30 17 23 9( ),N n n n n
2
17 17 25 14( ).N n n n
48 ISSN 2786-6491
Твердження 3. Кількість двофункціональних базисів у класі S дорівнює
2 2 2 2
2 26 29 30 17( ) .N B N N N N
Трифункціональні базиси можна побудувати з функцій класів еквівалентнос-
ті, які розташовані на другому, третьому і четвертому ярусах решітки Поста. Ви-
пишемо формули, за допомогою яких можна визначити потужності всіх функціо-
нально повних систем, що містять три функції:
3
17 17 25 13 14 3 23 24 25 9 12 14( ) ( ),N n n n n n n n n n n n
3
23 23 24 12 25 13 14 3( ) ( ),N n n n n n n n
3
24 24 9 25 13 14 3( ),N n n n n n n
3
25 25 9 12 ,N n n n
3
9 9 12 13 .N n n n
Розкриємо дужки в формулах
3
17 ,N
3
23,N
3
24N і опустимо ті доданки, які
не є базисами. Випишемо доданки, які утворюють базиси у формулі
3
17 ,N —
17 13 24 ,n n n 17 13 9 ,n n n 17 13 12 ,n n n 17 13 23 ,n n n 17 3 23 ,n n n 17 3 24 ,n n n 17 3 9 ,n n n 17 3 12 ,n n n
9 12 13n n n , і функціонально повні системи формули
3
17 ,N які не є базисами, —
17 13 25 ,n n n 17 13 14 ,n n n 17 3 25 ,n n n 17 3 14 .n n n Таким чином, формула
3
17 3( ),N B яку
отримали з
3
17N шляхом відкидання небазисних доданків, має такий вигляд:
3
17 3 17 13 24 23 9 12 3 23 24 9 12( ) ( ( )) ( ( ))N B n n n n n n n n n n n
17 9 12 23 24 13 3( )( ).n n n n n n n
Аналогічно, проводячи перевірку в формулах
3
20 ,N
3
23,N
3
24 ,N 3
25 ,N отри-
муємо відповідні формули для знаходження трифункціональних базисів і підра-
хунку їх кількості:
3
23 3 23 24 12 25 13 14 3( ) ( )( ),N B n n n n n n n
3
24 3 24 9 25 13 14 3( ) ( ),N B n n n n n n
3
25 3 25 9 12( ) ,N B n n n
3
9 3 9 12 13( )N B n n n .
Твердження 4. Кількість трифункціональних базисів системи S обчислю-
ється за допомогою класів еквівалентності решітки Поста за формулою
3 3 3 3 3
3 17 3 23 3 24 3 25 3 9 3( ) ( ) ( ) ( ) ( ) ( ).N B N B N B N B N B N B
Чотирифункціональні базиси можуть бути побудовані з функцій класів екві-
валентності, які розташовані на другому та третьому ярусах решітки Поста. Кіль-
кість цих базисів знаходимо за формулою
4 9 12 3 4 9 12 14 4 9 12 4 3 14( ) ( ).N B n n n n n n n n n n n n n
Міжнародний науково-технічний журнал
Проблеми керування та інформатики, 2022, № 5 49
Теорема 1. Якщо для системи булевих функцій S знайдено класи еквівалент-
ності 0 31n n решітки Поста, то кількість однофункціональних базисів буде
31n , двофункціональних — 2( ),N B трифункціональних — 3( )N B і чотирифунк-
ціональних — 4( ).N B
У класі булевих функцій, арність яких не перевищує два, можна побудувати таку
кількість базисів: однофункціональних — 2, двофункціональних — 24 і трифункціо-
нальних — 6. Розподіл числа функцій класів 3 ,S 4S і 5 ,S арність яких відповідно не
перевищує три, чотири і пʼять, за класами решітки Поста приведена в таблиці.
Таблиця
in
0n
3n
4n
9n
12n
13n
14n
17n
3S 3 1 1 1 1 3 14 4
4S 4 8 4 1 1 112 154 8
5S 5 76 11 1 1 32676 7498 16
in
23n
24n
25n
26n
29n
30n
31n
3S 3 3 42 4 60 60 56
4S 7 7 16102 120 16376 16376 16256
5S 15 15 1073701558 32752 1073741808 1073741808 1073709056
Знайдемо число всіх базисів для n = 5. Кількість однофункціональних базисів
рівна потужності класу 31n і становить 1073709056. Число двофункціональних об-
числюється за формулою
2 2 2 2
2 26 29 30 17( )N B N N N N =1153027056649370000.
Трифункціональні базиси знаходимо за формулою
3 3
3 17 3 23 3( ) ( ) ( )N B N B N B
3 3 3
24 3 25 3 9 3( ) ( ) ( )N B N B N B =274894664298. Потужність чотирифункціональних
базисів дорівнює 4 9 12 4 3 14( ) ( )N B n n n n n = 83314.
Використовуючи таблицю, а також формули для обчислення базисів, отрима-
ємо справедливість теореми.
Теорема 2. У класах булевих функцій 3 ,S 4S і 5S існує відповідно 6604,
274970502 і 1153027332617830000 базисів, з них відповідно 56, 16256 і
1073709056 — однофункціональні; 5460, 274710336 і 1153027056649370000 —
двофункціональні; 1073, 243262 і 274894664298 — трифункціональні; 15, 648 і
83314 — чотирифункціональні.
Висновок
У роботі проведено дослідження з теорії булевих функцій. Введено нові по-
няття куба і решітки класів Поста, а також характеристики Поста систем булевих
функцій. Отримано формули, які дають можливість знайти всі можливі базиси для
довільної системи функцій. Результати досліджень дозволяють розглянути про-
блему Дедекінда через призму обчислень потужностей класів Поста.
50 ISSN 2786-6491
I. Mych, V. Nykolenko, O. Vartsaba
DEDEKIND’S PROBLEM AND POST’S CLASSES
Ihor Mych
Uzhhorod National University,
ihor.mych@uzhnu.edu.ua
Volodymyr Nikolenko
Uzhhorod National University,
volodymyr.nikolenko@uzhnu.edu.ua
Olena Vartsaba
Uzhhorod National University,
olena.vartsaba@uzhnu.edu.ua
The paper studied Boolean functions using Postʼs classes. The concepts of
Postʼs characteristic of Boolean function and equivalence functions of Postʼs
characteristic are introduced. The thirty-two closed classes are considered based
on the equivalence relation by Postʼs characteristic. These classes form the
Postʼs cube. This cubeʼs seventeen classes are empty, and nonempty classes
form the Postʼs lattice. Formulas for computing the number of functions of
Postʼs classes have been discovered depending on the number of variables
1 2, ,..., nx x x in this investigation. Such formulas are found for eleven classes of
fifteen classes. The problem of computation of power of nonempty classes is
closely related to Dedekindʼs problem. The exercise finding of quantity of mon-
otone functions depending on the number of variables is called Dedekindʼs prob-
lem. Dedekind solved this problem for n 4 in 1897, Church — n 5 in 1940,
and Ward for n 6. The quantity of monotone functions was adduced for n 7,
but the authors got divergence of valuation. The most value of Dedekindʼs num-
ber is known as n 8. Finding the valuation of Postʼs classes gives the oppor-
tunity another side to solve Dedekindʼs problem. Analytical investigations were
conducted in this paper that allow arbitrary Boolean function systems from an
arbitrary quantity of variables to find all possible one-functional, two-functional,
three-functional, and four-functional bases. The distributions of Boolean func-
tions from three, four, and five variables about nonempty Post’s classes are
found. They are using this analytical apparatus we can to calculate the quantity
of all possible bases. The example of finding all bases for Boolean functions of
arity does not exceed five is given. The amount of one-functional, two-fun-
ctional, three-functional, and four-functional bases was found in this example.
Keywords: Post’s classes, Post’s lattice, bases of Boolean functions, Dede-
kind’s problem.
REFERENCES
1. Kleitman D. On Dedekind’s problem: the number of monotone Boolean functions. Proc. Amer.
Math. Soc. 1969. Vol. 21. P. 677–682.
2. Wiedemann D. A computation of the eighth Dedekind number. Order. 1969. N 8 (1). P. 5–6.
3. Bakoev V. On more way for counting monotone Boolean functions. Thirteenth International
Workshop on Algebraic and Combinatorial Coding. 2012. P. 47–52.
4. Fidytek R., Mostowski A., Somla R., Szepietowski A. Algorithms counting monotone Boolean
functions. Inform. Process. Lett. 2011. N 79. P. 203–209.
5. Pawelski B. On the number of inequivalent monotone Boolean functions of 8 variables. Prepr.
2021. 8 p. https://doi.org/10.48550/arXiv.2108.13997.
6. Stephen T., Yusun T. Counting inequivalent monotone Boolean functions. Discrete Applied
Mathematics. 2014. Vol. 167. P. 15–24. http://sfu.ca/~tyusun/inequivalentMBF.html.
Отримано 19.01.2023
mailto:ihor.mych@uzhnu.edu.ua
mailto:volodymyr.nikolenko@uzhnu.edu.ua
mailto:olena.vartsaba@uzhnu.edu.ua
file:///C:/Users/Lenovo%20-PC/Desktop/2023/8%20p.%20https:/doi.org/10.48550/arXiv.2108.13997
https://www.sciencedirect.com/journal/discrete-applied-mathematics
https://www.sciencedirect.com/journal/discrete-applied-mathematics
https://www.sciencedirect.com/journal/discrete-applied-mathematics
http://sfu.ca/~tyusun/%0binequivalentMBF.html
|
| id | nasplib_isofts_kiev_ua-123456789-210910 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Ukrainian |
| last_indexed | 2026-03-12T23:47:12Z |
| publishDate | 2022 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Мич, І.А. Ніколенко, В.В. Варцаба, О.В. 2025-12-20T14:21:46Z 2022 Проблема Дедекінда та класи Поста / І.А. Мич, В.В. Ніколенко, О.В. Варцаба // Проблеми керування та інформатики. — 2022. — № 5. — С. 42-50. — Бібліогр.: 6 назв. — укр. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210910 519.7 10.34229/2786-6505-2022-5-4 У роботі за допомогою класів Поста вивчаються булеві функції. Введено поняття характеристики Поста булевої функції та еквівалентних функцій за характеристикою Поста. На основі відношення еквівалентності за характеристикою Поста розглядаються 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. uk Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методи обробки та захисту інформації Проблема Дедекінда та класи Поста Dedekind's Problem and Post's Classes Article published earlier |
| spellingShingle | Проблема Дедекінда та класи Поста Мич, І.А. Ніколенко, В.В. Варцаба, О.В. Методи обробки та захисту інформації |
| title | Проблема Дедекінда та класи Поста |
| title_alt | Dedekind's Problem and Post's Classes |
| title_full | Проблема Дедекінда та класи Поста |
| title_fullStr | Проблема Дедекінда та класи Поста |
| title_full_unstemmed | Проблема Дедекінда та класи Поста |
| title_short | Проблема Дедекінда та класи Поста |
| title_sort | проблема дедекінда та класи поста |
| topic | Методи обробки та захисту інформації |
| topic_facet | Методи обробки та захисту інформації |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/210910 |
| work_keys_str_mv | AT mičía problemadedekíndataklasiposta AT níkolenkovv problemadedekíndataklasiposta AT varcabaov problemadedekíndataklasiposta AT mičía dedekindsproblemandpostsclasses AT níkolenkovv dedekindsproblemandpostsclasses AT varcabaov dedekindsproblemandpostsclasses |