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

У нас уже 176407 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

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

Количество страниц	78

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23582.doc

Содержание	Содержание Введение 3 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. Классы типа Ci ... 41 4.2. Равномерные порождающие системы в классах типа Q, при h ^ 2 . . . . 43 4.2.1. Порождающие системы... 43 4.2.2. Равномерность подсистем... 47 4.2.3. Существование равномерных порождающих систем... 52 4.3. Классы типа Q ... 58 4.3.1. Классы типа Q и С^. Т-максимальные функции... 58 4.3.2. Равномерность порождающих систем в классах типа Сг... 68 5. Доказательство основных теорем 76 Литература 78 Введение Данная работа относится к математической теории синтеза управляющих систем. В ней рассматривается задача о реализации формулами функций из предполных классов fc-значной логики. Одной из основных задач математической кибернетики является построение и изучение модельных классов управляющих систем с точки зрения сложности. Класс формул, реализующих функции fc-значной логики, к ^ 2, является одним из основных модельных классов управляющих систем. В качестве наиболее естественных мер сложности формул выступают число переменных, входящих в формулу, и глубина. Число переменных, называемое также сложностью формулы, характеризует "стоимость", а глубина время работы, при условии что различные вычисления можно производить параллельно. Для каждой функции требуется построить такую формулу, которая реализует эту функцию, и является наилучшей относительно выбранной меры сложности. Имеется простой метод для нахождения таких оптимальных формул, основанный на переборе всех формул данной сложности. Однако этот метод практически не применим, поскольку требует для своей реализации большого числа шагов. Поэтому возникает задача о разработке таких методов синтеза, которые позволяют строить для всех функций из заданного множества относительно хорошие формулы, и при этом существенно проще перебора всех формул. Для множества всех булевых функций асимптотически оптимальные методы синтеза формул в полных базисах (а также ряда других важных классов управляющих систем) были разработаны О. Б. Лупановым [7-13] (см. также [6, 45]). Оценки глубины формул в полных базисах были получены в работах [4, 5] (см. также [18]). Из результатов О. Б. Лупанова, в частности, следует, что большинство функций алгебры логики допускает лишь очень сложную реализацию. Поэтому, с одной стороны, представляет интерес выделение классов функций, допускающих более простую реализацию, и разработка методов синтеза оптимальных формул для функций из этих классов. С другой стороны, представляется важным для различных естественных классификаций функций /с-значной логики иметь оценки глубины и сложности формул, реализующих функции из соответствующих классов. Одной из наиболее известных и лучше всего изученных с функциональной точки зрения классификаций булевых функций является описание Э. Поста [40, 41] множества всех замкнутых относительно операции суперпозиции классов функций (см. также [14, 16, 22, 27, 37]). Обзор результатов, полученных для формул над конечными системами, реализующих функции из классов Поста содержится в [23]. При к ^ 3 к настоящему времени изучены только некоторые семейства замкнутых классов в Р^, в частности, предполные классы функций, все семейства которых описаны в работах И. Розенберга [46, 47] (см. также [2, 15, 26, 29]). Таким образом, возникает задача о реализации функций из замкнутых классов /г-значной логики формулами над конечными системами, имеющими наименьшую сложность или глубину. При этом при реализации функций из некоторого замкнутого класса ft-значной логики представляется естественным рассматривать формулы в базисах состоящих из функций принадлежащих этому же классу. Как правило, при разработке вычислительных устройств возникает необходимость минимизировать сложности формул одновременно по нескольким параметрам, например, по числу элементов и времени работы. Поэтому представляет интерес получение соотношений между глубиной и сложностью формул, реализующих заданные функции. Конечную систему функций 21 из Р^, к ^ 2, будем называть равномерной, если существуют такие константы end, зависящие только от системы 21, что для всех функций / из [21] выполнено неравенство Aa(/)^clog2La(/) + d, (1) где La(/) и Аа(/) — соответственно минимальные сложность и глубина, с которыми можно реализовать функцию / формулами над системой 21. Все необходимые определения приведены в главе 1. В. М. Храпченко показал (см. [28]), что любая полная в Р% конечная система функций равномерна. Аналогичный результат был получен Ф. Спирой [48], (см. также [42]). Похожую задачу о времени вычисления арифметических выражений с использованием нескольких процессоров рассматривали Р. Брент, Д. Кук и К. Маруяма [32] и Р. Брент [33, 34], применившие метод преобразования формул для арифметических выражений аналогичный предложенному В. М. Храпченко и Ф. Спирой. Поскольку нижняя оценка для Да(/) аналогичная (1) (с другими константами) получается тривиально, оценка (1) является наилучшей по порядку. Задача о получении оценок для константы с в соотношении (1) для различных полных систем булевых функций рассматривалась в работах [24, 25, 35, 39, 43, 49]. Использованный в работах [28, 48] метод позволяет по произвольной формуле построить эквивалентную ей формулу логарифмической глубины от сложности исходной формулы. При этом сложность формулы увеличивается. Путем модификации метода преобразования формул в некоторых случаях можно добиться чтобы увеличение сложности было незначительным (см. [31, 36]). Отметим, что методы преобразования формул, приведенные в работах [28, 48] легко переносятся на случай полных систем функций /r-значной логики при к ^ 3. Однако они существенно используют полноту систем. Для полных монотонных систем булевых функций равномерность была доказана И. Вегенером [51] (см. также [52]). Равномерность произвольных конечных систем булевых функций была доказана А. Б. Угольниковым [20, 21], им также приведены примеры неравномерных систем функций в Pf. при к ^ 3 (см. также [44]). Поскольку, как уже было отмечено выше, методы приведенные в работах [28, 48] позволяют устанавливать равномерность полных систем функций в Р при любом к ^ 3, возникает вопрос о равномерности неполных систем функций в Р. Л. И. Ахметовой [1] был анонсирован результат о том, что любая конечная система функций в Р3, порождающая предполный класс, является равномерной. В данной работе изучается равномерность конечных порождающих систем для предполных классов fc-значной логики. Пусть к ^ 2. Множество {0,1,..., к — 1} будем обозначать через ?. Класс функций, сохраняющих отношение р, будем обозначать через Ар (определения см. в главе 1). Будем пользоваться обозначениями из [29], согласно которым в Р^ имеются следующие семейства предполных классов: 1) классы самодвойственных функций — классы типа Р; 2) классы линейных функций — классы типа L; 3) классы функций, сохраняющих разбиения множества Ek, — классы типа Е; 4) классы функций, сохраняющих сильно гомоморфные прообразы Д-адических элементарных отношений, — классы типа В; 5) классы монотонных функций — классы типа О; 6) классы функций, сохраняющих центральные отношения, — классы типа С. Если р — отношение частичного порядка на ?, такое, что для любых двух элементов а и b из Ek существуют sup (а, 6) и inf(a, Ь) относительно частичного порядка р, то будем говорить, что Ар — класс типа О. Если т — бинарное центральное отношение, то будем называть Ат классом типа С^- Если а — унарное центральное отношение (то есть унарное отношение, отличное от ?* и 0), то будем называть Аа классом типа Q. Положим р* = Е1\{{1, 2,3), (2,1,3), (2, 3,1), (3,2,1), (3,1, 2), (1,3,2)}. В настоящей работе получены следующие основные результаты. Теорема 1. Пусть 21 — произвольная конечная система функций из Pk, к ^ 3, такая, что [21] является предполным классом одного из следующих типов: L, Р, Е, В, О, Q, Сг • Тогда система % равномерна. Следствие 1 (см. также [1]). ПусгпъШ произвольная конечная система функций из Рз, такая, что [21] — предполный класс в Р$. Тогда система 21 равномерна. Следствие 2. Пусть 2С — произвольная конечная систслш функций из Р4, такая, что [21] — предполный класс в Р$, не являющийся двойственным классу Ар. Тогда система 21 равномерна. Теорема 2. Пусть 21 -- произвольная конечная система функций из Р^, 3 ^ k ^ 7, такая, что [21] является предполным классом типа О. Тогда система 21 равномерна. Как известно, при к = 8 в Рк существуют предполные классы монотонных функций, не имеющие конечных порождающих систем (см. [50]). Кроме того, в настоящее время отсутствует полное описание всех предполных классов монотонных функций для к ^ 8, имеющих конечные порождающие системы, что затрудняет получение существенного усиления теоремы 2 (то есть доказательство аналогичного утверждения для всех предполных классов монотонных функций, имеющих конечные порождающие системы для произвольных к). Теорема 3. Пусть А — замкнутый класс в Рк, к ^ 3, являющийся предполным классом типа С. Тогда существует такая равномерная система 21, что А — [21]. Теорема 4. Пусть Ар — произвольный предполный класс в Р^, 2 ^ k ^ 7. Тогда существует такая равномерная система 21, что Ар = [21]. Доказательство теорем 1, 3, 4, использующее результаты, полученные в главах 1-4, приведено в главе 5. Теорема 2 доказывается в главе 3. Для доказательства теорем 1, 4 мы последовательно рассматриваем все семейства предполных классов в Pf~. Формулы будем называть эквивалентными если они реализуют равные (с точностью до добавления и удаления несущественных переменных) функции. При преобразовании формул над одной системой функций в эквивалентные формулы над другой системой функций глубина формул изменяется линейно. Для сложности же это вообще говоря не так (это следует, например, из результатов [17]). Однако, если 21 и 03 две конечные системы функций из Р^, [21] = [8] и система 21 равномерна, то любая формула над 21 может быть преобразована в эквивалентную формулу над 93 с не более чем полиномиальным увеличением сложности Поскольку в Рг любая конечная система равномерна, любые конечные системы, порождающие один и тот же класс булевых функций, полиномиально эквивалентны (см. [19, 21]). Из результатов данной работы, в частности, следует полиномиальная эквивалентность порождающих систем для некоторых семейств предполных классов. Кроме того, для большего числа предполных классов установлено, что для каждого из них существует порождающая система функций 21, такая, что сложность функций в любой другой конечной системе, порождающей этот класс, ограничена полиномом от сложности функций в системе 21 (см. главу 5). Опишем кратко содержание работы. В главе 1 приводятся основные определения и утверждения необходимые для доказательства равномерности различных систем функций. Приводится несколько обобщений метода использованного в [42, 48] для доказательства равномерности полных систем функций в Р?. (леммы 1.3.3, 1.3.4, 1.3.5). Вводится понятие 5-формул и доказывается обобщение этого метода для них (лемма 1.3.7). Кроме того, вводится понятие равномерности одной системы функций в другой системе, благодаря которому упрощается изложение доказательства равномерности в некоторых случаях (леммы 1.2.2, 1.3.6), путем сведения задачи к доказательству равномерности подсистемы функций в исходной системе. Одним из основных методов доказательства равномерности системы функций является использование разложения по переменной. Именно этот подход использовался в работах [28, 48]. Суть метода состоит в следующем. Произвольная формула Ф над рассматриваемой системой функций разбивается на две части и представляется в виде Ф(х) — В(А(х),х), где ЛиВ- формулы (являющиеся частями исходной формулы), причем они выбираются таким образом, чтобы сложность формулы Ф не превосходила сложности каждой из них более чем в т раз, где т — некоторая константа. Далее находится такая функция <р(у,хо,... ,Хк-\), что формула В(А(х),х) эквивалентна формуле ip(A(x), В(0, х),..., В (к — 1, х)). Глубина последней формулы меньше глубины исходной формулы Ф, если сложность формулы Ф достаточно велика. Аналогичная процедура применяется к формулам А(х), В(0, ?),..., В(к — 1,х), сложность которых меньше сложности исходной формулы. В итоге, при многократном применении этой процедуры, строится формула над системой { и константы принадлежат рассматриваемому классу функций, то есть выражаются через функции исходной системы, отсюда следует, что эта система функций равномерна (см. лемму 1.3.5). Следует отметить, что в некоторых случаях для разложения можно использовать различные функции в зависимости от свойств формул Л и В, на которые разбивается исходная формула. В случае, когда число необходимых для разложения функций конечно, обобщая описанный выше метод можно доказать, что исходная система функций равномерна (см. лемму 1.3.4). В главе 2 рассматриваются семейства классов линейных и самодвойственных функций, для которых равномерность порождающих систем доказывается без использования разложения по переменной или специальных преобразований формул. В обоих случаях доказательство равномерности основано на свойствах функций из рассматриваемого класса. В параграфе 2.1 доказывается равномерность порождающих систем для классов линейных функций. Равномерность следует из ассоциативности операции сложения. Любая линейная функция от п переменных может быть представлена как сумма п одноместных линейных функций и константы. Поэтому, в силу ассоциативности сложения сумма п переменных реализуется формулой, глубина которой по порядку равна log п. В параграфе 2.2 приведено доказательство равномерности порождающих систем в классах самодвойственных функций, которое сводится к доказательству равномерности полных систем функций в Рк. Применяется обобщение метода, использованного в [21] для доказательства равномерности порождающих систем класса самодвойственных функций в Р2- Равномерность произвольной порождающей системы для класса %к{$) функций, самодвойственных относительно некоторой подстановки 5, доказыва- ется следующим образом. Сначала к системе функций добавляется константа. Над новой системой, которая уже является полной, и, следовательно равномерной, строится формула нужной глубины. В случае, когда подстановка s имеет только один цикл, константа заменяется на переменную, которая оказывается несущественной и мы получаем формулу нужной глубины над исходной системой функций. В случае, когда подстановка имеет несколько циклов применяется обобщение описанного метода. Если константу в формуле заменить на любую другую константу из того же цикла подстановки s, то мы получим эквивалентную формулу. Выбрав по одной константе из каждого цикла подстановки и построив приведенным выше способом (при помощи замены константы на переменную) формулы, мы получим, что каждая из них имеет необходимое значение в случае, если новая переменная принимает значение из соответствующего цикла подстановки. Из полученных формул строится формула для исходной функции у которой новая переменная оказывается несущественной. В главе 3 рассматриваются случаи, в которых применимы методы связанные с разложением по переменной (то есть леммы 1.3.5 и 1.3.4). Доказывается равномерность конечных порождающих систем для классов функций сохраняющих разбиения, классов типа В, классов монотонных функций при к ^ 7 и классов типа О. В параграфе 3.1 для классов функций, сохраняющих разбиения, устанавливается, что каждую функцию f(y,x) из рассматриваемого класса можно представить в виде f(y, х) = <р(у, /(0, х),..., }{к — 1, ?)), где ср -— некоторая функция из класса, которая одинакова для всех функций /. Для классов типа В в параграфе 3.2 показывается, что верно аналогичное представление, но выбор функции <р зависит от исходной функции /, хотя число различных функций ip которые необходимы для разложения произвольных функции из рассматриваемого класса ограничено. В параграфе 3.3 для классов монотонных функций строится аналогичное представление, для которого используется единственная функция if. Основная проблема состоит в построении этой функции и проверке того, что она является монотонной. Для классов типа О* функция указывается в явном виде. Все оставшиеся случаи для классов монотонных функций в Pk при к ^ 7 сводятся к построению функции ср для одного фиксированного класса в Pq, для которого приводится алгоритм построения функции ip. Соответствующие функции для остальных классов получаются из последней, при помощи приведенных в работе монотонных отображений. Таким образом, предлагается способ, при помощи которого вопрос о существовании разложения по переменной в одном классе функций можно свести к аналогичному вопросу в другом классе функций логики меньшей значности. Глава 4 посвящена классам типа С, для которых, вообще говоря, не удается применить использованные ранее методы доказательства равномерности. Исключение составляют классы типа Q, которые рассматриваются в параграфе 4.1. Доказательство равномерности порождающих систем для классов типа Q в Pk сводится к доказательству равномерности полных в Рт систем функций (для 2 ^ г ^ к) при помощи метода моделирования констант (предложенного в [21]). Сначала к системе функций добавляется константа. Над расширенной таким образом системой функций, которая уже является равномерной, строится формула нужной глубины. Затем все вхождения константы заменяются некоторой формулой над исходной системой функций, реализующую близкую к константе функцию. В итоге получается формула, реализующая функцию, которая совпадает с исходной, когда значением формулы "моделирующей" константу является эта константа. На остальных наборах значение построенной формулы корректируется при помощи дополнительных преобразований. В параграфе 4.2 доказывается существование равномерных порождающих систем в произвольных классах типа Сд при h ^ 2 для любых возможных значений к. Для формул определенного вида удается построить метод преобразования, позволяющий доказывать равномерность системы. Сначала для каждого из классов строятся порождающие системы специального вида. Затем для каждой этих из порождающих систем рассматривается некоторое ее подмножество и доказывается его равномерность во всей порождающей системе (то есть для каждой формулы над этим подмножеством строится эквивалентная формула над всей системой функций, такая, что глубина этой формулы по порядку не превосходит логарифма сложности исходной формулы). При доказательстве существенным образом используются свойства функций рассматриваемого подмножества порождающей системы, благодаря которым произвольную формулу над ним можно преобразовать в эквивалентную таким образом, что выделенная переменная, входящая в исходную формулу, окажется в новой формуле на глубине, ограниченной некоторой константой, а глубина всей формулы не увеличится. Для доказательства равномерности применяется лемма 1.3.3. Поэтапно добавляя к выбранному подмножеству функции исходной порождающей системы и доказывая равномерность получающихся подмножеств в исходной системе функций, доказывается ее равномерность. В параграфе 4.3 доказывается равномерность произвольных порождающих систем для классов типа Q при любых возможных значениях к. Сначала рассматриваются классы типа Q специального вида (классы типа Q и классы типа Q). Для этих классов доказывается аналог разложения по переменной, который применим только к функциям определенного вида (не принимающим некоторых значений), но при этом разложение осуществляется сразу по нескольким переменным (утверждение 4.3.16). Используя полученное разложение, доказывается равномерность произвольных порождающих систем в классах типа С^. Для этого для каждой функции из рассматриваемой порождающей системы класса типа Сг строится несколько функций из классов типа С^ или О\|, по которым легко восстанавливается исходная функция, при этом значность логики для новых функций может уменьшиться. Используя построенные функции, формула над исходной системой преобразуется в несколько формул большей сложности над системой новых функций из классов типа Q или Qi. Построенные таким образом формулы реализуют функции, при помощи которых можно восстановить значения функции реализуемой исходной формулой. Несмотря на большую сложность, полученные формулы имеют структуру в некотором смысле похожую на структуру исходной формулы. В совокупности все они образуют так называемую s-формулу (определение см. в главе 1). Благодаря полученному ранее разложению (утверждение 4.3.16), к этой s-формуле можно применить лемму 1.3.7 и, таким образом, получить эквивалентную 5-формулу нужной глубины. Последняя s-формула преобразуется в обыкновенную формулу требуемой глубины над исходной системой функций, которая эквивалентна исходной формуле. В главе 5 приводятся доказательства теорем, содержащих основные результаты работы. Утверждения нумеруются тройками чисел, где первое число номер главы, второе — номер параграфа, третье — номер утверждения внутри параграфа. Леммы, теоремы и следствия (кроме основных теорем и следствий, приведенных во введении) нумеруются аналогичным образом. Так, например, лемма 1.3.2. — это вторая по счету лемма, расположенная в третьем параграфе первой главы. Рисунки и таблицы нумеруются парами чисел, где первое число — номер главы, второе — номер рисунка или таблицы внутри главы. Конец доказательства отмечается символом ¦. Основные результаты диссертации опубликованы в работах [53-57]. Глава 1. Основные определения и вспомогательные утверждения 1.1. Основные определения и обозначения Пусть к ^ 1. Через Ек будем обозначать множество {0,1,... ,к — 1}. Через Ап будем обозначать n-ую декартову степень произвольного множества А. Через \А\ будем обозначать количество элементов произвольного конечного множества А. Пусть к $; 2. Функции f(xx,...,xn), п > 1, аргументы которых определены на Ек, такие, что /(«1,..., ап) G Ek, при ct\,... ,ап Е Ек, будем называть функциями к-значной логики. Множество всех функций fc-значной логики обозначим через Р. Аналогично будем обозначать через Р\ множество функций f(xi,... ,хп), п ^ 1, аргументы которых определены на Ei, таких, что /(cti,..., ап) 6 Е\, при ot\,...,an € Ех. Функции от п переменных будем называть п-местными функциями. Константы мы будем считать одноместными функциями. Пусть 21 — произвольное множество функций из Р^, п^1. Через 21'") будем обозначать множество всех функций из множества 21, которые зависят от п или меньшего числа переменных. Пусть 21 — произвольное конечное множество функций из Р^. Через m(2l) будем обозначать максимальное количество переменных у функций из 21. Пусть Q — непустое подмножество Е^. Множество всех функций из Pfc, принимающих значения только из множества Q, будем обозначать через Pk,Q- Функции fc-значной логики /(х^,... ,xin) и д(х^,.. .,Xim) будем называть равными и писать f(xiv,..., xln) = д{хгг,..., xim), если они получаются друг из друга при помощи добавления и удаления несущественных переменных (подробнее см. [30]). Через х мы будем обозначать набор переменных (хг,... ,хп). Пусть 21 — произвольное множество функций из Рк. Формулой над 21 будем называть 1) любой символ переменой, 2) любую последовательность символов вида /(Фь..., Ф„), где / — символ п-местной функции, принадлежащей множеству 21, а Ф1;..., Фп — формулы над 21. Тривиальными формулами будем называть формулы состоящие из символов переменных. Нетривиальными формулами будем называть все остальные формулы. Заметим, что в отличие от [30] мы считаем символы переменных формулами. Формулам в определении [30] у нас соответствуют нетривиальные формулы. Подформулой тривиальной формулы является она сама. Подформулами нетривиальной формулы /(Фь ..., Ф„), где / — символ «-местной функции, принадлежащей множеству 21, а ФЬ...,Ф„ — формулы над 21, являются она сама, формулы Ф],..., Ф„ и все подформулы этих формул. Каждой формуле естественным образом сопоставляется функция, которую она реализует (подробнее см. [30]). Будем называть формулы Ф и Ф эквивалентными и писать Ф ~ Ф, если они реализуют равные функции. Будем называть формулы Ф и Ф равными и писать Ф = Ф, если они совпадают, как последовательности символов. Пусть 21 произвольная система функций из Рк- Через [21] обозначим замыкание системы 21 относительно операции суперпозиции, то есть множество всех функций равных функциям, которые реализуются нетривиальными формулами над 21. Множество функций А С Рк называется замкнутым классом, если [А] — А. Замкнутый класс функций А называется предполным классом в Р^, если А ф Р^, и для любой функции / ? Pk\A выполняется равенство [Ли{/\|] = Рк. Бесповторными суперпозициями функций из системы 21 будем называть функции, реализуемые такими формулами над 21, в которые каждая переменная входит не более одного раза. Пусть Ф — некоторая формула, в которую входят символы переменных хг,..., хп и только они. Тогда формулу Ф будем обозначать также через Ф(жь ..., хп), при этом каждая переменная может входить в формулу несколько раз. Пусть Ф — некоторая формула, 1 ^ i ^ п. Тогда через Ф(:Г1,...,хг_ьФ,х^+1,... ,хп) будем обозначать формулу, получающуюся в результатае подстановки формулы Ф вместо каждого вхождения переменной xt в формулу Ф. В некоторых случаях для удобства обозначений мы будем считать, что в формулу Ф(х) могут не входить какие-то из переменных х\,..., хп. Например, если А(х^,..., Xjr), В(у, х?1,..., xim) — произвольные формулы над 21, {ji,... ,jr} U {i\,..., im} = {1,..., n}, а формула Ф имеет вид Ф(:Г1,..., хп) = B(A(xj1,..., xJt), хг1,..., #!„,), то будем использовать для формул А и В обозначения А(х) и В(у,х) соответственно. Через Ф(й), где а е Е%, будем обозначать значение функции, реализуемой формулой Ф, на наборе а. Будем говорить, что формула Ф(х) не принимает некоторого значения 0 6 Ек, если для всех а. € Е? верно неравенство Ф(й) ф /3. Пусть 21 — произвольная конечная система функций из Р., Ф — некоторая формула над 21. Обозначим через Ь(Ф) число символов переменных, входящих в Ф. Будем называть -ЦФ) сложностью формулы Ф. Глубину .О(Ф) формулы Ф определим рскуррент-но: О(Ф) = 0, если Ф является тривиальной формулой, то есть состоит из одного символа переменной; ?>(Ф) — 1 + тах ?>(Фг), если Ф имеет вид (/?(ФЬ ... ,ФГ), где Фь .. -,ФГ, — формулы над 21, <р G 21. Отметим, что глубина и сложность формул состоящих из констант равны 1, поскольку константы мы считаем одноместными функциями. Пусть / — функция из [21]. Положим L%(f) — гшпЦФ), Аа(/) = гшп.О(Ф), где минимум берется по всем формулам Ф над 21, которые реализуют функцию /. Величину L<^(f) будем называть сложностью функции / в системе 21, а величину D%(f) — глубиной функции / в системе 21. Таким образом, ^а(/) — минимальная сложность с которой можно реализовать функцию / формулами над системой 21, a -Da(/) — минимальная глубина. Пусть 21 — произвольная конечная система функций из Р. Систему 21 будем называть равномерной, если существуют такие константы с и of (зависящие только от системы 21), что для всех функций / из [21] выполнено неравенство Пусть 21 и 93 — произвольные конечные системы функций из Рк, такие, что 25 С 21. Будем говорить, что система 5В равномерна в 21, если существуют такие константы с и d (зависящие только от систем 21 и Ш), что для любой функции / из [05] глубина -^а(/) Функции / в системе 21 и сложность Х«в(/) функции / в системе 23 связаны следующим соотношением Положим log х = log2 х, если х > 1; flogx, log 2 = если х €- 1. Функцию ip(x, у) из Р^ ' будем называть ассоциативной, если для любых a,b,c G Ек верно равенство ср(а, tp(b, с)) = <р((р(а, Ь), с). Пусть ¦< — произвольное отношение частичного порядка на Ек, f{x),g(x) — произвольные функции из Рк. Будем писать / ¦< д, если для любого набора а ? Е% верно неравенство /(а) ^ д(а). Пусть Ф и Ф — некоторые формулы, реализующие функции f(x) и д(х) соответственно. Будем писать Ф -< Ф, если / -< д. Подстановкой на множестве Ек называется взаимно однозначное отображение множества Ek на себя. Пусть s(x) — произвольная подстановка на Ек. Введем следующее обозначение. Положим six) = (s(xi), s(x2),..., s(xn)). Функция fs(x) = s~1(f(s(x))) называется двойственной к функции f{x\,... ,хп) относительно подстановки s. Функция f(x) из Рк называется самодвойственной относительно подстановки s, если fs(x) = f(x). Последнее равенство очевидно эквивалентно равенству f(s(x)) = s(f(x)). Пусть 21 — произвольное множество функций из Рк. Через 21s будем обозначать множество всех функций двойственных к функциям из 21 относительно подстановки s. Легко видеть, что если система 21 является равномерной, то система 21* также является равномерной. Пусть s(x) — произвольная подстановка на Ек, п ^ 1. Определим подстановку sn(x) на Ек следующим образом. Положим sn(x) — s(s(... s(x) •-.)). Пусть R — некоторое непустое подмножество Ек. Говорят, что функция /(х1) = /(.Xi,... ,хп) из Рк сохраняет множество R, если для любых аь ..., ап е R верно соотношение /(ai,..., ап) Е R. Пусть f(x) — функция из Pfc, сохраняющая множество Eg, 2 ^ q ^ к. Рассмотрим такую функцию д(х) из Pq, что для любого набора а € Е™ верно равенство /(а) = д(&)- Будем называть функцию д ограничением функции / на Eq и обозначать через }\Е ¦ Пусть 21 — произвольная система функций из Рк, сохраняющих Eq. Положим 21 Е ={/1^ 1/^21}. Пусть h ^ 1. Любое подмно^кество Е? будем называть h-ариым отношением. Говорят, что функция f(xi,... ,хп) сохраняет h-арное отношение р, если для любых п наборов (а},..., а\),..., «,..., О из отношения р набор (f(a\,..., а^),..., f(a\,..., а%)) также принадлежит отношению р. Через Ар будем обозначать класс функций, сохраняющих отношение р. Легко видеть, что [Ар] — Ар. Пусть s(x) — подстановка на множестве Ек. Рассмотрим отношение s(p) С Ек, такое, что набор (й1,...,й/,) 6 Е% принадлежит отношению s(p) тогда и только тогда, когда набор (s(a\),..., s(a/i)) принадлежит отношению р. Отношение s(p) будем называть двойственным отношению р относительно подстановки s. Нетрудно показать, что As(p) = Asp. Через Lk, h ^ 2, к ^ 2, будем обозначать множество всех наборов из Е%, каждый из которых имеет хотя бы два одинаковых элемента. Положим 4 = 0. Дадим обобщения понятий функций и формул. Пусть s ^ 1. Через xi будем обозначать набор переменных (х},х?,... ,х;-). Такой набор неременных будем называть s-переменной. Через х будем обозначать набор переменных Наборы вида (Д(ж),..., fs(x)), где /ь ..., /s произвольные функции из Рк от ns переменных, п ^ 1, будем называть s-функциями, зависящими от п s-переменных. Множество всех 5-функций будем обозначать через Vks. Также s-функцию (fi{x),..., fs(x)) будем обозначать через f(x). Будем называть /i,...,/s компонентами s-функции f и писать / = (/i).--,/s). Заметим, что при s = 1 s-функции являются обычными функциями А;-значной логики, то есть Vk — Pk. Пусть fug-— некоторые s-функции, / = (/ъ - • ¦, Л), 9 - (9i, ¦ • ¦ 19s)- Будем называть s-функции / и д равными, если для всех г — 1,.. ., s равны функции fi ид. Пусть 21 некоторое подмножество V?. Будем рассматривать формулы составленные из s-функций. А именно, будем называть s-формулами над 21 выражения вида: 1) хг1 где хг - произвольная s-переменная; 2) /(Фь -.., Фп), где / символ произвольной s-функции из множества 21, завися-щей от п s-переменных, аФь ..., Ф„- s-формулы над 21. Тривиальными будем называть s-формулы состоящие только из символов s-переменных. При s = 1 s-формулы являются обычными формулами над 21 С V? = Рк. Значение s-формулы Ф на наборе a G Eks определяется следующим образом. Если Ф является тривиальной и имеет вид хг, то ее значением будет набор оц Е Ef.. Если Ф имеет вид /(Фь..., Ф„), где / — символ произвольной s-функции из 21, зависящей от п s-переменных, Ф\, ..., Фп — s-формулы над 21, и значением s-формулы Ф^ на наборе с? € Е™ является набор /% Е Ef., г — 1,... ,п, то значением формулы Ф будет являть- ся набор /(/?i,. -., Рп) ? Esk. Таким образом, каждая s-формула реализует некоторую s-функцию. Две s-формулы Фи Ф будем называть эквивалентными и писать Ф ~ Ф, если они реализуют равные s-функции. Пусть s ^ 1, 21 — конечная система функций из Рк и каждой функции /(хг,... ,хп) из 21 поставлена в соответствие некоторая s-функция f(x\,..., хп) из конечной системы s-функций Ш, В С Vqs. Тогда каждой формуле Ф над 21 естественным образом ставится в соответствие s-формула Ф над 25. А именно, если формула Ф тривиальна и имеет вид Хг, то ей соответствует s-формула xf, если формула Ф имеет вид /(Фь ..., Фг), где / G 21, Ф1?..., Фг — формулы над 21, то формула Ф будет иметь вид /(Фь ..., Фг), где i,..., Фг — s-формулы над 03, соответствующие формулам Фь ..., Фг. 1.2. Основные свойства систем функций Очевидно, что при преобразовании формул над одной системой функций в эквивалентные формулы над другой системой функций их глубина увеличивается не более чем линейно. Сформулируем это в виде следующего утверждения Утверждение 1.2.1. Пусть 217 8 — конечные системы функций из Р^, 21 С с = тахДв(/). Тогда для любой функции / из [21] верно неравенство D^(f) ^ cD Следующее утверждение является очевидным свойством ассоциативных функций. Утверждение 1.2.2. Пусть функция ip(x,y) из Рк ассоциативна, Тогда для всякой функции f(xi,..., хп) из [{ip}} верно неравенство Следующая лемма является аналогом хорошо известного предстваления функций А;-значной логики (см. [30]). Лемма 1.2.1. Пусть Q — непустое подмножество Ек- Тогда [P^q] = Pk,Q- Доказательство. Без ограничения общности будем считать, что Q = Ег, иначе рассмотрим двойственную систему функций. Если г = 1, то P^q состоит из одной константы 0 и утверждение леммы очевидно. Если г > 1, то рассмотрим функции min(x, у), тах(х,у), где min и max* на El совпадают с обычными min и max, а на остальных наборах равны 0. Кроме того, рассмотрим функции J(.t), а — 0,... ,к — 1, определенные следующим образом. г — 1, если х = а; 0 в остальных случаях. Очевидно, что функции min(x,y), max(x, у), J(x) принадлежат PJ.Q. Для п > 2 положим i,..., xn) = min(xi, min (ж2,..., тщ(ж„_1,х„)...)), Легко видеть, что произвольную функцию f(x) из J\q можно представить в следующем виде f(x) = max min(/(a), Jx (xi),..., Jn(arn)). Следовательно, Рд.^ С [{min, max, Jo,..., J^_v 0,..., г - 1}] С [P^q] С Рл>д. ¦ Лемма 1.2.2. Пусть 2t м Ш — конечные системы функций из Pk, В С Я, 23 равномерна в 21 и 3D С 21^'. Пусть для любой функции ф{х\,... ,хп) из 53, п ^ 1, w любой функции f(x) из [?>р) существуют такие функции gi(x), г = 1,..., п, из и функция h(x\,..., жп) W3 Ш, что Тогда система 03 U 5? равномерна в 21. Доказательство. Назовем формулу Ф над 23 U [?>]^ приведенной, если она тривиальна, либо Ф = g(Xi), где g e [S)]^, либо существуют нетривиальная формула F(xi, ...,хт) над Ш и формулы Gi,...,Gm над [©](1), такие, что Ф = F(Gi,... ,Gm), и при этом D(Gj) ^ 1, г = 1,..., т. Докажем, что для произвольной формулы Ф над BU [S)]^1) существует такая эквивалентная ей приведенная формула Ф над Q3U [Х)]^\ что Ь(Ф) ^ ?(Ф) и ?>(Ф) ^ -^(Ф)-Будем доказывать это утверждение индукцией по глубине формулы Ф. Если ^(Ф) = 0 или D(Q) = 1, то Ф уже является приведенной формулой и утверждение очевидно. Пусть утверждение верно для всех формул, глубина которых не превосходит некоторого N, где N ^ 1. Докажем, что оно верно и для произвольной формулы Ф, такой, что ?>(Ф) = N + 1. Пусть Ф - формула над Ш U [S]W, ?>(Ф) = N + 1. Тогда Ф = f(Au .. .,АГ), где /(#1,... ,хТ) — функция из Ш U [?>p), a Ai, г = 1,...,г, — формулы над <В U [2>Р\ глубина которых не превосходит N. Пользуясь предположением индукции получаем, что для формул А\,..., Ат существуют эквивалентные им приведенные формулы Bi,...,Br над ЗЗи[Э]^), такие, что L(B{) <$ ЦАг), D(Bt) ^ D(At) < N. Таким образом, верно соотношение Ф ~ f(Bi,..., Вг). Случай 1. Предположим что / € 23. Тогда формула f(B\,..., Вг) является приведен- r r ной, ее глубина не превосходит iV + 1, и L(f(B\,..., Вг)) — ^2 L{Bt) ^ JZ L(Ai) — г=\ »=1 Случай 2. Предположим теперь, что / 6 [?>]^. Тогда г = 1 и Ф ~ f{B\). Случай 2.1. Формула В\ тривиальна. Тогда формула f(B\) является приведенной, а ее глубина и сложность равны 1 и не превосходят глубину и сложность исходной формулы Ф. Случай 2.2. Формула В\ нетривиальна. Случай 2.2.1. Вх — g(xi), где д G [2)](1\ Тогда функция h(x) = f(g(x)) принадлежит [S)]^\ и Ф ~ h(xt). Остается заметить, что h(xi) является приведенной формулой, глубина и сложность которой равны 1 и не превосходят глубину и сложность исходной формулы Ф. Случай 2.2.2. Вх = p{Gv,..., Gv), где <р е 03, а Сь ..., Gv — формулы над Ъ U [?>](1), глубина которых не превосходит N —1. Поскольку / 6 [S]^\ р Е 03, по условию леммы получаем, что f{ip(x\,..., xv)) = h(gi(xi),... ,gv(xv)) для некоторых функций h G 05 и gi,..., gv ? [ЗЗр). Следовательно, верны соотношения Ф ~ f( Каждая из формул gy(Gj), j — l,...,v, является формулой над Ъ U [5}]^\ глубина которой не превосходит N. Следовательно, к формулам gj(Gj), j = 1,...,?;, можно применить предположение индукции и получить приведенные формулы F\,..., Fv над Яи^р), такие, что F, - g3{Gj), L{F3) < L(G3), D{F3) ^ D{G3)+l < N+l, j = l,...,v. Легко видеть, что формула h(Fi,..., Fv) эквивалентна исходной формуле Ф, является приведенной, ее глубина не превосходит N + 1 = ?)(Ф), а сложность не превосходит Ь(Ф). Таким образом, во всех возможный случаях мы получили приведенную формулу необходимой глубины и сложности, которая эквивалентна исходной формуле Ф. Положим do — max L%(j). Пусть Ф — произвольная формула над SUD. Она является формулой над 25 U [?)]^. Мы показали, что для нее существует такая эквивалентная ей приведенная формула Ф' над 03и[5)]^\ что Ь(Ф') ^ Ь(Ф). Если формула Ф' тривиальна, то Ф' является формулой над 21, Ф' ~ ф, ?)(Ф') = 0. Если Ф' = g(xi), где д (Е [Э]^1', то по определению константы d0, суи1,ествует формула над 21 эквивалентная исходной формуле Ф, глубина которой не превосходит d0. Если Ф' = Ф((?1,..., Gm), где Ф(а;1,..., хт) — формула над 05, a Gi,..., Gm — формулы над [З?]'1^, глубина которых не превосходит 1, Ь(Ф) ^ ?>(Ф), то воспользуемся равномерностью 05 в 21. Поскольку система 03 равномерна в 21, существуют такие константы cud, что для всякой формулы В над 03 существует такая эквивалентная формула А над 21, что D{A) ^ c\ogL(B)+d. Следовательно, для формулы Ф(ж1;... ,хт) существует такая эквивалентная формула Ф'(агь ... ,хт) над 21, что ?>(Ф') ^ c\ogL(ty) + d. Очевидно, что существуют формулы G[,..., G'm над 21, такие, что G\ ~ Gif D(G[) ^ d0, i — 1,..., т. Получаем, что формула Ф'(С?1>... ,G'm) является формулой над 21, эквивалентна исходной формуле Ф, и ее глубина не превосходит clogL^) + d+ rf0- Следовательно, система 05 U S3 равномерна в 21. ¦ 1.3. Вспомогательные утверждения 1.3.1. Метод преобразования формул В данном параграфе доказывается лемма 1.3.3, являющаяся обобщением метода использованного в [28, 48] для доказательства равномерности полных систем булевых функций. Эта лемма дает возможность при выполнении некоторых условий, преобразовывать произвольную формулу в эквивалентную таким образом, что глубина получающейся формулы по порядку не превосходит логарифма сложности исходной формулы. Сначала мы докажем две вспомогательные леммы. Лемма 1.3.1. Пусть 21 — произвольная конечная система функций из Рк, к ^ 2, т = m(2l), Ф(х) — произвольная формула над 21, Л^ — ?>(Ф). Пусть N > т + 1. Тогда формулу Ф(х) можно представить в виде В(А(х)1х), где А(х) и В(у,х) — формулы над 21, такие, что переменная у имеет только одно вхождение в формулу В и выполняются неравенства L(A), L(B) ^ ^h[{N + 1) < N. Доказательство. Поскольку т ^ 1 и TV > m + 1, верны неравенства т< —^— (N + l) т + 1 Легко видеть, что в формуле Ф можно найти такую подформулу Ф, которая имеет вид /(Фь Фг, • • ¦ > Фи), где / — некоторая n-местная функция из 21, п ^ 1, Фь Ф2,..., Фп — формулы над 21, и при этом выполнены следующие условия: ТП ТП ?(Ф)>—— (N + 1), Ь(Фг)^~—AN + 1), i = 1,2,..., п. Поскольку число переменных у функций из 21 не превосходит тп, а / € 21, верно неравенство п ^ т, а значит найдется такое j, I ^ j ^ п, что выполняются соотношения Представим Ф в виде B(^j(x),x). Покажем, что данное представление формулы Ф является искомым. Используя неравенства (1.1), получаем следующие соотношения TV 4- 1 тп L(B(y, x))^N L() + 1^NJ + 1 m + 1 ' m4- lv~ ' ' Лемма 1.3.2. Пусть т и N — произвольные целые числа, такие, что т ^ 1, N > тп + 1. Тогда верно равенство 1 + ^ш^ fe" +1) - ™) - ^шта^ - •») Доказательство. Заметим, что выполнены следующие соотношения m m(N — m) 2m (N + l)-m= „ , , ^ ZTT-Г ^ 1- m + lv ' m +1 "m Поэтому верно равенство + 4 - (iV + I) - m) . Отсюда следует, что верна следующая цепочка равенств XT ^ + 1) - m ) = . m+1 , ( m log----+ log 1 , / m + 1 / m Пусть 21, 03 — произвольные конечные системы функций из Р^, А; ^ 2, i? некоторое множество формул над 21. Будем говорить, что множество Л является (21,93)-регулярным, если существует такое конечное множество формул $ над 03, что для любых формул А(х), В {у, х) над 21, таких, что переменная у имеет только одно вхождение в формулу В и формула В(А(х), х) принадлежит множеству Я, найдутся формула F(y1:...,ys,z1,...,zr) из #, и формулы Ai(x),..., As(x), Вг{х),..., Вт(х) из Д, такие что L(Ai) ^ -^(-4), г = 1,..., s, L(Bj) ^ L(B), j = 1,..., г, и верно соотношение 5(Л(х), х) - F(A!(5),..., Л(х), Вг(х),..., Вг(х)). Лемма 1.3.3. Пусть 21, 25 — произвольные конечные системы функций из Pk, к ^ 2, R — (21,03) -регулярное множество формул над 21. Тогда существуют такие константы cud, зависящие только от 21, 03 и R, что для любой формулы Ф из R существует такая формула Ф' над 21 U 03, что Ф' ~ Ф и выполняется неравенство i d. Доказательство. Положим m = m(2l), max D%(f), d — L(/)$+l Пусть Ф — некоторая формула из R. Положим М = ?(Ф). Будем доказывать утверждение леммы с указанными константами end индукцией по М. База: Из определения констант d& и d ясно, что для М ^ т + 1 утверждение выполняется. Шаг индукции: Пусть утверждение теоремы верно для всех М меньших некоторого N, где N > m + 1. Докажем, что оно верно и для М = N. По лемме 1.3.1 формулу Ф(х) можно представить в виде Ф(х) = В(А(х),ж), где А(х) и В(у, х) — такие формулы над 21, что переменная у имеет только одно вхождение в формулу В и верны неравенства ТП ТП Ь(А) <С----{N + 1) Поскольку формула В(А(х),х) принадлежит множеству R, по условию найдутся такая формула F G J и такие формулы Аи..., As, Bi,...,Br из R, что L(Ai) ^ L(A), г = 1,..., s, L(Bj) ^ L(B), j = 1,..., г, и верно соотношение В{А(х), х) ~ ^(^(5),..., As(x), Поскольку сложность формул Ai,..., As, Bi:..., Вг меньше N, к ним можно применить предположение индукции, в силу которого существуют такие формулы А[, г = 1,..., 5, B'j, j = 1,..., г над 21, что А[ ~ Аь г = 1,..., s, В\ ~ Б,, j = 1,..., г, и верны неравенства (^ d, i = l,...,s, (1.2) clog (—— (N + l)-m }+d. j = l,...,r. (1.3) у Tfl ~T~ J- J Положим Ф'(х) — F(A[(x),..., A's(x),B[(x),... ,B'r(x)). Формула Ф' является формулой над 21U Ъ. Легко видеть, что верны соотношения Ф(х) = В(А(х), х) ~ F{Al{x),..., Аа(х), В^х),..., Вт(х)) - - F(A[(x),.. .,A's(x),B[(x),.. .,#(?)) = Ф\х). Также верно следующее неравенство < D{F) + max(max Z>(A'), max Отсюда, учитывая неравенства (1.2), (1.3) и неравенство D(F) ^ rf5, получаем, что верно соотношение Из последнего соотношения, применяя лемму 1.3.2, получаем неравенство ?>(Ф') ^ clog(iV-m) +d. Таким образом, мы показали, что утверждение леммы справедливо для формул Ф имеющих произвольную сложность. ¦ 1.3.2. Основные следствия Приведем ряд следствий из леммы 1.3.3, которые будут использоваться для доказательства равномерности некоторых систем функций. Лемма 1.3.4. Пусть 21 — конечная система функций из Р^, k ^ 2, О,..., к — 1 G [21], ^ ~ конечная система функций из Pk, Ъ Q [Щ- Пусть для любой функции f(y,x) из [21] существует такая функция ip(y,Zo,...,Zk-i) из #; что верно равенство /(у, х) = ip(y, /(0, х), /(1, x),...,f(k- 1,х)). Тогда система 21 равномерна. Доказательство. Для доказательства мы воспользуемся леммой 1.3.3. Положим 21' = 21U {0,..., к — 1}. Из условия вытекает, что для всяких формул A(5t), B(y, х) над 21' формула В(А(х),х) эквивалентна формуле (р(А(х),В(0,х), В(1,х),... ,В(к — 1,5;)) для некоторой функции ср ? #. Формулы В (0, х), В{1, х),..., В (к — 1, х) являются формулами над 21'. При этом выполнены неравенства L(B(0, x)) ^ L(B(y, х)), ..., Ь(В(к - 1, i)) < L(B(y, х)).

Список литературы

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23582.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

15.04.24 Задачи, условия и этапы организации экспериментальной работы

15.04.24 Критерии качества преподавания

15.04.24 Категория нормы в обучающей деятельности

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2022. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.