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

случайные разбиения множеств, фиксированное разбиение, противоречивое разбиение, бесповторные конъюнктивные нормальные формы

Математические вопросы и теория численных методов