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

• Комбаров, Юрий Анатольевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Комбаров, Юрий Анатольевич

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ввсд( нпс

Введение диссертации (часть автореферата) на тему «Сложность и строение минимальных схем для линейных булевых функций»

Введение

Плчеппе свойств схем 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я балка состоящего пз пмп шкацпп п отрицания Т}(/„) = 4/1 — 4 4// — 4 ^ ^4п — 3 Нижние

оценки с юлчпос ш лппеппых ф\ пкцпп в работах |11 14 20] по i\ м(Л1ы при помощи Meioia забпьающпх копсташ

Прпве lom 1аклче pe з\ льтат касающппе я ]>еа ш зашш пшеппыч ф\ пкцпп схемами пз ф\ икцпопа тьпых элементов в бесконечном балке В^ с ос то-яшем пз отрицания а таклче коп ыонкцпп п дизыонкцни всево змолчпоп ДЛИПВ1 В работах [27] и [22] показано что ф\пмшю /„ невозможно pea ш-зовать схс'моп в базисе копе таит поп i т\бппы п полппочпа гьпоп с юлч-пос 1п (п ш более строю пе с \ щес iв\сч пос ie юьалелыюс тп схем ó-s в базисе В^ i а коп чго схема S1, реашзхет ф\ пкщпо 1, и (\ щеч ib\ioi константы C'i C¿ и к такие что дтя любого /? выполнены иеравепс i гза D(S„) ^ С i и ^ С>/?') Дока за ю лье гово лого факта (которое так

Лче модчпо папти в кпше [2 3]) основано на вероятное гпыч меч ода ч пока ,ы-ваеня чю ее тп такая пос ie юваютыюе ть с чем S„ найдется то пап имея

Введение

LI

такая схема ,5'/,. которая с пенутевои вероятностью будет реалпзовывл! в константу после подачп произвольных констант па большую часть (по не. па все) из ее входов;.

Перейдем к описанию результатов в которых устанавливаются значении сложности для других естественно заданных булевых функции В работе |11] найдена сложность реализацп операл'ора сравнения /■], и опералора совпадения ВЧ1 в базисе {:/;&;//. хУу. г}. Операторы сравнения и совпадения — это булевы функции, определяемые следующим образом:

Здесь х п у — наборы из пулсч'1 и единиц длины //. а через \х\ обозначается неотрицательное целое число., двоичной записью кот'орого является набор ,г. При помощи метода забивающих копстапг в работе [11] доказано,

Достаточно глубоко изучены минимальные реализации элементарных ксигыонкцнп и днгыопкцпи схемами в различных полных базисах Элементарными кенпдопкниями и дптыопкцнямп называются булевы фуик-цни вида = x^L . . и = ,vf[l V ... V х°п" соответственно. Е.П.

Сопрупепко было получено [17] значение сложности реализации функции Xik . . . k:t;„ и Xi V ... V хп в базисе Шес])с]>ера:

Дальнейшие обобщения элл!х реззулыгал'ов были произведены ГА Ко-черпнюй в работе [5]. В эл011 работе рассматриваются реализации элементарных конъюнкций и дизлдонкнпй в базисах В^ — {.?'] V ... V ./;/, V лТ/,+1 V . . . V х/,+/.Т}. В ра.бегте [5] найдены значения сложности Ьр}у {К£) и

что уу„т)(Еп) = 5// - 3 и L{jkj/ = 5?/ - 1.

Ь{,/}(.Г!& ■ ■ • кх„) = 2v - 2. L{r|,/}(.Ti V ... V х„) = 3/7 - 3. Е.С. Горе тик обобщил эти утверждения, доказав |3|. что

= 3/7 - 2 - |[а||. ЬШ№) = 2п - 3 + Цех

ввсд( п11с

12

Lby (D'¿) при в< ох возможных значениях А / // и а а таклчо дапо описание всех минимальных схем pea шзиощпх ф\пкцпю в базисе Вп

Еще одиоп хороню пз\чеппоп ф\пкцпеи яв [лепя мшверса 1ьпая ф\пк-цпя

SA„(1 у) — V Li:'kiM

I7=(rr i (7 )

где набор переменных г имеет i пш\ п набор переменных у имеет т. nin\ 2" а

п

|а| = + 1

/ = т

В работе [10] по т\ чепы с тод\ ющпе оценки д тя с южное тп pea ш защит ф\ ик-цнп 6 А,, в ба зпе е В>

2 2" — 2 ^ Lb2(SA„) ^ 3 2" — 3

В работе [4] по т\ чепы асимптотические лтачепия с толчнос ш ])еа пьанип с})М1кппп S А.,, в нескольких балках а пмеппо показано чю

LB( Ь4„)~2 2" L{(W,,Í/T}(S4„)~2 2"

2 2"

i ^ = ^{íVí/T}(b 4„) ~ 3 2"

Oimoiiim чю (]>\ пкцп/i S 4„ зависит oí жепопепциа плюго (по //) чпе ia переменных иозлом\ все вышепрпье ишые оценки осктютсл лппеппымп по чпе л\ перемслшых

В работе [6] папдены точные значения гллбппы санкции ЬАп в базис с U> при 2 ^ /? ^ "3 п д 1я // ^ 20 Л 1я с i\ чая "3 < и < 20 в рабою [6] по i\-чсл1ы очень i очные оценки па г i\бит ф\ пкнпп Si,, Наконец асимптотические оценки для с Ю/кпостп pea шзаппи фхпкппп ЪА„ в классе форм\ i молено пап тп в работе [2]

В работе [16] рассматрпваотся некоторый по ixcu к по i\ чеппю петршзп-альпых оценок слолчпостп схем из ф\ пкцпоиа 1ьпых элементов осиовап-пын на замене с толчпых ба зпе ов па бо юе прос т ые с после лмощпм не по л ь-зоваипем п »вес шы\ инукинх оценок с юлчпосш схем в п]>остых базисах Эффект пвиость 1тою подхода icmoiic т рпр\ ется на примерах пахолчдеппл

Ввсд( huí

а с 11 м 111 о 111 к 11 а в некоторых г пчаях и тонною шачения л \я с южное ш схем и з \hjoi овхо ювых з телтеп юь pea ш зу loiunx мопоюппьк сиутмс ipinie -екпе б\ ювы е|)\пкцнн п фупкцпп ( ма гым мне юм единиц

В работе1 [29] Шнорром про пожеп необычный метод получения ппж них оценок с южное ш Опишем зтот метод Пусть В — некоторый базис состоящий и, не более чем дв\ хвхо довых ) темен гов a S — мпппма ib-ная схема в базисе1 В реалиюгцая санкцию /(?i /„) Выберел! в, схеме S з темент В входы которою соединены со входами схемы и тн со входами инверторов на которые подаются входы схемы тобавпм в схему новый вход соответствующий нереуклпюн ?„+1 п уда ihm злемеш В соединив входы пемоитов KOiopBie бы тн соединены с выходом В с ю-багз тениылт входом с холил По п чим схомл 5] роа нт )\ ющу ю фу икцию /\ Да юо по тв злясь описанпыут преобразоьаипс м построим нос юдовато п> нос ti> схем 6\ Sf/ pea ли зу юитпх е])\ пкцттп /| fq схема St] pea пт ,л < ¡ пекотору ю ттеременну ю t ч б\ тем называть отображение // нз мпожес i i.а булевых функции во множество натуральных чпеем мерой чш ш иш/<>(, ее ли ввито шены с кдл ющпо условия

1 //(г,у) = 0

2 Для любою / б {1 q — 1} верно что //(/,) ^ //(/,- i) + 1

Будем счшагь что ь базисе В каж тоуту тьу хвходовоуту зклнмпу прпппсап вес 1 а инвертору (в случае ее ш он со тержи тся в В) приписан вес 0 Тем та ттес южно убедиться что Lß(j) ^ /'(/) В работе [29] нре пожен прнукр лтеры числа шат ов иодходящпп д 1Я побои бу тевоп фл нкцип / с помощью зтои меры можно дока зать что

L{,y4 — j.(i i '„ VTL Т„) = In - 1

(здесь вес днзъюнктора прение) ьиается ])авнт>1м о пппще а вес инвертора — ну но) В книге1 [18] Д СзвндуК высказываот предположение что при тю-лтощн лтедода Шпорра моту т быть по ту чепы ис1 пшенные1 отдопкп с южное тп бл левых фу нкцип

Отметим что все вышепреве теппыо пи/кипе оттенки для с южпостн б\-ловых функтшп ль тяюгея тппоппылпт Несмотря па то что согласно юо ролю Тупаттоьа ночш ьеебу юьыо cjn нкцип с у щос твелню зависящие oí п

Вы нас

переменных имеют экс нот п шла плп ю по п с толчпос ib до ( п\ по]) по \ ыюсь наши приме]) явно заданной (те с троящейся за по пшомпать-нор в])емл) по( юдоваю плюс тп б\ ювых фмпчцпп с толчпос ть фмпчцпп ко-ю])Оп рас leí бо юо чем шпеппо Задача псммюппя не пшенных оценок с толчпос ш pea ш >ацпп б\ ювых санкции в по пюм балке яв гяекл одпоп из валчпеишпх задач математической кпберпегнкп

В завершеппе п])пведем ])ез\тыат в ко юром описывается стрммхра мпппматьпых (хем Pa6oia |1] посвящена мпппма ibiibim pea пьацпям оператора ( Гц^ч / ¿^ ki,, схемами п з ф\ пкшюпатьпых i ie-мрпюв в балке В> Показано чю всякая мпппма шпая схема ])еа пьмо-щая 1акоп оператор ])а збпвартся па ibp непересекающиеся подсхемы одна пз коюрых явтяется мпппма тыюн схемоп д 1Я фмнчщш i]kt¿S¿ к i,, а фмая — мпппма ibiioii схемоп i ш санкции TJk'TJk,

Перейдем к оппсаппю реу\ 1ыаюв [аппоп рабопл В рабою paccxiai-рпваююя мшшматвпые схемы д 1я пшенных б\ iobbix c^mikiuiii /„ = /) ° <Ъ i„ п /„ = 11 (h °v ч г, Ф 1 в раз шчиых ба лк ах состоящих и > по бо iee чем дв\хвходовых элементов Ф\пкцпю 1,, б\дем называл. однородной пинеиной фцикит и а ф\нкцшо I,, — не одороднои тис иной франти и Вес рол ibiaibi работы оиюсяия к дв\ м пап])ав юппям — \с 1апов ienino с юлчпос ni тппепных ф\ пкцпп в ])а з шчпых ба зпе ах и оппс аппю стр\ к i \ -ры мпппма ibiibix схем реашзмощпх пшрппыр санкции Д ш оппсаппл ст])Мч!\])ы мпппматьпых схем вво цися понятие cían картою б юка

Стандартны м блоком в базисе В б\ тем называть схем\ S с дв\ мя входами pea ш зл ющ\ ю пшепт ю ф\ пкщпо от тв\ х пе])емеппых (о шородпх ю пти пеодпо])с)дп\ ю) ее ш с юллюсть схемы S в ба зтке В мпппма тьпа с ро-дп всех схем в базисе В pea ти змошпх тппеппмо фмпчцпю от дв\ х переменных (как одпородпмо так п neo пюродщ ю) На рис 1 представтепы стандартные б юкп дтя базиса {i^tj í V <у 7} па рис 2а прете i а в ien е шп-с гвеппып стап тарiыыы б юк д ш ба зпса { < | //} а па рис 26 — едипствеппып стаида])гнын б юк -щя базиса {i —> /у Т}

Отмешм 410 иосколькл l{,(v.ty ; = -ц О'г/ т} (h) Д 1я ба 311-

са {iLij i V t) 7} е\щес1в\ю1 с тапдарт пые б юкп pea лпзмощпе как о ь породнмо так п пеодпоро ш\ю тппеппмо ф\ пкцпю С цэмоп стороны

Вы {(Hiк

а) б)

I'm I

а) б)

Рис 2

< £{^(¿2) II < по )Jом\ в байках {/ |<у}

и {/—>(/ Т| по с\ществ\ел ( тапдарлпых блоков pea пн\ юипгх пооднороь пмо липеппмо ф\ нкшпо

Э unieii i с íaii даргпого б юка pea ш л юишп пшеппмо ф\ пкцпю б\ юм называть ьыюдным Пить в пекоюроп схеме S можно вы то нпь по к \е м\ явдяющл юс я с тан tap гптдм блоком б\ дом говорил в нго л i от с i андар г-пып блок входит в схемл приъи u>vo если выходы в< ох i юмептов б юка .а иск поденном выхо июго по соединены ( о вхо ta ми j домен юв по припал ло/катих б юк\ В основном юкс to нксерыцпп пя каж того конкретною балка приводятся более \добпвю д 1Я работbi опреде клшя стаи lapuioio блока и правп iBiioro вхож юпия (жвива юптпыо вышепрнво тонным)

Ввсд< пае

К)

Структура диссертации. Диссертация сосюш m введения икч m L iлв п списка птюрапры m 30 наименовании Общий обвем щссеры цпи — 1 30 с транпц в рабою содержи к я Г)Т рнечнков Персчпем к об ;ор\ ре ï\ ibia юв по i ывам

В Г iar»e 1 рас с малриваются реализации тпнеппыч булевых функции р. банках сосюящпх из инвертора и пескопжпх ib\хвходовых пометов реалплщпх не пшенные санкции Слолдюслв схем в таких базисах one ипваекя ипс юм дтлхвхо lobbix j icmcmhob в схеме (т с1 инвертор имеем веч равный и\ по а всякий хвходовоп пометы имеет вес равный едипи-це) В с тед\ тощей юореме содержится онпсаиие всех мппима ibiibix схем в таком блике В реализующих лнпечшмо ф\ пкцпю

Теорема 2. /Тюба и минами п>ния <ic\ia в ба>ш( В р< и пи ¡ijioui/i я 1„ и ш 1„ п ^ 2 рспбиьиспн я на п — 1 ucnapcí снаюи^и > ( я с /ииндаршны / б юио<> на )ic()i>i и и í но/поры/ et один) в ( к ш/ и pu ей юно

Для дока {ателье iва леоремы пока ¡ываеня что Ьр,{1И) = Lu(ln) — Зп — 3 Заюм для всякой мппималвпоп схемы S в базисе J3 роалтную щеп пшоппу ю фу пкцпю от п переменных и имеющей сл ру кп р\ oí шмнмо от огшеашюп в теореме \cjanaB шваскя возможное п> удаления чеплрех двухвходовых элементов таким образом чю по i\ цепная схеша ])еа тизхет лнпеннмо санкцию oí // — 1 персчменнон Эю приводит к противоречию с ввтшепрпве тсчшоп оценкой с толдюс ти и дока зыгзаел теорему Доказан1 п>-ство юоремтл основано иск почию твтю па ментоле забивающих копе lain

Г тава 2 посвящена описанию с i р\ к i л ры мппима льпых с хеш pea шз\ ющпх лннештмо санкцию в классическом базисе Т\ = {vSzij г V ij Т) Доказана следующая юорема

Теорема 3. 7юбия мини мшььная г / с ми в ба uta К рсо' ш н)юш,ин 1„ и ш /„ п ^ 2 [мпбнвиенк я на п — J itrnept ( chaioviu i ( я с шандарншы i бюиов h,и яедыи из которой в юдши о е lewy нравнпыю

Список литературы диссертационного исследования кандидат наук Комбаров, Юрий Анатольевич, 2013 год

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

[1] Бтюм Н Оепсеп М Характеристика всех оптпма ibiibix схем и ; фмпдщопа твпых моментов пя одновременного вычпе юппя ЛК1 D и NOR Кпберпеппескпп сборник Новая серия — 1990 — i\lu 27 — С 104-117

7тсрл i \ ¡)с:

121

[2] Власов H В О с ложное ш м\ лвпш ipkccjpnoii санкции в классе скорму л Проблемы leoperiHiec коп кпберпетпкп Ma lepua ты Х\ I Меяч-д\ народной коп(1)ерешиш (Нилчшш Hobi оро i 20-25 июня 2011 i ) Нпдчппп Hobi ород II ;да ie ibc тво Нплчсл ородеко! о roc \ пивереше ia 2011 - С 96-97

[Л] Горелик ЕС Ос юлчггослп реализации элементарных коплдопкцпп п un вюпкцип в балке {д|(/} Проблемв! кпберпеiикп —1973 -26 - С 27-36

[4] Коровин В В Ос южное hi pea пманпп мшверса лвноп фмпчцпп схе-мамп п; с}д пкцпопа лъпых элементов Дпскретпая математика -1995 - Т 7 ввш 2-С 95-102

[5| КочерпшаГ \ О с лолчпос i и pea ли ;ашш э юм(Л11 ajjiibix коп вюпкцпп п дпллонкцнп схемами в пекоюрвгх но пплх балках Маюмапню-( кие вопрос ы кибернетики — 2002 —№11 — С 219-246

[б] Чолчкпп С Л Втасов H В Or i\ бшк1 м\ лвтпплекс ориои ф\пкцпп Вести Моек мг-ла Вычпс лиге 1впая математика и кпберпелпка 2011 - № 2 - С 40-46

|7] Чолчкпп С А. О с тр\ кт\ре мпппма ibiibix схем в ба дк о {Д v -i} ре-аттмогцих пшепп\ ю функцию Тр\ды V Мсдюд народной конференции ,Дискретные модетп в теории \ правтяющих епс тем (Ралми-по 26-29 мая 2003 i ) — M IK raie ibckiih от ют фак\ лвгега BMnlx MTV имени M В Ломоносова 2003 - С 50-51

[8] Ложкин С А Об одном методе пот\ чеппя пплчнпх оценок с ю/киос ш кондаклнглх схем и о некоторгдх мпппмаtbiibix схемах для лшюииых фу пкцпп Сборник трхдов семинара семинара по дне крел поп маю-машке п сю при лолчеппям — M II и-во мехапико-матема m чес кем о фак\ лвIета МГЗ 1997 - С 113-115

[9] 4\ панов О Б Аепмптогпческпе оценки слолчносгп \ прав гяюгцпх систем - M MfV 1984

.'¡ИГС]МТ\-[>cl

|1U

111

|12

|13

jl4

|15 [10

lilis

|19

11а\лв В Дж . Оценка 2.5/? для комбинаторно!'! сложности булевых (|)ункц1111 Кибернетический сборник. — 1979 — № 10. — С 23—14

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

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

Редькин Н. П.. О сложности бучегзых с[д\дллш!"1 с малвш числом едп-Дпскрелпая математика. — 2004. — Т. 10. выи 4 — С. 20-31.

Редвкпн П.П.. О минимальной реализации линейной функции схемой ил ф\ пкцпопальпых элементов Кпберпечч1ка —1971 — 0 — С 31-38

Редькин Н П . Дискретная математика. — М • Фи змал лил. 2009

Редькин Н.П . Об оценках сложности схем п;з мпоговходовв!х ф\чж-цпопал 1Л1ых элементов Дискретная математика. — 2010 — Т 7. вып. 1. — С'. 50-67.

Сопр\пепко Е П.. Об одном классе схем из фупкцпопа жпвгх э юмен-тов Проблемы кибернетики — 1905. — 15 — 117-134.

Сэвидж Дж.. Сложности вычислений — М.: Факлюриа.л. 1998.

Угольников А Б . Классв! Поста — М ' Издательство Центра прн-кладшлх исс чедоваипи при мехаипко-ма л-чматическом фак\ лвгеле .МГУ. 2008

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

[21] Яб юпский С.В.. Введение1 в дискретную математику — М : Паука. 1980.

7шсрих\ })<)

127

[22] Ajtai M ^{-íenniulae 011 finite1 sti uc t mes Vniials of Рте1 and Applied Logic - 1983 - 24 - P 1-48

[23] Aioia S Baiak В Compntal lonal с oniplexitx — a modem appioadi — Canibiiclge Canibiiclge unixeisitx ])iess 2007

[24] Blum N A Boolean finie lion leqimmg hi notwoik size TCS - 198-1

- 28 - P 3 37—34r)

[25] Caidot С Quelques íezultats sui 1 a])phcation de 1 algebie de Boole a la s\ nthese des eneuits a îelais Vim Telecomm — 1952 — 7 M 2 — P 75-84

[20] Denieiiko\ E Knlikox \S An elementan piool oí a 3// — o(n) lowei bound on the с ne mt complexitx of affine chspei sen s Pioc oedings of 30th International Sunposmni on Mathematical Foundations ol Compute l Science (MFCS) Volume 0907 oí Lee tine ¡Notes m Computen Science

— Spinigei 2011 - P 250-203

[27] Fui st M Saxe I Sipstei M Paiih cncuifs and the pol\ noinial time lneiaic lix Mathematical Sx stems t lieon — 1984 — 37 — P 13-27

[28] Ix\ama К Lachish О Moiizunii FI Raz R An explicit low en bound oí 5// — o{n) foi Boolean cncmts Piocecxling oí the 33id STOC 2001

P 399-408

[29] Schnoii С P Zxxei lmeaie miteie Schlanken fui cbe Komplexität Booleschen Funktionen Computing — 1974 — 13 P 153-171

[30] Sloe knien ei L On the combinational eomplexitx of ceitain sunnieMiic Boolevui functions

Math Sx st Th - 1977 - 10 - P 32 3-320

[31] Wegenei I The e omplexit\ of Boolean func fions — Teubnei Sfuttgait \\ lllox-Teubnei Sei Comput Sei 1987

llITCp,lTY¡>cl.

Работы автора гго теме диссертации

|32] Комбаров К) А О мши шальных схемах для чиненных бхлевых функции Вести. Моек ун-та. Мачем. Мехап. — 2011 — № б — С 41-44.

[33] Комбаров К) А. О мипима чьиввх реализациях лппешплх б\ чевввх фу и kiuiii Днскретнвш аиа шч и исч чедоваиие операции — 2012.

- 19. № 3. - С. 30-57

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

[35| Комбаров К) А О с чожиости реализации линейной б\ левой функции в ба.зисе Шеффера - Весив Моск. ун-та Матем. Мехап — 2013 — № 2. - С. 49-53.

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

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

[38] Комбаров Ю А. О минимальных реализациях лппейпых бупевввх функций схемами из с])упкцнопалындх элементов в базисе {.?' —> у. тку} Трудв1 YIII международной конференции ..Дне кретпвю модели в теории управляющих систем" (Москва. 6-9 апреля 2009 i.)

- М . 2009 - С 145-149

[39] Комбаров Ю А О мпппма п»ных реализациях лппейпых бу.ловвзх санкций схемами из функциональных элементов в некотором базисе

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

■/7i-rrcj>iTvpti.

[40j Комбаров К) А О сложности реализации лппеппввх булевв1х ф\лй£ ций в одном базш е - Материалы XI Международного семинара ..Дискретная математика и ее приложения" . посвященного 80-летпю со дня рождения академика О.Б.Луллапова (Москва. 18-28 июня 2012 г) — М.: Изд-во механпко-матемаллщеского факулвтета МГУ. 2012 - С. 131-133.