Материалы для подготовки к экзамену прошлых лет, страница 7

Будем говорить, что КС Σ корректируетp, p > 0 обрывов и q, q > 0 замыканий, если она эквивалентна любой КС, получающейся из Σ в результате обрыва не более чем p, и замыкания не более чем qконтактов.Лемма 4.1. Если КС Σ реализует сферическую ФАЛ f из P2 (n), то в Σ встречаются замыкающие контакты всех БП x1 , . . . , xn , причем контакты всех этихтипов, за исключением, быть может, двух, встречаются в ней не менее двухраз.Доказательство. Из сферичности ФАЛ f следует, что она существенно зависит отвсех своих БП и не является антимонотонной ни по одной из них. Следовательно,в Σ имеются замыкающие контакты всех БП x1 , .

. . , xn . Обозначим через a1 и a2полюса КС Σ, а через E1 (E2 ) - множество тех ее контактов, каждый из которыхявляется первым (соответственно последним) замыкающим контактом для какойлибо проводящей цепи КС Σ идущей от a1 к a2 .Докажем, сначала, что E1 ∩E2 = ∅. Действительно, пусть E1 ∩E2 6= ∅ и поэтомув КС Σ имеется контакт K вида xi , 1 6 i 6 n, который является первым (последним) замыкающим контактом проводящей цепи C1 (соответственно C2 ), идущей отa1 к a2 . Для j = 1, 2 обозначим через Cj0 и Cj00 начальную (до контакта K) и заключительную (после контакта K) подцепи цепи Cj .

Пусть, далее, цепь C состоитиз начальной подцепи C10 , контакта K и заключительной подцепи C200 , если цепиC1 и C2 проходят контакт K в одном направлении и состоит из начальной подцепи C10 , которя сразу переходит в заключительную подцепь C200 в противном случае.Заметим, что подцепи C10 и C200 по построению состоят только из размыкающих контактов, среди которых нет контактов вида x̄i и поэтому цепь C будет проводить на§4. Сферические функции31наборе β = (0. . 0} 10 . .

. 0), что противоречит сферичности ФАЛ f .| .{ziДокажем теперь, что каждое из множеств Es , s = 1, 2, содержит замыкающиеконтакты всех БП x1 , . . . , xn за исключением, быть может, одной. Действительно,из сферичности ФАЛ f следует, что для любых i и j, 1 6 i < j 6 n, в КС Σ имеетсяцепь C, идущая из a1 в a2 , которая проводит на наборе γ = (0. . 01} 0 . . .

0 |10 {z. . . 0})| . {zin−j+1и состоит из замыкающих контактов БП xi , xj , а также размыкающих контактовостальных БП. Заметим, что в C не могут отсутствовать замыкающие контакты ниодной из БП xi , xj , так как иначе ФАЛ f обращалась бы в 1 на некотором набореβ, содержащем ровно одну 1. Следовательно, первый из контактов вила xi , xj нацепи C войдет в E1 , а последний - в E2 и поэтому как в E1 , так и в E2 контактывида xi , xj не могут отсутвствовать одновременно. Таким образом, во множествеE1 ∪ E2 не могут отсутствовать замыкающие контакты трех и более БП.Лемма доказана.Следствие 1. Если КС Σ реализует α - сферическую ФАЛ f из P2 (n), где α =(α1 , . . .

, αn ), то контакты всех типов xᾱ1 1 , . . . , xᾱnn встречаются в Σ по крайнеймере t = 1 раз, причем контакты всех этих типов за исключением, быть может,двух встречаются в Σ не менее r = 2 раз.Следствие 2. Если КС Σ корректируетp, p > 0 обрывов, то в условиях следlmp+1ствия 1 имеем t > p + 1 и r > 2 2 , то естьp+1(n − 1)L(Σ) > 2(p + 1) + 22.Теорема 4.1. При любом натуральном n имеют место равенстваLK (s1n ) = LK (snn−1 ) = 3n − 2,а если n > 2, тоLK (ln ) = LK (¯ln ) = 4n − 4.(4.1)Доказательство. Все необходимые верхние оценки могут быть получены с помощью метода каскадов (см., например, §3 из [2, гл.

4]).Пусть КС Σ реализует ФАЛ f = snn−1 . Из того, что ФАЛ sn−1не являетсяnни монотонной ни антимонотонной ни по одной из своих БП, следует что в КСΣ встречаются константы всех типов x1 , . . . , xn , x̄1 , . . . , x̄n . Заметим, что при этомконтакты всех типов x1 , . . . , xn за исключением, быть может, двух встречаются вΣ не менее двух раз.

Действительно, пусть, например, контакты типов x1 , x2 , x3встречаются в Σ только по одному разу. Тогда, подставив константу 1 вместо всех32Глава 2. Синтез схем для индивидуальных функцийБП x4 , . . . , xn , мы получим КС Σ0 , которая реализует сферическую ФАЛ s23 и содержит только по одному замыкающему контакту своих БП, что противоречит лемме4.1.

Следовательно,L(Σ) > 3n − 2.Случай, когда КС Σ реализует ФАЛ f = s1n , сводится к рассмотренному случаюинвертированием БП.Пусть теперь n > 2 и КС Σ реализует ФАЛ f = ln . Из того, что ФАЛ fявляется α - сферической при любом α из B.n , в силу (1.1) и следствия 1 из леммы4.1 вытекает неравенство:2n−2 L(Σ) > 2n−1 (2n − 2),из которого следует, чтоL(Σ) > 4n − 4.Случай, когда f = ¯ln , рассматривается аналогично.Теорема доказана.Для ФАЛ f и p > 0, q > 0 определим «самокорректирующуюся» сложностькак минимальную из сложностей тех КС, реализующих ФАЛ f , которыекорректируют p обрывов и q замыканий.LК(p,q) (f )Теорема 4.2.

При любоых натуральных p и n, n > 2, имеют место равенстваp+1(n − 2),(4.2)LK(l)=4(p+1)+4(p,0) n2LK(1,1) (ln ) = 8n.(4.3)Доказательство. Нижняя оценка в (4.2) доказывается аналогично нижней оценке(4.1) с использованием следствия 2 леммы 4.1. Верхнюю оценку (4.2) в случае p = 1дает схема из [18, гл. 3, §1], которая получается из КС, построенной для линейнойФАЛ по методу каскадов, добавлением 4 контактов. В общем случае p > 1 искомаяКС представляет собой результат параллельногоdbp + 1c 2e указанныхj соединенияkp+1выше самокорректирующихся КС и (p + 1) − 2 2КС, построенных по методукаскадов.Верхнюю оценку в (4.3) дает КС, которая получается в результате последовательного соединения двух упомянутых выше КС для линейной ФАЛ, корректирующих 1 обрыв. Для доказательства нижней оценки заметим, что в силу теоремыо максимальном потоке и минимальном разрезев КС Σ, которая реализует ФАЛf и корректирует p обрывов, для любого набора α, α ∈ Nf , сущестует не менее,чем p + 1 не пересекающихся по контактами проводящих на наборе α цепей, соединяющих полюса Σ.

Если при этом f = lnσ и КС Σ корректирует q замыканий, то§5. Теорема Храпченко33каждая из указанных цепей иемет длину не меньше чем (q + 1)n, и следовательно,|E(Σ|α )| > (p + 1)(q + 1)n(4.4)для любого набора α, α ∈ Nf . Из (4.4) в силу (1.1) при δ = Nf вытекает, чтоσLK(p,q) (ln ) > (p + 1)(q + 1)n. Теорема доказана.§5Теорема Храпченко. Сложность линейной функции в классеπ–схемПод контактной схемой (КС) в данном параграфе будем понимать (1,1) - КС изнеориентированных контактов.

Для множества C, состоящего из t контактов видаxσj11 , . . . , xσjtt , положим K(C) = xσj11 · . . . · xσjtt , J(C) = xσj11 ∨ . . . ∨ xσjttДля КС Σ, реализующей ФАЛ f из P2 (n), через C(Σ) будем обозначать множество проводящих простых цепей Σ, соединяющих ее полюса, а через S(Σ) множество отделимых тупиковых сечений Σ, разделяющих ее полюса (см. [2, §5гл. 2]).

При этом каждому набору α = (α1 , . . . , αn ) из Nf соответствует цепь C,C ∈ C(Σ), состоящая из проводящих на наборе α контактов вида xα1 1 , . . . , xαnn , анабору β = (β1 , . . . , βn из N̄f = B n \ Nf - сечение S, S ∈ S(Σ), состоящее из разомкнутых на наборе β контактов вида xβ̄1 1 , . . . , xβ̄nn . Заметим, что множество S ∩ C,то есть множество общих для S и C контактов не пусто и состоит из контактоввида xαi i , где αi = βi .Результат последовательного (параллельного) соединения КС Σ1 и Σ2 будемобозначать через Σ1 · Σ2 (соответственно Σ1 k Σ2 ). Назовем простейшей π–схемойлюбую КС, состоящую из одного контакта, а затем индукцией по сложности определим π–схему Σ как КС вида Σ1 · Σ2 или Σ1 k Σ2 , где Σ1 , Σ2 — π–схемы.Лемма 5.1.

Для π–схемы Σ любая цепь C, C ∈ C(Σ), и любое сечение S, S ∈ S(Σ)имеют ровно один общий контакт.Доказательство. Проведем индукцию по стороению π–схемы Σ. В случае, когдаΣ - простейшая π–схема, состоящая из одного контакта, утверждение леммы, очевидно, выполняется. Докажем справедливость индуктивного перехода.Отметим, сначала, что для произвольных КС Σ1 и Σ2 выполняются равенства:C(Σ1 · Σ2 ) = {C | C = C1 · C2 , где K(C) 6= 0 и Ci ∈ C(Σi ), i = 1, 2}(5.1)S(Σ1 · Σ2 ) = S(Σ1 ) ∪ S(Σ2 )(5.2)C(Σ1 k Σ2 ) = C(Σ1 ) ∪ C(Σ2 )(5.3)S(Σ1 k Σ2 ) = {S | S = S1 ∪ S2 , где J(S) 6= 1 и Si ∈ S(Σi ), i = 1, 2}(5.4)34Глава 2.

Синтез схем для индивидуальных функцийДействительно, любая цепь C из C(Σ1 · Σ2 ) имеет вид C = C1 · C2 , где Ci ∈ C(Σi ),i = 1, 2, и K(C1 ) · K(C2 ) 6= 0, а любое сечение S из S(Σ1 · Σ2 ) совпадает либо снекоторым сечением S1 из S(Σ1 ), либо с некоторым сечением S2 из S(Σ2 ).Заметим, что при этомC ∩ S = Ci ∩ Si ,где S = Si , и, следовательно, если КС Σ1 , Σ2 являются π–схемами, удовлетворяющими условиям леммы, то π–схема Σ1 · Σ2 тоже будет им удовлетворять. Аналогичным образом доказываются равенства (5.3), (5.4), и устанавливается справедливость индуктивного перехода в случае π–схемы вида Σ1 k Σ2 .Лемма доказана.Для пересекающихся подмножеств N0 и N00 множества B n обозначим черезR(N0 , N00 ) множество всех пар (α, β), состоящих из соседних по какой-либо БПx1 , . . .