ОК_Часть_2_2015_(320-328)_v03-09 (1132806), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

. . , vp0 и V 00 =0000= v1 , . . . , vq из множества V (G) графа G определим матрицу достижимости выборки V 0 из выборки V 00 как матрицу M, M ∈ B p,q , для которой(1, если vj00 достижима из vi0 ,M hi, ji =0, в остальных случаях.Заметим, что в случае V 0 = V 00 матрица M является ре-14Глава 2. Основные классы управляющих системфлексивной и транзитивной1 , а если, кроме того, G — неориентированный граф, то и симметричной матрицей. Заметим также, что транзитивность рефлексивной матрицы M ,M ∈ B m,m , имеет место тогда и только тогда, когда2M 2 = M.(1.5)c = M 2 , получимДействительно, полагая Mc hi, ji =Mm_M hi, ti · M ht, ji(1.6)t=1c = M неравенства транзитиви, следовательно, в случае Mностиc hi, ji = M hi, ji > M hi, ti · M ht, jiMбудут выполнены при любых i, j, t из отрезка [1, m].

С другойстороны, из транзитивности рефлексивной матрицы M , всилу (1.6), следует, что _c hi, ji = M hi, ji ∨ M hi, ji · M ht, jiM = M hi, ji .16t6mt6=i,jМатрица достижимости выходной выборки сети из ее входной выборки называется матрицей достижимости этой сети.1Матрица M, M ∈ B m,m , считается рефлексивной (транзитивной)тогда и только тогда, когда она задает рефлексивное (соответственнотранзитивное) отношение на множестве [1, m], то естьM hi, ii = 1(соответственно M hi, ti · M ht, ji > M hi, ji)для любого i (соответственно любых i, j и t) из отрезка [1, m].2Считаем, что при умножении матриц из 0 и 1 вместо операциисложения используется операция дизъюнкции.§1. Основные понятия из теории графов, сетей, схем.15Под «абстрактной» схемой понимается сеть, часть пометок которой составляют входные переменные и в каждойвершине которой реализуется функция (столбец из функций) от этих переменных.

При этом считается, что самасхема реализует систему (матрицу), состоящую из функций (соответственно столбцов функций), реализованных наее выходах. В качестве выходных пометок схемы используются, как правило, специальные выходные переменные,а схема Σ с входными переменными (входами) x1 , . . . , xnи выходными переменными z1 , . . . , zm записывается в видеΣ = Σ(x1 , .

. . , xn ; z1 , . . . , zm ).Номер ν(α) набора α = (α1 , . . . , αn ) из B n считается номером ЭК (ЭД) ранга n от БП X (n) вида xα1 1 · · ·xαnn (соответственно xα1 1∨. . .∨xαnn ), множество всех таких ФАЛ обозначается Qn (соответственно Jn ), а система из всех указанныхФАЛ, упорядоченных по их номерам, называется конъюнктивным (соответственно дизъюнктивным) дешифратором−→порядка n от БП x1 , . . . , xn и обозначается через Qn (соответ−→ственно Jn ). Функция вида_µn (x1 , .

. . , xn , y0 , . . . , y2n −1 ) =xα1 1 · · · xαnn yν(α)α=(α1 ,...,αn )называется мультиплексорной функцией, или, иначе, мультиплексором порядка n, а переменные x = (x1 , . . . , xn ) (y =(y0 , . . . , y2n −1 )) считаются адресными (соответственно информационными) БП мультиплексора µn .Мультиплексорную ФАЛ порядка (n − q) , 0 6 q < n, отадресных БП x00 = (xq+1 , . . . , xn ) и информационных БП y =(y0 , . . . , y2n−q −1 ) часто используют для разложения произвольной ФАЛ f (x1 , .

. . , xn ) по БП x00 (см. разложение Шеннона (2.5) из §2 главы 1).Схему, которая реализует систему ФАЛ Qn (Jn , µn ) будем называть дешифратором (соответственно дизъюнктивным дешифратором, мультиплексором) порядка n. Схемы,16Глава 2. Основные классы управляющих системреализующие равные системы функций, называются эквивалентными. Предполагается, что изоморфные схемы всегда эквивалентны, и поэтому для любого конечного множества схем U выполняется неравенствоkUk 6 |U| ,(1.7)где kUk — число попарно не эквивалентных схем в U.§2Формулы, их структура, эквивалентность испособы задания. Оптимизация подобных формул по глубинеВ §1 главы 1 дано индуктивное определение формулы и реализуемой ею функции.

Напомним его и рассмотрим способпредставления формул алгебры логики с помощью ориентированных упорядоченных деревьев.Пусть, по-прежнему, X = {x1 , x2 , . . . , xn , . . . } — счетныйупорядоченный алфавит входных БП и пусть Б == {ϕ1 , ϕ2 , . . .

, ϕb } — базис, где ФАЛ ϕi , i = 1, . . . , b, зависитот ki , ki > 1, БП и является существенной ФАЛ, если ki > 2.Предполагается, что Б — полный базис (см. §1 главы 1) идопускается, в общем случае, наличие в нем равных ФАЛ.Чаще всего мы будем иметь дело с базисом Б0 = {&, ∨, ¬}.Любая переменная xj из X считается формулой глубины0 или, иначе, тривиальной формулой над базисом Б, которая реализует функцию xj . Если i ∈ [1, b] и для каждогоj, j ∈ [1, ki ], определена формула Fj глубины qj над Б, которая реализует ФАЛ fj , то запись F видаF = ϕi (F1 , . . . , Fki )(2.1)является формулой глубины q над Б, гдеq = max {q1 , . . .

, qki } + 1,(2.2)§2. Формулы, их оптимизация по глубине17которая реализует функцию f вида f = ϕi (f1 , . . . , fki ).Все записи, полученные в результате указанного индуктивного построения, и только они считаются формулами надбазисом Б. При этом формулы, полученные в процессе индуктивного построения формулы F, называются ее подформулами, а те подформулы F1 , . . . , Fki , из которых на последнем шаге индуктивного построения строится формула F вида (2.1), считаются ее главными подформулами.Заметим, что запись подформулы F0 формулы F является частью записи F, причём каждая такая часть считаетсявхождением F0 в F или, иначе, позиционной подформулойвида F0 формулы F, а число указанных частей называетсякратностью F0 в F. Под сложностью (рангом) формулы Fпонимается число вхождений в нее функциональных символов (соответственно символов переменных), которое обозначается через L (F) (соответственно R (F)).Напомним, что «графически» совпадающие формулы считаются изоморфными, а формулы F0 и F00 , реализующие равные функции f 0 и f 00 , называются равными или, иначе, эквивалентными.

При этом равенство вида t : F0 = F00 считаетAся тождеством. Через tKϕ и tϕ будем обозначать тождествокоммутативности и тождество ассоциативности для ФАЛϕ (x1 , x2 ), где ϕ ∈ {x1 · x2 , x1 ∨ x2 , x1 ⊕ x2 , x1 ∼ x2 }(см. §2главы 1).Множество всех формул над базисом Б будем обозначатьΦΦчерез UΦБ и положим UБ0 = U .

Индукцией по глубине любой формуле глубины q над Б можно сопоставить упорядоченное ориентированное корневое дерево глубины q, каждому листу которого приписана БП из X, а каждой внутреннейвершине — функциональный символ (ФС) из Б. Формуле xjглубины 0 сопоставим «тривиальное» дерево с единственной вершиной, являющейся корнем и листом одновременно,которой приписана БП xj (см. рис. 2.1a). Формуле F вида (2.1) сопоставим дерево D глубины q, определяемой ра-18Глава 2.

Основные классы управляющих системвенством (2.2), и с корнем v, показанное на рис. 2.1b, гдеDj , j = 1, . . . , ki — дерево глубины qj с корнем vj , котороесоответствует формуле Fj .•xjD1v1...••1•va)Dkiϕivkikib)Рис. 2.1: представление формулы деревомЗаметим, что формула F по сопоставленному ей деревуD восстанавливается однозначно с точностью до изоморфизма, и что при этом поддеревья дерева D взаимнооднозначносопоставляются позиционным подформулам формулы F. Нарис.

2.2a показано дерево, соответствующее формуле((x1 ∨ x2 ) ∨ x3 ) ∨ (x3 (x1 ∨ x2 ) ∨ x1 x2 ) ,(2.3)которая является формулой глубины 4 над базисом Б0 и{0,2,3}реализует ФАЛ s3.Для удобства будем считать, что в UΦБ входят не толькоотдельные формулы, но и упорядоченные системы (наборы)формул над базисом Б, что каждая такая система реализуетнабор, состоящий из ФАЛ, реализуемых ее формулами, ичто этой системе формул соответствует система из деревьев,сопоставленных ее формулам.Заметим, что ранг R (F) формулы F равен числу листьевсвязанного с ней дерева D, ее сложность L(F) равна числу§2. Формулы, их оптимизация по глубинеx1x2•1∨x1•x3•21•21•∨x3•¬11•1&•wx1x2••••21•w219x111x2•∨••2&&•w•1 21 • 2∨222∨x2•2∨2∨1•w•12•&x3•'•1 ••2∨1¬1z1 ∨∨a)b)Рис.

2.2: представление формулы (2.3) деревом иквазидеревомостальных вершин D, а ее глубина D (F) — глубине его корня. Заметим также, что порядок вхождения БП в записьформулы F при ее просмотре слева направо соответствует последовательности появления БП на листьях связанного с ней дерева,просматриваемых в «естественном» порядке(см. §1).Рассмотрим теперь некоторые соотношения между параметрами формул над базисом Б0 . Заметим, что представляяформулы деревьями, такие соотношения можно доказыватьболее простым и наглядным способом.Лемма 2.1. Для формулы F, F ∈ UΦ , выполняются неравенстваR (F) = L&,∨ (F) + 1 6 L (F) + 1 6 2D(F) ,(2.4)где L&,∨ (F) — число ФС & и ∨ в формуле F.Доказательство.

Сравнивая число ребер, входящих в вершины дерева (формулы) F с числом ребер, выходящих из20Глава 2. Основные классы управляющих системего вершин, получим|E (F)| = 2L&,∨ (F) + L¬ (F) = L (F) + R (F) − 1,где L¬ (F) — число ФС ¬ в формуле F, откуда следует, чтоR (F) = L&,∨ (F) + 1.Второе из соотношений (2.4) легко устанавливается индукцией по D (F).Лемма доказана.Следствие.D (F) > dlog (L (F) + 1)e .(2.5)Для того чтобы выделить набор x = (xi1 , . . . , xin ), который состоит из всех различных БП алфавита X, встречающихся в формуле F и перечисленных в порядке возрастания их номеров, будем записывать ее в виде F = F (x). Приэтом формулу, которая получается из F в результате заменыкаждого вхождения БП xij , j = 1, . .

. , n, формулой Fj будемсчитать результатом подстановки формулы Fj вместо БПxij , j = 1, . . . , n, в формулу F и будем обозначать ее черезF (F1 , . . . , Fn ). Заметим, что формула F (F1 , . . . , Fn ) реализует ФАЛ f (f1 , . . . , fn ), где ФАЛ f (ФАЛ fj ) — ФАЛ, реализуемая формулой F (соответственно Fj , j = 1, . . . , n). Отсюда следует, что если указанную подстановку применитьк обеим частям тождества t : F0 = F00 , где F0 = F0 (x) иF00 = F00 (x), мы получим тождествоb0 = Fb 00 ,bt: Fb 0 = F0 (F1 , . . .

, Fn ) и Fb 00 = F00 (F1 , . . . , Fn ), которое нагде Fзывается подстановкой для тождества t.Из определений следует, что для формул имеет место такназываемый принцип эквивалентной замены. Это означает,§2. Формулы, их оптимизация по глубине21b 0 (вида Fb 00 ) форчто если позиционную подформулу вида Fмулы F заменить, учитывая тождество bt, эквивалентной ейb 00 (соответственно Fb 0 ), то полученная в результаформулой Fте такой замены формула F̌ будет эквивалентна формуле F.Указанный переход от формулы F к формуле F̌ называется(однократным) эквивалентным преобразованием (ЭП) формулы F на основе тождества t, а последовательность однократных ЭП формулы F, выполняемых на основе тождествиз системы τ , считается её (многократным) ЭП на основеэтой системы.Формулы из UΦ , получающиеся друг из друга эквиваKлентными преобразованиями на основе тождеств tK& и t∨ ,AAа также тождеств t& и t∨ , называются подобными.

Легковидеть, что подобные формулы получаются друг из другаперестановкой аргументов и изменением порядка выполнения однотипных двуместных базисных операций, образующих соответствующую многоместную операцию, и поэтомумогут отличаться друг от друга только глубиной.Заметим, что сложность характеризует время вычисления формулы на одном процессоре, а глубина — время ее параллельного вычисления на неограниченном числе процессоров. Поэтому оптимизация подобных формул по глубинеявляется частным случаем «распараллеливания» вычислений.Формулы из UΦ можно оптимизировать также по числуотрицаний с помощью эквивалентных преобразований на основе тождествtM& : (x1 · x2 ) = x1 ∨ x2 ,tM∨: (x1 ∨ x2 ) = x1 · x2 ,tM¬ : (x1 ) = x1— тождеств де Моргана для конъюнкции, дизъюнкции иотрицания соответственно, а также преобразований подобия.

Тождество tM¬ используется при этом для устранения22Глава 2. Основные классы управляющих системнескольких последовательных вхождений ФС ¬ в оптимиMзируемой формуле, а тождества tM& , t∨ — для выполненияпереходаF0 = F1 ◦ · · · ◦ Ft = (F1 · · · Ft ),где (◦, ) ∈ {(&, ∨), (∨, &)} и t > 2, во всех ее максимальных по включению подформулах вида F0 , формируемых спомощью преобразований подобия.Формула, в которой все ФС ¬ встречаются только надБП, называется формулой с поднятыми отрицаниями.

Характеристики

Список файлов лекций