Проблема полноты для функциональных систем полинолов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

им. М.В. Ломоносова

Механико-математический факультет

Кафедра

Математической теории интеллектуальных систем УДК 519.95 На правах рукописи

В.Ш.ДАРСАЛИЯ

ПРОБЛЕМА ПОЛНОТЫ ДЛЯ ФУНКЦИОНАЛЬНЫХ СИСТЕМ ПОЛИНОМОВ

Диссертация на соискание ученой степени кандидата физико-математических наук

Специальность 01.01.09 - математическая кибернетика

Научный руководитель академик Российской академии технологических наук, профессор Московского государственного университета им. М.В.Ломоносова, доктор физико-математических наук В.Б.Кудрявцев

Москва 1997

ОГЛАВЛЕНИЕ

Предисловие..........................................................................................................................................................................................4

ГЛАВА 1. Введение................................................................................................................................................................8

§ 1 .Предварительные сведения из теории функциональных систем..............................................................................................................................................................................................8

§2.Проблема полноты для функциональных систем.........................................._ 18

§3.Постановка задачи............................................................................................................................................20

§4,Основные результаты диссертации......................................................................................22

§5.Теоретическое и практическое значение полученных результатов......................................................................................................................................................................................23

ГЛАВА 2. Функциональная система полиномов с натуральными

коэффициентами................................................................................................................................25

§ 1 .Определение ф.с. ^.................................................................................................................25

§ 2. Замкнутые классы....................................... ..............................................................29

§3.Полнота систем......................................... ....................................................................38

§4.Базисы полных систем............................................................... ..40

§ 5. Относительная полнота..........................................................................................................................42

ГЛАВА 3. Функциональная система полиномов с целыми коэф-

фициентами....................................................................................................................................................45

§ 1 .Определение ф.с. ........................................................................................................................................45

§2.Замкнутые классы...................................... ..................................................................49

§3.Полнота систем......................................... ......................................................................52

§4.Базисы полных систем................................................................................................................................54

§ 5 .Универсальные функции........................................................................................................................64

§6.Относительная полнота................................... ......................................................65

ГЛАВА 4. Функциональная система полиномов с рациональными

коэффициентами....................................................................................................................................71

§ 1 .Определение ф.с. Fq......................................................................................................................................71

§2.3амкнутые классы..............................................................................................................................................77

§3.Полнота систем......................................................................................................................................................85

§4.Базисы полных систем................................................................................................................................87

§ 5. Относительная полнота............................................................................................................................89

ГЛАВА 5. Некоторые вопросы, связанные с проблемой полноты

для функциональных систем полиномов..................................................97

§1.06 аналоге теоремы Колмогорова о суперпозициях непрерывных функций................................................................................................................................................97

§2.0 связи ф.с. FzhFq............................................................................................................................100

§3.0 проблеме выразимости для функциональных систем полиномов....................................................................................................................................................................................108

Литература................................................................................................................................................................................................114

Предисловие

Функциональная система представляет собой множество функций с некоторым набором операций, применяемых к этим функциям и приводящих к получению других функций из этого же множества.

Функциональные системы являются одним из основных объектов математической кибернетики и дискретной математики и отражают следующие главные особенности реальных и абстрактных управляющих систем: функционирование (в функциональных системах это - функции), правила построения более сложных управляющих систем из заданных и описание функционирования сложных систем по функционированию их компонент (последние два момента отражены в операциях функциональных систем).

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

В качестве обобщений реальных функциональных систем могут в принципе рассматриваться и универсальные алгебры, однако, в этом случае теряются основные достоинства реальных функциональных систем и, прежде всего, такие, как конструктивность множеств и операций.

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

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

В настоящей работе рассматриваются следующие функциональные системы: - функциональная система полиномов с натуральными коэффициентами',

Т7/ — функциональная система полиномов с целыми коэффициентами;

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

Для решения поставленных задач необходимо формализовать понятие суперпозиции функций. Существует несколько таких формализаций, например, операции в итеративных алгебрах Поста, предложенные А.И.Мальцевым [19], и операции в алгебрах Менгера [32]. Мы выбираем первый путь и с этой целью строим новые объекты: Гъ, -^д - итеративные алгебры полиномиальных функций, соответственно, с натуральными, целыми и рациональными коэффициентами.

В работе данные объекты расположены так, что каждая последующая функциональная система является "расширением" предыдущей. Это позволяет переносить результаты с

простых систем на более сложные; при этом обращается внимание на аналогии и на существенные различия.

Диссертация состоит из

• 5 глав, которые содержат, соответственно, по 5, 5, 6, 5 и 3 параграфа;

• списка литературы.

Общий объем диссертации 116 страниц.

При изложении материала в основном используется терминология книг [17] и [22].

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

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

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

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

В пятой главе рассматриваются некоторые вопросы, связанные с проблемой полноты, а именно: аналог теоремы Колмогорова о суперпозициях непрерывных функций; взаимосвязь ф.с. Ръ, ^д и алгоритмический вариант проблемы выразимости для этих функциональных систем.

В заключении дается некоторая сравнительная оценка ф.с. Р7 и .Рд (их особенности - отличие и сходство).

В конце диссертации приведен список используемой литературы.

Нумерация для каждой главы своя.

Основные результаты диссертации опубликованы в научных статьях автора, приведенных в списке литературы [3]-[8], а также докладывались на семинарах по теории автоматов механико-математического факультета Московского государственного университета им. М.В.Ломоносова (руководитель семинара академик В.Б.Кудрявцев).

Автор выражает глубокую благодарность своему научному руководителю академику Российской академии технологических наук, профессору Московского государственного университета им. М.В.Ломоносова, доктору физико-математических наук В.Б.Кудрявцеву за постановку задачи и постоянную поддержку при выполнении данной работы.

ГЛАВА 1 Введение

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

§1. Предварительные сведения

Сначала введем некоторые "стандартные" обозначения, необходимые для дальнейшего изложения:

N - множество всех натуральных чисел (включая число 0);

Z - множество всех целых чисел;

С> - множество всех рациональных чисел;

\А\ - мощность множества А;

с0 - мощность счетного множества;

с - мощность континуума.

Для удобства полагаем, что 0°=1.

Пусть и={щ,...ит,...} - исходный алфавит переменных (аргументов).

Пусть X - некоторое (конечное или бесконечное) множество, содержащее не менее двух элементов.

Обозначим через Рх множество всех функций 1,... ,и;п) (и/ Фит при /^г), переменные которых определены на множестве X и сами функции принимают значения из этого же множества X. Предполагается, что множество Рх содержит и все функции от нулевого числа переменных, т.е. функции, являющиеся просто элементами (константами) множества X.

Пусть Р1хп) множество всех п - местных функций из Рх (п=0,1,2,...).

Очевидно, что

. Р?>=Х-

со

. Рх= и Р<">.

п=0

Чтобы избежать сложных обозначений для индексов переменных, мы будем употреблять в качестве метаобозначений (обозначений для произвольных символов алфавита Ц) символы х,у,г,... , а также, эти символы с индексами. Таким образом, запись Дхь...,хп) понимается как запись функции из Рх, зависящей от произвольных фиксированных аргументов и^,...,^, где и^и^ при

Говорят, что функция А?с 1,...,х;.1,х;,х;+1,...,хп) существенно зависит от переменной хь если существуют такие два набора (с\,...,с\.],а,с1+],...,сп) и (с\,...,с\.и Ъ,с1+ь...,сп) значений переменных х1,...,х1.1,х;,х;+1,...,хп, что

В этом случае переменная х{ называется существенной переменной функции

у(х1,...,х],...,хп).

Если х\ не является существенной переменой функции Дхь...,хь...,хп), то она называется несущественной или фиктивной переменной функцииУ(хь...,х;,...,хп).

Пусть 1дхь...,х,_ьхьх1+ь...,хп) и <§-(хь...,х|.ьх^],...,хп) две произвольные функции из Рх и пусть X; фиктивная переменная функции/(хи...,хм,х;,х;+ ь...,хп). Если для любых С1,...,С{.\,С[,С[+\,...,СП значений переменных х\,...,х;.|,хь х;+ь...,хп имеем

то говорим, что функция g(x¡,...,x¡_l,xj+¡,...,xn) получается из функции /(хь...,хм,хь ) изъятием фиктивной переменной х; и, наоборот, функция Дхь...,х;.

ьх;,х1+1,...,хп) получена из функции £-(хь...,Хм,х;+ь...,хп) добавлением фиктивной переменной X;.

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

Замечание 1.1.1. В дальнейшем будем считать, что вместе с функцией/ заданы и все равные ей функции, т.е. функции рассматриваем с точностью до фиктивных переменных.

Замечание 1.1.2. Если дана конечная система функций

где т> 1, то можно считать, что все эти функции зависят от одних и тех же переменных хь...,хп , т.е. они имеют вид

Замечание 1.1.3. Если дана функция, отличная от константы, то путем отождествления переменных из нее можно получить равную ей функцию, все переменные которой являются существенными.

Функции

5," (хь...,хп)=х;(1</<и; «=1,2.3,...) называются селекторными функциями на множестве X. Функция

{(х)=х

называется тождественной (единичной) функцией на множестве X.

Следуя А.И. Мальцеву, введем четыре унарных операции ц, х, А, V и одну бинарную операцию * над функциями из Рх так:

(ту)(х ьх2,... ,хп)=Дх2,х3,... ,х,ъх,) при п>2 и (г|/)=/при и= 1; (т/)(х ЬХ2, • • • ,хп)=Дх2,х! ,х3,... ,хп) при и>2 и (х/)=/ при и=1; (А/}(хьх2,...,хп_])=/(х1,хьх2,...,хП_1) при п>2 и (А/)=/ при п= 1;

(у/) 0е! лг-л1л1+1 )=ЛХ2>ХЗ ,хп,хп+|).

Далее, если имеются/[х1,х2,...,хп) и £(хп+1,...,хп+т) из Рх, то полагаем

,хз,... ,хп,хп+1,.. .,хп-|-т) л^(хп+1,...,хп+т),х2,...,хп).

Эти операции называются операциями суперпозиции. Легко заметить, что операции суперпозиции включают в себя:

• перестановку переменных;

• отождествление переменных;

• переименование переменных (без отождествления);

• введение фиктивной переменной;

• удаление фиктивной переменной;

• подстановку одной функции в другую.

Алгебру РХ=( Р* М), где 0={г|,т,Д,У,*}, а Р*х - произвольное непустое подмножество множества Рх, при этом Рх замкнуто относительно операций из Д назовем функциональной системой (ф.с.).

Когда X конечное множество, состоящее из к (к>2) элементов, то ф.с. (Рх, П) обозначается через Рк и называется к-значной логикой. В частности, когда к=2, тогда имеем ф.с. Р2, которая называется алгеброй логики.

Для произвольного подмножества М множества Р*х обозначим через 1о(Щ множество всех функций из Р*х , которые получаются из функций М с помощью конечного числа применения операций из ¿2.

Замечание 1.1.4. Если множество Мсодержит селекторную функцию я), тогда для любой функции / из М имеем У/=/« т.е. операция V не является независимой. Следовательно, в этих случаях, в предыдущем предложении вместо множества операций /2={г|,т,Л,У,*} можно брать множество операций Д={т1,т,Л,*}.

В ф.с. с операциями суперпозиции естественным образом свяжем оператор замыкания, отображающий совокупность всех подмножеств множества Р*х в себя.

Оператор, переводящий произвольное подмножество М множества Р*х на множество ЫМ), называется оператором замыкания {относительно операций из О) и обозначается через 1п.

Функции из 1&(М) называются суперпозициями функций множества М. Само множество 1а(М) называется замыканием множества М.

Легко заметить, что

• М<= 1а(М);

• 1аЫЩ=М-

• Если М\сМ2, то

где М, М],М2 - произвольные подмножества множества Р"х .

Множество М (Мс: Рх) называется (функционально) замкнутым, если 1а(М)=М. Замкнутое множество принято называть замкнутым классом.

Ясно, что всякое множество 1п(М) будет замкнутым классом. Очевидно, также, что пустое множество и все множество Рх являются замкнутыми классами. Пусть ЦТ- произвольное подмножество множествах

Обозначим через и(Щ множество всех таких функцийДхь... ,хп) из Рх , что

/(си...,сп)е Ж, если сь...,спе Ж. В этом случаеЛхь...,хп) называется функцией, сохраняющей множество IV, а 17(Ж) -классом, сохраняющим множество УУ.

Нетрудно показать, что для любого непустого собственного подмножества ]¥ множества X выполнено:

• и(Ю*0;

• и(УГ)*Рх;

• 1а Ш(Щ= ЩЩ;

- множество всех нульместных функций (т.е. констант) из Щ Щ.

Более того, для любых двух подмножеств и Щ множествах выполнено

если

Подмножество М множества Рх называется (функционально) полным, если /п(М)= . Полное множество принято называть полной системой.

Функция / из ^ называется универсальной функцией, если {/}является полной системой.

Назовем систему М базисом полной системы Т, если МсГ и М полна в Рх, но всякая ее собственная подсистема не является полной в В частности, когда Т= Рх, тогда Мявляется базисом ф.с.

Подмножество М множества Р*х называется предполным (максимальным) классом, если /о(М) фР