Содержание к диссертации
Введение
Часть 1. Сложность полиномиальных представлений функций k-значнойлогики 49
1. Полиномиальные формы функций 49
2. Приближение функций полиномами 96
Часть 2. Алгоритмические вопросы полиномиальных представлений функций k-значной логики 115
3. Распознавание свойств функций, заданных полиномами 115
4. Нахождение полиномиальных представлений функций 152
5. Мультипликативная сложность функций алгебры логики 195
Заключение 219
Список литературы
- Полиномиальные формы функций
- Приближение функций полиномами
- Нахождение полиномиальных представлений функций
- Мультипликативная сложность функций алгебры логики
Введение к работе
Актуальность темы. Функция /с-значной логики - это такая функция, каждая переменная и значение которой принадлежат конечному множеству Ек = {0,1,..., к — 1}, где к > 2 - натуральное число. Функции двузначной логики называются также функциями алгебры логики, при к > 3 функции /с-значных логик называют функциями многозначных логик. Функции /с-значных логик подходят для построения моделей при решении широкого класса задач. Функции алгебры логики применяются в схемотехнике, ведутся исследования и созданы промышленные цифровые устройства на основе функций многозначных логик.
Первые исследования функций /с-значной логики касались вопросов полноты и выразимости одних функций при помощи других. Особую роль играет выразимость функций /с-значных логик при помощи констант и операций сложения и умножения по модулю к. При помощи эквивалентных преобразований такие выражения можно привести к полиномам по модулю к. В 1927 г. И.И. Жегалкиным доказано, что каждую функцию алгебры логики можно задать полиномом по модулю два. Выразимость каждой функции /с-значной логики полиномом по модулю к зависит от вида числа /с, а именно, каждая функция /с-значной логики задается полиномом по модулю к тогда и только тогда, когда к - простое число. Функции /с-значной логики, которые предста-вимы полиномами по модулю /с, названы полиномиальными.
Полное решение задачи выразимости одних функций при помощи других состоит в построении решетки замкнутых классов по включению. Э. Пост доказал, что в двузначном случае эта решетка счетная. В работе Ю.И. Яно-ва, А.А. Мучника показано, что при к > 3 эта решетка уже континуумальна. Кроме того, А.В. Кузнецовым доказано, что при каждом составном к все полиномиальные функции /с-значной логики образуют замкнутый класс, не являющийся предполным классом. В работах Г.П. Гаврилова, А.А. Крохина,
Д.Г. Мещанинова, А.Б. Ремизова, К.Л. Сафина, Е.В. Суханова, А.Н. Черепо-ва изучаются решетки замкнутых классов, содержащих все полиномиальные функции k-значной логики, и решетки полиномиальных функций k-значной логики, содержащих все линейные функции. При этих исследованиях получены критерии полиномиальности функций k-значной логики при составных k. Таким образом, одно из направлений исследований полиномиальных представлений функций k-значной логики связано с задачей полноты и выразимости.
Другое направление исследований функций k-значной логики относится к синтезу и сложности управляющих систем. В этом случае речь идет не о функциональной выразимости функции, как в первом случае, а о представимости функции определенным образом и о сложности такого представления. Надо отметить, что это направление тесно соприкасается и с прикладными исследованиями. Представления функций алгебры логики различными полиномиальными выражениями рассматриваются с точки зрения их применения при проектировании цифровых устройств. В работах А.С. Балюка, С.Ф. Винокурова, А.С. Зинченко, А.С. Казимирова, В.И. Пантелеева, Н.А. Перязева исследуются вопросы полиномиальной декомпозиции и операторных полиномиальных представлений функций алгебры логики и функций k-значной логики при k 3. Изучаются также представления логических функций и их систем в программируемых логических матрицах (ПЛМ). ПЛМ – это особый вид интегральных схем. С логической точки зрения в ПЛМ представляется либо некоторая дизъюнктивная нормальная форма (ДНФ), либо некоторая полиномиальная нормальная форма (ПНФ). В работах К.Д. Кириченко, Н.А. Перязева, В.П. Супруна, P. Besslich, T. Sasao исследуется сложность представлений функций алгебры логики полиномиальными формами некоторых видов. Если сравнивать длину ДФН и длину ПНФ для функций алгебры логики, то оказывается, что при помощи ПНФ функции задаются более ко-
роткими представлениями (для самых сложных функций). Экспериментальные результаты показывают, что для средней длины функций, зависящих от четырех переменных, ситуация аналогична.
С развитием вычислительной техники все большую актуальность приобретали вопросы построения быстрых алгоритмов для решения важных задач. В работах В.Б. Алексеева, А.А. Вороненко, Н.Р. Емельянова разработаны методы построения алгоритмов распознавания свойств, связанных с полнотой и выразимостью, для функций k-значной логики, заданных вектором своих значений, и построены быстрые распознающие алгоритмы для соответствующих задач. Построение полинома по модулю k для функции k-значной логики также является одной из важных задач. Известен быстрый алгоритм построения полинома Жегалкина для функции алгебры логики, который напрямую обобщается на случай функций k-значной логики для произвольного простого числа k. В 1995 г. Д.Г. Мещаниновым предложен быстрый алгоритм, который при составном k выясняет, является ли функция k-значной логики полиномиальной, и в случае положительного ответа строит какой-то ее полином по модулю k. Изучается также алгоритмическая сложность распознавания свойств функций алгебры логики и функций k-значной логики при k 3, заданных полиномами. Полином по модулю k (при простых k) в тех случаях, когда он содержит относительно небольшое число слагаемых, может рассматриваться как сокращенное представление функции k-значной логики или вектора из kn ее значений. В связи с известным результатом об NP-полноте задачи выполнимости конъюнктивных нормальных форм (КНФ) представляет интерес построение полиномиальных алгоритмов распознавания свойств функций k-значных логик в том случае, когда функция подается на вход алгоритма полиномом. Этот интерес вызван тем, что задачи распознавания свойств функций, заданных своими сокращенными представлениями, часто оказываются NP-трудными. В ряде работ доказывается, что
некоторые свойства функций k-значной логики можно распознать с полиномиальной сложностью, если на вход алгоритма функция подается в виде полинома. Таким образом, еще одно направление исследований полиномиальных представлений функций k-значных логик можно определить как алгоритмическое.
Полиномы по модулю k и их обобщения служат не только предметом изучения, но и являются подходящим средством при решении других важных задач. Полиномы по модулю два и по модулю степени простого числа применяются в методах доказательства экспоненциальных нижних оценок сложности СФЭ ограниченной глубины в базисах, содержащих сложение по модулю два, для некоторых функций алгебры логики. Полиномиальные представления функций алгебры логики над конечными кольцами применяются в теории сложности, в задачах квантовых вычислений. Полиномиальные формы находят применение при проектировании интегральных схем, т.к. построенные при помощи них схемы допускают достаточно простое тестирование. Полиномы Жегалкина и полиномы над конечными полями или кольцами нашли широкое применение при решении задач криптографии. Полиномы Жегалки-на и полиномиальные выражения оказались очень подходящими для исследования и описания криптографических свойств функций алгебры логики.
Исследуются не только полиномиальные формы, но и представления в полиномиальных базисах, т.е. такие представления, которые построены при помощи умножения и сложения по модулю k, а также констант. Изучается сложность реализации систем линейных функций алгебры логики СФЭ в базисе из одного элемента сложения по модулю два. Отметим одну особенность, касающуюся сравнения операций дизъюнкции и сложения по модулю два. Для систем элементарных дизъюнкций, которые определяют так называемую матрицу без прямоугольников, в 1966 г. Э.И. Нечипоруком доказано, что сложность их реализации СФЭ в базисе из одного элемента дизъюнкции
тривиальна, т.е. равна сумме сложностей реализации СФЭ в этом же базисе составляющих их функций. В ряде работ получены нелинейные нижние оценки сложности реализации явно заданных систем дизъюнкций СФЭ в базисе из одного элемента дизъюнкции. Для СФЭ в базисе из одного элемента сложения по модулю два ситуация оказалась другой. В 1996 г. К.А. Зыковым построена последовательность таких систем линейных функций, образующих матрицы без прямоугольников, что сложность реализации каждой системы этой последовательности СФЭ в базисе из одного элемента сложения по модулю два асимптотически в два раза меньше, чем тривиальная реализация этой системы. В ряде работ этот результат существенно усилен. Для явно заданных систем линейных функций известны только линейные нижние оценки сложности СФЭ в базисе из одного элемента сложения по модулю два, нелинейные нижние оценки сложности явно заданных систем получены в СФЭ с ограничениями. Рассматриваются также задачи, связанные с изучением наименьшего числа умножений, необходимого для вычисления функции или системы функций в полиномиальном базисе. При получении лучших из существующих на сегодняшний день оценок сложности умножения матриц, важной прикладной задачи, оказался подходящим класс билинейных алгоритмов, в которых оценивается число умножений. Изучается мультипликативная сложность функций алгебры логики, т.е. наименьшее число конъюнкций, которые необходимы, чтобы вычислить эту функцию СФЭ в базисе из конъюнкции, сложения по модулю два и константы единица. Мультипликативная сложность функций алгебры логики находит применение в теории сложности.
Целью работы является решение следующих задач при исследовании полиномиальных представлений функций k-значной логики:
нахождение оценок сложности представлений функций k-значной логики полиномиальными формами различных видов и разработка методов,
обеспечивающих эти оценки;
нахождение оценок сложности полиномов, приближающих функции k-значной логики с заданной точностью;
отыскание полиномиальных алгоритмов для распознавания важных свойств функций k-значной логики, заданных в виде полиномов;
получение оценок алгоритмической сложности построения полиномов по модулю k для функций k-значной логики;
нахождение оценок некоторых видов сложности вычисления функций k-значной логики в полиномиальных базисах и разработка методов, обеспечивающих эти оценки.
Методы исследований. В работе применяются методы дискретной математики и математической кибернетики, комбинаторные и алгебраические методы.
Научная новизна. Все результаты работы являются новыми и получены автором самостоятельно.
Теоретическая и практическая ценность. Диссертация носит теоретический характер. Полученные результаты могут применяться в дальнейших исследованиях полиномиальных представлений дискретных функций и при чтении курсов для студентов и аспирантов математических специальностей. При получении верхних оценок длины функций k-значных логик в различных классах полиномиальных форм описаны методы построения этих полиномиальных форм для произвольных функций. Эти методы могут применяться при проектировании цифровых устройств. Полученные в работе быстрые алгоритмы решения рассматриваемых задач могут применяться при решении этих задач на практике.
Апробация результатов работы. Результаты диссертации докладывались на научных и научно-исследовательских семинарах в Институте систем-8
ного программирования РАН, в Казанском (Приволжском) федеральном университете, «Математические вопросы кибернетики» механико-математического факультета МГУ имени М.В. Ломоносова, «Дискретная математика и математическая кибернетика» факультета ВМК МГУ имени М.В. Ломоносова, а также на следующих конференциях: IV Международный семинар «Дискретная математика и ее приложения» (Москва, 29 января - 2 февраля 2001 г.), 31th International Symposium of Multiple-Valued Logic (Poland, Warsaw, May 22-24, 2001 у.), Международная школа-семинар «Дискретная математика и математическая кибернетика» (Ратмино, 31 мая-3 июня 2001 г.), V Международная конференция «Дискретные модели в теории управляющих систем» (Ратмино, 26-29 мая 2003 г.), VI Международная конференция «Дискретные модели в теории управляющих систем» (Москва, 7-11 декабря 2004 г.), IX Международный семинар «Дискретная математика и ее приложения», посвященный 75-летию со дня рождения академика О.Б. Лу-панова (Москва, 18-23 июня 2007 г.), Третья международная конференция по проблемам безопасности и противодействия терроризму. Секция: Математические вопросы безопасности информационных технологий, МАБИТ-2007 (Москва, МГУ имени М.В. Ломоносова, 25-27 октября 2007 г.), Четвертая международная научная конференция по проблемам безопасности и противодействия терроризму. Секция: Математические вопросы безопасности информационных технологий, МАБИТ-2008 (Москва, МГУ имени М.В. Ломоносова, 30-31 октября 2008 г.), VIII Международная конференция «Дискретные модели в теории управляющих систем» (Москва, 6-9 апреля 2009 г.), XV Международная конференция «Проблемы теоретической кибернетики» (Казань, 2009 г.), X Международный семинар «Дискретная математика и ее приложения» (Москва, 1-6 февраля 2010 г.), Десятая общероссийская научная конференция «Математика и безопасность информационных технологий». Секция: Математические проблемы информационной безопасности
(Москва, МГУ имени М.В. Ломоносова, 2011 г.), XI Международный семинар «Дискретная математика и ее приложения», посвященный 80-летию со дня рождения академика О.Б. Лупанова (Москва, МГУ, 18-23 июня 2012 г.), 7th International Computer Science Symposium in Russia, CSR 2012 (Nizhny Novgorod, July 3-7, 2012 y.), Тихоновские чтения (Москва, МГУ имени М.В. Ломоносова, 29-31 октября 2012 г.), Тихоновские чтения (Москва, МГУ имени М.В. Ломоносова, 28 октября - 1 ноября 2013 г.), Ломоносовские чтения (Москва, МГУ имени М.В. Ломоносова, 14-23 апреля 2014 г.), XVII международная конференция «Проблемы теоретической кибернетики» (Казань, 16-20 июня 2014 г.), Third Russian Finnish Symposium on Discrete Mathematics (Petrozavodsk, September 16-18, 2014 y.), Тихоновские чтения (Москва, МГУ имени М.В. Ломоносова, 2014 г.), IX Международная конференция «Дискретные модели в теории управляющих систем» (Москва и Подмосковье, 20-22 мая 2015 г.).
Публикации. Результаты диссертации опубликованы в 55 работах [1-55], из которых 24 работы [3,5,11-13,15,19,21,24,25,28,29,32,37,38,41,47-50,52-54], а также перевод работы [36] в журналах из списка рецензируемых изданий, рекомендованного ВАК. В совместной работе [25] автору диссертации принадлежат постановка задачи и теоремы 1.11 и 1.13 диссертации, в совместной работе [28] автору диссертации принадлежат постановка задачи и теорема 4.7 диссертации, в совместной работе [48] автору диссертации принадлежат постановка задачи и теорема 1.12 диссертации. Совместная работа [50] обзорна, в ней описан подход, разработанный автором диссертации при доказательстве полиномиальности распознавания самодвойственности функции к-значной логики по ее полиному, а также рассматриваются свойства функций алгебры логики, для распознавания которых можно применить этот подход.
Структура и объем диссертации. Диссертация состоит из введения, основных определений, основного содержания работы, разделенного на 2 части,
Полиномиальные формы функций
Функция /с-значной логики /(жі,..., хп) называется симметрической, если для всех возможных значений переменных х\,..., хп верно для произвольной перестановки 7Г на множестве переменных {хі,... ,хп}. Множество всех симметрических функций /с-значной логики обозначим как Sk. Симметрическая функция /(жі,... , хп) называется периодической c периодом т = (TQT\ ... тт-і) Є Е%, если f(a) = Tj при \а\ = j(mod Т) для каждо го набора а Є Е%. При этом число Т называется длиной периода. Периодическую функцию /с-значной логики /(жі,... , хп) с периодом г = [TQT\ ... тт-і) Є Еі будем обозначать как /у v
Функция /с-значной логики задается (или представляется) полиномом по модулю к, если эту функцию можно записать в виде где Cj Є Ek - коэффициенты, Xj - произведения переменных в некоторых степенях, и сложение и умножение рассматриваются по модулю к, j = Мы будем полагать, что в представлениях вида (1) приведены подобные слагаемые и опущены слагаемые с нулевыми коэффициентами. Если Cj = 0 при всех j = 1,...,/, то мы говорим, что это пустой полином 0 с нулевым числом слагаемых, который представляет константу 0. Будем говорить, что моном Xj входит в полином вида (1) (или является слагаемым этого полинома), если коэффициент при нем не равен нулю, т.е. если Cj ф 0. Множество всех функций /с-значной логики, представимых полиномами по модулю к, обозначим как Polk, множество функций из Polk, зависящих от переменных Х\: ... ,хП, обозначается как Polvk. Каждая функция из множества Polk называется полиномиальной. Известно ( [218], стр. 69), что Polk = Рк тогда и только тогда, когда к - простое число.
Моном (одночлен) Ха = YI ХТ , где ХТ – степени, назовем соответствую г=1 щим набору а = ( 2i,..., ап) Є Е . Типом монома Ха, а Є Е , назовем множество t(Xa) = t(a) С {1,..., п}. Рангом монома Ха, а Є Е%, назовем число r(Xa) = \t(a)\. Степенью монома Ха, а Є Е%, назовем число deg(Xa) = \а\. Если к - простое число, то каждая функция /с-значной логики /(жі,... , хп) может быть однозначно задана полиномом вида где Cf (а) Є Ek - коэффициенты, а Є Е , и операции сложения и умножения рассматриваются по модулю к [218] (стр. 69-71), [219] (стр. 38-39) (если Cf (а) = 0 при всех а Є Е%, то это пустой полином 0). Это представление функции /с-значной логики назовем ее полиномом по модулю к. В двузначном случае полином по модулю 2 вида (2) называется полиномом Жегалкина. При простом к однозначно определенный полином по модулю к вида (2) для функции /с-значной логики / будем обозначать как P(f). При простом к вектором коэффициентов полинома P(f) функции /с-значной логики /(жі,... ,хп) называется вектор значений функции с/(жі,..., хп).
Везде в дальнейшем, если не оговорено другое, будем считать, что к -простое число, и под операциями сложения и умножения в формулах для функций /с-значной логики понимается сложение и умножение по модулю к. При этом, если не оговорено другое, знак 0 обозначает операцию сложения по модулю два.
Рангом г(f) (соответственно, степенью deg(/)) функции /с-значной логики f(xi,..., Хп) назовем наибольший ранг (соответственно, степень) среди слагаемых с ненулевыми коэффициентами в ее полиноме P{f), т(0) = deg(0) = 0 по определению. Длиной /(/) функции /с-значной логики f(xi,... ,хп) назовем число попарно различных слагаемых с ненулевыми коэффициентами в ее полиноме P(f). Множеством (семейством) типов слагаемых полинома функции f(xi,..., Хп) назовем семейство T(P(f)) типов слагаемых с ненулевыми коэффициентами в полиноме P(f). Весом w(P(f)) полинома функции /с-значной логики /(жі,... ,хп) назовем число \T(P(f))\.
Функция /с-значной логики /(жі,..., хп) называется аффинной, если ее сте пень не больше единицы, т.е. если deg(/) 1. Аффинная функция /с-значной логики j{Xi,... , хп) называется линейной, если c/(U,..., U) = U. Функция к-значной логики /(жі,..., жп) называется мультиаффинной, если эта функция может быть представлена в виде произведения некоторых аффинных функций. Функция /с-значной логики /(жі,... , хп) называется квадратичной, если ее степень равна двум, т.е. если deg(/) = 2.
Мы будем рассматривать полиномиальные формы для функций /с-значной логики. В общем виде, полиномиальной формой (ПФ) для функций /с-значной логики будем называть формулу вида где Cj Є Ek, а Xj - это произведения функций /с-значной логики определенного вида. Эти функции определенного вида будем называть базисными функциями. Мы будем считать, что в ПФ приведены подобные слагаемые, при этом мы будем полагать, что слагаемые Xj различны, если в них перемножаются разные совокупности базисных функций. Также будем считать, что в ПФ слагаемые с нулевыми коэффициентами (CJ = 0) опущены. Если Cj = 0 при всех j = 1,..., /, то мы говорим, что это пустая ПФ 0 с нулевым числом слагаемых, которая представляет константу 0. Мы будем говорить, что выражение Xj входит в некоторую ПФ (является слагаемым этой ПФ), если в этой ПФ коэффициент Cj при нем не равен нулю. Обычный полином по модулю к также является ПФ. Длиной l(Q) ПФ Q назовем число ее попарно различных слагаемых с ненулевыми коэффициентами. Пусть К -какой-то класс полиномиальных форм, которыми представима каждая функция /с-значной логики. Тогда длиной lf{f) функции / Є Рк в классе ПФ К называется наименьшая из длин среди всех ПФ из класса К, которые задают функцию /. Длиной Lf(n) функций /с-значной логики в классе ПФ К называется наибольшая из длин функций из множества Pj? в классе ПФ К.
Различные полиномиальные формы отличаются видом их базисных функций. Мы будем рассматривать следующие полиномиальные формы: поляризованные полиномиальные формы (ППФ), обобщенно поляризованные полиномиальные формы (ОППФ), полиномиальные нормальные формы (ПНФ) и псевдополиномиальные формы (ПСПФ). Каждый следующий вид полино-мильной формы в этом перечислении является расширением предыдущего. Каждый из перечисленных видов полиномиальных форм будет строго определен в соответствующем разделе.
Пусть Ak С Рк - свойство на множестве функций /с-значной логики Рк. Тогда под задачей распознавания свойства Ак для функций /с-значной логики, заданных полиномами по модулю к, мы понимаем следующую задачу. Вход: функция /с-значной логики /(жі,... , жп), заданная в виде полинома P(f). Вопрос: верно ли, что / Є А . При исследовании алгоритмической сложности распознавания свойств функций /с-значной логики, заданных полиномами, мы будем подразумевать некоторую алгоритмически полную алгоритмическую модель, например, равнодоступную адресную машину (РАМ) [203] (стр. 15), на вход которой подается полином P(f) функции /с-значной логики /(жі,... ,хп) в виде слова a(P(f)) Є А , где А = Ек U {+} = {0,1,..., к — 1, +}.
Приближение функций полиномами
Таким образом, построена последовательность симметрических функций трехзначной логики, длина которых в классе ППФ растет быстрее, чем полученная нижняя мощностная оценка соответствующей функции Шеннона. Но, в отличие от двузначного случая, длина функций в построенной нами последовательности не достигает и полученной нами верхней оценки функции Шеннона в классе ППФ (теорема 1.3). Поэтому вопрос об асимптотике длины функций /с-значной логики в классе ППФ (при п — оо) при к 3 остается открытым.
Можно рассматривать ППФ не для отдельных функций, а систем функций /с-значной логики. В этом случае можно по-разному определять сложность (длину) таких представлений систем функций. Мы рассмотрим такое определение сложности систем функций /с-значной логики в классе ППФ, которое уместно с точки зрения реализации систем функций программируемыми логическими матрицами (ПЛМ) [217].
Сложностью системы ППФ, имеющих один и тот же вектор поляризации, называется число попарно различных слагаемых, встречающихся во всех этих ППФ. При простых к сложностью Lk {F) системы функций /с-значной логики F = {/і(жі,..., хп),..., fm(xi,... , хп)} в классе ППФ называется наименьшая сложность среди всех таких систем ППФ {pi,... ,рт}, что все ППФ pi,... ,рт имеют один и тот же вектор поляризации, и ППФ pj реализует функцию fj,j = 1,... ,m. Для произвольной системы функций /с-значной логики F = {fi(x\,..., хп),..., fm(xi,... , хп)} верно L П, (F) кп. Пусть к - простое число, и Ак С Рк, а Ак = Ак П Р. Введем функцию ЬП (т,п) (функцию Шеннона) сложности систем функций /с-значной логики, принадлежащих множеству А, в классее ППФ:
Рассмотрим периодические функции алгебры логики /у11Пч /у1т, /Vm спе (IIUJ, (11)1) (OilJ риодами длины 3. Для простоты обозначим их как /n, дп, hn соответственно. Эти функции рассматривал Н.А. Перязев в [115]. В [115] доказаны следующие свойства этих функций: при п 1 для периодических функций алгебры
Доказательство проведем индукцией по п. Базис индукции: п = 1. Тогда при поляризации = (0) мы получаем следующие системы ППФ {1, х\ 0 1}, {1,Жі}, {хі 0 1,Жі}. При поляризации 6 = (1) мы получаем такие системы ППФ {1,жі}, {1,Жі 0 1}, {жі,Жі 0 1}. Мы видим, что при каждой из возможных поляризаций сложность каждой из рассматриваемых систем равна двум. Следовательно, базис индукции обоснован.
Индуктивный переход: предположим, что для некоторого п, п 1, утверждение теоремы 1.6 верно. Рассмотрим вектор поляризации 6 = (di,..., dn, dn+\) Є Е + . Обозначим вектор (d\,..., dn) Є Е как 5.
Сначала рассмотрим систему F\ = {fn+i,gn+i}. Пусть dn+\ = 0. Тогда по перечисленным выше свойствам из [115] верно, что Р5 (fn+i) = %n+iPs(hn) 0 Ps(fn), PS І9п+і) = Xn+\P5{fn) 0 PS(9n) По индуктивному предположению при векторе поляризации 6 ППФ Ps(fn) и Ps(gn) содержат 2П попарно различных слагаемых. Аналогично по индуктивному предположению при векторе поляризации 5 ППФ P5(hn) и Ps(fn) содержат 2П попарно различных слагаемых. А значит, и ППФ xn+\P6{hn) и xn+\P5(fn) содержат 2П попарно различных слагаемых. Следовательно, при векторе поляризации (d\,..., dn, 0) Є Е + сложность системы F\ равна 2n+1. Пусть теперь dn+i = 1. Тогда по перечисленным выше свойствам из [115] верно, что Р6 (fn+i) = Xn+\P6{hn) 0 P6{9n)i Р6 І9п+і) = Xn+\P6{fn) 0 PS(hn). Аналогичными рассуждениями доказываем, что при векторе поляризации (d\,... ,dn, 1) Є E + сложность системы F\ равна 2n+1. Следовательно, для системы F\ индуктивный переход обоснован. Индуктивный переход для систем F2 и F% обосновывается аналогично. 2. Теперь рассмотрим общий случай т 2. Положим, что система Fm n f110N Є TOjn, и /поп т,п. Тогда по доказанному в п. 1 верно
Доказательство проведем индукцией по п. Базис индукции: п = 1. По лемме 1.6 мы видим, что при каждой из возможных поляризаций (d), d Є Е%, сложность каждой из рассматриваемых систем равна 3. Следовательно, базис индукции обоснован. Индуктивный переход: предположим, что для некоторого п, п 1, утверждение теоремы 1.7 верно. Рассмотрим вектор поляризации 6 = (di,..., dn, dn+\) Є Е + . Обозначим вектор (d\,..., dn) Є Е как 5. Сначала рассмотрим систему F\ = {fn+ii9n+i}. Пусть dn+\ = 0. По лемме 1.5 мы получаем, что Ps (fn+i) = aixn+i-PSІ9п) + b\xn+iP6\hn) + c\Ps(fn), P6 (gn+i) = a2%n+iPs(fn) + b2Xn+\Ps(tn) + C2Ps(gn), где ai, &i, ci, Й2, &2? c2 {1, 2}. По индуктивному предположению при векторе поляризации 6 ППФ Ps(fn) и Ps(gn) содержат Зп попарно различных слагаемых. Значит, и ППФ x2n+lP6{fv) и x2n+lP6 {gv) содержат Зп попарно различных слагаемых. Аналогично по индуктивному предположению при векторе поляризации 5 ППФ P6{hn) и P6{tn) содержат Зп попарно различных слагаемых. А значит, и ППФ xn+\P6{hn) и xn+\P6{tn) содержат Зп попарно различных слагаемых. Следовательно, при векторе поляризации (d\,... ,dn,0) Є Е + сложность системы F\ равна 3n+1.
Обозначим множество всех одноместных функций /с-значной логики, степень которых в точности равна т, как Dm, т = 1,..., к — 1. Пусть D = Dk Обобщенным вектором поляризации назовем вектор 5 = (ді,..., 5п), в котором Si = (siyk-i{xi), степень функции Si,m{xi) равна т. поляризованной полиномиальной формой (ОППФ), или обобщенно поляризованным полиномом по вектору S назовем сумму попарно различных обобщенно поляризованных по тому же вектору мономов с коэффициентами из Е . Число попарно различных слагаемых с ненулевыми коэффициентами обобщенно поляризованного полинома Р назовем его длиной 1(Р).
Нахождение полиномиальных представлений функций
Пусть s(x) - связное преобразование. Каждый элемент единственного цикла графа G(s) назовем циклическим элементом преобразования s(x). Отметим некоторые свойства циклических элементов преобразований. Если а Є Ek - циклический элемент связного преобразования s(x) Є Р ранга q, то 1) для произвольного элемента Ъ Є Ek найдется такое число т 0, что sm(b) = а; 2) sq(a) = а; 3) для произвольного числа т 0 элемент sm(a) также является циклическим. Перечисленные свойства циклических элементов следуют из определения циклического элемента.
Зафиксируем некоторый циклический элемент а Є Ek связного преобразования s(x) Є Р. Тогда для произвольного числа т 0 найдется такой единственный циклический элемент Ъ Є Ek, что sm(b) = а. Положим по определению, что s m(a) = Ъ.
Лемма 3.3. [233] Пусть к 2. Если функция /(жі,..., хп) Є Pk инвариантна относительно набора связных преобразований Si(x), ..., sn{x), то для произвольного і (1 і п) найдется такое связное преобразование s x) с нулевым циклическим элементом, эквивалентное преобразованию Si{x), что функция f(xi, ..., хп) инвариантна относительно набора преобразований Si(x),..., Si-i(x), s x), Si+i(x), ..., sn(x). Доказательство. 1. Рассмотрим преобразование Si(x) (1 і n). Возможны две ситуации: либо 0 является циклическим элементом SJ(IE), либо нет. Если верна первая из них, то пусть s x) = Si(x). Иначе, пусть а Є Ek - некоторый циклический элемент преобразования Si(x). T.к. Si(x) - связное преобразование, найдутся такие числа т 0 и rrii2 О, что si n(0) = si n{a).
Положим, что rrii3 = rrii2 — rrii1. Тогда циклический элемент si гз(а) Є Ek эквивалентен элементу 0. Таким образом, мы обнаружили циклический элемент (обозначим его как с), эквивалентный элементу 0. Построим преобразование s x) по следующим правилам: а) s (0) = Si(c); б) s (c) = Sj(0); в) если Si(x) = 0, то s x) = с; г) если Si(x) = с, то s lix) = 0; д) во всех оставшихся возможными случаях преобразования s x) и Si{x) совпадают.
Докажем, что преобразования s x) и Si{x) эквивалентны. Другими словами, нам надо доказать верность двух условий определения эквивалентных преобразований. Содержательно их выполнение следует из того, что т.к. 0 Si с, классы эквивалентности, на которые разбивают множество Ek преобразования Si и s i, совпадают и порядок следования их друг за другом при применении преобразований Si и s одинаков. Теперь более подробно.
Леммы 3.1, 3.2 и 3.3 описывают функциональные свойства функций к-значной логики, инвариантных относительно связных преобразований. В следующей лемме 3.4 представлено одно структурное свойство их полиномов относительно операций поля Fk.
Напомним, что семейство всех типов слагаемых полинома Ppk(f) обозначается как Т(РрА()). Обозначим как Т (РрЛО) множество пересечений всех возможных / элементов (не обязательно различных) из семейства T(Ppk(f)).
Лемма 3.4. [233] Пусть к = ph, где р - простое число, h 1, и F = (Ek] +, ) - поле. Если функция /(жі,..., хп) Є Pk, не равна нулю и инвариантна относительно набора связных преобразований Si(x),..., sn(x) ранга а, то 0 Є T (Pj?,(f)).
Доказательство. По лемме 3.3 мы можем полагать, что элемент 0 является циклическим для каждого из преобразований Si{x). 1. Если функция / равна константе а Є Е} , а ф О, то Ppk(f) = а, и 0 є T q (Pp,(f\). 2. Пусть теперь функция / не равна константе. Заметим, что функция f(xi,... ,хп) инвариантна относительно некоторого набора преобразований тогда и только тогда, когда относительно этого же набора преобразований инвариантна функция /(жі,..., хп) + а для произвольного а Є Е . Поэтому, мы можем считать, что /(0,..., 0) = 0. Т.к. функция /(жі,..., хп) не равна 0, найдется такой ненулевой набор ( 2і,... ,ап) Є Е%, что /( 2і,... ,ап) Ф 0. Пусть mi,...,mn 0 такие числа, что й (а ) Є являются циклическими элементами, і = 1,...,п. Пусть т — наибольшее из чисел mi,... ,тп. Положим, что bi = sm(ai) Є Е . По замечанию к определению циклического элемента &і,..., Ъп являются циклическими элементами.
Каждому связному преобразованию s{x) с нулевым циклическим элемен том сопоставим функцию ts(x), построенную по правилу: для каждого эле мента а Є Ek верно ts(a) = m, если т - наименьшее из всех таких чисел, что sm(a) = 0, т 0. Назовем функцию ts(x) функцией расстояний пре образования s(x). По определению функции расстояний ts(x) связного пре образования s(x) с нулевым циклическим элементом верно, что sts x (x) = 0 и sts (x) = s(x) = х. Имеет место также следующее равенство: если S\(x) - связное преобразование с нулевым циклическим элементом, tSl(x) - его функция расстояний, и S2(x) — связное преобразование, то s24 г (2(2/)) = s2 (у). Действительно, s2 {S2{y)) = s2 [у) = s2 (у). Лемма 3.5. [233] Пусть к 2. Функция f(xi,... ,хп) Є Pk инвариантна относительно набора связных преобразований si(x),..., sn(x) с нулевыми циклическими элементами тогда и только тогда, когда
Докажем необходимость. Пусть функция /(жі,... ,хп) инвариантна относительно набора связных преобразования Si(x),..., sn(x) с нулевыми циклическими элементами. Пусть t\{x) — функция расстояний преобразования S\{x).
Мультипликативная сложность функций алгебры логики
Нижняя оценка доказывается аналогично доказательству теоремы 4.5. Пусть задана какая-то СФЭРП Sn в базисе о, реализующая систему Пп.
Докажем, что в СФЭРП Sn каждому такому набору а Є Е%, что 1 \а\ п, можно сопоставить не менее 3- \а\ элементов конъюнкции или дизъюнкции, причем так, что для разных наборов а и (3 соответствующие им множества элементов не пересекаются, и если элемент s соответствует набору а, то из этого элемента s найдется ориентированный путь в выход v(a). Доказывать это утверждение будем индукцией по весу наборов t, 1 t п.
Базис индукции: t = 1. Пусть а Є Е , и \а\ = 1. Рассмотрим в СФЭРП Sn куст, растущий из выхода v(a). На выходе v(a) реализуется функция /(О,..., 0) 0 /(а), поэтому этот куст содержит хотя бы 3 элемента конъюнкции или дизъюнкции [194]. Припишем всем таким элементам пометку а. Если 1 ф (У-2, \&і\ = ск2І = 1, то пометки а,\ и «2 будут приписаны разным элементам. В самом деле, пусть какой-то элемент s получил хотя бы две пометки, OL\ и «2, OL\ ф СЇ2. Рассмотрим куст, растущий из элемента s. Если он содержит только один вход, то элемент s без ущерба для СФЭРП можно удалить. Пусть он содержит два входа, например, it(0,... ,0) и и{а\). Но тогда есть ориентированный путь из входа и{а\) к элементу s, и есть ориентированный путь из элемента s к выходу (о ). Противоречие, этого не может быть в силу разделенности переменных СФЭРП.
Индуктивный переход от t — 1 к t, 2 t п. Пусть в СФЭРП Sn каждому такому набору /З Є Е , что 1 /3 t — 1, сопоставлено не менее 3 /3 элементов конъюнкции или дизъюнкции, причем множества элементов, сопоставленных разным наборам, не пересекаются, и если элемент s сопоставлен набору /3, то из этого элемента s найдется ориентированный путь в выходную вершину v((3).
Преобразуем СФЭРП Sn: подадим на все входы и((3), /3 t — 2 значение 0. Рассмотрим в СФЭРП Sn произвольный элемент конъюнкции или дизъюнкции s, которому сопоставлен набор /3, где 1 /3 t — 2. Из элемента s есть ориентированный путь в выход v((3), поэтому в элемент s могут вести ориентированные пути только из входов, на которые поданы 0. Преобразуем СФЭРП Sn по правилам алгебры логики О&ж = 0, 0 V ж = ж, 0 = 1, 1&ж = ж, 1 Ух = 1 и т.д. до тех пор, пока это возможно. При этом мы удалим все входы и{(3), \(3\ t — 2, все элементы, хотя бы на один вход которых пришла константа 0 или константа 1, и все выходы v((3), \(3\ t — 2 (на каждом из таких выходов реализуется функция, тождественно равная нулю). Отметим также, что при этом удалятся все вершины, которым были сопоставлены наборы /3, где 1 /3 t — 2, т.к. в эти вершины вели ориентированные пути только от входов, которым мы приписали 0. Обозначим полученную СФЭРП с входами и(а), \а\ t — 1, и выходами v(a), \а\ t — 1, как S n
Итак, в СФЭРП S n t] нет элементов конъюнкции и дизъюнкции, сопоставленных наборам /3, где 1 /3 t — 2. Но в СФЭРП S n могут быть элементы конъюнкции или дизъюнкции, сопоставленные каким-то наборам /3, /3 = t — 1. Рассмотрим такой элемент s. Пусть он сопоставлен набору /3. Рассмотрим выход v((3), /3 = t — 1. На нем реализуется тождественная функция и((3). Из элемента s есть ориентированный путь в выход v((3). Поэтому в силу разделенности переменных СФЭРП S„/ в элемент s могут вести ориентированные пути только из входа и((3). Поэтому элемент s можно удалить без ущерба для функционирования СФЭРП и не увеличивая ее сложность. Таким же образом удалим все элементы конъюнкции и дизъюнкции, сопоставленные наборам /3, /3 = t — 1.
Обозначим полученную СФЭРП с входами и(а), \а\ t — 1, и выходами v(a), \а\ t — 1, как SV. Заметим, что по построению в СФЭРП S{n] нет элементов конъюнкции и дизъюнкции, сопоставленных наборам /3, 1 /3 t — 1.
Пусть ск = t. Рассмотрим в СФЭРП п куст, растущий из выхода v(a). На выходе -и(а) реализуется функция и(а) 0 ф u{fi), т.е. сумма по модулю 2 своих (t + 1) входов. Для этого требуется не менее 3(t + 1) — 3 = 3t элементов конъюнкции и дизъюнкции [194]. Припишем всем таким элементам пометку а.
Если а,\ Ф (І2, \OL\\ = «2І = t, то пометки «і и «2 будут приписаны разным элементам. В самом деле, пусть какой-то элемент s получил хотя бы две пометки, а,\ и «2, OL\ ф СЇ2. Рассмотрим куст, растущий из элемента s. Если он содержит только один вход, то его без ущерба для СФЭ можно удалить. Пусть он содержит хотя бы два входа и{(3\) и и((32), А ф @2. Тогда, т.к. ({скі} U S{(1\)) П ({«2} U S{(l2)) 1, например, не верно, что /Зі OL I. Тогда, с одной стороны, найдется ориентированный путь от входа it (/Зі) к элементу s. А с другой стороны, найдется ориентированный путь от элемента s к выходу v{a,2). Получаем противоречие с разделенностью переменных СФЭРП. Индуктивный переход обоснован.