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

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

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
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
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Problems of Control and Informatics

Institution

Problems of Control and Informatics
id oai:ojs2.jais.net.ua:article-16
record_format ojs
institution Problems of Control and Informatics
baseUrl_str
datestamp_date 2024-03-14T08:26:32Z
collection OJS
language Ukrainian
topic класи Поста
решітка Поста
базиси булевих функцій
проб¬лема Дедекінда
spellingShingle класи Поста
решітка Поста
базиси булевих функцій
проб¬лема Дедекінда
Nikolenko, Volodymyr
Mych, Ihor
Vartsaba, Olena
Проблема Дедекінда та класи Поста
topic_facet Post’s classes
Post’s lattice
bases of Boolean functions
Dedekind’s problem
класи Поста
решітка Поста
базиси булевих функцій
проб¬лема Дедекінда
format Article
author Nikolenko, Volodymyr
Mych, Ihor
Vartsaba, Olena
author_facet Nikolenko, Volodymyr
Mych, Ihor
Vartsaba, Olena
author_sort Nikolenko, Volodymyr
title Проблема Дедекінда та класи Поста
title_short Проблема Дедекінда та класи Поста
title_full Проблема Дедекінда та класи Поста
title_fullStr Проблема Дедекінда та класи Поста
title_full_unstemmed Проблема Дедекінда та класи Поста
title_sort проблема дедекінда та класи поста
title_alt Dedekind's problem and post's classes
description У роботі за допомогою класів Поста вивчаються булеві функції. Введено поняття характеристики Поста булевої функції та еквівалентних функцій за характеристикою Поста. На основі відношення еквівалентності за характеристикою Поста розглядаються 32 замкнені класи, які утворюють куб Поста. У цьому кубі 17 класів є порожніми, а решта 15 непорожніх утворюють решітку Поста. У роботі виведено формули для обчислення кількості функцій у класах Поста в залежності від числа змінних  Такі формули знайдено для 11 з 15 класів. Проблема обчислення потужностей непорожніх класів тісно повʼязана з проблемою Дедекінда. Задачу знаходження кількості монотонних функцій в залежності від числа змінних називають проблемою Дедекінда. У 1897 році цю задачу розвʼязав Дедекінд для n=4; у 1940 році Черч — для n=5; Вард — для n=6; для n=7 є розходження в отриманих оцінках. Найбільше значення числа Дедекінда відомо для n=8. Знайдено оцінки потужностей класів Поста, які дають можливість інакше підійти до розвʼязання проблеми Дедекінда. У даній роботі проведено аналітичні дослідження, за допомогою яких можна для довільної системи булевих функцій від довільної кількості змінних, для яких знайдено характеристики Поста, знайти всі можливі одно-, дво-, три- та чотирифункціональні базиси. Знайдено розподіли булевих функцій від трьох, чотирьох і пʼяти змінних за непорожніми класами Поста. Використовуючи приведений аналітичний апарат, можна обчислити число всіх можливих базисів. У роботі наведено приклад знаходження всіх базисів для булевих функцій, арність яких не перевищує пʼяти. У цьому прикладі знайдена кількість одно-, дво-, три- та чотирифункціональних базисів.
publisher V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
publishDate 2023
url https://jais.net.ua/index.php/files/article/view/16
work_keys_str_mv AT nikolenkovolodymyr problemadedekíndataklasiposta
AT mychihor problemadedekíndataklasiposta
AT vartsabaolena problemadedekíndataklasiposta
AT nikolenkovolodymyr dedekindsproblemandpostsclasses
AT mychihor dedekindsproblemandpostsclasses
AT vartsabaolena dedekindsproblemandpostsclasses
first_indexed 2025-10-30T02:48:29Z
last_indexed 2025-10-30T02:48:29Z
_version_ 1847373342742413312
spelling oai:ojs2.jais.net.ua:article-162024-03-14T08:26:32Z Проблема Дедекінда та класи Поста Dedekind's problem and post's classes Nikolenko, Volodymyr Mych, Ihor Vartsaba, Olena Post’s classes Post’s lattice bases of Boolean functions Dedekind’s problem класи Поста решітка Поста базиси булевих функцій проб¬лема Дедекінда У роботі за допомогою класів Поста вивчаються булеві функції. Введено поняття характеристики Поста булевої функції та еквівалентних функцій за характеристикою Поста. На основі відношення еквівалентності за характеристикою Поста розглядаються 32 замкнені класи, які утворюють куб Поста. У цьому кубі 17 класів є порожніми, а решта 15 непорожніх утворюють решітку Поста. У роботі виведено формули для обчислення кількості функцій у класах Поста в залежності від числа змінних  Такі формули знайдено для 11 з 15 класів. Проблема обчислення потужностей непорожніх класів тісно повʼязана з проблемою Дедекінда. Задачу знаходження кількості монотонних функцій в залежності від числа змінних називають проблемою Дедекінда. У 1897 році цю задачу розвʼязав Дедекінд для n=4; у 1940 році Черч — для n=5; Вард — для n=6; для n=7 є розходження в отриманих оцінках. Найбільше значення числа Дедекінда відомо для n=8. Знайдено оцінки потужностей класів Поста, які дають можливість інакше підійти до розвʼязання проблеми Дедекінда. У даній роботі проведено аналітичні дослідження, за допомогою яких можна для довільної системи булевих функцій від довільної кількості змінних, для яких знайдено характеристики Поста, знайти всі можливі одно-, дво-, три- та чотирифункціональні базиси. Знайдено розподіли булевих функцій від трьох, чотирьох і пʼяти змінних за непорожніми класами Поста. Використовуючи приведений аналітичний апарат, можна обчислити число всіх можливих базисів. У роботі наведено приклад знаходження всіх базисів для булевих функцій, арність яких не перевищує пʼяти. У цьому прикладі знайдена кількість одно-, дво-, три- та чотирифункціональних базисів. 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  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 monotone functions depending on the number of variables is called Dedekindʼs problem. 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 number is known as n=8. Finding the valuation of Postʼs classes gives the opportunity 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 functions 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.v V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2023-01-19 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/16 10.34229/2786-6505-2022-5-4 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 67 № 5 (2022): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 42-50 International Scientific Technical Journal "Problems of Control and Informatics; Том 67 № 5 (2022): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 42-50 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 67 No. 5 (2022): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 42-50 2786-6505 2786-6491 10.34229/2786-6505-2022-5 uk https://jais.net.ua/index.php/files/article/view/16/28 Copyright (c) 2022 Volodymyr Nikolenko, Ihor Mych, Olena Vartsaba https://creativecommons.org/licenses/by-nc-nd/4.0

Ähnliche Einträge