оки2 (С.А. Ложкин - Лекции по основам кибернетики (2014)), страница 5

, fm ), или реализуетсистему булевых уравнений z1 = f1 , . . . , zm = fm , еслиfj , j = 1, . . . , m, — ФАЛ, реализованная в той выходнойвершине СФЭ Σ, которой приписана БП zj .Заметим, что квазидерево, которое соответствует формуле F, реализующей ФАЛ f , а также любая СФЭ, полученная из него отождествлением изоморфных квазиподдеревьев, реализует и формулу F, и ФАЛ f . Так, СФЭ на рис.{0,2,3}3.2 реализует формулу (2.3) и ФАЛ s3(x1 , x2 , x3 ), или{0,2,3}уравнение z1 = s3(x1 , x2 , x3 ).28Глава 2.

Основные классы управляющих системВ соответствии с §1 две СФЭ считаются изоморфными,если они изоморфны как помеченные графы, и эквивалентными, если они реализуют равные системы ФАЛ. Заметим,что СФЭ всегда эквивалентна системе формул, реализуемыхею на своих выходах. Заметим также, что изменение нумерации дуг, входящих в такую вершину v СФЭ Σ, которойсопоставлен ФЭ Ei с симметрической ФАЛ ϕi , не изменяет ФАЛ, реализуемую в вершине v, а значит, не влияет нафункционирование Σ.

Схемы, получающиеся друг из другав результате указанных преобразований, называются квазиизоморфными, а номера дуг, входящих в вершину v с симметрической ФАЛ, как правило, не указываются. Легко видеть, что в соответствующих друг другу вершинах изоморфных (квазиизоморфных) СФЭ реализуются одинаковые (соответственно подобные) формулы, а значит, и одинаковыеФАЛ. Следовательно, две изоморфные (квазиизоморфные)СФЭ эквивалентны, то есть для СФЭ справедливо неравенство (1.7).Вершина СФЭ называется висячей, если она являетсястоком, но не является выходом схемы.

Схема называетсяприведенной, если в ней нет висячих вершин. Заметим, чтосистема формул является приведенной СФЭ, и что из любой СФЭ можно получить эквивалентную ей приведеннуюСФЭ с помощью операции удаления висячих вершин. Заметим также, что приведенные СФЭ, и только они, получаются из систем квазидеревьев в результате отождествлениянекоторых изоморфных квазиподдеревьев, и что в приведенных СФЭ все вершины лежат на цепях, идущих от входов схемы к ее выходам.Также как и для формул, для каждой СФЭ Σ, Σ ∈ UCБ,определим следующие параметры (функционалы сложности):1. L (Σ) — сложность Σ, то есть число всех ее ФЭ;§3.

СФЭ, оценка числа формул и схем292. D (Σ) — глубина Σ, то есть максимальная глубина еевершин.3. R (Σ) — ранг Σ, то есть число дуг,исходящих из ее входов.Лемма 2.1 обобщается для СФЭ следующим образом.Лемма 3.1. Для приведенной СФЭ Σ, Σ ∈ UC , с однимвыходом, выполняются неравенстваR (Σ) 6 L&,∨ (Σ) + 1 6 L (Σ) + 1 6 2D(Σ) ,(3.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 .(3.2)Лемма 3.2. Для любых натуральных n, L, D выполняются неравенства ΦU (L, n) 6 (10n)L+1 ,(3.3) ΦL+1U (L, n) 6 (8n)(3.4), ΦDU [D, n] 6 (8n)2 .(3.5)30Глава 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.Перемножая указанные числа, получаем оценку (3.3).

Оценка (3.4) доказывается аналогично с учетом того, что при снятии нумерации с дуг дерева D0 , то есть при рассмотренииформул с точностью до квазиизоморфизма, двоичные наборы длины 2, сопоставленные его вершинам , можно выби-§3. СФЭ, оценка числа формул и схем31рать из множества {(00) , (01) , (11)} и поэтому число неупорядоченных деревьев D0 рассматриваемого вида не больше,чем 8L .Неравенство (3.5) вытекает из (3.4) и (3.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 .Лемма 3.3. Для любых натуральных n и L выполняетсянеравенство CU (L, n) 6 (8 (L + n))L+1 .(3.6)Доказательство. Заметим, что для того, чтобы задать СФЭΣ, Σ ∈ UC (L, n), с точностью до квазиизоморфизма достаточно:1. выбрать её остовное неупорядоченное наддерево D0 cq, q 6 L, нелистовыми вершинами, которые помеченыФС базиса Б0 ;2.

присоединить каждый лист D0 либо к одному из n входов Σ, либо к одной из нелистовых вершин D0 , отличной от корня.32Глава 2. Основные классы управляющих системОценка (3.6) получается из приведенной в лемме 3.2 оценкичисла деревьев D0 и оценки числа способов присоединениякаждого листа D0 путем их перемножения.Лемма доказана.§4Контактные схемы и π-схемы, оценка их числа. Особенности функционирования многополюсных схемРассмотрим класс контактных схем, в которых реализацияФАЛ осуществляется не с помощью преобразования входных значений в выходные, как это происходит, например, всхемах из функциональных элементов (см.

§3), а в результате передачи значений по ребрам графа, проводимостьюкоторого «управляют» входные БП. Ребро или дуга графа спометкой xi (xi ) называется замыкающим (соответственноразмыкающим) контактом БП xi (см. рис. 4.1).xivssuvsa)xisuvsb)xσisu-c)Рис.

4.1: типы контактовxq ivqqq?a)xq iquvqq 6qqub)Рис. 4.2: физическая интерпретация контактовСчитается, что контакт вида xσi , σ ∈ {0, 1}, проводит§4. Контактные схемы и π-схемы, оценка их числа33тогда и только тогда, когда xi = σ, причем ориентированный контакт, то есть контакт, связанный с дугой, проводиттолько в соответствующем направлении.С точки зрения управления проводимостью неориентированный размыкающий (замыкающий) контакт БП xi функционирует как p-МОП (соответственно n-МОП) транзистор,на затвор которого поступает БП xi (см.

рис. 4.2a и 4.2b), ааналогичный ориентированный контакт — как МОП-транзисторсоответствующего типа с диодом Шоттки [17, 23]. Кроме того, ориентированный контакт вида xσi , идущий из вершиныv в вершину u (см. рис. 4.1c), часто рассматривают как команду условного перехода из v в u, который выполняется,если xi = σ.Сеть Σ с входами a01 , . . . , a0p и выходами a001 , . . .

, a00q , в которой все ребра (дуги) помечены переменными x1 , . . . , xn илиих отрицаниями x1 , . . . , xn , называется (p, q)-контактной схемой (КС) от БП x1 , . . . , xn и обозначается Σ == Σ (x1 , . . . , xn ) или Σ = Σ x1 , . . . , xn ; a01 , . . . , a0p ; a001 , . . . , a00q .При этом число контактов называется сложностью КС Σи обозначается через L (Σ).

На рис. 4.3a–c показаны некоторые конкретные КС от БП x1 , x2 , x3 с входом a1 и выходамиa2 , a3 .Пусть Σ — КС от БП X (n) и α = (α1 , . . . , αn ) — набор из B n . Определим сеть Σ|α как сеть, получающуюсяиз Σ в результате удаления всех ребер (дуг) с пометкамиxα1 1 , . . . , xαnn , то есть ребер, которые не проводят на наборе α, и снятия пометок с остальных ребер Σ. Для вершинv и u КС Σ введем функцию проводимости от вершины vк вершине u как ФАЛ gv,u (x1 , .

. . , xn ), которая равна 1 нанаборе α = (α1 , . . . , αn ) ∈ B n тогда и только тогда, когдав сети Σ|α существует (v − u)-цепь, то есть тогда и только тогда, когда в Σ имеется цепь из проводящих на набореα контактов вида xα1 1 , . . . , xαnn , идущая из v в u. Будем говорить также, что ФАЛ gv,u является функцией достижи-34Глава 2. Основные классы управляющих системvs3sx1s v1v2 sa2a1x1x1x1s v1x2 v2x2a1x1x2v4sx3sa)C2C1sa2C3b)a1 svsx1x1sx2sx3s a3x1x2x3x1x2x3sx2sx3sa2c)Рис.