2 (1132838), страница 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Введениефлексивной и транзитивной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, jiM = 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 вместо операциисложения используется операция дизъюнкции.Введение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Введениереализующие равные системы функций, называются эквивалентными. Предполагается, что изоморфные схемы всегда эквивалентны, и поэтому для любого конечного множества схем 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)Введение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), и с корнем 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) равна числуВведениеx1x2•1∨19x1•x3•21•21•∨x3•¬11•1&•wx1x2••••21•w2x111x2•∨••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Введениеего вершин, получим|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 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
