ОК_Часть_2_2015_(320-328)_v03-09 (1132806), страница 6
Текст из файла (страница 6)
Следовательно, две изоморфные (квазиизоморфные)СФЭ эквивалентны, то есть для СФЭ справедливо неравенство (1.7).Вершина СФЭ называется висячей, если она являетсястоком, но не является выходом схемы. Схема называетсяприведенной, если в ней нет висячих вершин. Заметим, чтосистема формул является приведенной СФЭ, и что из любой СФЭ можно получить эквивалентную ей приведеннуюСФЭ с помощью операции удаления висячих вершин.
Заметим также, что приведенные СФЭ, и только они, получаются из систем квазидеревьев в результате отождествлениянекоторых изоморфных квазиподдеревьев, и что в приведенных СФЭ все вершины лежат на цепях, идущих от входов схемы к ее выходам.Также как и для формул, для каждой СФЭ Σ, Σ ∈ UCБ,определим следующие параметры (функционалы сложности):1. L (Σ) — сложность Σ, то есть число всех ее ФЭ;§4.
СФЭ, оценка числа формул и схем372. D (Σ) — глубина Σ, то есть максимальная глубина еевершин.3. R (Σ) — ранг Σ, то есть число дуг,исходящих из ее входов.Лемма 2.1 обобщается для СФЭ следующим образом.Лемма 4.1. Для приведенной СФЭ Σ, Σ ∈ UC , с однимвыходом, выполняются неравенстваR (Σ) 6 L&,∨ (Σ) + 1 6 L (Σ) + 1 6 2D(Σ) ,(4.1)где L&,∨ — число ФЭ & и ∨ в Σ.С содержательной точки зрения различные функционалы сложности отражают различные параметры моделируемых схем или программ. Так, например, сложность может характеризовать стоимость, размеры или потребляемую мощность СБИС, а также время выполнения программы на одном процессоре.
При этом задержка схемы характеризует время срабатывания СБИС или время выполненияпрограммы на параллельных процессорах. Ранг схемы отражает число обращений программы к памяти, в которойхранятся значения входных БП и т.п.ΦОбозначим через UΦБ (L, n) и UБ [D, n] множество формулF = F (x1 , . . . , xn ) над базисом Б, для которых L (F) 6 L иD (F) 6 D, причем индекс Б0 будем, как обычно, опускать.Заметим, что из неравенства (2.4) вытекает включениеUΦ [D, n] ⊆ UΦ 2D − 1, n .(4.2)Лемма 4.2.
Для любых натуральных n, L, D выполняются неравенства ΦU (L, n) 6 (10n)L+1 ,(4.3) ΦL+1U (L, n) 6 (8n)(4.4), ΦDU [D, n] 6 (8n)2 .(4.5)38Глава 2. Основные классы управляющих системДоказательство. Оценим сверху число попарно не изоморфных (попарно не квазиизоморфных) формул во множествеU Φ (L, n). Для того, чтобы задать с точностью до изоморфизма упорядоченное дерево D, соответствующее формулеF, F ∈ UΦ (L, n), достаточно:1. выбрать упорядоченное двоичное корневое дерево D0 сq, q 6 L, нелистовыми вершинами, в котором вершиныс полустепенью захода 2 помечены ФС &, ∨;2. каждый исток D0 пометить одной из БП x1 , .
. . , xn , авершины с полустепенью захода 1 — ФС ¬.Пронумеруем множество нелистовых вершин дерева D0 числами 1, 2, . . . , q в обратном относительно естественной нумерации τ (см. §1) порядке и сопоставим каждой такой вершине v с полустепенью захода d, d ∈ [1, 2] набор α, α ∈ B d ,где α = (α1 , . . . , αd ) и αj = 1 тогда и только тогда, когдадуга с номером j, входящая в v, начинается с листа дерева D0 .
Заметим, что набор γ = (γ1 , . . . , γL ), где γi — набор, сопоставленный вершине с номером i, если 1 6 i 6 q,и произвольный набор из объединения B 1 ∪ B 2 в случаеi > q, а также набор ФС & и ∨, приписанных тем вершинамvi , 1 6 i 6 L, для которых γi ∈ B 2 , однозначно определяетдерево D0 с точностью до изоморфизма.Следовательно, число упорядоченных деревьев D0 рассматриваемого вида не больше, чем 10L , а число получаемых из него деревьев D не больше, чем nL+1 , так как в силулеммы 2.1R (F) 6 L + 1.Перемножая указанные числа, получаем оценку (4.3). Оценка (4.4) доказывается аналогично с учетом того, что при снятии нумерации с дуг дерева D0 , то есть при рассмотренииформул с точностью до квазиизоморфизма, двоичные наборы длины 2, сопоставленные его вершинам , можно выби-§4.
СФЭ, оценка числа формул и схем39рать из множества {(00) , (01) , (11)} и поэтому число неупорядоченных деревьев D0 рассматриваемого вида не больше,чем 8L .Неравенство (4.5) вытекает из (4.4) и (4.2).Лемма доказана.Следствие 1. Число попарно не квазиизоморфных формулс поднятыми отрицаниями от БП X (n) ранга не больше,чем R, не превосходит (12n)R .Действительно, сопоставим формуле F указанного вида формулу F0 из UΦ{&,∨} от БП x1 , . . . , x2n , которая получается изF заменой каждой её подформулы xi , i ∈ [1, n], формулойxi+n и для которой, в силу (2.4)L F0 = R (F) − 1 6 L − 1.С учётом этих соотношений из доказательства леммы вытекает, что число попарно не квазиизоморфных формул вида F0 , которое, очевидно, равно искомому числу, не больше,чем (12n)R .Лемма 4.3.
Для любых натуральных n и L выполняетсянеравенство CU (L, n) 6 (8 (L + n))L+1 .(4.6)Доказательство. Заметим, что для того, чтобы задать СФЭΣ, Σ ∈ UC (L, n), с точностью до квазиизоморфизма достаточно:1. выбрать её остовное неупорядоченное наддерево D0 cq, q 6 L, нелистовыми вершинами, которые помеченыФС базиса Б0 ;2. присоединить каждый лист D0 либо к одному из n входов Σ, либо к одной из нелистовых вершин D0 , отличной от корня.40Глава 2.
Основные классы управляющих системОценка (4.6) получается из приведенной в лемме 4.2 оценкичисла деревьев D0 и оценки числа способов присоединениякаждого листа D0 путем их перемножения.Лемма доказана.§5Эквивалентные преобразования схем из функциональных элементов и моделирование с ихпомощью эквивалентных преобразований формул. Моделирование эквивалентных преобразований формул и схем в различных базисах, теорема переходаРаспространим введенные в §3 понятия и обозначения напроизвольный класс схем U. В соответствии с определениями из §3 эквивалентность схем Σ0 и Σ00 из U имеет местотогда и только тогда, когда Σ0 и Σ00 реализуют равные системы (матрицы) ФАЛ.
При этом, обычно, предполагается,что соответствующие друг другу полюса (выходы, входы) вΣ0 и Σ00 имеют одинаковые пометки, а эквивалентность Σ0 иΣ00 записывается в виде тождестваt : Σ0 ∼ Σ00 .Для схем из U, как и для формул, определяется ряд«простейших» преобразований, сохраняющих эквивалентностьсхем, которые называются подстановками. Тождествоb0 ∼ Σb 00 ,bt: Σкоторое получается в результате применения одной и тойже подстановки к обеим частям тождества t : Σ0 ∼ Σ00 , называется подстановкой тождества t. Схема Σ0 называетсяподсхемой схемы Σ, еслиV Σ0 ⊆ V (Σ) ,E Σ0 ⊆ E (Σ)§5.
Преобразования на основе тождеств41и любая вершина v, v ∈ V (Σ0 ), которая либо относится кмножеству входов (выходов) Σ, либо служит конечной (соответственно начальной) вершиной некоторого ребра из E(Σ)\E(Σ0 ), является входом (соответственно выходом) Σ0 .Будем считать, что для схем из U, как и для формул,имеет место принцип эквивалентной замены, то есть замеb 0 схемы Σ эквивалентной ей схемой Σb 00 мыняя подсхему Σeполучаем схему Σ, которая эквивалентна схеме Σ. При этомвсе введенные в §3 для случая эквивалентных преобразований формул понятия (однократная и кратная выводимость,полнота системы тождеств и др.), а также связанные с ними обозначения переносятся на случай ЭП схем из U безизменений.
Заметим, что вопрос о существовании конечнойполной системы тождеств (КПСТ) является одним из основных вопросов, связанных с изучением ЭП схем из заданногокласса U.Рассмотрим эти вопросы на примере ЭП СФЭ. Мы будемиспользовать все введенные выше общие понятия и определения, касающиеся ЭП схем, считая подстановкой СФЭ переименование (с возможным отождествлением) ее входныхБП и переименование (с возможным дублированием и снятием1 ) ее выходных БП.Напомним, что формулы представляют собой частныйслучай СФЭ, и для определенности будем считать, что любая формула F из UΦБ является формулой-словом (см. §2), асоответствующую ей формулу-граф, т.
е. квазидерево (см. §2),будем обозначать через F. При этом тождеству t : F0 = F00 ,где F0 и F00 —формулы из UΦБ , будет соответствовать тождество t : F0 ∼ F00 , где F0 и F00 — соответствующие F0 и F00схемы из UCБ , являющееся «схемным» аналогом тождества t.Множество СФЭ вида F, где F ∈ F ⊆ UΦБ , будем обозначать1Под дублированием (снятием) выхода zi СФЭ понимается нанесение на вершину с пометкой zi еще одной выходной БП (соответственноудаление с неё пометки zi )42Глава 2. Основные классы управляющих системx1x2•1x1••2&x2••¬ •∼1¬ z•1x1x2••• ¬• ¬&2•z1 ∨•yz1a)•{∨x1∼ z•1b)ΠKРис. 5.1: тождества tM& и t1,&через F, а систему тождеств вида t, где t ∈ τ , а τ — систематождеств для UΦБ , — через τ .
Так, на рис. 5.1a и 5.1b привеΠKдены тождества tM& и t1,& , являющиеся схемными аналогамиПKвведенных выше формульных тождеств tM& и t1,& .На рис. 5.2a и 5.2b показаны тождество ветвления tBEiи тождество снятия tCEi для функционального элемента Ei , i ∈[1, b], соответственно, а на рис. 5.2c — тождество снятиявхода tCвх . Заметим, что применение тождества снятия равносильно выполнению операции удаления висячей вершинысоответствующего типа (см.
§7). Заметим также, что тожCCдества tBEi , tEi , tвх не являются аналогами формульных тождеств и положим bτБB = tBEi i=1 , bCτБC = tCEi i=1 ∪ tвх .Очевидно, что с помощью этих тождеств можно избавитьсяот всех висячих вершин и всех внутренних ветвлений, имеющихся в СФЭ.
Следовательно, для любой СФЭ Σ, Σ ∈ UCБ,существует ЭП вида Σ |⇒ F, где F — формула (система{τ C ,τ B }формул) изUΦБ.§5. Преобразования на основе тождествx1 . . . xki••ki1ϕi •x1•∼...1ϕi • kiz1z1 , z243xki•ki1 • ϕiz2a)x1 . . . xki••∼x1 . .
. xk i••x1•∼ ∅ϕi •b)c)Рис. 5.2: тождества ветвления, снятия ФЭ и снятия входаb — однократное ЭП для формул изПусть, далее, F 7→ FtUΦБ , где тождество t имеет видt : F0 (x1 , . . . , xn ) = F00 (x1 , . . . , xn ) ,b получается из формулы F заменой подфора формула Fмулы F0 (F1 , . . . , Fn ) формулой F00 (F1 , . .
. , Fn ). Сопоставимэтому ЭП «моделирующее» его однократное ЭП СФЭ виb (см. рис. 5.3). Заметим, что в том случае, когдада F 7→ Σtформулы F0 и F00 являются бесповторными формулами, аb совпадаБП x1 , . . . , xn — их существенными БП, СФЭ Σ00ет с СФЭ F . В остальных случаях из подформулы видаF0 (F1 , . . . , Fn ) формулы F необходимо с помощью тождествτБB сформировать сначала подсхему F0 (F1 , . .
. , Fn ), а затемb могут появитьсяприменить тождество t. При этом в СФЭ Σ44Глава 2. Основные классы управляющих системF1FnF1...F0→−~Fn...tF00F~bΣРис. 5.3: моделирование ЭП формул с помощью ЭП СФЭвисячие вершины или внутренние «ветвления», и тогда дляb необходимо провести ЭП вида Σbb кFb |⇒ F.перехода от Σ{τ C ,τ B }b где F, Fb ∈ UΦ ,Следовательно, для любого ЭП вида F |⇒ F,Бτсуществует моделирующее его ЭП видаFbF.|⇒{B ,τ Cτ ,τББ}На рис. 5.4 показано ЭП СФЭ из UC , которое моделируетЭП (3.1) для формул из UΦ :x1 (x2 x3 ∨ x2 ∨ x3 ) 7→ x1 (x2 x3 ∨ x2 · x3 ) 7→ x1 .tM&tΠK1,&Из описанного выше способа «моделирования» ЭП формул с помощью ЭП СФЭ, а также способа перехода от формул к СФЭ и обратно на основе ЭП с помощью тождествτБB , τБC вытекает справедливость следующего утверждения.Теорема 5.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
