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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА

на правах рукописи

Комбаров Юрий Анатольевич

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

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

МОСКВА 2013

г 4 ОХТ 2№

005535701

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

Научный руководитель: доктор физико-математических наук,

профессор Редькин Николай Петрович Официальные оппоненты: Ложкин Сергей Андреевич,

Ведущая организация: ФГБУН "Институт системного анализа РАН"

Защита диссертации состоится 15 ноября 2013 г. в 1645 на заседании диссертационного совета Д.501.001.84 при ФГБОУ ВПО "Московский государственный университет им. М. В. Ломоносова" по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВПО "Московский государственный университет им. М. В. Ломоносова" (Москва, Ломоносовский проспект, дом 27, сектор А, 8 этаж). Автореферат разослан 15 октября 2013 г.

^ /7

Ученый секретарь //

доктор физико-математических наук, профессор (ФГБОУ ВПО "Московский государственный университет им. М.В.Ломоносова", Факультет вычислительной математики и кибернетики, кафедра математической кибернетики)

Стеценко Владимир Алексеевич,

кандидат физико-математических наук, профессор (ФГБОУ ВПО "Московский педагогический государственный университет", кафедра теоретической информатики и дискретной математики)

Д.501.001.84 при ФГБОУ ВПО МГУ

диссертационного совета

А. О. Иванов

доктор физико-математических наук, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

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

С практической точки зрения разумно рассматривать схемы, оптимальные по какому-либо параметру (например, содержащие наименьшее количество функциональных элементов). В связи с этим вводятся такие понятия, как сложность схемы, сложность булевой функции в классе схем и функция Шеннона.

Пусть В — некоторый базис, каждому элементу Е которого приписано положительное число Ь(Е), называемое весом элемента Е. Сложностью схемы 5 в базисе В называют сумму весов всех входящих в 5 функциональных элементов, сложность схемы Б обозначают через ¿(5). Для произвольной булевой функции / сложностью реализации функции / схемами в базисе В называют число 1<в(/) = гтп£(5), где минимум берется по всем схемам 5 в базисе В, реализующим /. Схемы в базисе В, реализующие функцию / со сложностью Ьв{1) называются минимальными. Наконец, функцией Шеннона для базиса В называют функцию Ав(гс) = тахЬ(/), где п £ Я, а максимум берется по всем функциям /от п переменных.

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

'Лупанов О. В., Асимптотические оценки сложности управляющих систем. — М.: МГУ, 1984.

схемы 5 обычно обозначается как Л (5).

О.Б. Лупанов1 предложил метод построения почти минимальных схем для почти всех булевых функций, а также нашел асимптотику для функции Шеннона. Пусть В = {Е\,..., Ей] — произвольный полный конечный базис и пусть каждому элементу Е( сопоставлен положительный вес Ь(Е{), а число входов элемента Е^ обозначается как т;. Будем называть минимальным приведенным весом базиса В величину

. ОД)

рв = тт —-— <е{1,...,А} ГГЦ — 1

Верна следующая

Теорема (О.В. Лупанов). При п —> оо

2 п

Ьв{п) ~ рв

п

причем среди булевых функций от п переменных хи...,хп доля функций f таких, что Ьв{/) < рв^ ^1 + 0 стремится к нулю сростом

п.

Для доказательтва верхней оценки теоремы О.Б. Лупановым предложен метод, позволяющий для любой булевой функции /, существенно зависящей от п переменных, построить схему 5, реализующую / со сложностью, не превышающей рв^ (^й))- Однако использование метода синтеза Лупанова приводит к асимптотически наилучшим результатам лишь при построении схем для сложнореализуемых и потому малодоступных на практике булевых функций. Встречающиеся в практических приложениях функции имеют относительно небольшую сложность реализации. В связи с этим возникает задача построения минимальных схем для индивидуальных последовательностей „простых" булевых функций и получения оценок сложности их реализации.

Приведем известные нижние оценки ДЛЯ СЛОЖНОСТИ схем В базисе 1?2, состоящего из всех функций, существенно зависящих не более, чем от двух переменных. Для любой булевой функции /, существенно зависящей от п переменных, верна тривиальная нижняя оценка Ьд2(/) > п — 1 (здесь и далее сложность схем определяется числом элементов в них, т.е. вес

каждого элемента базиса принимается равным единице). Для некоторых функций эта оценка оказывается оптимальной, например, для линейной функции 1п(х 1, ..., хп) = XI е ... ® хп верно, что Ьв2(1п) —п - 1.

К.П. Шнорр2 получил оценку Ьв2{1) > 2п- 3 для функций / из достаточно широкого класса Q%3 . Класс Q23 определяется индуктивно: булева функция /, существенно зависящая от п переменных принадлежит классу Q2.3' если среди функций, полученных после подстановки всевозможных констант вместо каких-то двух переменных функции /, найдутся хотя бы три различные функции и если любая функция, полученная после подстановки константы вместо какой-либо переменной функции /, принадлежит классу Q2 з1.

Опишем подход, на котором основано доказательство оценки сложности для функций из класса 3. Пусть S — минимальная схема, реализующая функцию / из класса Можно доказать, что после подачи некоторой константы на определенный вход схемы S какие-то два элемента в схеме S станут излишними (например, будут реализовывать константу или функцию, которая реализована каким-либо другим элементом в схеме), и их можно удалить из схемы S. Схема, полученная из схемы S после подачи константы и удаления двух элементов будет реализовывать некоторую функцию из класса Q\31 (это следует из определения класса з)- С учетом этого соображения требуемая нижняя оценка получается по индукции.

Описанный прием носит название „метод забивающих констант" („elimination method" в англоязычной литературе). Он был предложен Н.П. Редькиным3. Значительная часть известных нижних оценок сложности булевых функций получена с помощью этого приема. В общем случае для того, чтобы доказать нижнюю оценку сложности вида L(f) > кп — С (к,п 6 N,C - константа) для булевых функций / из класса Fn, содержащего функции, зависящие от п переменных, необходимо доказать следующее утверждение: для любой булевой функции f(x 1, ...,xn) е F„ существуют г 6 {1,..., п} и а € {0,1} такие, что из всякой минимальной схемы S,

2Schnorr С. Р., Zwei lineare untere Schranken für die Komplexität Boolescher Punktionen // Computing - 1974. - 13. - P. 155-171.

3Редькпн Н.П., Доказательство минимальности некоторых схем из функциональных элементов // Проблемы кибернетики. — 1970. — № 23. — С. 83-101.

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

J1. Стокмейер4 изучал реализации симметрических функций специального вида схемами в базисе Вг- При помощи метода забивающих констант он показал, что сложность таких функций, зависящих от п переменных, не меньше 2.5п + 0(1). Наконец, Н. Блюм5 получил нижнюю оценку вида £д2(/п) > Зп — 3 для сложности специально сконструированных функций fn, являющихся обобщением функции выбора. Доказательство последней оценки помимо метода забивающих констант в ряде случаев использует достаточно сложный анализ структуры схемы. На настоящее время последняя оценка является самой высокой нижней оценкой для базиса Вг-

Функции, для которых Стокмейер и Блюм получили оценки, являются в некотором роде искусственными, сконструированными специально для получения высокой нижней оценки сложности. Н.П. Редькин6 нашел сложность в базисе Дг для естественно определенного и имеющего значительное практическое значение оператора суммирования. Оператор суммирования — это отображение из {О, I}2™ в {0,1}п+1 вида р(хi,..., хп, у\,..., уп) = {Рп+ъРп, ■ ■ •,Pi), где Pi является г-м знаком в двоичной записи числа х+у, & хп у — числа, двоичной записью которых являются строки (хп,..., xi) и (уп,..., yi) соответственно. Доказано, что сложность оператора суммирования в базисе В2 составляет 5п — 3 (необходимо отметить, что оператор суммирования является оператором от 2п переменных). Доказательство нижней оценки сложности оператора суммирования проводится при помощи метода забивающих констант.

Более высокие нижние оценки сложности были получены для более узких, чем В2, базисов. Так, в работе7 получена нижняя оценка сложности с

4Stockmeyer L., On the combinational complexity of certain symmetric Boolean functions // Matli.Syst.Th. - 1977. — 10. — P. 323-326.

5Blum N., A Boolean function requiring 3n network size // TCS. — 1984. — 28. — P. 337-345.

^Редькин Н.П., О минимальной реализации двоичного сумматора // Проблемы кибернетики. — Вып. 38. М.: Наука, 1981. - С. 181-216.

TIwama К., Lachish О., Morizumi H., Raz R., An explicit lower bound of 5n - o(u) for Boolean circuits // Proceeding of the 33rd STOC, 2001. - P. 399-408.

минорантой вида Ъп - о(п) для сложности реализации булевых функций из некоторого множества схемами в базисе (72 = В2 \ {я ® у, х Ф у ф 1}. В работе8 получено значение асимптотики сложности в базисе 1]% для другого класса булевых функций. Эта работа посвящена исследованию класса функций с малым числом единиц, т.е. класса содержащего все булевы функции, зависящие от п переменных и принимающие значение 1 ровно на к наборах значений переменных (к предполагается малым по сравнению с п). Приведем определение сильных переменных, которое используется в формулировке результата работы8.

Определение. Пусть f(xi,...,xn) — некоторая функция из обращающаяся в единицу на наборах c?i,..., dk- Функции / можно сопоставить матрицу Mf, строками которой являются наборы ах, ...,<?(.. Будем считать, что г-ый столбец матрицы Mj соответствует переменной Xi (г g {1,...,п}). Для произвольного набора т через Mf обозначим группу столбцов матрицы М/, равных f (быть может, М? = 0). Непустую группу столбцов Mf будем считать сильной, если она содержит не менее двух столбцов и в этих столбцах содержатся как нули, так и единицы. Переменные, соответствующие столбцам из сильных групп, будем называть сильными.

В работе8 доказана следующая

Теорема. Пусть у булевой функции f(xi,..., хп) из класса имеется тп сильных переменных, а для параметра кп выполняется условие

1 < кп < logn — clog log п, где с — произвольная константа, большая единицы. Тогда

Lu2(f) ~п + тп.

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

8Редькин Н. П., О сложности булевых функций с малым числом единиц // Дискретная математика. - 2004. — Т. 16, вып. 4. - С. 20-31.

Настоящая работа посвящена изучению минимальных схем для линейных булевых функций 1п(х 1, ...,х„) = Xi © ... © хп и 1п(х 1, ...,хп) = х\ © ... ф хп © 1 в различных базисах. Функцию 1п называют однородной линейной функцией, а функцию 1п — неоднородной. Первый результат в этом направлении получен для класса управляющих систем, отличного от схем из функциональных элементов: в 1952 г. Кардо9 доказал, что всякая минимальная контактная схема, реализующая линейную функцию от п переменных содержит ровно An — 4 контакта. Более простое доказательство того же результата получил С.А. Ложкин10, он же для некоторых случаев нашел число минимальных контактных схем, реализующих операторы, составленные из линейных функций. Первые результаты, в которых устанавливается значение сложности линейных функций в классе схем из функциональных элементов получил Н.П. Редькин: в работе11 доказано, ЧТО ¿{x&î/,iVy,ï}{In) = ^{хку,хУу,х}{In) = 4n —4 И Ь{х&уз}{1п) = ii{xty,x}{^n) = L{xvy,x}{ln) — £{xvy,x}(У = 7n — 7. В работе12 установлено значение сложности функции 1п и даны оценки для сложности функции 1п в базисе, состоящем из единственного функционального элемента — штриха Шеффера (т.е. функции х\у = х&,у © 1). А именно, доказаны следующие утверждения: L{x\y}(ln) = 4п - 4, An - 4 < L{x\y}{ln) < 4n - 3. И.С. Шкребела13 получил аналогичный результат для базиса, состоящего из импликации и отрицания: Ь[х^у<щ{1п) = 4п - 4, 4п - 4 < L[x_,yß}{Q < An - 3. Нижние оценки сложности линейных функций в трех вышеприведенных работах получены при помощи метода забивающих констант.

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

9Cardot С., Quelques résultats sur l'application de l'algèbre de Boole & la synthèse des circuits â relais // Ann. Telecomm. — 1952. — 7, № 2. — P. 75-84.

10Ложкин С.A., Об одном методе получения нижних оценок сложности контактных схем и о некоторых минимальных схемах для линейных функций // Сборник трудов семинара семинара по дискретной математике и ее приложениям. — М.: Изд-во механико-математического факультета МГУ, 1997. -С. 113-115.

11 Редькин Н.П., Доказательство минимальности некоторых схем из функциональных элементов '// Проблемы кибернетики. — 1970. — Л'« 23. — С. 83-101.

12Редькин Н.П., О минимальной реализации линейной функции схемой из функциональных элементов // Кибернетика. — 1971. — № 6. — С. 31-38.

13Шкребела И.С., О сложности реализации линейных булевых функций схемами из функциональных элементов в базисе {ж у,х} // Дискретная математика. — 2003. — Т. 15, вып. 4. — С. 100-112.

Редькиным10 найдена сложность реализаци оператора сравнения Fn и оператора совпадения Rn в базисе {х&у, х V у, Щ. Операторы сравнения и совпадения — это булевы функции, определяемые следующим образом:

„ .. J 1, если \х\ < \у\ ( 1, если £ = у

I 0, если |ж| > |у| 1 0, если х фу

Здесь хну — наборы из нулей и единиц длины п, а через |х| обозначается целое неотрицательное число, двоичной записью которого является набор х. При помощи метода забивающих констант доказано, что L{xky,xVy,x} (Fn) = 5n — 3 И £{z&y,xVy,x} (-^n) = 5n — 1.

Достаточно глубоко изучены минимальные реализации элементарных конъюнкций и дизъюнкций схемами в различных полных базисах. Элементарными конъюнкциями и дизъюнкциями называются булевы функции вида К? = х^к... кх%п и D~ = х^1 V ... V х°п соответственно. Е.П. Сопруненко14 было найдено значение сложности реализации функций х\к... кхп и xi V ... V хп в базисе Шеффера: Ь{х\у}{х\Ил... кхп) = In—2, L{x|yj(a;iV.. .Wxn) = 3n—3. E.C. Горелик15 обобщил эти утверждения, доказав, что L{x\y}{K£) = Зп - 2 - ||?||, L{x\y}{Dfj - 2п - 3 + Здесь через ||сг|| обозначается число единиц в наборе д.

Дальнейшие обобщения этих результатов были произведены Г.А. Ко-чергиной10, изучавшей реализации элементарных конъюнкций и дизъюнкций в базисах В^ — {х\ V... V XkVxk+i V... Vxfc+г, х}. В работе16 найдены значения сложности Ьв^(К^) и Lb^D1-) при всех возможных значениях к, I, п и <т, а также дано описание всех минимальных схем, реализующих функцию Ж1&... кхп в базисе

Еще одной хорошо изученной функцией является универсальная функция

SAn(x,y)= V

5-=(сг1.....ег„)

14Сопруненко Е.П., Об одном классе схем из функциональных элементов // Проблемы кибернетики. - 1965. - № 15. - 117-134.

15Горелик Е.С., О сложности реализации элементарных конъюнкций и дизъюнкций в базисе {i|j/} // Проблемы кибернетики. — 1973. — № 26. — С. 27-36.

16Кочергина Г.А., О сложности реализации элементарных конъюнкций и дизъюнкций схемами в некоторых полных базисах // Математические вопросы кибернетики. — 2002. — № 11. — С. 219-24S.

где набор переменных х имеет длину п, набор переменных у имеет-длину 2", а

п ¿=1

В. Дж. Пауль17 получил следующие оценки для сложности реализации функции БАп в базисе В2;

2 • 2П - 2 < ЬВ2(ЗАп) < 3 ■ 2" - 3.

В. В. Коровин18 получил асимптотические значения сложности реализации функции БАп в нескольких базисах, а именно показал, что

Ьв^БАп) ~ 2 • 2га, Ь[хьу,хчу$}(ЗАп) ~ 2 • 2",

Ь{хку$}{8Ап) = Ь{хУу^(8Ап) ~ 3 • 2". Отметим, что функция БАп зависит от экспоненциального (по п) числа переменных, поэтому все вышеприведнные оценки остаются линейными по числу переменных.

В работе19 найдены точные значения глубины функции ЭАп в базисе £/2 при 2 < п < 5 и для п > 20. Для случая 5 < п < 20 в работе18 получены очень точные оценки на глубину функции БАп. Наконец, асимптотические оценки для сложности реализации функции БАп в классе формул можно найти в работе20.

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

"Пауль В. Дж., Оценка 2.5п для комбинаторной сложности булевых функций // Кибернетический сборник. — 1979. — № 16. — С. 23-44.

18Коровин В.В., О сложности реализации универсальной функции схемами из функциональных элементов // Дискретная математика. — 1995. — Т. 7, вып. 2. — С. 95-102.

28Ложкин С.А., Власов Н.В., О глубине мультиплексорной функции // Вестн. Моск. ун-та. Вычислительная математика и кибернетика. — 2011. — № 2. — С. 40-46.

20Власов Н.В., О сложности мультиплексорной функции в классе формул // Проблемы теоретической кибернетики, Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.) — Нижний Новгород, Издательство Нижегородского госуниверситета, 2011. — С. 96-97.

21Редькин Н.П., Об оценках сложности схем из многовходовых функциональных элементов // Дискретная математика. — 2010. — Т. 7, вып. 1. — С. 50-57.

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

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

В завершение приведем результат, в котором описывается структура минимальных схем. Работа22 посвящена минимальным реализациям оператора (xi&x2&... ЖІ&Ї2&... кх^) схемами из функциональных элементов в базисе В%. Показано, что всякая минимальная схема, реализующая такой оператор, разбивается на две непересекающиеся подсхемы, одна ИЗ которых является минимальной схемой ДЛЯ функции XI&LX2& • • • &хп, а другая — минимальной схемой для функции ЩкЩк....

Цель работы

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

Основные методы исследования.

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

2аБлюм Н., Сейсен М., Характеристика всех оптимальных схем из функциональных элементов для одновременного вычисления AND и NOR // Кибернетический сборник. Новая серия. — 1990. — if» 27 — С. 104-117.

Научная новизна. Все основные результаты диссертации являются новыми и состоят в следующем:

1. Получено описание минимальных схем, реализующих однородные линейные функции в базисе Шеффера.

2. Найдены точные значения сложности неоднородных линейных функций в базисе Шеффера.

3. Получено описание минимальных схем, реализующих однородные линейные функции в базисе {х —» у, х}.

4. Найдены точные значения сложности неоднородных линейных функций в базисе {х —>• у, х}.

Апробация результатов. Результаты диссертации докладывались на семинарах „Надежность управляющих систем" и „Диагностика управляющих систем" под руководством профессора Н.П. Редькина (МГУ, 20092013гг, неоднократно), на VIII Международной конференции „Дискретные модели в теории управляющих систем" (Москва, 2009г., 6-9 апреля), на XVI Международной конференции „Проблемы теоретической кибернетики" (Нижний Новгород, 2011г., 20-25 июня), на XI Международном семинаре „Дискретная математика и ее приложения" (Москва, 2012г., 18-23 июня), на Международной научных конференцях студентов, аспирантов и молодых ученых „Ломоносов-2011" (МГУ, Москва, 2011г., 11-15 апреля), „Ломоносов-2012" (МГУ, Москва, 2012г., 9-13 апреля) и „Ломоносов-2013" (МГУ, Москва, 2013г., 8-12 апреля), на научных конференциях „Ломоносовские чтения" (МГУ, Москва, 2009г., 16-24 апреля), „Ломоносовские чтения" (МГУ, Москва, 2012г., 16-24 апреля), „Ломоносовские чтения" (МГУ, Москва, 2013г., 15-26 апреля).

Публикации. Основные результаты диссертации опубликованы в работах автора [1-9], список которых приведен в конце автореферата.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

В работе рассматриваются минимальные схемы для линейных булевых функций 1п — х\ © ... © х„ и 1п = х\ ® ... ф хп ф 1 в различных базисах, состоящих из не более чем двухвходовых элементов. Для описания структуры минимальных схем вводится понятие стандартного блока.

Стандартным блоком в базисе В будем называть схему 5 с двумя входами, реализующую линейную функцию от двух переменных (однородную или неоднородную), если сложность схемы Я в базисе В минимальна среди всех схем в базисе В, реализующих линейную функцию от двух переменных (как однородную, так и неоднородную). На рис. 1 представлены стандартные блоки для базиса {х&у, хУу, х}, на рис. 2а представлен единственный стандартный блок для базиса {х\у}, а на рис. 26 — единственный стандартный блок для базиса {х —у,х}.

а)

б)

Рис. 1:

а)

б)

Рис. 2:

Отметим, что поскольку Ь{хку^Уу<щ{12) = для бази-

са {х&су, х V у,х} существуют стандартные блоки, реализующие как однородную, так и неоднородную линейную функцию. С другой стороны, Ь{х\у}(к) < £{х|!/}(¿2) и < поэтому в базисах {я|у}

и {ж -> у,х} не существует стандартных блоков, реализующих неоднородную линейную функцию.

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

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

Теорема 2. Любая минимальная схема в базисе В, реализующая 1п или 1п, п ^ 2, разбивается на п — 1 непересекающихся стандартных блоков, каждый из которых входит в схему правильно.

Для доказательства теоремы показывается, что Ьв{1п) — £>в(1п) = 3п — 3. Затем для всякой минимальной схемы 5 в базисе В, реализующей линейную функцию от п переменных и имеющей структуру, отличную от описанной в теореме, устанавливается возможность удаления четырех двухвходовых элементов таким образом, что полученная схема реализует линейную функцию от п — 1 переменной. Это приводит к противоречию с вышеприведенной оценкой сложности и доказывает теорему. Доказательство теоремы основано исключительно на методе забивающих констант.

Глава 2 посвящена описанию структуры минимальных схем, реализующих линейную функцию в классическом базисе К = {х&у,х У у, х].

Доказана следующая

Теорема 3. Любая минимальная схема в базисе К, реализующая 1п или ln, п ^ 2, разбивается на п — 1 непересекающихся стандартных блоков, каждый из которых входит в схему правильно.

Доказательство теоремы опирается на результат работы11, в которой устанавливается значение сложности линейных функций в базисе К. В данном случае установить структуру схем с использованием лишь метода забивающих констант не удалось; при помощи этого метода оказалось невозможным опровергнуть существование минимальных схем, содержащих подсхемы особого вида, названные специальными блоками. Поэтому доказательство теоремы выстраивается следующим образом: сначала при помощи метода забивающих констант доказывается, что из всякой минимальной схемы в базисе К, реализующей линейную функцию от п переменных, можно удалить стандартный или специальный блок, получив схему, реализующую линейную функцию от п — 1 переменной; затем существование минимальных схем, содержащих специальные блоки, опровергается при помощи ряда соображений, основанных на подсчете числа конъюнк-торов и дизъюнкторов в схеме.

Отметим, что аналогичную теорему, описывающую структуру минимальных схем в базисе К, ранее сформулировал (без доказательства) С.А. Ложкин23.

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

В главе 3 рассматриваются минимальные схемы для линейных функций в базисе S, состоящем из единственного функционального элемента, реализующего штрих Шеффера (т.е. функцию х\у = xky® 1). В работе12 доказано, что Ls(ln) = 4п-4и4п-4 < LS(Q < 4п - 3. В настоящей работе найдено точное значение сложности неоднородной линейной функции

23Ложкин С.А., О структуре минимальных схем в базисе {&, V,-■}, реализующих линейную функцию // Труды V Международной конференции „Дискретные модели в теории управляющих систем" (Ратмино, 26-29 мая 2003 г.). — M.: Издательский отдел факультета ВМиК МГУ имени M.D. Ломоносова, 2003. - С. 50-51.

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

Теорема 5. Сложность реализации функции 1п, п Е N, в базисе 5 составляет 4п — 3.

Теорема 6. Любая минимальная схема в базисе 5, реализующая 1п, п ^ 2, разбивается нап — 1 непересекающихся стандартных блоков, каждый из которых входит в схему правильно.

Доказываются теоремы 5 и 6 одновременно: показывается, что всякая минимальная схема, реализующая линейную функцию от п переменных (как однородную, так и неоднородную) со сложностью 4п — 4 разбивается на п — 1 непересекающихся стандартных блоков. Из этого утверждения немедленно следует описание структуры минимальных схем, реализующих однородную линейную функцию. С другой стороны, поскольку всякая схема, состоящая из п — 1 стандартного блока, реализует однородную линейную функцию, из этого утверждения также следует, что не существует минимальных схем, реализующих неоднородную линейную функцию со сложностью 4п — 4. Последний факт с применением результатов работы12 и позволяет получить точное значение сложности неоднородной линейной функции.

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

Глава 4 посвящена исследованию минимальных схем, реализующих линейные функции в базисе / = {х у,х}. В главе доказываются следующие теоремы.

Теорема 8. Сложность реализации функции 1п, п £ N, в базисе I составляет 4п — 3.

Теорема 9. Любая минимальная схема в базисе I, реализующая 1п, п ^ 2,

разбивается пап — 1 непересекающихся стандартных блоков, каждый из которых входит в схему правильно.

Теорема 8 усиливает результаты работы13, в которой показано, что Ь7(гп) =4п-4и4п-4< ЬДУ < 4п - 3. Отметим, что в доказательстве теорем 8 и 9 дополнительные рассуждения, с помощью которых доказывается невозможность существования минимальных схем, содержащих специальные блоки, значительно проще, чем для базисов К и 5 (хотя эту невозможность по-прежнему не удается доказать при помощи метода забивающих констант). С другой стороны, часть доказательства, использующая метод забивающих констант, заметно сложнее и объемнее, чем для базисов К и 5.

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

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Комбаров Ю. А. О минимальных схемах для линейных булевых функций /'/ Вестн. Моск. ун-та. Матем. Механ. — 2011. — № 6. — С. 41-44.

[2] Комбаров Ю. А. О минимальных реализациях линейных булевых функций // Дискретный анализ и исследование операций. — 2012. - 19, № 3. - С. 39-57.

[3] Комбаров Ю. А. О минимальных схемах для линейных функций в некоторых базисах // Дискретная математика. — 2013. — 25, № 1. — С. 33-44.

[4] Комбаров Ю. А. О сложности реализации линейной булевой функции

в базисе Шеффера // Веста. Моск. ун-та. Матем. Механ. — 2013. — № 2. - С. 49-53.

[5] Комбаров Ю. А. О минимальных схемах в базисе Шеффера для линейных булевых функций // Дискретный анализ и исследование операций. - 2013. - 20, № 4. - С. 65-87.

[6] Комбаров Ю. А. О сложности реализации линейных булевых функций схемами в базисе „импликация-отрицание" — М., 2013. — 40 с. — Деп. в ВИНИТИ 24.06.2013, № 177-В2013

[7] Комбаров Ю. А. О минимальных реализациях линейных булевых функций схемами из функциональных элементов в базисе {¡г ->■ У. х&су} 11 Труды УШ международной конференции „Дискретные модели в теории управляющих систем" (Москва, 6-9 апреля 2009 г.) — Москва, 2009. - С. 145-149.

[8] Комбаров Ю. А. О минимальных реализациях линейных булевых функций схемами из функциональных элементов в некотором базисе // Проблемы теоретической кибернетики, Материалы ХУІ Международной конференции (Нижний Новгород, 20-25 июня 2011 г.) — Нижний Новгород, Издательство Нижегородского госуниверситета, 2011.

- С. 215-218.

[9] Комбаров Ю. А. О сложности реализации линейных булевых функций в одном базисе // Материалы XI Международного семинара „Дискретная математика и ее приложения" , посвященного 80-летию со дня рождения академика О.Б.Лупанова (Москва, 18-23 июня 2012 г.)

— М.: Изд-во механико-математического факультета МГУ, 2012. — С. 131-133.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж 100 экз. Заказ № 46

Московский государственный университет имени М. В. Ломоносова

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

На правах рукописи ^УДК 519.71

04201451672

КОМБАРОВ Юрий Апа,то.льеыг

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

01.01.00 - дискретная математика п математическая кибернетика

ДИССЕРТАЦИЯ па соискание ученой степени кандидата фи'шко-математическпх наук

Научный руководитечь. доктор фп'шко-математпческпх паук.

профессор Н.П Редькпп

Москва - 2013

Содержание

Введение 2

Глава 1. Минимальные схемы в базисах, содержащих инверторы нулевого веса. 22

1. Определения и вспомогательные утверждения.......... 22

2. Сложность линейных функции................. 23

3. Структура, минимальных схем. реалшуюнх чиненные функции. 27

Глава 2. Минимальные схемы в классическом базисе. 35

1. Определения и вспомогательные утверждения....................35

2. Основная лемма........................................................38

3. Доказательство теоремы............................................51

Глава 3. Минимальные схемы в базисе Шеффера. 54

1. Определения и вспомогательные утверждения....................54

2. Основная лемма......................................................75

3. Доказательства теорем................................................80

Глава 4. Минимальные схемы в базисе „импликация — отрицание^. 83

1. Определения и вспомогательные утверждения.......... 83

2. Основная лемма........................... 89

3. Доказательства теорем........................119

Глава 5. Сложность линейных функций в неизбыточных базисах из двухвходовых элементов. 122

Ввсд( нпс 2

Введение

Плчеппе свойств схем in фмгкцпона 1ьпы\ элементов является отпои ш главных "задач математической кибернетики Схемы in функциональных тлемептов представляют собой матема гинее кие модели pea н>иы\ физнче-ски\ \ с тропе lв in поть )\емых д ¡я вычпе ieiiini Нарядх с б\ левыми фор-м\ 1ами кошакшымп схемами конечными авшматами и машинами Тьюринга схемы из функциональных пемептов являются примерами дискретных \правляющпх систем

В книге [9] О Б Т\ панов определяет схем\ из фмпшнопа 1ьных ) юмеи-юв ноль>\ясь вспомоытельпым иопяшем сеш Приведем соответсил-ioimie опреде юппя

Определение. Сеть — объект сосюящпп из по not оь и )ч\иитоь Каждый тлемеил имес-д несколько входов н один выход Ниже нпдхкшыю определяется сеть и множество ос вершин

1 Полюс есть ceib On являедея едппс твенпоп вершппоп )юп сеш

2 Если Sj и S) — сеш без общих вершин то их обьедипение ecib

сеть Вершинами угон сети являются ьершипы псхотпых ceieii

3 Ее ni 6 — с егь и Ь — .помели выхо i ко юрою не является ьо]) шииои сели S лоропльта! присоеднпеппя всех входов )темеша Е к пекоюрым вершинам сети S ее ш сеш при пом к одной верните сети могут присоединяться pa s шчпые входы по каждып вхо i присоединяется то н>ко к отпои вершппе Вершинами повои сети яв-ляюня вершины сеш 6 и выход ) юмепта Е

Определение. С'/елюи т фупи ujionn п)п bii j нс мрптпоь па зывае i с л сель в ко юрой

1 каждом\ по нос\ приписана одна из переменных t „ прп-

чем ра Л1ым по посам — разные переменные По нос а пазываюхея ык-же в i одами с гемы

Ввсд< HIIC

2 каждому "пемешл Е с ? входами нос 1аь юна в соответс i вне пекот орая б\ тева фмпчнпя o¿(tji у,) с\ше(твеппо зависящая от / арпмеп юв (при / = 0 функция ol р(--гь константа) п называемая фхпкдпен зтемепта Е "пемепг Е с сошк 1ав leinioii ему ф\ пкцпеп o¿ ría зыьаекя фупыцюна ii>iihi м j к ментом

3 некоторой вершине пршпк ano мне ю 1 пекоюроп вершине (быть моле i совпадающей с нервон) пригшеano чисто 2 и гд пекоюрон вершине приписано чис то /?? Вершины коюрым приписано хс)1я бы одно m чисет отмечены симвотом * Эти вершины называются выгодами схемы

Калдом\ ь\од\ п к а/к цпп ) гемеш\ ( чемы с гед\ ющпм обра н>м ( ошк 1ав-тяется pea ш пемая пм (фикция

1 каждом\ входу схемы (опое 1автясмся с^пкцпя равная переметши пришк аппоп ^том\ ьход\

2 п\сгь ьг(лм ьершппам к которым прпсое пигепы вхоты тюмеша L схемы \ ле с опост автепы ф\ пкции То1да выход\ згою j юмеша со поехав [яется санкция o¿(/(1) где o¿ — (фикция печены Е а/^—ф\п кция согюстав генная топ вершине с кот opon соединен у-и вход ) темепта Е

Схема по опре [отеишо реатнлех \поря ючептю (пехемх (])\нкцш1 (опе рагор)

(АО i ?„) tmb i -с,,)) где // — (фикция сопоставтеипая/-м\ выхеид

Е( тп (J)mikihin всех пемептов схемы S Н1шпадтелат мполесгву В ю блдем i оворн i ь чю схема S есть i к иа о байке В (и ш пас) В) Базпс В па ¡ываегся

а) по тыл: естп всякая б\ тева (фикция топ\скает реатпзаншо схемой в банк е В

б) пси ¡быточиим естп ба як В — по шып по перестает быть по шым посте удатеппя in нею тюбоп ф\пкцпп

Вы дс шк

ь) конечным епн базис В с одержит конечное чпе то ф\ пкцпи Часто \доб по считать ч ю базисы с опоят не т бл левых фу пкцпн а из фу пкцнона н> пы\ 1 гемепгоь рем ш ющи\ зтп санкции

С пракшчес коп точки трепня ра з\ мио рассма тривать схемы огппма ш пые по каком\-тибо нараметрл (например содержащие наименьшее ко пь чество ф\ пкщюпатьпых пемептов) Всвядтс )тпл[ вводя к я такие понятия как с южное ть схемы сложность б\ тевоп санкции в классе схем и ф\ икцня Шеппона

П\ с ть £>—некоторый базис каждом\ злемептл Е колорот о п1)пппсапо по ложп ю 1ыюе чпе ло Ь(Е) называемое ьееом )1с\инти Е С ложное 1 ыо схемы Ь в базисе В называют еумм\ ьос оь всех входящих в Ь ф\ пкцнона 1ьпы\ )лемеитов с южное 1 ь с хс мы обо знача ю 1 через Ь(3) Ды произвольной б\левой ф\икцпп / с юл< но( тыо реа ш зешии фуиьиии / е и \ieiMii е-> битее В называют число Ьв(1) = тт/,(5) где мшшм\м бе рется по всем схемам 6 в базисе В реа пь\ клдпм / Схемы в балке В реалнзмощпе функцию / со сложностью ЬвЦ) называются шишмипь-иы\ш Наконец санкцией Шешюиа I. ¡я базиса В па>ыьакн санкцию = 1ИахЬ(7) 1 ц1 п £ \ а макспмхм борекя но всем ф\нкцплм ] сн н переменных

Наряд\ с о с ложное л ыо важной харак юрис шкои схем из е})М1кцпопа п> пых ) юмоптов являемся их гпбипа Г п]буцои схемы 5 с одним выхо юм называется число т темен гов припад южащпх самой лдпппон орпелип])*) ваппоп цепи в К0Ю])0П некоторый вход ее 1юрьело ) юмоша является входом схемы а выход нос ле шел о ) юмоша яв [яотся выхо юм схемы Г 1\бппа схемы 5 обычно обозначается как 1)(Ь)

В кпше [9] О Б Чупановым д пт пропзво шною полною конечною ба знса представлен метод построения помы минимальных схем д 1я почти всех б\ леьых флпкцпп а также найдена асимптотика тля санкции Шоп попа 11хс п> В = {Е[ Е/} — пропзво шпыи полный коночный баше и п\с ть каждомх 1 темоптл Е, с опое лав юи по южшельпыи вес Ь(Е,) а чпе то входов ) юмоша Е, обозначается как т, Блдсм называть мшшма шпым

Вы к нпс

)

приведенным весом банка В ве шчпп\

L(E,)

Pl¡ = lililí -

/€{1 А } III, — L

Верпа с к1 i\ ющая

Теорема (О Б Ъпаноь [0]). Г1ра п —> оо

2"

LB{ri) ~ рв— п

)ij)ii4(\t ср(ди букььп фупьциа от п т рс\к ниы г i\ ?„ дот функтш / таит что LB{f) ^ í}B~ Н О 6tnP( Ш/Г?/Г/7 ь lllJ 110 ( potmou

п

Для дока затетьтва верхней оценки теоремы О Б Ч\ Пановым пред ю-жеи метод гюзво [яющпп для любой б\ ¡евоп фмпчцпп / с \ щес i веппо за впеящеп о г а переменных гюс iponib схемл S реалп>\ющ\ю / со с южпо-с 1ыо не превьппаюшен [>в~ ^ О шако ik по гьзоваппе ме-

юда ciiiiie>a Т\ Панова приводит к аснмптошчески нанял чшпм ре л тыа-там шшь при гюс 1])оеппп схем дтя с тожнореали лемых п поюмл малодо-сг\ппых па п])акгпке б\ тевых фхикцпи Встречающиеся в практических приложениях с})\ пкцпп имеют ошоспгетыю небольшую с южное п> pea ш->ацпп В связи с )гпм возникает задача нос ipoemi/i мниима 1ьпы\ схем дтя пидивпдлальных нос ледователыюс теп простых бл левых ф\пкции и пол\ченпя опенок с южноетп их pea ниацип

Приведем известные нижние оценки для сложности схем в башее В> состоящею н э всех фмнчцпн с \ щестьенно зависящих не бо ice чем oí дь\х переменных Д ш любой б\ левоп фл нкинн / емцеывешю зависящей oí и переменных верпа гривпа льиая нижняя опенка Ьв (/) ^ и — I (здесь п ta-лее с ложное ть схем опреде тяелея чпе юм )лемептов в них i е вес каждого элемента ба ;пса принимается равным единице) Дтя дока ^ателье пза jtoii оценки дое raí очно \чссть что калчдып вход схемы ло 1Ж(Ч1 быть соединен со входом хотя бы одного ф\пкпиопалыю1 о элемента Для некоторых фмпчцип зга опенка оказывается оптпматыюи например пя шпеппоп санкции /„(/i („) = ti tD i„ верно что L в >{},,) = n — 1

ВвГД( лпс

Ь

В рабою [20) К П Шпорр но т\ чп i оценкх Ly ( f) ^ 2и — $ л ш ф\ нкцпп j п > достаточно широко! о к iacca Q23 Q'i 3 оиреде ню гся нпд\ kihh

по

Определение. Б\лева флпкцпя / существенно зависящая о 1 п переменных прппад тежш к iacc\ <7? 3 ос лп среди с|")\ пкцни по i\чеппых гюс ю rio i-стаповкп всеьо змодшых копе íain вмос 1 о каких-10 дв\ \ переменных с])\пк-шш / паид\гся хотя бы три раз шчпые ф\пкцпи и ее ли любая (|)\пкнпя гюлл ченпая после подстановки константы вместо какой-либо переменной фхпкции/ прппад южнт к iac с \ Q""^1

Опишем подход па котором основано дока sa тельс тво оценки с ложное гп д 1Я cj)\ нкцнн и з к iacca Q'¡ >, Пл сть Ч — мшшма 1ьпая схема pea ш s\ ющая санкцию / п з к iacea Q'¡ i Можно доказать что гюс те по игш некоторой копегаигы па опредечеппын вход схемы S какие-то два момента в схе ме S сгаи\1 излпшппмн (например б\д\т реялизоьываль копелапп и ш санкцию которая pea ш зоьапа каким-либо ф\гпм ) юмеп i ом ь с хомо) и их можно \ да ni и> из схемы S Схема по л\ чепиая из схемы S после иода чп константы и удаления дв\\ злемелпоь бхдем pea шзоьывать пекогор\ю санкцию Из к iacca (это еле i,\ei из определения класса Q^ С \ че-

том jtoio соображения треблеммо нижнюю оценкл несложно rio i\ чип. по пнд\кцпп

Оппсаппыи прием носит надзапие медо i сбивающих копе тан 1 ( eli-mmation methocl в ашлоязычпои шюратлре) Оп был предложен Н 11 Редькииым в работе [11] Значительная часть известных нижних оценок сложности б\ теьых функции гю пчелы с помощью утото приема В об щем с iy чае для того чтобы доказать нижнюю оценк\ с ложное ш вида L{f) ^ кп — С [к 71 Е Л С - копе rain а) для булевых ф\пкцнп j из класса F,, (содержащего флнкцни зависящие-1 от п пе])еменных) достаточно доказать с кдмошее у гверж iciiiie для любон б\ ювои функции /(?! •?„) £ Fn 11 всякой мшшма irnoii схемы S pea шз\ ющен / емцо-с гвмел / £ {1 /?} и <т £ {0 1} ыкне чю и; нос ie подачи па вхо i схемы S с оотвелс тву юшин переменной константы а из S можно \ ы-шть к элементов так что полхчеиная схема будет pea ш зовыват ь с])\пк-

Ь'вгдс UIK

7

цшо п з F„-1 Пос ric дока зате шспза и oí о \ i верлч кчшя треб\рм\ю оцопк\

С ЮЛчПОСЛН МОЛчПО 6\ДР1 ПО IVIIllb ПО ППДМчЦИП

В рабою | 30] п i) ча ик в pea ni ¡апип спмме i ричес ки\ ф\ пкцпп спедпа п>-пою вида схс мамп в ба шее В? При помощи метода ¡абпваюищх копе iani показано чго слолчпостъ 1акп\ флпкцпп зависящих от п переменных не меньше 2 r)ii +0(1) Наконец, в рабою [24] поллчепа пшкпяя оценка вида LbAÍh) ^ 3/? ~ ()> Л1Я ( юлчпос ш (пецпепыю с копе i р\ проваппых фмичцпп f„ являющихся обобщением фипчцнн выбора Доказательство пос 1едпеп оценки помимо метода забивающих копсташ в ря ie с 1\чаев пепошзич их та точно пожпып ana ип сх])\кг\ры схемы На пас гоящее время по-( ледпяя оценка является самоп ьысокоп пплчпеп оценкой д ш балка В Дока зале льс гва лрех \ помят гых выше пилчппх опенок клклчо молчпо пап ni в кпше [31) В работе1 [26] прежде хав icna пплчпяя оценка с мшюрапшп вида ]и — о(п) дтя ф\нмтш1 п ; пекошрого класса Дока зате шс гово нон гшлчнеп оценки значите хыю проще чем доказало ibctbo из раболы |24|

Фмичцпп л ля которых поллчеиы опенки в работах [24) п [30] яв щются в некотором роде1 пс к\сс хвеппымп скопе хр\ проваппымп специально i 1я пол\чеппя высокой пплчпеп оценки с юлчпос i и В рабою [12] НП Ре щ КППВ1М папдеиа с лолчпос i в в банке В> ил ее тс с твенпо определенною и имеющею зпачпле плюе практическое значение оператора с\м\шроваппл Оператор с \ ммпрованпя — по отобралчепне из {0 I}2" в {0 ви щ

PÍU i„ tji ij„) = (Ahí Pn Pi) i К" ¡), является ?-м знаком в двоичноп кшпеп числа ? 4-ц а / п tj — мне ia лвопчиоп записью которых я в ля ю i с я с i роки (in i [) и (iju iji) с оответс т вепно В рабою |12| цжазапо что слолчпосль опр])аюра с\ ммпрованпя в балке B¿ состав ыех ")/? — 3 (необходимо отметить что оператор с\ммпрованпя является оператором от 2п переменных) Доказаютвс гво пплчпеп оценки слоукиос i и оператора с\ммпрованпя проводится при помощи мет езда забивающих коп-с i аил при и ом в ря те с л\ чаев всышкает пеобхо шмоств по ьлвахь копе jan ты о щовречеппо па дьа ра зличпых входа схемы

Во iee высокие пплдше опенки с лолчиостн были иот\чены д 1я более \ з-ких чем В) базисов Так в работе [28] по i\ чепа высокая шпеппая пплч-пяя опенка с юлчпос ш для pea ли заппп б\ левых ф\ пкцпп схемами в ба пне

Вы д( нас

8

Ьт2 = В) \ { i td у i Т> у <Ъ 1} Приводом опре-лделеппя необходимые для юю чюбы ( форм\ тпроьат ь резллыал работы [28|

Определение. Б\лова фмпчцпя / (-71 /„) называемся 2- íaeiu и мои (в орш ипа к — Two-Dependent) ее ni i/гя любых/ у таких что 1 ^ / < у ^ п верно 4 10 ф\ икцнп /|,=-о,; о J |,=o,;_l /|,_i,,_oii /1 , =1 , попарно pa 3 шчиы

Определение. Б\ лева флпкппя f(>i i,,) называется (/? к)-< и \ыю-¿~ íueiuuMOu ((/? Á.)-Stioiie,lv-Two-Dependent) если всякая санкция по i\чаемая пз фиткцпп / пос к1 подстановки каких- шбо копе lain вместо пеко-юрых ni переменных (0 ^ /?? ^ />) являемся 2-зависимой

Необходимо отменив сходе тво лих определении с oripe re юппем к lace а Q'¿ i данным выше В работе [28] юка зана с лед\ ющая

Теорема ([28]). Пусть f(i¡ i,,) яьпкики (// /, )-е и ii>uo-2- тык и мои булевой (j)yiihuu(u mahou что /. — о(п) Тогда L¡ (/) ^ Г)П — о(п)

Дока за ie н>с jbo теоремы основано па методе сбивающих копсташ Oi-мешм что в работе1 [28] ппжпяя оценка с южное ги по i\ чепа также' ил меры стожпостп схем SD(S) = Le ,(S) — Deey(S) где Dc(¡{S) — чпе ю входов схемы S соединенных со входом ровно одного ф\ пкцпона шгюш ) гемеша Нижняя еягепка д 1я ктс])1>т с тожпос тп l¡ яв гяекя с ie ц гвне м оценки 11Я меры с тожпос тп 3D

В работе [13] по i\ четто значение аспмппн пкп с шжпосш в базисе lh дтя дрмого ктаеса б\ 1евых санкции Эта рабола посвящена псс юдова-нтпо к iacea фхпкцпп с матым чистом едиппц те ктаеса 1-), ¡ содержащею все б\ тевы санкции зависящие от п переменных и прпппмающпе значение 1 ровно па L наборах значении переменных (А претпотагаекя матым по сравнению с п) Приведем опре ie т orí i re сильных переменных которое пеполь з\ечсл в форм\ шровке pen ibiaia работы [13|

Определение. П\сп> /(? i г,,) — пекоюрая санкция пз /•„/, обра-птающаяся в е липши на наборах сгi сх/ Фмпчщш / можно с опое га-ьпть матрипл Mf строками woiopon явщюлся пабо])ы (Т[ ó¡ Б\ ¡ем считать что /-ып с то тбеп матрппы \í¡ coo i ьег ст вл ет переменной t, (/ е

Вьгд< нпо

о

{1 п}) Д 1Я произвольней о набора f через М- обозначим гр\пп\ с ю 16-цоь ма iрпци V/ равных f (был ь можег М~ = 0) Попу с ту ю i ру пт с i о [б нов М~ будем считан, си iliioii ее ли она содержит не менее двух столбцов и в )шх с то 1бцах содержатся как н\ m так и единицы Переменные соответствующие столбцам из сильных тр\пп б\ тем называть сильными

В раболе |Н| тока заиа с к дмотая

Теорема. [Jij< ть ij 6tj ne вой ejnjit h ujiu f{i L i n) m л пек с с/ t,, / имеете и inn (iiibiibir ii( ¡)( \iLiiiit)i t а с) ¡я пара \к ////ю к „ ohiiiej гняе-чпе я ijí шьие

J ^ k „ ^ log п — с loe, 1о£ п /Ос с — пртнвоаыи/я ноне тонта боиииая (Отиты То?до

Le (/) ~ ¡i -i m,,

Доказате п>слво поп теоремы являелся одним из пемпот их п])пмеров ю-казательс тв опенок с ложное тп схем пс испо тьзмощих мето т забивающих конслант Прпве юм ос повпу ю и тс ю лен о дока >а i е и.с иза

П\ с i ь / ( / i 1 п) — ф\ пкщы ib к iac с а Ь,, / П\ ст ь некоторая с \с ма S в ба шее Vi pea ш >\с т ф\пкцпю / Ь\дем называть вход схемы 6 соот-ветствмощнн переменной г, дефектным ее ли — сильная переменная функции / и вход соотвелс тву ющпп переменной 1, соедппеп в схеме S со вхо том роыю езди oí о фупкцпона ibiioio помечи а Нижняя оценка породы является следствием следующего у i верждення существует минимальная cxeyia Smm рс а ш л ющая функцию / 13 кс)г0])0п каж ц>ш вхо i cooiboi сльующин си 1ыюп переменной соодппеп со входами хотя бы двух функ-цпопа льпых племен iов (или жьньа лен тно с л щес i гзу ел мпинма 1ьиая с хома Sinm не содержащая дефектных входов) Для доказательства лого у тьер /К leiiiKi в работе [13| описано предобра юьанне кото[)ое по мппима лыюи схеме S pea ш зУ lomen фупкшпо / и с о юржащотт дес^ектпын ьхо i cooi-всдству ющпп иеремоппоп i, строит пову ю мппима п>пу ю cxeyiy S' также реатп зу ющ\ ю / по в которой вход соответствующий неремечшои , уже1 по явтяется кфекгным (а 1зходы которые пс бы ni дефектными в S не становятся дофектпыуш и в 5') Схема Ь,тп строится многократным нрн-монепиоу! описапнон) иреоб])а .ования к нобон мппима iliioii схеме pea ш-зу ющоп фу нкцию f

Bbi д< пне

LO

Настоящая рабсма посвящена mviPnnio мшшыа п»пы\ схем { [я шпеп-

ПЫ\ б\ К'ЬЫЧ ф\ ПКЦПП l„(l[ I п) = /1 Ф — I ,, II /,)('! > ,,) -

¿i i„ vi 1 в pa лпчпbi\ ба зисач Первый реп штат в иом naiipaij>яс

шш пог[\ чегг л 1я 1ч iac с а \ прав ляющпч с пс тем оппмного от (чем п з ф\ нк ипопальпыч -лемешов в 10j2 г Кар ю доказал [2Г>] мто всякая минимальная контактам схема pea ли ющая пшепщю с|)\пкшно oí // переменных содерлчш ровно 4// — 4 контакта Бо ieo нрос юе юка зато н>с изо юго лче pe ix п> i a i а представ юно в рабою [8| 1ам Лче для пеколорыч с i\наев пап-депо мпс ю минимальных контакт пых схем роалпз\ющпх операторы составленные и з пшенных ф\ пкдпп Первые рез\ льлаты в которых \с кшав-лпвасчся значение с лолчпос гп лппеппых ф\ пкцпп в классе схем пз с])\шч цпона 1ьных )лемешов гюл\ мепы Н П Редькппым в рабою (11] кжазапо тп° L{ и , ,1/т\(1ц) = , iit}{1>,) — 4/г —4 п л „) = L{ ijT}{1>) --L{i\,j т}{1ц) = ,„г){1,) = 7// — 7 13 рабою |11] \с танов течто юмпое зпа меипе с лолчпос ш санкции /„ п даны омепь точные оценки т ш с южное ш с})\пк1шп /„ в байке сосюящем пз единственного фмпчшюпалвпо1 о ) ю-мепла — штриха Шеффера А. пмслшо кжазапы с ледмощпе \ тверлчдемшя £{,и(/„) = -1//-4 1//-4 ^ 1-{1|,/}(7Д 4//-3 В работе [20] II С Шкребе ia по л\ мил ana югпчпып реп 1ыаг д 1я балка состоящего пз пмп