Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
-4 —>?
/во+Л—1 С/х» /о, /о, ^4) 5=1 /г0(1,0,0,*4)+й—1 (#4) = А4 (^4) — ^4-
Таким образом, из {/} при помощи суперпозиций мы
получили }у(хи х2) и х, что по теореме 11 дает полноту системы {/}, Теорема доказана.
Мы видим, что для системы (Род, С, О) сохраняются некоторые свойства, которые справедливы для (Рь, С)-Прогноз других свойств системы (Род, Л, С, О) затруднителен, так как, с одпой стороны, функциональный объект Род, * значительно сложнее, чем Р„, и, с другой стороны, добавилась операция О. Первое имеет тенденцию разрушать положительные свойства, второе, наоборот — их усиливать. Заранее сказать трудно, какая тенденция окажется доминирующей. На самом деле в случае проблемы полноты оказалось, что сложность функционального объекта все же влияет сильнее, чем дополнительная операция. Для пояснения приведем без доказательства два ре-вультата. Формулировка первого из них может быть понята скорее содержательно, так как в ней используется понятие алгоритма.
ПО 4.1. ФУШДИиИАЛЬНЫЬ LiiUJJ.bfli-bJ U иli?*'AJJ.ilniVL±l
Теорема 1.4 (М. II. Кратко [9, 10]). Не существует алгоритма, который бы для любой конечной системы о.~д. функций выяснял, является она полной или нет.
Теорема 15 (В. Б. Кудрявцев [12]). Мощность множества предполных в {Poa.kj С классов равна континууму.
Таким образом, проблема полноты для (Род,*, С, О) содержит значительные трудности.
§ 6. О соотношении операций С и О
Функциональная система (Род, А, С, О) обладает многими специфическими свойствами. Однако их формулировка и изложение требуют значительно больше места, чем, например, для (Pk, С). Поэтому здесь мы коснемся только одного вопроса, связанного с тем, что в отличие от рассмотренных, система (Род, ь, С, О) содержит две операции С и О. Речь пойдет о том, в какой мере обе эти операции существенны. Более точно: можпо ли выразить результат одной операции через другую п, в частности, отличаются ли друг от друга операции замыкания в системах (Род, й, С), (Род.а, О) и (Роп> h, С, О)?
Сначала докажем некоторые вспомогательные утверждения.
Теорема 16. Пусть Х = (хи •••» &а), a f(X)—о.-д.
функция веса г; пусть а — периодическая последовательность с периодом р. Тогда существует rt (rt < г) такое, что последовательность f ('Y=/(°0) периодическая с периодом ри где pi — гАр.
Доказательство. В силу периодичности последовательности а, существует такое ?0, что при t > ?0 > 1
сс(? + р)~ а (?).
Функцию }{Х) можно задать диаграммой Мура, содержащей г вершин. Возьмем числовую ось t и в точке t* (?* —1, 2, ...) поставим две пометки: числа а(?*) и х(?* —1)—номер вершины, в которую мы попадаем, исходя из начальной вершины и следуя по пути (а(1), ... ..., а(?* — !)) (см. рис. 18). Рассмотрим далее решетку с начальной точкой ?0 и с периодом р (см. рис. 19).
Так как диаграмма Мура содержит г вершин, то в доел едователъности
х (4> - 1), * (*с + Р ~ 1), • ? « (С + гр - 1)
ГЛ. 3. О.-Д. ФУНКЦИИ С ОПЕРАЦИЯМИ
111
по крайией мере два числа совпадают. Пусть I и / таковы, что
к (г0 + — 1) == и (*0 + )р - 1) {/ > г > 0).
Положим г, ™ / — г. Ясно, что г, < г. Рассмотрим надре-
шетку данной решетки с периодом р1 = г,р и начальной
л(1) а(2) * * * аГО * • *
х(в) хЮ ...
Рис. 18
точкой (и + 1р (см. рис. 20). Очевидно, вершины и + ьр и ?0 + 1р + /?( характеризуются тем, что в них обе пометки а и % совпадают. Это означает, что в эти моменты времени мы находимся в одной и той же вершине диаграммы
Ч(Ьп)
а(Ьв+1р)
хЫ0~1) х&с+р-?) х&в+1р~1)
Рис. 19
и перемещаемся затем по одному и тому же ребру. Тогда к следующему моменту мы попадем в одну и ту же вершину, т. е. пометки
к(?0-Нр), к (*0+ //>)',
также совпадают. Кроме того, в силу периодичности а
к (?о + ір + 1) = а(?0 + }р -Ь 1)
и т. д. Отсюда вытекает, что и выходные последовательности
+ Ч>). Ч(*о + ІР+ 1), ? ?.},
Ь(^о + 7», к(їо+Л>+ 1),
совпадают, т. е. при І ї* 1й + ір
ТГ(і + 7Ч) = Тґ(0-
Этим теорема доказана.
Теорема 17. Пусть /(X) = /0 (/, (X), ..., }т(Х)),где /о, Л, - • *, /т — о.-<9. функции с весами г0} г4, ..гт, не превосходящими П, и а — периодическая последователь-
112
Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
кость, период которой содержит только простые множи-тели, каждый из которых не превосходит Я. Тогда 7=* = 1(а)—периодическая последовательность с периодом, содержащим только простые множители, каждый из которых не превосходит Я.
Рис. 20
Доказательство. Пусть а — периодическая последовательность, период которой р содержит только простые множители, не превосходящие Я. Рассмотрим последовательности
ТГI = /1 <«). •••. Т»“/т(«)-
По предыдущей теореме они являются также периодическими с периодами
Р\ = ..., рт *= ттр (г1} .. Я).
Очевидно, опи содержат также только простые множители, не превосходящие Я. Рассмотрим, далее, вектор
(1и .... ТГ«.);
он будет периодическим и его период ро — общее наименьшее кратное периодов р1( ..рт; значит, все его простые множители не будут превосходить Я, Наконец, последовательность
ТТ-МЦь Тш)
по предыдущей теореме будет периодической с периодом р':
