О свойствах полиномов над конечными полями и об алгоритмической сложности распознавания свойств функций многозначных логик, представленных полиномами

• Автор: Селезнева, Светлана Николаевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Москва
• Количество страниц: 61 с.

Содержание.
Введение
Часть I. Некоторые свойства многочленов над конечными полями, зависящих от нескольких переменных
1.1. Основные понятия и формулировка результатов
1.2. Доказательство основной теоремы
Часть II. Об алгоритмической сложности распознавания свойств дискретных функций
11*1. Основные понятия
11.2. Об алгоритмической сложности распознавания полноты систем булевых функций, представленных полиномами
11.3. Об алгоритмической сложности распознавания принадлежности полиномов функций fc-значной логики предполным классам самодвойственных функций
11.4. Об алгоритмической сложности распознавания принадлежности полиномов функций /с-значной логики классам функций, сохраняющих рефлексивный и транзитивный предикат
11.5. Об алгоритмической сложности распознавания принадлежности полиномов функций fc-значной логики классам функций, сохраняющих тотально рефлексивный и обобщенно транзитивный предикат
Заключение
Литература

Введение.
В настоящей работе исследуются свойства многочленов над конечными полями, зависящих от многих аргументов, и вопрос об алгоритмической сложности распознавания свойств функций А:-знатной логики, представленных полиномами. В частности, рассматривается проблема распознавания полноты.
Проблема распознавания полноты систем функций многозначной логики, как и более общая проблема выразимости, является одной из важных проблем дискретной математики и берет свое начало в большом исследовании Э. Поста, опубликованном в 1921 году [4]. Это исследование касалось алгебры логики и полностью решало проблему построения всех замкнутых систем алгебры логики. В частности, в нем содержался критерий полноты произвольной системы функций алгебры логики. Формулировка его такова: система функций алгебры логики неполна тогда и только тогда, когда она содержится в одном из пяти известных замкнутых классов, а именно классов монотонных, линейных, самодвойственных функций и функций, сохраняющих константы. Таким образом, из этого критерия следует, что проблема выявления полноты системы функций сводится к проблемам распознавания некоторых свойств отдельно взятой функции.
Позже, в 1941 году, указанное исследование вышло в виде монографии [25], в которой ставился вопрос об обобщении полученных результатов на случай функций многозначной логики.
Критерий полноты для функций многозначной логики был получен в 1957 году А. В. Кузнецовым [8]. Он опирается на понятие предпол-ного класса, введенное в работах С. В. Яблонского и А. В. Кузнецова, и формулируется следующим образом: система функций к-значной логики неполна тогда и только тогда, когда она содержится в одном из конечного числа предполных классов.
Таким образом, аналогично случаю булевых функций проблема вы-

яснения полноты системы функций сводится к распознаванию принадлежности функции предполным классам. Доказательство критерия полноты Кузнецова не содержало конструктивного описания всех предполных классов. Поэтому усилия многих математиков в 1957-1965 годах были направлены на описание всех предполных классов. Отдельные их типы были описаны в работах [9, 10, 11]. Окончательный результат был получен И. Розенбергом [12, 14].
С развитием вычислительной техники возник вопрос о рассмотрении проблемы полноты систем функций с алгоритмической точки зрения. Здесь следует отметить несколько аспектов.
Функция — суть абстрактный объект. И при решении теоретических вопросов, вообще говоря, не важно, как функция представлена. Однако алгоритмическая процедура имеет дело с данными. Поэтому рассмотрение функций как входных данных для алгоритмических процедур предполагает реализацию функций определенным образом. Мы говорим, что для представления функций /с-значной логики выбирается некоторый язык в самом общем смысле. Язык, по меньшей мере, должен обладать тем свойством, что каждая функция может быть записана в нем. Примерами языка могут служить векторы значений функций, формулы над определенным базисным множеством формул и т. д. Очевидно, что язык, в котором функции реализованы, существенно определяет алгоритм распознавания свойств функций. Другими словами, априори зная, как функция представлена, каковы свойства такого ее представлении, мы пытаемся максимально использовать эти знания при построении алгоритма распознавания свойств функций.
Важной характеристикой алгоритмической процедуры является ее сложность, которая, напомним, есть функция длины входных данных. Представления одной и той же функции в различных языках имеют различную длину. И поэтому сложность распознавания свойств

В следующей лемме 2.4 мы докажем, что ответ на вопрос о само-двойственности булевой функции может быть получен, имея ответ на вопрос о четности некоторой, известным образом полученной из нее, функции.
Лемма 2.4. Булева функция /(ап
д(хи
является четной.
Доказательство. 1. Докажем необходимость.
Пусть функция /(ап
= f(Xl 0 1,.. ,Хп © 1) 0 (Хг 01)
= /(ян,. , Хп) 0 1 0 Х{
= /(Ж1
Т. е. функция д(хх
2. Докажем достаточность. Пусть функция д(хх
1(х1ф
= (/(1 © 1, . , хп ф 1) 0 (ж,; ф 1) © (ж,; © 1))
= д(хг © 1
= д(х 0 (ж; ф 1)
= /(жх
— f (®1 ) " ! Жп) Ф 1.
Т. е. функция /(жь ... ,хп) самодвойственна.
Лемма 2.4 доказана.
Следующая лемма 2.5 представляет собой критерий четности полинома Жегалкина булевой функции. На этом критерии основывается алгоритм распознавания четности полиномов.