ИСТИНА

В связи с широким развитием информатики и цифровой техники большое значение для приложений имеют дискретные функции и дискретные структуры. Дискретные функции и дискретные структуры возникают также во многих областях естествознания. Основные направления исследований: исследование свойств дискретных функций и операций над ними, изучение специальных представлений дискретных функций; разработка быстрых алгоритмов для распознавания свойств дискретных функций и расшифровки дискретных функций; исследование свойств графов и применение теорий графов к решению комбинаторных задач алгебры и теории чисел; разработка быстрых алгоритмов для дискретных структур.

Для класса максимально-нелинейных булевых функций установлена асимптотика величины изменения параметра нелинейности при добавлении к приближающим функциям k нелинейных слагаемых. Доказана нижняя оценка 3k+2 для билинейной сложности умножения матрицы размера k х 2 на матрицу размера 2 х 2 над любым полем. Доказана полиномиальность распознавания Мёбиус-инвариантности функции алгебры логики по ее полиному Жегалкина. Получен ряд результатов о длине сертификата для свойств булевых функций. Поставлена задача порождения ложного образа дискретных функций. Доказано, что при каждом составном числе k распознать полиномиальность функции k-значной логики, заданной вектором своих значений, и в случае положительного ответа построить ее полином по модулю k можно с линейной сложностью. В терминах полугрупп эндоморфизмов охарактеризованы все позитивно замкнутые классы многозначной логики. В счетнозначной логике определен и исследован оператор FE-замыкания, в многозначной логике определен и исследован новый оператор замыкания по перечислению. Построена решетка пересечений всех основных замкнутых классов (т.е. тех, которые являются пересечением предполных классов) в трехзначной логике, а в четырехзначной логике аналогичная решетка построена для объединения семейств предполных классов U и M.