Статья в сборнике "Математические вопросы кибернетики" №8, Москва, 1999
Авторы:Сачков В.Н.
Случайные разбиения множеств
Аннотация:
В первой части данной работы изложена история изучения случайных разбиений множеств, а также описан ряд объектов, которые могут быть представлены в таком виде. Во второй части приводятся полученные автором результаты по противоречивым разбиениям, применяемые к изучению бесповторных конъюнктивных нормальных форм. Рассмотрены разбиения m-множества, имеющие заданное число блоков, общих с фиксированным разбиением, а также случайные разбиения с данным числом блоков. Приведена формула для числа бесповторных конъюнктивных нормальных форм определенного вида, получена асимптотика для числа б.к.н.ф., существенно зависящих от всех переменных. Также автором выведена формула для мощности подкласса булевых функций, для которых соответствующие системы уравнений имеют полиномиальную сложность решения.