Lectionc3 (С.А. Ложкин - Лекции по основам кибернетики (2007)), страница 7

. ∨ gp ,где gi ∈ G при всех i, i = 1, . . . , p. Стандартный способ построения таких множеств связан с разбиениями единичногокуба.Пусть Π = (π1 , . . . , πp ) — разбиение куба B m , и пусть длявсех i, i = 1, . . . , p, ФАЛ ψi (x1 , . . . , xm ) — характеристическая ФАЛ множества πi , а G(i) — множество всех тех ФАЛ46Глава 3. Синтез и сложность управляющих системg, g ∈ P2 (m), которые обращаются в 0 вне πi . Заметим, чтомножество ФАЛ G видаG = G(1) ∪ . . . ∪ G(p)является ДУМ порядка m и ранга p. Действительно, любаяФАЛ g, g ∈ P2 (m), может быть представлена в видеg = g1 ∨ .

. . ∨ gp ,(6.1)где gi = ψi g и, следовательно, gi ∈ G(i) для всех i, i = 1, . . . , p.Заметим также, что мощность множества G(i) , i = 1, . . . , p,равна 2si , где si = |πi |, и что множество G(i) ∩ G(j) состоит из ФАЛ, тождественно равной 0, если 1 6 i < j 6 p.Следовательно,p pXX (i) λ = |G| =2si 6 p2s ,G − (p − 1) 6i=1i=1гдеs = max si .16i6pУказанное ДУМ G будем называть стандартным ДУМпорядка m и высоты s, гдеs 62m ,(6.2)если выполнены соотношения1.p=2m,ss1 = s2 = · · · = sp−1 = s,sp = 2m − (p − 1) s 6 s.(6.3)§6. Метод Лупанова синтеза СФЭg1 g2 . . .g2s g2s +1.

. .g2s+1 −1 . . . g(p−1)(2s −1)+2. . . gλx1 x2 . . . xm−1 xm... 00 0 01 0 0 ... 0...π1 ............π2 ...πp−1 πp 0 1 ... 10...0...0...00 0 .... . .. . .. . .0 0 ...1...0...0.........0...00...0.........0...1.........0 0 ... 01...1...0...00 0 ....

. .. . .. . .0 0 ...0...0...1.........0...01...0.........0...0...............47......0...0...0...0...0.........0...00...0.........0...0.........0......0 0 .... . .. . .. . .0 0 ......0 0 ... 00...0...1...1...0 0 .... . .. . .. . .0 0 ...0...0...0.........0...00...0.........1...0.........o2s/o/O...2s −1s=s2...0...O00 0 ... 0...s=s10......Oos2 p −1s=sp−10Osp 6s0/Рис. 6.1: к определению дизъюнктивно-универсальногомножества2. Π = (π1 , .

. . , πp ) — разбиение куба B m на последовательные отрезки, то есть такое разбиение, что номерлюбого набора из множества πi меньше номера любого набора из множества πj , если i < j.Компоненты разбиения Π будем при этом называть полосами ДУМ G, а ФАЛ ψ1 , . . . , ψp — его характеристическими ФАЛ. Заметим, что характеристические ФАЛ попарноортогональны, то есть одновременно в 1 не обращаются, ипринадлежат G.

Заметим также, что представление (6.1) в48Глава 3. Синтез и сложность управляющих системслучае стандартного ДУМ G равносильно представлению:g = ψ1 g1 ∨ ψ2 g2 ∨ · · · ∨ ψp gp(6.4)Таблица значений ФАЛ стандартного ДУМ G приведена нарис. 6.1.Из построения и отмеченных выше свойств стандартногоДУМ вытекает справедливость следующего утверждения.6.1. Для любых натуральных p, m и s, где p =Лемма2m,существуетДУМ G порядка m и ранга p такое, что:s1.

λ = |G| 6 p2s ;2. в G имеется система из p ортогональных ФАЛ ψ1 , . . . , ψp ,обладающих тем свойством, что для любой ФАЛ g,g ∈ P2 (m), и некоторых ФАЛ g1 , . . . , gp из G справедливо не только представление (6.1), но и представление (6.4).Теорема 6.1. Для любой ФАЛ f, f ∈ P2 (n), существуетреализующая ее СФЭ Σf , Σf ∈ UC , такая, что5 log n + O (1)2nL (Σf ) 61+.(6.5)nnДоказательство. Пусть x0 = (x1 , . . . , xq ), x00 = (xq+1 , . . . , xn )и fσ00 (x0 ) = f (x0 , σ 00 ) для всех σ 00 из B n−q . Пусть, далее,Σ00 — мультиплексор порядка (n − q) от адресных БП x00 иинформационных БП y = (y0 , .

. . , y2n−q −1 ), который построен в соответствии с леммой 1.6, представляет собой формулуFn−q и реализует мультиплексорную ФАЛ µn−q (x00 , y).Пусть s — некоторый параметр, удовлетворяющий (6.2),а G — стандартное ДУМ порядка m = q и высоты s, удовлетворяющее требованиям леммы 6.1. Обозначим через ΣG→−СФЭ, которая реализует систему ФАЛ G и представляет§6. Метод Лупанова синтеза СФЭ49собой объединение схем, построенных для каждой из них всоответствии с леммой 1.2.

Заметим, что, в силу леммы 1.3,(1.3) и леммы 6.1, выполнены неравенстваL Σ00 6 4 · 2n−q ,(6.6)L (ΣG ) 6 3p2s+q .Схема Σ0 содержит СФЭ ΣG в качестве подсхемы и реализует каждую ФАЛ fσ00 (x0 ), где σ 00 ∈ B n−q , на одном из своих выходов как ФАЛ g (x0 ) вида (6.1) с помощью СФЭ из(p − 1) ФЭ ∨, входы которой присоединены к соответствующим выходам ΣG . Искомая СФЭ Σf имеет вид Σf = Σ00 (Σ0 )и реализует ФАЛ f в соответствии с разложением (2.4). Длянее, в силу (6.6), будут выполняться неравенстваL (Σf ) 6 2n−q (p − 1) + L Σ00 + L (ΣG ) 66 2n−q (p − 1) + 4 · 2n−q + 3p2s+q ,из которых, выбрав значения параметровs = dn − 5 log ne ,m = q = d2 log ne ,удовлетворяющие (6.2), в соответствии с леммой 6.1 получим n2n2L (Σf ) 6+O=n − 5 log nn25 log n + O (1)2n1+.=nnТеорема доказана.Следствие.

Из (6.5) и (5.10) (см. также следствие 1 изтеоремы ??) вытекает, чтоLC (n) ∼2n.n50Глава 3. Синтез и сложность управляющих системОтметим, в заключение, что в соответствии с (6.5) иследствиями из теорем ??, 6.1 сложность LC (f ) для почтивсех ФАЛ f, f ∈ P2 (n), асимптотически равна функцииШеннона LC (n), то есть сложности самой сложной ФАЛ изP2 (n). Тем самым, в отличие от класса ДНФ (см. §7 главы 1), в классе схем UC имеет место т. н. эффект Шеннона — асимптотическое равенство сложности почти всех ФАЛи сложности самой сложной ФАЛ от заданного числа БП,стремящегося к бесконечности.§7Асимптотически наилучший метод синтезаконтактных схемЗаметим сначала, что асимптотически наилучший метод синтеза СФЭ из §6 без существенных изменений переносится накласс контактно-вентильных схем (КВС), в которых нарядус контактами можно использовать «вентили», то есть ориентированные ребра, проводящие только в направлении своейориентации.

Действительно, для любой ФАЛ f , f ∈ P2 (n),e f может быть получена на осреализующая ее (1, 1)-КВС Σнове разложения 2.4 так же, как и СФЭ Σf из теоремы 6.1.Она является результатом корректной суперпозиции (см. §9e f = Σ00 (Σ0 ), где Σ00 — (2n−q , 1)-КД от БПглавы 2) вида Σ00n−qx , а (1, 2 )-КВС Σ0 реализует систему всех ФАЛ видаfσ00 (x0 ) , σ 00 ∈ B n−q . При этом схема Σ0 по-прежнему содержит в качестве подсхемы (1, λ)-КС ΣG , реализующую систе→−му ФАЛ G на основе леммы 1.2, и реализует каждую ФАЛg (x0 ) типа fσ00 (x0 ) на основе ее представления 6.1 в видедизъюнкции g = g1 ∨ · · · ∨ gp с помощью присоединения входов вентильной звезды порядка p к соответствующим выходам КС ΣG (см. рис. 7.1a, а также рис. 9.2c из главы 2),которое является корректной суперпозицией.

Сложность поe f при тех же значениях параметров, что истроенной КВС Σ§7. Асимптотически наилучший метод синтеза КСqqqqqqqqqqqqqqΣG1 •qMMMMMMMMMMMMMMM51gN1• NNNNNN.. NNNr•9& g. rrrrrrrrr•...gpa)qqqqqqqqqqqqqqΣG1 •MqMMMMMMMMMMMMMMgN1• NNNNψNN1.. NNNr• g. rrrrrrrψprr•...gpb)Рис. 7.1: Корректная реализация дизъюнкции ФАЛg1 , . . . , gp в классах КВС и ИКСв теореме 6.1, будет удовлетворять неравенству 6.5.Напомним (см. §6), что в силу специфики стандартногоДУМ G вместо представления 6.1 для ФАЛ g можно использовать эквивалентное 6.1 представлениеg = ψ1 · g1 ∨ · · · ∨ ψp · gp(7.1)и на его основе реализовать ФАЛ g с помощью корректной суперпозиции т.н. итеративно-контактных схем, показанной на рис.

7.1b, где ФАЛ ψ1 , . . . , ψp управляют проводимостью соответствующих контактов. Асимптотически наилучший метод синтеза КС связан с «моделированием» этойсуперпозиции и представления 7.1 на компонентах подходящего m-регулярного разбиения куба B m+p .52Глава 3. Синтез и сложность управляющих систем. . . xm−1 xm ψ1 x1 0 ... 010... 0101.....π1....1...0...0.....π2....0.........0...0.....πp....1110ψ200...011...1.... . .

ψp00... ...000... ...0... ...00.. . . ..011...1δ̌a)qq g1qqqq•MMM xαm+1qMMm+1qqqMMMqqqM..qΣG1 qMMMMq.qqMMMǧqqMMMqqq αm+p•q xm+pMMMMM gpb)Рис. 7.2: m-регулярное множество δ̌ и связанная с нимсуперпозиция КС§7. Асимптотически наилучший метод синтеза КС53Пусть δ̌ — m-регулярное множество наборов куба B m+p ,→−соответствующее системе ФАЛ ψ = (ψ1 , . . . , ψp ) (см. рис. 7.2a),а ∆ = (δ1 , .

. . , δ2p ) — построенное для нее по лемме 5.1 разбиение куба B m+p . Заметим, что любая ФАЛ g, g ∈ P2 (m + p),на любой компоненте этого разбиения вида δ̌ ⊕ α, гдеα = (0, . . . , 0, αm+1 , . . . , αm+p ),| {z }mсовпадает с ФАЛααm+pm+1· g1 ∨ . . . ∨ xm+p· gp ,ǧ = xm+1(7.2)где gi = gψi ∈ G(i) , i = 1, . . . , p. При этом ФАЛ ǧ может быть реализована в результате операции присоединеαm+pαm+1ния звезды из контактов вида xm+1, . . .

, xm+pк выходам→−(1, λ)-КС ΣG , реализующей систему ФАЛ G , так, как этопоказано на рис. 7.2b. Заметим также, что указанная операция суперпозиции является корректной на множестве наборов δ̌ ⊕α в силу разделительности присоединяемой (p, 1)-КСна этом множестве.Теорема 7.1 (ср. [14]). Для любой ФАЛ f , f ∈ P2 (n), существует реализующая ее КС Σf такая, что12n1+O √(7.3)L (Σf ) 6nnДоказательство.