ИСТИНА

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

The purpose and the courses of the researches are to obtain the lattices for closed classes of discrete functions and to study their properties, to describe the characteristics of discrete functions, to construct rapid algorithms for discrete structures.

Решение вопроса о конечности числа замкнутых классов в частичной k-значной логике, содержащих произвольный класс монотонных всюду определенных k-значных функций. Решение задачи порождения ложного образа линейных функций для составных k. Исследование задачи одновременного порождения литералов. Решение вопроса о гиперконтинуальности числа FE-предполных классов счетнозначной логики. Получение порядка длины функций алгебры логики в классе псевдополиномиальных форм. Построение решетки (по вложению) всевозможных пересечений предполных классов монотонных функций и предполных классов функций, сохраняющих разбиения, в пятизначной логике. Построение быстрых алгоритмов проверки инвариантности булевых функций относительно линейных преобразований переменных.

Руководитель и исполнители НИР имеют публикации по указанным направлениям научных исследований. НИР является продолжением и развитием НИР "Дискретные функциональные системы, дискретные структуры и алгоритмы" (2011-2015 г.г.)

При выполнении НИР опубликовано 6 монографий; 77 работ в реферируемых журналах; 24 статьи в сборниках трудов конференций; защищена 1 докторская диссертация. Получены следующие результаты. Этап 1. 1 января 2016 г.-31 декабря 2016 г. Результаты этапа. Доказано, что любой предполный класс в алгебре всюду определенных k-значных функций, состоящий из функций, монотонных относительно частичного порядка, в котором для любых двух элементов имеется наименьшая верхняя грань и для любых двух элементов имеется наибольшая нижняя грань, содержится в конечном числе замкнутых классов в частичной k-значной логике. Доказано, что оператор замыкания относительно систем функциональных уравнений (FE-оператор) порождает на множестве функций счетнозначной логики гиперконтинуальное семейство предполных классов. Доказано, что любая алгебра одноместных функций с носителем из счетного примитивно рекурсивно замкнутого класса и операцией композиции имеет континуальное число максимальных подалгебр, содержащих все одноместные функции из класса E2 Гжегорчика. Доказано, что для произвольного счетного частично-рекурсивно замкнутого класса функций группа всех перестановок, принадлежащих этому классу, имеет континуальное число максимальных подгрупп. Получены нижние оценки длины спада l(n) (т.е. числа элементов в (3k+1)-последовательности с началом в числе n) в (3k+1)-проблеме. Задача о существовании универсальных функций для класса линейных k-значных решена полностью при составном k. Доказана нетривиальная оценка мощности области определения универсальной функции для класса линейных булевых функций n переменных. Получены достаточные условия возможности одновременного порождения литералов. Получен порядок длины функций алгебры логики в классе псевдополиномиальных форм. При каждом составном k найдена асимптотика числа полиномиальных функций k-значной логики, зависящих от n переменных. Найдены необходимые и достаточные условия, при которых последовательность симметрических периодических функций с одним и тем же периодом является сложной в классе поляризованных полиномиальных форм (при простых k). Найдены все тривиальные (состоящие только из констант и селекторных функций) пересечения предполных классов семейства C \ T в четырехзначной логике. Построена решетка пересечений предполных классов четырехзначной логики из объединения семейств M и U. Установлены девять универсальных (справедливых при любом k>2) свойств пересечений предполных классов k-значной логики. Этап 2. 1 января 2017 г.-31 декабря 2017 г. Результаты этапа. Найдены новые замкнутые классы всюду определенных k-значных функций, монотонных относительно заданного частичного порядка, которые содержатся лишь в конечном числе замкнутых классов частичной k-значной логики. В частности, доказано, что при k=3 таким свойством обладает любой замкнутый класс всех функций, монотонных относительно заданного частичного порядка. Введен новый сильный оператор замыкания – оператор CQ-замыкания. Установлены основные свойства этого оператора. Найдены все 15 CQ-замкнутых классов булевых функций. Проведено сравнение оператора CQ-замыкания с другими известными операторами замыкания. Получена классификация вычислительной сложности задачи выполнимости мультилинейных форм над конечным полем. Найдено точное значение наибольшей сложности систем из m функций над конечным полем нечетной характеристики, зависящих от n переменных, в классе поляризованных полиномиальных форм. Найдена верхняя оценка длины функций над произвольным конечным полем в классе псевдополиномиальных форм. Найдены все слабоповторные в элементарном базисе функции, получаемые из бесповторных одним и двумя отождествлениями переменных. Найдены все слабоповторные в бинарном базисе функции, получаемые из бесповторных одним отождествлением переменных. Известно, что билинейный алгоритм сложности r для умножения матриц 3х3 можно задавать с помощью r упорядоченных троек 3х3-матриц. Широко изучаемыми являются алгоритмы, обладающие различными симметриями. В работе найдены два алгоритма сложности 25, обладающие двумя симметриями: 1) в алгоритме присутствует тройка единичных матриц, 2) если в алгоритме присутствует тройка A, B, C, то в нем также присутствуют тройки B, C, A и C, A, B. Доказаны 9 универсальных (справедливых при любом k>2) свойств о вложениях пересечений предполных классов, лежащих в некоторых классах C(k) сохранения центральных предикатов, в некоторые другие предполные классы, а также 3 универсальных свойства о вложениях пересечений предполных классов в классы из C(k). Найдена глубина и ширина решетки основных замкнутых классов, являющихся пересечениями предполных классов четырехзначной логики из объединения семейств M и U. Найдены все тупиковые аксиомы вложения пересечений предполных классов, содержащих все константы, в некоторый предполный класс из семейства M(4). Описан один класс линейных преобразований переменных булевой функции. Получен полиномиальный алгоритм проверки инвариантности относительно описанного класса линейных преобразований переменных булевой функции, заданной полиномом. Этап 3. 1 января 2018 г.-31 декабря 2018 г. Результаты этапа. Установлен простой критерий, который по частичному порядку, задающему предполный класс A всюду определенных монотонных функций, позволяет установить, является ли семейство T(A) всех замкнутых классов в частичной k-значной логике, содержащих A, конечным или бесконечным. Этим завершается решение задачи о конечности T(A) для всех предполных классов k-значной логики. Введен новый класс абстрактных вычислительных устройств - счетчиковые машины с сумма-тором (CS-машины). Доказано, что любую общерекурсивную функцию можно строго вычислить на CS-машине. Определены полиномиально-регистровые машины (PR-машины), близкие к машинам с произ-вольным доступом к памяти. Доказано, что вычисления на PR-машинах можно промоделиро-вать полиномиальными возвратными последовательностями, а вычисление элементов полиномиальной возвратной последовательности - выполнить с помощью подходящей PR-машины. Установлено, что всякое собственное расширение оператора позитивного замыкания с помощью логических связок дает либо оператор с полной системой связок, либо оператор импликативного замыкания. Для оператора импликативного замыкания в терминах полугрупп эндоморфизмов получено описание всех замкнутых классов. Предложена итеративная процедура для подсчета числа n-местных функций k-значной логики с заданным эдоморфизмом. С ее помощью получены формулы для числа n-местных функций трехзначной логики с произвольными эндоморфизмами. Решена задача нахождения минимального количества переменных, требуемого для получения каждой из слабоповторных функций из бесповторной формулы в элементарном решена как для двух семейств из одной функции, так и для трех счетных семейств слабоповторных функций. Установлены свойства особых обобщенных конъюнктивных нормальных форм, представляющих предикаты над конечным множеством, инвариантные относительно некоторой полурешеточной функции. На основе этих свойств улучшена оценка сложности полиномиального алгоритма проверки выполнимости систем предикатов над конечным множеством, которые инвариантны относительно некоторой полурешеточной функции. Построена решетка U5 пересечений классов из U(5). Доказано, что она содержит ровно 271380 узлов. Из них ровно 2542 узлов соответствуют попарно недвойственным классам–пересечениям K. Также получен полный список всех возможных классов, соответствующих узлам этой решетки. Установлено одно свойство полиномов k-значных функций, которое гарантирует достаточно большую длину полинома. Это свойство даёт возможность ограничивать перебор при проверке того, что функция, заданная полиномом, сохраняет определённый класс предикатов. Этап 4. 1 января 2019 г.-31 декабря 2019 г. Результаты этапа. Доказано, что билинейная сложность умножения матрицы порядка 2 на матрицу размера 2 x m над конечным полем с K элементами не меньше, чем (3+3/(K^2+2)) m. Таким образом, увеличен коэффициент в нижней оценке для умножения матрицы порядка 2 на матрицу размера 2 x m над любым конечным полем. Доказано, что при любом k > 1 операторы эквационального замыкания и замыкания по пере-числению (П-оператор) порождают одну и ту же классификацию на множестве частичных функ-ций k-значной логики. Найдены критерии однозначности алфавитного кодирования сверхслов для конечного и бесконечного кодов. Доказано, что в случае бесконечного кода проблема рас-познавания неоднозначности кода является m-полной в классе Е1А0 аналитической иерархии Клини. Рассмотрены предикаты на конечном множестве, инвариантные относительно некоторой (m+1)-местной функции почти единогласия. Такие предикаты названы m-юнктивными. Получены свойства обобщенных конъюнктивных форм m-юнктивных предикатов на конечных множествах. На основе полученных свойств построены полиномиальные алгоритмы проверки выполнимости конъюнкций предикатов, инвариантных относительно одной и той же функции почти единогласия. Построено в явном виде сведение задачи проверки принадлежности булевой функции, заданной полиномом, классу О_2 и задачи проверки периодичности булевых функций к задаче выполнимости КНФ. Этап 5. 1 января 2020 г.-31 декабря 2020 г. Результаты этапа. Для случая, когда k есть произведение двух различных простых чисел, полностью описаны все классы предикатов на множестве {0, 1, …, k-1}, замкнутые относительно переименования переменных, добавления и изъятия фиктивных переменных, подстановки в предикат полиномов по модулю k вместо переменных и конъюнкции предикатов. Это дает новое полное описание интервала Int(Pol) всех замкнутых классов в частичной k-значной логике, содержащих все полиномы по модулю k и состоящих только из функций, доопределимых до полиномов. Результат может быть использован для представления частично определенных дискретных функций полиномами при реализации дискретных функций схемами. В классе экспоненциально-полиномиальных функций эффективно определены шесть предполных (относительно операции суперпозиции) классов и на их основе сформулированы критерий полноты и алгоритм распознавания полноты для конечных систем функций. При любом k > 1 в классе Pk* частичных функций k-значной логики определены две серии импликативно замкнутых классов и доказано, что классы этих серий исчерпывают все импликативно предполные классы в Pk*. Для класса логико-автоматных формул, построенных с помощью логических связок из равенств автоматных термов, доказана разрешимость проблемы выполнимости по функциональным (автоматным) переменным. Показано (с получением верхних оценок времени), как многоленточные машины Минского и Тьюринга можно промоделировать трехленточными машинами Минского. Установлена сложность расшифровки монотонных функций алгебры логики с искажением в одной точке. Показано, что эта сложность такая же, как и сложность расшифровки монотонных функций алгебры логики без искажений. Расшифровка функций может применяться при решении вопросов восстановления объектов по неполным сведениям о них. Доказано, что полный условный диагностический тест также, как и безусловный, имеет длину 2^n. Данный результат важен для сравнения классических постановок условного и безусловного тестирования. Получен способ декомпозиции задачи проверки равенства 0 булевой функции, заданной обобщённым полиномом, на задачи меньшей размерности при помощи алгоритма поиска мостов в графе. Данный результат позволяет декомпозировать исходную задачу на две аналогичные, но с меньшей длиной обобщённого полинома, что приводит к уменьшению размерности входа подзадач.