Содержание к диссертации
Введение
1. Основные onj. геления и вспомогательные утверждения 9
1.1. Основные определения и обозначения 9
1.2. Основные свойства систем функций 12
1.3. Вспомогательные утверждения 14
1.3.1. Метод преобразования формул 14
1.3.2. Основные следствия 17
1.3.3. Преобразование s-формул 19
2. Классы типов L и Р 22
2.1. Классы линейных функций 22
2.2. Классы самодвойственных функций 23
3. Классы типов Е, В и О 26
3.1. Классы функций сохраняющих разбиения 26
3.2. Классы типа В 28
3.3. Классы монотонных функций 32
4. Классы типа С 41
4.1. Классы типа d 41
4.2. Равномерные порождающие системы в классах типа Qj при h,^ 2 43
4.2.1. Порождающие системы 43
4.2.2. Равномерность подсистем 47
4.2.3. Существование равномерных порождающих систем 52
4.3. Классы типа Сг 58
4.3.1. Классы типа Q и Q*. Т-максимальные функции 58
4.3.2. Равномерность порождающих систем в классах типа Сг 68
5. Доказательство основных теорем 76
Литература 78
- Основные свойства систем функций
- Классы самодвойственных функций
- Равномерные порождающие системы в классах типа Qj при h,^ 2
- Равномерность порождающих систем в классах типа Сг
Введение к работе
Данная работа относится к математической теории синтеза управляющих систем. В ней рассматривается задача о реализации формулами функций из предполных классов /с-значной логики.
Одной из основных задач математической кибернетики является построение и изучение модельных классов управляющих систем с точки зрения сложности. Класс формул, реализующих функции А;-значной логики, к 2, является одним из основных модельных классов управляющих систем. В качестве наиболее естественных мер сложности формул выступают число переменных, входящих в формулу, и глубина. Число переменных, называемое также сложностью формулы, характеризует "стоимость", а глубина время работы, при условии что различные вычисления можно производить параллельно. Для каждой функции требуется построить такую формулу, которая реализует эту функцию, и является наилучшей относительно выбранной меры сложности. Имеется простой метод для нахождения таких оптимальных формул, основанный на переборе всех формул данной сложности. Однако этот метод практически не применим, поскольку требует для своей реализации большого числа шагов. Поэтому возникает задача о разработке таких методов синтеза, которые позволяют строить для всех функций из заданного множества относительно хорошие формулы, и при этом существенно проще перебора всех формул.
Для множества всех булевых функций асимптотически оптимальные методы синтеза формул в полных базисах (а также ряда других важных классов управляющих систем) были разработаны О. Б. Лупановым [7-13] (см. также [6, 45]). Оценки глубины формул в полных базисах были получены в работах [4, 5] (см. также [18]). Из результатов О. Б. Лупанова, в частности, следует, что большинство функций алгебры логики допускает лишь очень сложную реализацию. Поэтому, с одной стороны, представляет интерес выделение классов функций, допускающих более простую реализацию, и разработка методов синтеза оптимальных формул для функций из этих классов. С другой стороны, представляется важным для различных естественных классификаций функций fe-значной логики иметь оценки глубины и сложности формул, реализующих функции из соответствующих классов. Одной из наиболее известных и лучше всего изученных с функциональной точки зрения классификаций булевых функций является описание Э. Поста [40, 41] множества всех замкнутых относительно операции суперпозиции классов функций (см. также [14, 16, 22, 27, 37]). Обзор результатов, полученных для формул над конечными системами, реализующих функции из классов Поста содержится в [23]. При к 3 к настоящему времени изучены только некоторые семейства замкнутых классов в Рк, в частности, предполные классы функций, все семейства которых описаны в работах И. Розенберга [46, 47] (см. также [2, 15, 26, 29]). Таким образом, возникает задача о реализации функций из замкнутых классов fc-значной логики формулами над конечными системами, имеющими наименьшую сложность или глубину. При этом при реализации функций из некоторого замкнутого класса А;-значной логики представляется естественным рассматривать формулы в базисах состоящих из функций принадлежащих этому же классу.
Как правило, при разработке вычислительных устройств возникает необходимость минимизировать сложности формул одновременно по нескольким параметрам, например, по числу элементов и времени работы. Поэтому представляет интерес получение соотношений между глубиной и сложностью формул, реализующих заданные функции.
Конечную систему функций 21 из Рк, к 2, будем называть равномерной, если существуют такие константы cud, зависящие только от системы 21, что для всех функций / из [21] выполнено неравенство
a(/) clog2Lsi(/) + d, (1)
где La(/) и D n(f) — соответственно минимальные сложность и глубина, с которыми можно реализовать функцию / формулами над системой 21. Все необходимые определения приведены в главе 1.
В. М. Храпченко показал (см. [28]), что любая полная в Р2 конечная система функций равномерна. Аналогичный результат был получен Ф. Спирой [48], (см. также [42]). Похожую задачу о времени вычисления арифметических выражений с использованием нескольких процессоров рассматривали Р. Брент, Д. Кук и К. Маруяма [32] и Р. Брент [33, 34], применившие метод преобразования формул для арифметических выражений аналогичный предложенному В. М. Храпченко и Ф. Спирой. Поскольку нижняя оценка для Аа(/) аналогичная (1) (с другими константами) получается тривиально, оценка (1) является наилучшей по порядку. Задача о получении оценок для константы с в соотношении (1) для различных полных систем булевых функций рассматривалась в работах [24, 25, 35, 39, 43, 49]. Использованный в работах [28, 48] метод позволяет по произвольной формуле построить эквивалентную ей формулу логарифмической глубины от сложности исходной формулы. При этом сложность формулы увеличивается. Путем модификации метода преобразования формул в некоторых случаях можно добиться чтобы увеличение сложности было незначительным (см. [31, 36]). Отметим, что методы преобразования формул, приведенные в работах [28, 48] легко переносятся на случай полных систем функций А;-значной логики при к 3. Однако они существенно используют полноту систем.
Для полных монотонных систем булевых функций равномерность была доказана И. Вегенером [51] (см. также [52]). Равномерность произвольных конечных систем булевых функций была доказана А. Б. Угольниковым [20, 21], им также приведены примеры неравномерных систем функций в Рь при к 3 (см. также [44]). Поскольку, как уже было отмечено выше, методы приведенные в работах [28, 48] позволяют устанавливать равномерность полных систем функций в Рк при любом к 3, возникает вопрос о равномерности неполных систем функций в Рк- Л. И. Ахметовой [1] был анонсирован результат о том, что любая конечная система функций в Р3, порождающая предполный класс, является равномерной. В данной работе изучается равномерность конечных порождающих систем для предполных классов fc-значной логики.
Пусть к 2. Множество {0,1,..., & —1} будем обозначать через Ек- Класс функций, сохраняющих отношение р, будем обозначать через Ар (определения см. в главе 1). Будем пользоваться обозначениями из [29], согласно которым в Рк имеются следующие семейства предполных классов:
1) классы самодвойственных функций — классы типа Р;
2) классы линейных функций — классы типа L;
3) классы функций, сохраняющих разбиения множества Ек, — классы типа Е;
4) классы функций, сохраняющих сильно гомоморфные прообразы Л-адических элементарных отношений, — классы типа В;
5) классы монотонных функций — классы типа О;
6) классы функций, сохраняющих центральные отношения, — классы типа С. Если р — отношение частичного порядка на Ек, такое, что для любых двух элементов а и Ь из Ек существуют sup (а, Ь) и inf (а, Ь) относительно частичного порядка р, то будем говорить, что Ар — класс типа О . Если т — бинарное центральное отношение, то будем называть Ат классом типа (. Если о — унарное центральное отношение (то есть унарное отношение, отличное от Ek и 0), то будем называть А„ классом типа Ci. Положим р = Е!\{(1, 2,3), (2,1, 3), (2, 3,1), (3, 2,1), (3,1, 2), (1,3, 2)}. В настоящей работе получены следующие основные результаты.
Теорема 1. Пусть 21 — произвольная конечная система функций из Рк, к 3, такая, что [21] является предполным классом одного из следующих типов: L, Р, Е, Ш, О , С\, Q. Тогда система 21 равномерна.
Следствие 1 (см. также [1]). Пусть 21 — произвольная конечная система функций из Р3, такая, что [21] — предполный класс в Р$. Тогда система 21 равномерна.
Следствие 2. Пусть 21 — произвольная конечная система функций из Р4, такая, что [21] — предполный класс в РІ, не являющийся двойственным классу Ар . Тогда система 21 равномерна.
Теорема 2. Пусть 21 - произвольная конечная система функций из Рк, 3 к 7,
такая, что [21] является предполным классом типа О. Тогда система 21 равномерна.
Как известно, при к = 8 в Рк существуют предполные классы монотонных функций, не имеющие конечных порождающих систем (см. [50]). Кроме того, в настоящее время отсутствует полное описание всех предполных классов монотонных функций для к 8, имеющих конечные порождающие системы, что затрудняет получение существенного усиления теоремы 2 (то есть доказательство аналогичного утверждения для всех предполных классов монотонных функций, имеющих конечные порождающие системы для произвольных к).
Теорема 3. Пусть А — замкнутый класс в Рк, к 3, являющийся предполным классом типа С- Тогда существует такая равномерная система 21, что А — [21].
Теорема 4. Пусть Ар — произвольный предполный класс в Рк, 2 к 7. Тогда существует такая равномерная система 21, что Ар — [21].
Доказательство теорем 1, 3, 4, использующее результаты, полученные в главах 1-4, приведено в главе 5. Теорема 2 доказывается в главе 3. Для доказательства теорем 1, 4 мы последовательно рассматриваем все семейства предполных классов в Рк.
Формулы будем называть эквивалентными если они реализуют равные (с точностью до добавления и удаления несущественных переменных) функции. При преобразовании формул над одной системой функций в эквивалентные формулы над другой системой функций глубина формул изменяется линейно. Для сложности же это вообще говоря не так (это следует, например, из результатов [17]). Однако, если 21 и 03 две конечные системы функций из Pfc, [21] = [53] и система 21 равномерна, то любая формула над 21 может быть преобразована в эквивалентную формулу над 93 с не более чем полиномиальным увеличением сложности Поскольку в Рг любая конечная система равномерна, любые конечные системы, порождающие один и тот же класс булевых функций, полиномиально эквивалентны (см. [19, 21]). Из результатов данной работы, в частности, следует полиномиальная эквивалентность порождающих систем для некоторых семейств предполных классов. Кроме того, для большего числа предполных классов установлено, что для каждого из них существует порождающая система функций 21, такая, что сложность функций в любой другой конечной системе, порождающей этот класс, ограничена полиномом от сложности функций в системе 21 (см. главу 5).
Опишем кратко содержание работы.
В главе 1 приводятся основные определения и утверждения необходимые для доказательства равномерности различных систем функций. Приводится несколько обобщений метода использованного в [42, 48] для доказательства равномерности полных систем функций в Р2 (леммы 1.3.3, 1.3.4, 1.3.5). Вводится понятие s-формул и доказывается обобщение этого метода для них (лемма 1.3.7). Кроме того, вводится понятие равномерности одной системы функций в другой системе, благодаря которому упрощается изложение доказательства равномерности в некоторых случаях (леммы 1.2.2, 1.3.6), путем сведения задачи к доказательству равномерности подсистемы функций в исходной системе.
Одним из основных методов доказательства равномерности системы функций является использование разложения по переменной. Именно этот подход использовался в работах [28, 48]. Суть метода состоит в следующем. Произвольная формула Ф над рассматриваемой системой функций разбивается на две части и представляется в виде Ф(х) = В(А(х),х), где А и В формулы (являющиеся частями исходной формулы), причем они выбираются таким образом, чтобы сложность формулы Ф не превосходила сложности каждой из них более чем в т раз, где т — некоторая константа. Далее находится такая функция (у,х0,... ,Хк-\), что формула В{А(х),х) эквивалентна формуле (р(А(х), 5(0, х),..., В(к — 1, ж)). Глубина последней формулы меньше глубины исходной формулы Ф, если сложность формулы Ф достаточно велика. Аналогичная процедура применяется к формулам А(х), В(0, х),..., В(к — 1,х), сложность которых меньше сложности исходной формулы. В итоге, при многократном применении этой процедуры, строится формула над системой { /з, 0,.. .,к — 1}, глубина которой по порядку не превосходит логарифма сложности исходной формулы. В том случае, когда функция ip и константы принадлежат рассматриваемому классу функций, то есть выражаются через функции исходной системы, отсюда следует, что эта система функций равномерна (см. лемму 1.3.5).
Следует отметить, что в некоторых случаях для разложения можно использовать различные функции в зависимости от свойств формул Л и ІЗ, на которые разбивается исходная формула. В случае, когда число необходимых для разложения функций конечно, обобщая описанный выше метод можно доказать, что исходная система функций равномерна (см. лемму 1.3.4).
В главе 2 рассматриваются семейства классов линейных и самодвойственных функций, для которых равномерность порождающих систем доказывается без использования разложения по переменной или специальных преобразований формул. В обоих случаях доказательство равномерности основано на свойствах функций из рассматриваемого класса.
В параграфе 2.1 доказывается равномерность порождающих систем для классов линейных функций. Равномерность следует из ассоциативности операции сложения. Любая линейная функция от п переменных может быть представлена как сумма п одноместных линейных функций и константы. Поэтому, в силу ассоциативности сложения сумма п переменных реализуется формулой, глубина которой по порядку равна log п.
В параграфе 2.2 приведено доказательство равномерности порождающих систем в классах самодвойственных функций, которое сводится к доказательству равномерности полных систем функций в Pfc. Применяется обобщение метода, использованного в [21] для доказательства равномерности порождающих систем класса самодвойственных функций в Р2. Равномерность произвольной порождающей системы для класса Zk{s) функций, самодвойственных относительно некоторой подстановки s, доказыва ется следующим образом. Сначала к системе функций добавляется константа. Над новой системой, которая уже является полной, и, следовательно равномерной, строится формула нужной глубины. В случае, когда подстановка s имеет только один цикл, константа заменяется на переменную, которая оказывается несущественной и мы получаем формулу нужной глубины над исходной системой функций. В случае, когда подстановка имеет несколько циклов применяется обобщение описанного метода. Если константу в формуле заменить на любую другую константу из того же цикла подстановки s, то мы получим эквивалентную формулу. Выбрав по одной константе из каждого цикла подстановки и построив приведенным выше способом (при помощи замены константы на переменную) формулы, мы получим, что каждая из них имеет необходимое значение в случае, если новая переменная принимает значение из соответствующего цикла подстановки. Из полученных формул строится формула для исходной функции у которой новая переменная оказывается несущественной.
В главе 3 рассматриваются случаи, в которых применимы методы связанные с разложением по переменной (то есть леммы 1.3.5 и 1.3.4). Доказывается равномерность конечных порождающих систем для классов функций сохраняющих разбиения, классов типа В, классов монотонных функций при к 7 и классов типа О .
В параграфе 3.1 для классов функций, сохраняющих разбиения, устанавливается, что каждую функцию f(y,x) из рассматриваемого класса можно представить в виде f(y,x) = ip(y,f(Q,x),...,f(k — 1,х)), где р — некоторая функция из класса, которая одинакова для всех функций /. Для классов типа В в параграфе 3.2 показывается, что верно аналогичное представление, но выбор функции (р зависит от исходной функции /, хотя число различных функций р которые необходимы для разложения произвольных функции из рассматриваемого класса ограничено.
В параграфе 3.3 для классов монотонных функций строится аналогичное представление, для которого используется единственная функция tp. Основная проблема состоит в построении этой функции и проверке того, что она является монотонной. Для классов тина О функция указывается в явном виде. Все оставшиеся случаи для классов монотонных функций в Ffc при к 7 сводятся к построению функции ср для одного фиксированного класса в Р$, для которого приводится алгоритм построения функции р. Соответствующие функции для остальных классов получаются из последней, при помощи приведенных в работе монотонных отображений. Таким образом, предлагается способ, при помощи которого вопрос о существовании разложения по переменной в одном классе функций можно свести к аналогичному вопросу в другом классе функций логики меньшей значности.
Глава 4 посвящена классам типа С, для которых, вообще говоря, не удается применить использованные ранее методы доказательства равномерности. Исключение составляют классы типа Q, которые рассматриваются в параграфе 4.1. Доказательство равномерности порождающих систем для классов типа Q в Рк сводится к доказательству равномерности полных в Рт систем функций (для 2 г к) при помощи метода моделирования констант (предложенного в [21]). Сначала к системе функций добавляется константа. Над расширенной таким образом системой функций, которая уже является равномерной, строится формула нужной глубины. Затем все вхождения константы заменяются некоторой формулой над исходной системой функций, реализующую близкую к константе функцию. В итоге получается формула, реализующая функцию, которая совпадает с исходной, когда значением формулы "моделирующей" константу является эта константа. На остальных наборах значение построенной формулы корректируется при помощи дополнительных преобразований.
В параграфе 4.2 доказывается существование равномерных порождающих систем в произвольных классах типа С/4 при h 2 для любых возможных значений к. Для формул определенного вида удается построить метод преобразования, позволяющий доказывать равномерность системы. Сначала для каждого из классов строятся порождающие системы специального вида. Затем для каждой этих из порождающих систем рассматривается некоторое ее подмножество и доказывается его равномерность во всей порождающей системе (то есть для каждой формулы над этим подмножеством строится эквивалентная формула над всей системой функций, такая, что глубина этой формулы по порядку не превосходит логарифма сложности исходной формулы). При доказательстве существенным образом используются свойства функций рассматриваемого подмножества порождающей системы, благодаря которым произвольную формулу над ним можно преобразовать в эквивалентную таким образом, что выделенная переменная, входящая в исходную формулу, окажется в новой формуле на глубине, ограниченной некоторой константой, а глубина всей формулы не увеличится. Для доказательства равномерности применяется лемма 1.3.3. Поэтапно добавляя к выбранному подмножеству функции исходной порождающей системы и доказывая равномерность получающихся подмножеств в исходной системе функций, доказывается се равномерность.
В параграфе 4.3 доказывается равномерность произвольных порождающих систем для классов типа С? при любых возможных значениях к. Сначала рассматриваются классы типа Q специального вида (классы типа С и классы типа Cj ). Для этих классов доказывается аналог разложения по переменной, который применим только к функциям определенного вида (не принимающим некоторых значений), но при этом разложение осуществляется сразу по нескольким переменным (утверждение 4.3.16). Используя полученное разложение, доказывается равномерность произвольных порождающих систем в классах типа Сг. Для этого для каждой функции из рассматриваемой порождающей системы класса типа Сг строится несколько функций из классов типа Cj или С , по которым легко восстанавливается исходная функция, при этом значность логики для новых функций может уменьшиться. Используя построенные функции, формула над исходной системой преобразуется в несколько формул большей сложности над системой новых функций из классов типа Q или Q . Построенные таким образом формулы реализуют функции, при помощи которых можно восстановить значения функции реализуемой исходной формулой. Несмотря на большую сложность, полученные формулы имеют структуру в некотором смысле похожую на структуру исходной формулы. В совокупности все они образуют так называемую s-формулу (определение см. в главе 1). Благодаря полученному ранее разложению (утверждение 4.3.16), к этой s-формуле можно применить лемму 1.3.7 и, таким образом, получить эквивалентную s-формулу нужной глубины. Последняя з-формула преобразуется в обыкновенную формулу требуемой глубины над исходной системой функций, которая эквивалентна исходной формуле.
В главе 5 приводятся доказательства теорем, содержащих основные результаты работы.
Утверждения нумеруются тройками чисел, где первое число — номер главы, второе — номер параграфа, третье номер утверждения внутри параграфа. Леммы, теоремы и следствия (кроме основных теорем и следствий, приведенных во введении) нумеруются аналогичным образом. Так, например, лемма 1.3.2. — это вторая по счету лемма, расположенная в третьем параграфе первой главы. Рисунки и таблицы нумеруются парами чисел, где первое число — номер главы, второе — номер рисунка или таблицы внутри главы. Конец доказательства отмечается символом Основные результаты диссертации опубликованы в работах [53-57].
Основные свойства систем функций
Очевидно, что при преобразовании формул над одной системой функций в эквивалентные формулы над другой системой функций их глубина увеличивается не более чем линейно. Сформулируем это в виде следующего утверждения Утверждение 1.2.1. Пусть 21, 23 — конечные системы функций из 1\, 21 С [23], с = тах)(в(/). Тогда для любой функции / из [21] верно неравенство D (f) . cD%(f). /е[я] Следующее утверждение является очевидным свойством ассоциативных функций. Утверждение 1.2.2. Пусть функция р(х,у) из Pk ассоциативна, Тогда для всякой функции f(xi,..., хп) из [{(р}} верно неравенство Следующая лемма является аналогом хорошо известного предстваления функций fc-значной логики (см. [30]). Лемма 1.2.1. Пусть Q — непуст,ое подмножество Еь- Тогда [Pkq\ = Pk,Q- Доказательство. Без ограничения общности будем считать, что Q = Ег, иначе константы 0 и утверждение леммы очевидно. Если г 1, то рассмотрим функции тіп (ж,у), тах (.х,у), где min и max на Е% совпадают с обычными min и max, а на остальных наборах равны 0. Кроме того, рассмотрим функции / (я;), а = 0,..., А; — 1, определенные следующим образом. [0 в остальных случаях. Очевидно, что функции тт (х,у), тах (ж, у), J (x) принадлежат Pfc Q. ДЛЯ п 2 положим min !,. ..,„) = min (iCi, min (х2,..., тіп (ж„_1,жп)...)), тах (ж!,... ,х„) — тах (жі,тах (а:2,..., Легко видеть, что произвольную функцию f(x) из Pk,Q можно представить в следующем виде Следовательно, PktQ С [{min , max , J0 ,..., J_x, 0,..., r - 1}] С [P Q] С Pfc(?. Лемма 1.2.2. Пусть 2t u 03 — конечные системы функций из Рк, 03 С 21, 03 равномерна в 21 -и ) С 21 . Пусть для любой функции р(х\,... ,хп) шЗЗ, п 1, и любой функции f(x) из [2)]0 существуют такие функции gi{x), г — 1,..., п, мз [2)] , м функция h(x\,..., ж„) ш 03, что Тогда система Q5US равномерна в 21. Доказательство. Назовем формулу Ф над 58 U [3] приведенной, если она тривиальна, либо Ф = g(xi), где g Є [S)] \ либо существуют нетривиальная формула F(xi, ...,хт) над 03 и формулы d,..., Докажем, что для произвольной формулы Ф над 23 U [S] существует такая эквивалентная ей приведенная формула Ф над 03U [ ] , что (Ф) (Ф) и (Ф) -О(Ф). Будем доказывать это утверждение индукцией по глубине формулы Ф. Если -О(Ф) = 0 или -О(Ф) = 1, то Ф уже является приведенной формулой и утверждение очевидно. Пусть утверждение верно для всех формул, глубина которых не превосходит некоторого N, где N 1. Докажем, что оно верно и для произвольной формулы Ф, такой, что»(Ф) = N + 1. Пусть Ф - формула над 03 U [Э](1\ И(Ф) = N + 1. Тогда Ф = f(Ax,..., Аг), где f(xi,..., xr) — функция из 03 U [Э] \ а АІ7 г = 1,..., г, — формулы над 23 U [S) 1), глубина которых не превосходит N. Пользуясь предположением индукции получаем, что для формул Ai,..., Д. существуют эквивалентные им приведенные формулы ВЪ...,ВТ над 03и[ ](1), такие, что Ь(В{) Ь(Аг), 0{Вг) D(Ai) N.
Таким образом, ВерНО СООТНОШение Ф I I f(Bi, . . . , Вг). Случай 1. Предположим что / Є 03. Тогда формула f(B\,..., Д.) является приведен- ной, ее глубина не превосходит JV+1, и L(f(Bi,..., Br)) = J2 Ь{Вг) Yl L(Ai) = (Ф). Случай 2. Предположим теперь, что / Є [ЗЭ] . Тогда г = 1 и Ф f(Bi). Случай 2.1. Формула В\ тривиальна. Тогда формула f(Bi) является приведенной, а ее глубина и сложность равны 1 и не превосходят глубину и сложность исходной формулы Ф. Случай 2.2. Формула В\ нетривиальна. Случай 2.2.1. В\ — g(xi), где д Є [ ] . Тогда функция h[x) = f(g(x)) принадлежит [3D] 1), и Ф h(xt). Остается заметить, что h(xi) является приведенной формулой, глубина и сложность которой равны 1 и не превосходят глубину и сложность исходной формулы Ф. Случай 2.2.2. Вх = p{G\,..., Gv), где р Є 03, a Gu ..., Gv — формулы над 03 U [D](1), глубина которых не превосходит JV — 1. Поскольку / Є [2)] \ р Є 03, по условию леммы получаем, что f(ip(x\,... ,xv)) — h(gi(xi),... ,gv(xv)) для некоторых функций h є 03 и 7i,..., gv Є [Э] 1 . Следовательно, верны соотношения Каждая из формул g3(Gj), j = 1,...,v, является формулой над 53 U [5)] , глубина которой не превосходит N. Следовательно, к формулам gj(G3), j = 1,..., и, можно применить предположение индукции и получить приведенные формулы Fi,. . ., Fv над «BUpDp, такие, что F3 g3{G3), L(F3) L{G3), D{F}) D(G3) + l N+l, j = 1,...,v. Легко видеть, что формула h(Fi,..., Fv) эквивалентна исходной формуле Ф, является приведенной, ее глубина не превосходит N + 1 = (Ф), а сложность не превосходит Ь(Ф). Таким образом, во всех возможный случаях мы получили приведенную формулу необходимой глубины и сложности, которая эквивалентна исходной формуле Ф. Положим do = max L%{f). Пусть Ф — произвольная формула над 03 U ЗЭ. Она является формулой над 03 U [3D] 1). Мы показали, что для нее существует такая экви валентная ей приведенная формула Ф над Su[X)] \ что Ь(Ф ) Ь(Ф). Если формула Ф тривиальна, то Ф является формулой над 21, Ф Ф, Р(Ф ) = 0. Если Ф = g{xt), где д Є [3D] 1 , то по определению константы d0, существует формула над 21 эквивалентная исходной формуле Ф, глубина которой не превосходит do- Если Ф = Ф(Сі,..., Gm), где Ф(жі,...,хт) — формула над 03, a Gi,..., Gm — формулы над [3D] 1), глубина которых не превосходит 1, Ь(Ф) (Ф), то воспользуемся равномерностью 03 в 21. Поскольку система 03 равномерна в 21, существуют такие константы end, что для всякой формулы В над 03 существует такая эквивалентная формула А над 21, что D(A) c\ogL(B) + d. Следовательно, для формулы Ф(ж1;..., хт) существует такая эквивалентная формула Ф (жі,... ,хт) над 21, что (Ф ) c\ogL(4 ) + d. Очевидно, что существуют формулы G\, .., G m над 21, такие, что G\ Gi, D(G[) d0, і = 1,..., т. Получаем, что форму ла 4 (G[, ... ,G m) является формулой над 21, эквивалентна исходной формуле Ф, и ее глубина не превосходит clogZ ) + d + d0. Следовательно, система 03 U ЗЭ равномерна В данном параграфе доказывается лемма 1.3.3, являющаяся обобщением метода использованного в [28, 48] для доказательства равномерности полных систем булевых функций.
Эта лемма дает возможность при выполнении некоторых условий, преобразовывать произвольную формулу в эквивалентную таким образом, что глубина получающейся формулы по порядку не превосходит логарифма сложности исходной формулы. Сначала мы докажем две вспомогательные леммы. Лемма 1.3.1. Пусть 21 — произвольная конечная система функций из Pk, к 2, т = m(2l), Ф(х) — произвольная формула над 21, N = Ь{Ф). Пусть N т + 1. Тогда формулу Ф(х) можно представить в виде В(А(х),х), где А(х) и В(у,х) — формулы над 21, такие, что переменная у имеет только одно вхождение в формулу В и выполняются неравенства L{A), L(B) h[{N + 1) Доказательство. Поскольку т 1 и N т + 1, верны неравенства Легко видеть, что в формуле Ф можно найти такую подформулу Ф, которая имеет вид /(Фі, Фг, , Фп) гДе / некоторая n-местная функция из 21, и 1, Фі, Ф2,..., Ф„ — формулы над 21, и при этом выполнены следующие условия: Поскольку число переменных у функций из 21 не превосходит тп, а / Є 21, верно неравенство п т, а значит найдется такое j, 1 j п, что выполняются соотношения Представим Ф в виде В(Ф (ж),ж). Покажем, что данное представление формулы Ф является искомым. Используя неравенства (1.1), получаем следующие соотношения Лемма 1.3.2. Пусть m и N — произвольные целые числа, такие, что т 1, N т + 1. Тогда верно равенство Доказательство. Заметим, что выполнены следующие соотношения Поэтому верно равенство Отсюда, следует, что верна следующая цепочка равенств Пусть 21, 05 — произвольные конечные системы функций из Рк, к 2, .ft — некоторое множество формул над 21. Будем говорить, что множество R является (21,23)-регулярным, если существует такое конечное множество формул # над 23, что для любых формул А(х), В(у, х) над 21, таких, что переменная у имеет только одно вхождение в формулу В и формула В(А(х), х) принадлежит множеству R, найдутся формула F(yi,...,ys,zi,...,zr) из , и формулы Ai(x),...,Aa(x),Bi(x),...,Br(x) из R, такие что L(Ai) L(A), і — 1,..., s, L(Bj) L(B), j = 1,... , г, и верно соотношение Лемма 1.3.3. Пусть 21, 23 — произвольные конечные системы функций из Р , к 2, R — (21,23) -регулярное множество формул над 21. Тогда существуют такие константы cud, зависящие только от 21, 23 и R, что для любой формулы Ф из R существует такая формула Ф над 21 U 23, что Ф Ф и выполняется неравенство (Ф ) сЩ(ЦФ) - m(2l)) + d. Доказательство.
Классы самодвойственных функций
Для классов самодвойственных функций доказательство равномерности порождающих систем аналогично доказательству для класса S в Р2 (см. [21]). Функции из Pk самодвойственные относительно s образуют замкнутый класс Zk(s), который является предполным тогда и только тогда, когда s имеет только циклы одинаковой простой длины (см., например, [29]). Предполные классы самодвойственных функций называют классами типа Р. Пусть s — произвольная подстановка на Ек- Пусть количество циклов подстановки s равно г. Множество элементов входящих в г-ый цикл подстановки s будем обозначать через АІ, г = 1,... , Утверждение 2.2.1. Пусть f(x) и g(y,x) самодвойственные относительно подстановки s функции, і Є {1,... ,г}, а Є Аг и g(a,x) = /(5)- Тогда для всякого /З Є АІ верно равенство g(ft, х) — f(x). Доказательство. Из того, что а, /З Є А% следует, что существует та кое число т, что sm(/3) = а. По условию g(a,x) = f(x), следовательно д(а, sm(x)) = f(sm(x)). Из самодвойственности д и / относительно s следует, что smW,x)) = g(sm(P),sm(x)) = g{a,sm{x)) = f{sm{x)) = sm(f(x)). Откуда получаем, Определим функцию ф(у,Хі,..., хт) Рк следующим образом. Положим ф(у, х\,... ,хг) равным хг, если у є Аг, і = 1,..., г. Таким образом, мы полностью определили функцию ф, поскольку U Аг — Ek- Определение корректно, поскольку при і ф j множества АІ И А, не пересекаются. Утверждение 2.2.2. ф Є Zk(s). Доказательство. Покажем, что для всякого набора (a,/3i,...,/3r) из Е +і верно равенство Пусть а Є Аг. Тогда верно равенство ф(а,/Зі,...,/Зг) = /. Заметим, что s(a) тоже принадлежит Л», и, следовательно, 0(s(a),,s(/3i),... ,s(/3r)) = s(/3j), откуда и следует нужное равенство. Утверждение 2.2.3. Пусть 21 — конечная система функций из Р такая, что [21] = Zk(s). Пусть для каждого і — 1,..., г существует такое а» Є АІ, что система 21 U {а,і} равномерна. Тогда, система 21 равномерна. Доказательство. Поскольку по условию для каждого г = 1,..., г, система 21U (} равномерна, получаем, что для любого аг, г = 1,..., г, существуют такие константы с; и d,, что для всякой функции / Є [21] верно неравенство Ааи{а,}(/) сг logLau{flj}(/) + di. Положим с = max (с»), d = max (di).
Очевидно, что Ь цыал(/) &(/) Отсюда следует, что для любой функции / Є [21] верно неравенство Для каждого г, г = 1,...,г, рассмотрим формулу Ф , которая реализует функцию f(x) над 2t U {aj}, такую, что )(Ф,) = Даи{а,}(/)- Заменим в формуле Ф все вхождения константы G,J на переменную у. Получим формулу Ф;, которая реализует самодвойственную относительно s функцию gi(y,x), такую, что Qi(ai,x) — f(x). Рассмотрим формулу Q(y,x) — ф(у, Фі(у,:г),..., Фг(у, ж)). Она реализует функцию ф(у,Уі(у, х),... ,gr(y,x)). Из утверждения 2.2.1 и определения функции ф следует, что ф(у,д\(у,х),... ,gr(y,x)) — f(x). Из вида формулы О получаем равенство D(Q) = 1+ max (Даи{а,}(/)) из которого, учитывая неравенство (2.1), получаем, что для любой функции / Є [21] верно неравенство Из утверждения 2.2.2 следует, что ф Є [21], а значит по утверждению 1.2.1 существует такая константа С\, что для любой функции / Є [21] верно неравенство Аа(/) ciDau{0}(/)- Отсюда, учитывая неравенство (2.2), получаем неравенство Следовательно, система 21 равномерна. Теорема 2.2.1. Пусть s(x) — такая подстановка на Е , что класс Zk(s) является предполным в Рк, к 2. Пусть 21 — конечная система функций из Рк и [21] = Zk(s). Тогда система 21 является равномерной. Доказательство. В каждом из множеств Аг выберем по одному элементу щ. По скольку класс Zk(s) является предполным, система 21 U {а,} является полной в Рк, и следовательно, по утверждению 1.3.1 равномерной для каждого г — 1,...,г. Таким образом, утверждение теоремы следует из утверждения 2.2.3. Классы типов Е, В и О В этой главе рассматриваются классы функций, сохраняющих разбиения (классы типа Е), классы типа В, и классы монотонных функций (классы типа О). Равномерность порождающих систем для классов этих типов доказывается с использованием лемм 1.3.5 и 1.3.4. 3.1. Классы функций сохраняющих разбиения Пусть D — какое-нибудь разбиение множества Ек на непересекающиеся подмножества Di,... ,DS, то есть все множества Dt не пусты и каждый элемент множества Ек принадлежит одному и только одному из множеств Д-. Разбиение D будем называть тривиальным, если s = 1 или s — к. Очевидно, что при к = 2 все разбиения Ек тривиальны. Элементы а и (5 из Ек называются эквивалентными относительно разбиения D (будем писать а /3 (mod D)), если они принадлежат одному и тому же множеству Di. Наборы а и [3 из Е% называются эквивалентными относительно разбиения D (будем писать а /3 (mod ))), если для всех г = 1,..., п верно аг (Зг (mod D). Будем говорить, что функция /() из Рк сохраняет разбиение D, если для всех наборов а, /З Є Ek, для которых а /3 (mod D), верно f(a) /(/?) (mod D). Множество всех функций, сохраняющих разбиение D, обозначим через U(D). Нетрудно показать, что U(D) является замкнутым классом. Очевидно, что константы 0,1,..., к — 1 принадлежат классу U(D). Легко видеть, что если D — тривиальное разбиение Ек, то U(D) = Рк. В случае, если D — нетривиальное разбиение Ек, класс U(D) отличен от Рк и является предполным (см. [26]). Следуя [29] будем называть такие классы классами типа Е. В данном параграфе мы докажем равномерность произвольных конечных порождающих систем для классов типа В при любых к Пусть /і ) 2, m ) 1, о Є Е}ьт.
Будем обозначать через а№ г-ю цифру числа а, записанного в системе счисления по основанию h. Тогда мы можем представить а в виде Отношение m С Epm, содержащее те и только те наборы (ao,«i,... ,ап-і), для которых (а0 , а[ ,..., а _г) Є і\ при всех г, 0 = і т — 1, будем называть h-адическим элементарным отношением. Отношение р С Ер называется сильно гомоморфным прообразом отношения а С Ер, если существует такое отображение q (сильный гомоморфизм) множества Ек на множество Е\, что р содержит те и только те наборы (а0) АН? , h-i), для которых (q(ao),Q{ai),...,q(ah-1)) Є а. Пусть /і З, т 1, к hm. Если /г-арное отношение р С Ер является сильно гомоморфным прообразом /г-адического элементарного отношения т Є Ерт, то класс функций, сохраняющих р, Ар называется классом типа В, ар- отношением типа В. Классы типа В являются предполными в Рк, к 3, (см., например, [29]). Пусть р С Ер — /г-арное отношение типа В. Тогда существует такое т, т 1, к hm, что р является сильно гомоморфным прообразом отношения т при некотором отображении q : Ек —» Е/,. Положим Аг = {х Є Ек \ q{x) = г}, г Є . m, ТО ЄСТЬ JT.4 является полным прообразом г при отображении . В каждом из множеств АІ выберем по одному элементу (. Определим отображение г : Е т — , положив г (г) = аІ5 і Є і?/, . Пусть В - {а0, аь .. ., Доказательство. Для того, чтобы доказать, что А Є Ар надо показать, что для любых двух наборов (bo,..., 6Л-І), (со,... , Qj_i) из отношения р набор (A(bo,t o), - , A(6/j_i, c/j-x)) тоже принадлежит отношению р. Пусть (&о, , frft-i), (со, , ch-\) Є р. По определению, из того, что (&о,..., 6Л_і) Є р следует, что (q(bo), .. ,9(6/1-1)) Є m. Заметим, что верно равенство q(X(xi,x2)) = q(xi). Таким образом, получаем, что (q(\(b0,co)),... ,q(X(bh-i,ch-i))) = (9(60),...,9(6 1)) е т, и, следовательно, (А(60, с0),. - , А(&Л_Ь сЛ_і)) Є p. Покажем теперь, что Я Є Ар. Пусть (6(,,...,6 ) Є р, г — 1,...,т. Тогда (9(Ьо) - --.«(&Л-І)) Є те, г = l,...,m, и, следовательно, (g(6j,)(0),..., 7( _г)(0)) Є ig, і = 1,...,т.
Равномерные порождающие системы в классах типа Qj при h,^ 2
В этом параграфе мы построим порождающие системы в классах типа C/j из Р для произвольных к 3 и h, таких, что 2 h к. В дальнейшем мы докажем равномерность этих порождающих систем. Пусть р С Е% — отношение типа С , к 3, 2 : h к, Z — центр этого отношения. Без ограничения общности будем считать, что 0 Z, 1 ф Z. По определению центрального отношения любой набор содержащий 0 или имеющий хотя бы два одинаковых элемента принадлежит отношению р. Утверждение 4.2.1. Пусть f(x) — функция из Ар, а Є Е%, Тогда функция д(х) принадлежит Ар. Доказательство. Пусть (а],..., а1}) Є р, j — 1,..., п, 6? — (а\,..., агп), і = 1,..., h, д(аг) = (Зг, г — 1,..., h. Покажем, что (/З1,..., fih) Є р. Если для какого-нибудь і выпол нено равенство аг — а, то /Зг — 0 и, следовательно, (/З1,... ,/3h) Є р. Если все наборы а1, г — l,...,/i, отличны от набора а, то (Зг = /( 5г), і = 1,...,h, и, следовательно, (/З1,..., (5к) р, поскольку f Є Ар. ш Будем говорить, что набор (а ,..., ап_і) является перестановкой набора (bo, ,bn-\), если существует такая перестановка s(x) на Еп, что (a0,...,a„_i) = (6s(o),---, (n-i))- Для каждого набора о - (au...,ah) /э положим Ms, = Z U {«і,..., ад}. Утверждение 4.2.2. Пусть у — (71, , 7/») р. Тогда JP .M Q Д - Доказательство. Пусть функция f(x) принадлежит Рк,Му- Покажем, что / Є Ар. Пусть {а ,..., а) е р, j = 1, , п, f(a\,..., агп) = (3\ і = 1,..., h. Нам нужно доказать, что (/З1,. ..,fih) Є p. Из того, что / Є Рк,Мі следует, что (З1,... ,(3h Є My. Если хотя бы одно из чисел /З1,..., (5h принадлежит Z, то набор (/91,..., (3h) принадлежит р. Если ни одно из чисел /З1,..., 0h не принадлежит Z, то все они принадлежат множеству {71, -.. ,7л}- В таком случае, поскольку h 2, набор (/З1,... , f3h) либо содержит хотя бы два одинаковых элемента, и, следовательно, (/З1,..., /3Л) G Q Л либо является перестановкой набора 7, и, следовательно тоже принадлежит р. Определим множество функций 21 следующим образом. Положим Отметим, что {0,..., к — 1} С 21», поскольку для любого а = 0,..., к — 1 набор а — (а,..., а) принадлежит отношению р и константа а принадлежит мно- Чй) h жеству функций PJ: м . Из леммы 1.2.1 следует, что (J Рк,м& Q [21 ], поскольку Ль,л/д С [Р .] С [21 ]. В частности, верны следующие свойства множества 21 . Утверждение 4.2.3. Пусть f Є Рк и выполнено одно из условий a) f принимает только значения 0,1; b) f принимает только значения из Z; c) f принимает менее h значений вне Z. Тогда f Є [21 ]. Определим функцию t(x,y) и ф(х,у) следующим образом. Положим Пусть о = (oi,..., ад), b—(bi,..., bh), a,b $. І, a,b Є \/?. Определим функцию su (ж) следующим образом.
Положим Положим = {s&-b\a,b Є Е%\р}. Определим функции иг(х,у), г Є E\\Z. Положим г, если а; = г или у = г; х, если х — у . Z; О в остальных случаях. Положим /7 = {«І г Є Ek\Z}. Определим функции рп{хъ .. .,хп), п 3, следующим образом. Пусть для всякого а Є Ek\Z на наборах у которых хотя бы п — 1 элементов равны а функция / принимает значение о, а на остальных наборах принимает значение 0. Положим т(р) = к — \Z\. Заметим, что т(р) h, поскольку если т(р) h, то любой набор из h элементов либо содержит одинаковые элементы, либо содержит элемент из Z, а р Ф Е . Положим ffl — {/i/i+i,... ,pm(p)}, если m(p) h и 0Я = 0, если m(p) = h. В данном параграфе мы докажем, что Ар = [Щ U U U 21 в остальных случаях. Утверждение 4.2.4. Ж U U U 21 U 6 U {t, ф] С А,. Доказательство. Покажем, что при п h функция цп принадлежит классу Ар. Пусть рп(аг) — (Зг, г = l,...,h, (aj,...,«j) р, j = 1,..., п. Если среди /Зг есть одинаковые или хотя бы одно из /Зг принадлежит Z, то (/З1,..., j3h) Є р. Если же все /Зг не принадлежат Z, то в каждом наборе аг, і = 1,..., h, найдется не более одного элемента отличного от /Зг. Обозначим через г (г) номер элемента из набора аг отличного от /З1 (aLj) ф /Зг), г — 1,..., h, если же все элементы набора о? равны /Зг то положим г (і) равным 1. Тогда рассмотрим множество М = {1,..., n}\{r(l),..., r(h)}. Оно не пусто, поскольку п h. Для всякого j из М верно /Зг — aj, г = 1,...,/г, и, следовательно, Докажем, что С/ С Л . Покажем, что функция щ(х,у) принадлежит Ар. Пусть (a1,..., ah) Є р, (/З1,..., /Зл) Є р, Ui(aj, /З3) = j\ j 1,..., h. Если среди j3 найдутся элементы из Z, то (7і, , lh) Є p. Пусть все у3 не принадлежат Z. Если среди -у3 есть хотя бы два одинаковых, то (71,.. -, "fh) Є і\ С р. Пусть все 7J различны. Если среди 7J нет равных 1, то а3 — (З3 = 7J i j = 1,..., Л., а, тогда (71, . -, 7Л) = (с 1, , ) Є /з. Если среди 7J есть единицы, то их не более одной, так как мы предположили, что все j3 различны. Пусть j30 = 1. Тогда а30 = 1 или /З30 = 1. Пусть, без ограничения общности, а30 = 1. Поскольку все j3, кроме 7J0 отличны от единицы и не принадлежат Z, а3 = у3 для всех j = 1,..., h. В таком случае (j1,..., jh) — (a1,..., ah) Є р. Для остальных щ, і Є Ek\Z, доказательство аналогично. Из утверждения 4.2.2 вытекает, что 21 С Ар. Докажем, что в С Ар. Пусть a, b Є Е \р, а = (а\,..., a/J, b = (bi,...,bh). Заметим, что в этом случае a, b ф L\. Покажем, что функция sh b{x) принадлежит Ар Пусть (a1,... ,ah) Є р, s -b(al) = /Зг, г = 1,..., h. Если среди аг есть отличные от аі,..., ал, то среди /Зг есть 0 и тогда (/З1,..., (3h) Є р. Если среди а1 есть одинаковые, то и среди /Зг есть одинаковые, и, следовательно, (/З1,... ,f3h) Є. Q Р- Если же все аг различны и содержатся среди аь ..., а , то набор (a1,... ,ah) не может содержаться в отношении р, поскольку является перестановкой набора (ai,..., a/() . p. Докажем, что t Є Ар. Пусть t(al,/3l) = j\ і = 1,..., h, (a1,... ,ah) Є p, (/З1,... ,/3h) Є p. Если для какого-нибудь j верно а3 Є Z или /3J ф 1, то j3 — О Є Z, и, следовательно, (71,. ..,7Л) Є р. Если /З1 = = j3h — 1 и al,...,ah . Z, то (71, , 7Л) = (ftli ah) z9- Следовательно, функция t сохраняет отношение р. Покажем, что ф Є Ар. Пусть ф(аг,(Зг) = У, г = l,...,h, {a1,.. .,ah) Є р, (j3l,..., j3h) р. Тогда либо среди у есть хотя бы один элемент из Z, а значит (71,...,7А)Єр,либо/31,...,/0 и (7\...,7Л) = (/3\...,Л) р. Множество всех функций из Ар, которые принимают только значение 0 из Z обозначим через Ар.
Таким образом, Ар — Ар П Pk,{o}uEk\z- Обозначим через Ap h множество функций из Ар, которые принимают ровно h различных значений, не принадлежащих Z, причем каждое из этих значений принимается только на одном наборе. Утверждение 4.2.5. А0/ С [21, U 6 U { }] Доказательство. Пусть f(x) — произвольная функция из A h, аг = (а\,... ,агп), f(al) =/? , г = 1,...,/і, и все значения (Зг различны. Предположим, что (/З1,... ,/3Л) р. Тогда, поскольку / Є Ар, существует такое j, что (aj,...,а ) . р. Положим Заметим, что при 7 = (Ть 7«) е { 5\ , &h] верно равенство /О?) = »{а),...,а)и ,...Фн)Ьз)-Отсюда получаем равенство Поскольку функция /і(ж) принимает только значения 0,1, по утверждению 4.2.3 /і Є [21 ]- Следовательно, / Є [21 U & U { }]. Предположим теперь, что (/31,..., (5h) р. Тогда /(х) принимает значения только из множества Мд = ZU{/?\ .. ./З 1}. Следовательно / Є -Р д/, Я [21 ] С [2Uu6U{i}]. Пусть 0 г т(р). Обозначим через Вгр множество всех функций из Ар, которые принимают ровно г различных значений вне Z. Утверждение 4.2.6. Bhp С [U U А0/1]. Доказательство. Пусть /(х) — произвольная функция из Вр, которая принимает некоторое значение г . Z на наборах а и /3, а ф /3. Тогда /(х) = иг(/і(х), /г(х)), где По утверждению 4.2.1 /і,/г Є Лр. Очевидно, что /ь /2 Є .? Количество наборов, на которых функции /і и /2 принимают значение г, на единицу меньше, чем у функции /. Таким образом, можно уменьшить количество наборов, на которых принимается значение і до одного. Аналогично поступим со всеми значениями исходной функции / вне Z. ш Из утверждений 4.2.6 и 4.2.5 вытекает очевидное следствие. Следствие 4.2.1. Bhp С [U U 21» U 6 U {t}}. Утверждение 4.2.7. Если г h, то ВТр С [{pr} U Вт 1\. Доказательство. Пусть f(x) — произвольная функция из множества Вр значениями которой вне Z являются pi,...,pr, причем все они различны. Построим г функций /j(x), і = 1,..., г. Положим I 0 в остальных случаях. Очевидно, что /(х) = nr(fi(x),..., /г(х)). Каждая из функций /j принимает ровно г — 1 значение вне Z и по утверждению 4.2.1 принадлежит Ар. ш Следствие 4.2.2. Если h r т(р), то Вгр С [Ш U Sj]. Утверждение 4.2.8. А С [ШІU U U 2Ц U U { }]. Доказательство. Пусть /(х) — произвольная функция из множества Л , принимающая г различных значений вне Z. Возможны три случая. 1) Пусть г h. Тогда / є [21 ] по утверждению 4.2.3. 2) Пусть г = Л. Тогда / Є [t/ U 21, U & U {t}] по следствию 4.2.1. 3) Пусть г h. Тогда по следствию 4.2.2 и следствию 4.2.1 получаем, что Утверждение 4.2.9. Ар = [Ш U U U 21 U 6 U {t, ф}]. Доказательство. Из утверждения 4.2.4 получаем [9ЭТ U U U 21 U & U {t, -0}] С Лр. Покажем, что Лр С [9# U У U 21 U в U {і, }]- Пусть /(ж) — произвольная функция из Лр. Положим v у О, в остальных случаях. / Q, Легко видеть, что f(x) = ф(/і(х),/2(х)). По утверждению 4.2.3, поскольку fi прини мает только значения из Z, /і Є [21 ]. По утверждению 4.2.1 функций /2 принадлежит классу Ар. Следовательно, по утверждению 4.2.8 /2 Є [97tU U U 21 U в U {і}].
Равномерность порождающих систем в классах типа Сг
Пусть р С Ек, к 3, р Є CQ, Z — центр отношения р. Положим г = к — \Z\. По определению Z -ф Ек, следовательно, г 1. Если г = 1, то из определения центрального отношения получаем, что р = Ек . С. Поэтому г 2. Пусть Z = {ai,. .. ,ак_г}, Ek\Z = {61,..., 6Г}, и выполнены следующие условия. Предположим, что существуют такие і и j, что 1 і J г и ( ,) Є р. Тогда существуют такие попарно различные і\,І2,із, 1 ъ 2) з т, что (6 ,6 2) р, (ЬІ2,ЬІ3) Є р. Если это не так, то легко показать, что р = Ек, но это невозможно, поскольку р — центральное отношение. Без ограничения общности будем считать, что i\ = 1, = 2,гз = 3. Таким образом, мы считаем, что всегда верно соотношение (61,62) - Р- Определим число q следующим образом. Рассмотрим два случая. 1. Если для всех і я j, таких, что 1 і j . г набор (bi,bj) не принадлежит отношению р, то положим q = к — г + 2. Таким образом, в этом случае {ai,..., afc_r, bub2} = Ея, (6Ь b2) І p. 2. Если существуют такие і и _; , что 1 г j г и (Ьг,Ь}) 6 /), то положим q — к—г+3. Таким образом, в этом случае {ab ..., afc_r, 61,62,} = ) (61,62) Р, кроме того, (62, 6з) Є Р- Заметим, что Z С 9, 3 g А;. Пусть г — такое бинарное отношение на Eq, что (а, 6) є г тогда и только тогда, когда (а, 6) Є р и а, 6 Є -Eg. Заметим, что если функция f(x) принадлежит классу Ар и на наборах их множества Eg принимает значения из Eq, то функция / (являющаяся ее ограничением на Eq) принадлежит классу Ат. Доказательство. Из того, что (bi, 62) - P следует, что (6І5 йг) т, а значит т ф Е2 Если для всех і и j таких, что 1 і j г пара (Ьг, bj) не принадлежит отношению р, то очевидно, что Z является центром т, и по определению т Є С 2 В противном случае по определению (62,) Є р, и, следовательно, ()) Є т. Если при этом (Ьі,Ьз) Є г, то Z U (} является центром г и г 6 С 2- Если же (Ьъ 63) . т, то Z является центром Рассмотрим множество М — {(i,j) Є {1,..., г}2 \ г j]. Положим $ = \М\. Легко видеть, что множество М не пусто, поэтому s 1. Пронумеруем пары из множества М числами от 1 до s. Пару с номером п обозначим через (in,jn). Определим прямоугольную матрицу Е состоящую из г строк и s столбцов (см. таблицу 4.2), элементами которой являются ст" Є {йі, bi, 62, Ьз} п = 1,..., s, і = 1,..., г. Для каждого п = 1,..., s положим а" — аь для всех t, таких, что 1 t г, t ф in, t ф jn; если [bin,bjn) р, то положим о 2п = 6i, о? = 62, если {bin,bJn) Є р, то положим оп = Ь2, с = Ьз-Определим функцию rj{xi,... ,xs) из Pk следующим образом.
На к наборах определим таблицей 4.3. На остальных наборах положим г/ равной а\. Определим функции щ{х),... ,r)s(x) из Рк таблицей 4.4. Из определений вытекают следующие очевидные свойства функций ту, 1. Функции 771,--., принимают только значения из множества Eq, причем каждая из этих функций либо не принимает значения Ь\, либо не принимает зна чения &з- 2. Верно равенство 77(7/1 (ж),..., ws(x)) — х. Утверждение 4.3.18. п, 771,..., rjs є Ар. Доказательство. Предположим, что ц Ар Тогда существуют такие наборы (a},...,aj),(a?,. ..,a2) Esk, что (a,1, a?) Є p, і = 1,..., s, rj(a\,...,al) = P1, 77(02,..., a2) = /?2 и (/3і, /З2) p. Из определения отношения р следует, что существуют такие i,j, 1 і г, 1 j г, что (/З1, 2) = (Ьг,Ь3). Тогда из определения функции Докажем теперь, что для всякого t = 1,..., s, функция T]t принадлежит Ар. Если (blt,bn) є р, то функция rjt по определению принимает только значения из множества ZU {b2,63}, и, следовательно, принадлежит классу Ар. Пусть {bit,bjt) ф р. Предполо жим, что r/t . Ар. Тогда существуют такие а1,»2 Є Ек, что (а:1,а2) Є р, (о;1) = /З1, i]t{a2) = ft2, (/З1, /З2) ф р. Из определения отношения р следует, что существуют такие i,j, l i .r,l j r, что (/З1, ft2) — (bi,bj). Для определенности будем считать, что і j. В таком случае і — 1, j — 2, поскольку функция щ принимает значения только из множества ZL){bi,b2, 63}- По определению, функция rjt(x) принимает значения 6Х и Ь2 на элементах bit и соответственно, при этом (bit,bJt) р. Значит (ct1, a2) = {bit,bjt) $_ р. Это противоречит нашему предположению. Следовательно, r)t Є Ар. ш Для каждой функции f(x) из Лр рассмотрим s функций gi(x) = rji{f(x)), ..., gs(x) = %(/(х)). Каждая из этих функций принимает значения только из множества Eq. Используя функции 7i,..., 7« мы можем восстановить исходную функцию /, поскольку в силу свойства 2 функций 77,771,..., верно равенство f(x) — r/(gi(x),... ,gs(x)). Определим функции hi,...,hs, зависящие от переменных х\,..., х\,..., xln,..., xsn, следующим образом. В каждую из полученных функций дг подставим вместо переменной Xj функцию Г7(аг],... ,х ). Проделывая эту операцию для всех переменных хг,... ,хп, получаем функции Ограничивая множество возможных значений переменных ж до Ед, каждую из функций h\,...,ha мы можем рассматривать как функцию из Pq, поскольку она принимает только значения из Eq. Легко видеть, что по функциям hi,..., hs также можно восстановить исходную функцию /, поскольку верны равенства Таким образом, мы можем вместо одной функции / рассматривать s функций h\,...,hs, которые зависят от большего числа переменных. Мы воспользуемся этим фактом для доказательства равномерности систем функций из Рк, рассматривая вместо исходной формулы s-формулу (определения s-функций и s-формул были введены в главе 1). При этом значность логики станет равной q, q к. Напомним, что через x.i МЫ обозначаем набор переменных (x\,xf,... ,х\), а через х набор переменных (х\,... ,хп) = (х\,х\,... ,х\,х\,х\,... ,х%, .. ,х\,х\,... ,xsn). Для каждой функции f(x) из класса Ар определим функции fi(x) из Рк, г 1,..., s, следующим образом. Положим Заметим, что функции f%{x) принимают только значения из Eq. Напомним, что через /, , і — 1,..., s, мы обозначаем ограничения этих функций на Eq (таким образом, fA„ Є Рп). Для каждой функции f(x) из класса Ар определим s-функции f(x) из Vks и /j (х) из V соответствующие функции / следующим образом. Положим / = (/i,.-.,/s), f\E = (h\E , , fs\E ) Обозначим набор Утверждение 4.3.19.
Пусть f(x) — произвольная функция из Ар, f(x) — (fi(x),... ,fs(x)) — s-функция из Vks соответствующая функции f. Тогда верно равенство f(x) = r]{fi(H(x)),... Доказательство. Используя свойство 2 функций г], щ,..., T)S получаем следующие равенства Следствие 4.3.12. Пусть f{x) — произвольная функция из Ар, f(x) = {fi(x),..., fs(x)) — соответствующая функция из Vks. Пусть g\(х),..., gs(x) — такие функции из Pk, что дЛ (х) = /цЕ (х), для всех г = 1,...,3. Тогда верно равенство f(x) = rj(gi(H(x)),..., gs{H(x))). Доказательство. Поскольку функции щ,.-.,г]8 принимают значения только из Eq, верны равенства gi(H(x)) — /г(Н(х)), г — \,...,s. Поэтому требуемое равен ство вытекает из равенства f(x) = 77(/1 (#()),..., fs(H(x))), полученного в утвер ждении 4.3.19. Пусть 21 — произвольная конечная система функций из Pk, такая, что [31] = Ар. В соответствии с построениями проведенными выше каждой функции f(x) из 21 соответствуют s-функции f(x) из Vk и /\ЕЧ{Х) из Vqs. Положим Bk = {f(x) I f(x) Є 21}, Q39 = {f\E (x) I f(x) Є 21}. Таким образом, 93fc С Vk, 939 С Vq. Кроме того, множества 25fc и Q59 конечны. Напомним, что через K(Q3fc) мы обозначаем множество функций из Рк, определенное следующим образом: К( Вк) = {/І (/і, ,/.,) Є fc, і = 1,..., s}. Аналогично через /sT( 89) мы обозначаем множество функций из Pq, определенное следующим образом: К ) = {}І\Е (/І ,... ,/яЕ ) Є Bg, і = 1,...,5}. Таким образом, А («8Л) = {гіг(І{г](х\),г](х7),...,г](хп)))\} Є 21, і = 1,..., Утверждение 4.3.20. К(ЪЧ) С Ат. Доказательство. Функции из множества К{Ч$ь) принадлежат классу Ар, посколь ку являются суперпозициями функций из Ар (функции ri,ri\,...,r)s принадлежат клас су Ар по утверждению 4.3.18). Функции из множества К(ЪЧ) являются ограничениями функций из K(%$k) на Eq и поэтому принадлежат классу АТ. ш Поскольку каждой функции из 21 мы поставили в соответствие некоторую s-функцию из QSfc и некоторую s-функцию из В9, каждой формуле Ф над 21, реализующей некоторую функцию /, соответствует некоторая s-формула над 03 и некоторая s-формула над Bq (см. определения в главе 1). Эти формулы реализуют некоторые s-функции. В следующем утверждении и его следствии показано, что эти s-функции есть / и цЕ , где / — s-функция из Vfc , соответствующая функции /. Утверждение 4.3.21. Пусть Ф(х) — нетривиальная формула над над 21, реализующая функцию /(х) из Ар, f(x) = (fi(x),..., fs(x)) — s-функция из V, соответствующая функции /. Пусть Ф(х) — s- формула над 23 , соответствующая формуле Ф(х). Тогда s-формула Ф реализует s-функцию /. Доказательство. Будем доказывать утверждение индукцией по глубине формулы Ф(х). Пусть С (Ф) = 1. Тогда формула Ф(х) имеет вид Ф(х) = р(х), где р Є 21.
