В работе рассматривается задача о сложности реализации формулами функций из P_3,2 - множества всех трехзначной логики, принимающих значения 0 или 1. Для каждого конечно-порожденного максимального (в решетке классов с одинаковой проекцией) замкнутого класса функций из P_3,2 и некоторой конечной системы, порождающей его, получены верхние и нижние оценки для соответствующих функций Шеннона. Для каждого конечно-порожденного замкнутого класса F функций из P_3,2, за исключением максимального, такого, что проекция F совпадает с множеством всех линейных булевых функций, и некоторой конечной порождающей системы такого класса найдены точные формулы для соответствующих функций Шеннона. Выделено некоторое счетное семейство B замкнутых классов булевых функций и показано, что для каждого замкнутого класса F функций из P_3,2, проекция которого принадлежит семейству B, и любой конечной системы, порождающей F, функция Шеннона по глубине, соответствующая классу F, имеет линейный порядок роста.

функции многозначной логики, формулы, сложность

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