О.Б. Лупанов - Элементы математической кибернетики (1161667), страница 6
Текст из файла (страница 6)
Без ограничения общности считаем, что врезультате использования контактов x1 , x1 , x2 , x2 , x3 , x3 и xσ3 реализуется функция x1 ⊕ x2 ⊕ x3 ⊕ ε. Если ε = 0, то получаем противоречиес доказанным ранее; если ε = 1, то вместо x1 подставим x1 — распределение контактов не изменится, а реализуемая функция изменится наx1 ⊕ x2 ⊕ x3 , что опять–таки невозможно. Итак, µ(4) > 4 и λ(3) > 8.Теперь неравенство (8) доказывается по индукции.
Базисом является случай n = 4 (но не n = 3, как было отмечено выше):λ(4) > µ(4) + λ(3) > 4 + 8 = 4 · 4 − 4.Допустим теперь, что λ(n) > 4n − 4 для n > 5. Тогдаλ(n + 1) > µ(n + 1) + λ(n) >> µ(4) + 4n − 4 > 4 + 4n − 4 = 4(n + 1) − 4,что и доказывает справедливость оценки (8).29Глава 3Параллельно–последовательныесхемы§ 3.1. Основные понятияОпределим параллельно–последовательную схему (π–схему) следующим образом.
Пусть одно ребро есть параллельно–последовательнаясеть. Если A и B — параллельно–последовательные сети, то ипараллельное, и последовательное их соединения также являются параллельно–последовательными сетями. Других параллельно–последовательных сетей нет. Параллельно–последовательная схема (π–схема) есть схема, сеть которой является параллельно–последовательной. Параллельно–последовательным схемам можно поставить в соответствие формулы FA и FB , тогда FA ∨ FB будет отвечать параллельному их соединению, а FA &FB — последовательному.Если вхождение переменной xi — это число символов xi и xi в схеме,то под расширенным вхождением переменной будем понимать формулу, содержащую кроме этой переменной и другие переменные внутритекущих скобок.Сложность Lπ (S) π–схемы S определяется как число входящих всхему символов переменных (но не как число операций).
ЗатемLπ (f ) = min Lπ (S).S=S(f )Принимаем, что Lπ (0) = 0 и Lπ (1) = 0. Можно сразу считать, что формулы, соответствующие π–схемам, приведены к такому виду, в которомлибо не содержатся константы 0 и 1, либо не содержатся переменные.30Если π–схеме S соответствует формула Φ, реализующая функцию f ,то сложность L(Φ) формулы Φ определяется так же, как сложностьLπ (S) схемы S, и аналогичноL(f ) = min L(S).Φ=Φ(f )§ 3.2. Нижние оценки сложности. МетодыСубботовской и ХрапченкоТеорема 5.
Пусть f (x1 , . . . , xn ) — произвольная булева функция, существенно зависящая от двух и более переменных. Тогда найдетсяпеременная xj такая, чтоL(f ) >1L(f |xj =α )1 − n1(9)13 L(f |xj =β ),1 − 2n(10)для любого α ∈ {0, 1}, иL(f ) >где β ∈ {0, 1} — некоторая константа.Доказательство.
1. Пусть m — число вхождений переменной xj впроизвольной минимальной формуле Φ сложности L(f ), тогдаm>L(f ).nПодставив константу вместо переменной xj , получим некоторую формулу Φ∗ . В результате ее упрощения может получиться константа (тогда (9) выполняется автоматически), а общем же случае по сравнениюс Φ сложность уменьшится по крайней мере на m:L(f |xj =α ) 6 L(Φ∗ ) 6 L(f ) −L(f ).nОтсюда вытекает оценка (9).2. Аналогично, возьмем минимальную формулу Φ функции f с числом вхождений переменной xj равным m, по причине чегоm>L(f ).n31Рассмотрим какое–либо вхождение переменной xj . Его общий вид таков: xσj ◦ Ψ, где Ψ — некоторая подформула, ◦ — либо конъюнктивная,либо дизъюнктивная операция.
Покажем, что для различных вхождений xj соответствующие формулы Ψ не пересекаются. Предположим,что это не так, и Ψ содержит некоторую подформулу Ψ′ того же вида,т. е. Ψ′ = xαj ◦′ Ψ∗ . Получается, что формула Φ допускает упрощенияпо переменной xj , что само по себе противоречит минимальности формулы Φ.Найдется такое значение xj , при котором формула xσj ◦ Ψ обратитсяв константу.
При этом сложность уменьшится, во-первых, как минимум на m, и во-вторых (в отличие от случая 1), как минимум на m/2благодаря подформуле Ψ. Значит в итоге уменьшение составит 3m/2и более, откуда3L(f ).L(f |xj =β ) 6 L(f ) −2nТеорема доказана.Следствие 1.n3/2 a L(ln ),ln (x1 , . . . , xn ) = x1 ⊕ · · · ⊕ xn .Доказательство. Согласно (10)L(ln ) >13 L(f |xj =β )1 − 2nдля некоторых β и xj . В результате замены одной из переменных константой формула станет реализовывать либо функцию ln−1 , либо функцию ln−1 , поэтому есть смысл применить оценку (10) и для L(f |xj =β ):L(ln ) >111···3 ·33 · 1,1 − 2n 1 − 2(n−1)1 − 2·2где 1 есть сложность реализации xi или xi .
Так как1> e−x ,1+xтоL(ln ) > expСледствие доказано.n3X12i=2i!> exp 3232Zn21 n3/2dx = √ .x2 2Сечением T параллельно–последовательной схемы S будем называть такое подмножество контактов схемы, что любая цепь схемы Sсодержит хотя бы один контакт из T . Под цепью понимаем любуюнесамоперескающуюся цепь в S. Тупиковое сечение при удалении произвольного контакта перестает быть сечением.Лемма 4. Любая цепь и любое тупиковое сечение произвольной π–схемы содержат ровно один общий контакт.Докажем индукцией по числу контактов схемы. Для схемы с однимконтактом утверждение леммы выполняется тривиальным образом.Предположим, что оно верно для схемы с не более чем m контактами.Рассмотрим схему S сложности m + 1. Существует две возможности.1) Схема S представляет собой последовательное соединение схемменьшей сложности.
Если взять цепь, соединяющую полюсы схемы, топо предположению индукции она будет пересекать тупиковое сечениеодной из схем (оно в этом случае будет тупиковым сечением и для всейсхемы S).2) Схема S является параллельным соединением схем меньшейсложности. В этом случае тупиковое сечение схемы S будет тупиковым сечением для каждой из параллельно соединенных схем меньшейсложности. А для схем меньшей сложности справедливо предположение индукции.
Лемма доказана.Пусть Nf1 — произвольное подмножество множества Nf единицфункции f , а Nf0 — произвольное подмножество множества En2 \ Nfнулей функции f . Обозначим через Rf множество пар (σ̃, σ̃ ′ ) соседних наборов σ̃ ∈ Nf1 , σ̃ ′ ∈ Nf0 . Пару (σ̃ (0) , σ̃ (1) ), где σ̃ (0) ∈ Nf0 , σ̃ (1) ∈ Nf1 ,будем называть ребром по j–му направлению, если эти наборы отличаются только по j–й компоненте.Теорема 6. Для произвольной функции f (x1 , . . .
, xn ) и подмножествNf0 и Nf1 справедливо|Rf |2L(f ) >.(11)|Nf0 | · |Nf1 |Доказательство. Обозначим через mj число контактов по j–й переменной в π–схеме S, реализующей функцию f . Будем считать, что S —минимальная схема, т. е. L(S) = L(f ). Пусть σ̃ 0 ∈ Nf0 , σ̃ 1 ∈ Nf1 .
Набору σ̃ 1 = (σ11 , . . . , σn1 ) поставим в соответствие какую–либо цепь в S, соσ1σ1держащую контакты x1 1 , . . . , xnn . Аналогично, набору σ̃ 0 = (σ10 , . . . , σn0 )33ставится в соответствие какое–либо тупиковое сечение схемы S. Если (σ̃ 0 , σ̃ 1 ) ∈ Rf , сопоставим паре (σ̃ 0 , σ̃ 1 ) контакт с номером i, принадлежащий и цепи, и тупиковому сечению (по лемме 4 он определенединственным образом). Все контакты j–й переменной занумеруем следующим образом: 1, 2, . . .
, mj . Причем i–му контакту j–й переменнойможет соответствовать несколько пар (σ̃ 0 , σ̃ 1 ). Общее число подобныхпар обозначим через aji . Пусть число ребер, которым сопоставленыконтакты j–й переменной, естьrj =mjXaji ,i=1тогда|Rf | =nXrj ,L(S) =j=1nXmj .j=1Построим соответствующие множествами Nf0 матрицы M 1 и M 0 .1. M 1 — матрица цепей (|Nf1 | × n). Заменим j–ю компоненту набора σ̃ 1 на противоположную.
Обозначим полученный в результате наборчерез τ̃ . Если τ̃ содержится в Nf0 , то ему соответствует некоторое тупиковое сечение, которое в свою очередь по лемме 4 пересекает цепьσ̃ 1 по единственному контакту, например, i–му. Итак, если τ̃ ∈ Nf0 , тов j–м разряде строки σ̃ 1 ставится i, иначе ставится прочерк.2. M 0 — матрица тупиковых сечений (|Nf0 | × n). Аналогично заполним эту матрицу. Инвертируем j–ю компоненту набора σ̃ 0 и обозначимполученный набор через ρ̃. Если ρ̃ содержится в Nf1 , то ему соответствует некоторая цепь, которая пересекает тупиковое сечение σ̃ 0 поконтакту номер i′ .
Если ρ̃ ∈ Nf1 , то в j–м разряде строки σ̃ 0 ставитсяi′ , иначе ставится прочерк.3. Построим теперь матрицу N размера |Nf0 | · |Nf1 | × n. В j–м разряде строки (σ̃ 0 , σ̃ 1 ) ставится или пара (i′ , i) для номеров i′ , i соответственно из матриц M 0 , M 1 , или прочерк.Номер i встречается в j–м столбце матрицы M 1 ровно aji раз. Аналогично для номера i′ и матрицы M 0 . Соответственно, в j–м столбцематрицы N дубль (i, i) встречается a2ji раз.
Причем, разные дубли немогут встречаться в одной и той же строке матрицы N, так как иначецепь и тупиковое сечение перескались бы по нескольким контактам,что невозможно. Тогда общее число дублей (kj , kj ) в j–м столбце естьa2jkj , а всего различных дублей в матрице N будетNf1mjn XXj=1 i=134a2ji .И их число не должно превышать число всех строк:mjn XXj=1 i=1a2ji 6 |Nf0 | · |Nf1 |.Применим для|Rf |2 =nXj=1rj!2=mjn XXajij=1 i=1!2неравенство Коши — Буняковского:! n mj !mjn XXXX1 6 |Nf0 | · |Nf1 | · L(S).a2ji|Rf |2 6j=1 i=1j=1 i=1Отсюда следует (11). Теорема доказана.Рассмотрим пример.
ПустьN 0 = {(σ1 , . . . , σn )|σ1 ⊕ · · · ⊕ σn = 0}иN 1 = {(σ1 , . . . , σn )|σ1 ⊕ · · · ⊕ σn = 1}для линейной функции ln (x1 , . . . , xn ). Следовательно, |N 0 | = |N 1 | = 2n−1 .Поэтому число пар четных“ и нечетных“ наборов будет равно 2n−1 n,””т. е. |R| = 2n−1 n. Значит, согласно теореме 6 имеем следующую нижнюю оценку сложности: L(ln ) > n2 .Пусть n = 2m для некоторого m. Отметим справедливость равенстваln1 +n2 (x1 , . .
. , xn ) = ln1 (x1 , . . . , xn1 ) ⊕ ln2 (xn1 +1 , . . . , xn2 ) == ln1 (x1 , . . . , xn1 )ln2 (xn1 +1 , . . . , xn2 ) ∨ ln1 (x1 , . . . , xn1 )ln2 (xn1 +1 , . . . , xn2 ).ОтсюдаL(ln1 +n2 ) 6 2L(ln1 ) + 2L(ln2 ),или в случае n = 2m :L(l2m+1 ) 6 4L(l2m ).По индукции можно доказать, чтоL(l2m ) 6 4m .35В самом деле, L(l20 ) = 1, и индукционный переход:L(l2m+1 ) 6 4L(l2m ) 6 4m+1 .Пусть 2m < n 6 2m+1 . Представим ln в видеln (x1 , . .
. , xn ) = l2m+1 (x1 , . . . , xn , 0, . . . , 0).ТогдаL(ln ) 6 L(l2m+1 ) 6 4m+1 = (2m+1 )2 < 4n2 .Поэтому имеем, что в общем случаеn2 6 L(ln ) 6 4n2 ,хотя, впрочем, можно показать, что существует более точная верхняяоценка:9L(ln ) < n2 .8Пусть n = 2m + 1. Введем функцию fˆ такую, чтоfˆ(σ̃) =σ1 + · · · + σn > m + 1,σ1 + · · · + σn 6 m.0,1,Для двоичных наборов σ̃, аналогично, |N 0 | = |N 1 | = 2n−1 . Ребер, соответствующих σ1 + · · · + σn = m + 1, будет√22m+1m+1|R| = C2m+1(m + 1) ∼ C √ (m + 1) ∼ C22m+1 m,mгде C = const. По теореме 6 нижняя оценка√|R|2(C22m+1 m)2∼∼ 4Cm ∼ 2Cn|N 0 ||N 1 |(22m )2получается линейной.Вообще говоря, сложность схемы оценивается снизу величинойC′nlog2 nгде C ′ = const (оценка Нечипорука).362,Глава 4Системы эквивалентныхпреобразованийБудем рассматривать формулы над множеством {&, ∨, ¬, x, 0, 1}, удовлетворяющие следующим правилам.1◦ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
