Lectionc2 (1132951), страница 3
Текст из файла (страница 3)
С другойстороны, из транзитивности рефлексивной матрицы M , всилу (1.6), следует, что _c hi, ji = M hi, ji ∨ = M hi, ji .MMhi,ji·Mht,ji16t6mt6=i,jМатрица достижимости выходной выборки сети из ее входной выборки называется матрицей достижимости этой сети.Под «абстрактной» схемой понимается сеть, часть пометок которой составляют входные переменные и в каждойтогда и только тогда, когда она задает рефлексивное (соответственнотранзитивное) отношение на множестве [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 ).Схему, которая реализует систему ФАЛ Qn (Jn , µn ) будем называть дешифратором (соответственно дизъюнктивным дешифратором, мультиплексором) порядка n. Схемы,реализующие равные системы функций, называются эквивалентными. Предполагается, что изоморфные схемы всегда эквивалентны, и поэтому для любого конечного множества схем U выполняется неравенствоkUk 6 |U| ,(1.7)где kUk — число попарно не эквивалентных схем в U.Рассмотрим, в заключение, оценки числа сетей из некоторых классов.Лемма 1.1. Число попарно неизоморфных корневых двоичных ориентированных упорядоченных (неупорядоченных)деревьев с не более, чем p, нелистовыми вершинами не превосходит 6p (соответственно 5p ).Доказательство.
Возьмем произвольное упорядоченное дерево D рассматриваемого вида и пронумеруем множествоего нелистовых вершин V̂ с помощью естественной нумерации τ (см. выше) числами 1, 2, . . . , q, где q = |V | 6 p.Сопоставим каждой вершине v из V̂ с полустепенью заходаd, d ∈ [1, 2] набор α, α ∈ B d , где α = (α1 , . . . , αd ) и αj = 1тогда и только тогда, когда дуга с номером j, входящая в v,начинается с листа дерева D.16Глава 2.
Основные классы управляющих системЗаметим, что набор γ = (γ1 , . . . , γp ), где γi — набор, сопоставленный вершине из V̂ с номером i, если 1 6 i 6 q, ипроизвольный набор из объединения B 1 ∪ B 2 в случае i > q,однозначно определяет дерево D с точностью до изоморфизма. Следовательно, число упорядоченных деревьев рассматриваемого вида не больше, чем 6p .Легко видеть, что при снятии нумерации с дуг дерева Dдвоичные наборы длины 2, сопоставленные его вершинам изV̂ , можно выбирать из множества {(00) , (01) , (11)} и поэтому число неупорядоченных деревьев рассматриваемого видане больше, чем 5p .Лемма доказана.Следствие.
Если в условия леммы вершины дерева с полустепенью захода 2 могут иметь две различные пометки,то число рассматриваемых упорядоченных (неупорядоченных) деревьев не превосходит 10p (соответственно 8p ).Лемма 1.2. Число попарно неизоморфных упорядоченныхориентированных ациклических связных графов с не более,чем r, истоками, помеченными числами 1, 2, . . . , r, у которых число дуг, число отличных от истоков вершин иразность между этими числами не более, чем q, p и t соответственно, не превосходит 4q (r + p − 1)t+1 .Доказательство. Пусь G — произвольный граф рассматриваемого вида, D — его остовное наддерево, а V̂ — множествоотличных от истоков вершин G, то есть множество нелистовых вершин D. Заметим, что при этом |E (G)| = |E (D)| 6 q, V̂ 6 p,(1.8) (1.9)V (D) \ V̂ 6 |E (D)| − V̂ + 1.Для того, чтобы задать граф G с точностью до изоморфизма, достаточно:§2.
Формулы и СФЭ171. выбрать его остовное наддерево D, |E (D)| 6 q;2. присоединить каждый лист D либо к одному из r истоков G, либо к одной из нелистовых вершин D, отличной от корня.Так как в силу (1.4), (1.8) и (1.9) число вариантов выборадерева D не больше, чем 4q , а число способов присоединениякаждого из его листьев не больше, чем (p + r − 1), то числопопарно неизоморфных графов G рассматриваемого вида непревосходит 4q (r + p − 1)t+1 .Лемма доказана.Замечание. Из доказательства следует, что аналогичное утверждение справедливо для случая неориентированных сетей.Следствие 1. При r = 1 число указанных графов с не более,чем q, ребрами не превосходит (4q)q .Следствие 2. Число неупорядоченных двоичных графов рассматриваемого вида, у которых вершины с полустепеньюзахода 2 могут иметь 2 различные пометки, не превосходит (8 (p + r))p+1 .§2Представление формул с помощью деревьев,схемы из функциональных элементов.
Оценка числа формул и схем в базисе {&, ∨, ¬}В §1 главы 1 дано индуктивное определение формулы и реализуемой ею функции. Рассмотрим способ представленияформул алгебры логики с помощью ориентированных упорядоченных деревьев.Пусть, по-прежнему, X = {x1 , x2 , .
. . , xn , . . . } — счетныйупорядоченный алфавит входных БП и пусть Б == {ϕ1 , ϕ2 , . . . , ϕb } — базис, где ФАЛ ϕi , i = 1, . . . , b, зависитот ki , ki > 1, БП и является существенной ФАЛ, если ki > 2.18Глава 2. Основные классы управляющих системПредполагается, что Б — полный базис (см. §1 главы 1) идопускается, в общем случае, наличие в нем равных ФАЛ.Чаще всего мы будем иметь дело с базисом Б0 = {&, ∨, ¬}.Сопоставим каждому ФС ϕi , i = 1, .
. . , b, функциональный элемент (ФЭ) Ei , имеющий ki входов, причем входу с номером j соответствует j-я БП xj ФАЛ ϕi , где j = 1, . . . , ki , иодин выход, на котором эта ФАЛ реализуется (см. рис. 2.1a).Упрощенный вариант изображения ФЭ Ei в виде вершиныграфа с пометкой ϕi , в которую входят ki упорядоченных,то есть пронумерованных числами 1, . . . , ki дуг, показан нарис. 2.1b. При этом предполагается, что дуга с номеромj, 1 6 j 6 ki , соответствует j-му входу ФЭ Ei .
В дальнейшеммы, как правило, не будем делать различий между функциональным символом ϕi и функциональным элементом Ei .x1 . . . xki••Ei11 1111 ϕi 11 11 a)x*1 . . . xki•*•Ei****1 ** ki** *•ϕib)Рис. 2.1: функциональный элемент EiМножество всех формул над базисом Б будем обозначатьΦΦчерез UΦБ и положим UБ0 = U . Индукцией по глубине каждой формуле глубины q над Б можно сопоставить упорядоченное ориентированное корневое дерево глубины q, каждому листу которого приписана БП из X, а каждой внутренней вершине — ФС из Б.
Формуле xj глубины 0 сопоставим«тривиальное» дерево с единственной вершиной, являющейся корнем и листом одновременно, которой приписана БП xj§2. Формулы и СФЭ19(см. рис. 2.2a). Формуле F видаF = ϕi (F1 , . . . , Fki ) ,(2.1)которая является формулой глубины (q + 1) над Б, гдеq = max {q1 , . . . , qki } ,(2.2)а qj , j = 1, . . . , ki , — глубина главной подформулы Fj формулы F, сопоставим дерево D глубины (q + 1) с корнем v,показанное на рис. 2.2b, где Dj , j = 1, . . . , ki — дерево глубины qj с корнем vj , которое соответствует формуле Fj .•xjD1...Dki•<v1 <<<<1• vki<< << ki• ϕiva)b)Рис.
2.2: представление формулы деревомЗаметим, что формула F по сопоставленному ей деревуD восстанавливается однозначно, и что при этом поддеревьядерева D взаимнооднозначно сопоставляются подформуламформулы F. На рис. 2.3a показано дерево, соответствующееформуле((x1 ∨ x2 ) ∨ x3 ) ∨ (x3 (x1 ∨ x2 ) ∨ x1 x2 ) ,(2.3)которая является формулой глубины 4 над базисом Б0 и{0,2,3}реализует ФАЛ s3.20Глава 2. Основные классы управляющих системx41x2x1x2••44•44 44 44x43 1 4 2 x41x21 4 2 x3•4••44•••444 ∨44 ∨ 444 441 4 21 4 21 4 2•44•44oo•44o∨ 44& 44 ooo o &1 41 4 oo 2•4oo•wo¬ 444ooo ∨o4o1 4 oo 2•wo•4∨a)xO41x2•4OO oo•4441 2 o44ooOoOOO1 2o 4 O 44344oo 1 4•44 2 OO4•'44 ox•woo•o444o∨∨44& 44oo4 444 2 4•wo 1ooo1 4• 22 4444 1 & 1 ∨••44∨ 444 ¬2 4 1•z1 ∨b)Рис.
2.3: представление формулы (2.3) деревом иквазидеревомДля удобства будем считать, что в UΦБ входят не толькоотдельные формулы, но и упорядоченные системы (наборы)формул над базисом Б, что каждая такая система реализуетнабор, состоящий из ФАЛ, реализуемых ее формулами, ичто этой системе формул соответствует система из деревьев,сопоставленных ее формулам.Заметим, что ранг R (F) формулы F равен числу листьевсвязанного с ней дерева D, ее сложность L(F) равна числуостальных вершин D, а ее глубина D (F) — глубине его корня. Заметим также, что порядок вхождения БП в записьформулы F при ее просмотре слева направо соответствует последовательности появления БП на листьях связанного с ней дерева,просматриваемых в «естественном» порядке(см. §1).Рассмотрим теперь некоторые соотношения между параметрами формул над базисом Б0 . Заметим, что представляяформулы деревьями, такие соотношения можно доказыватьболее простым и наглядным способом.§2.
Формулы и СФЭ21Лемма 2.1. Для формулы F, F ∈ UΦ , выполняются неравенстваR (F) = L&,∨ (F) + 1 6 L (F) + 1 6 2D(F) ,(2.4)где L&,∨ (F) — число ФЭ & и ∨ в формуле F.Доказательство. Сравнивая число ребер, входящих в вершины дерева (формулы) F с числом ребер, выходящих изего вершин, получим|E (F)| = 2L&,∨ (F) + L¬ (F) = L (F) + R (F) − 1,где L¬ (F) — число ФЭ ¬ в формуле , откуда следует, чтоR (F) = L&,∨ (F) + 1.Второе из соотношений 2.4 легко устанавливается индукцией по D (F).Лемма доказана.Следствие.D (F) > dlog (L (F) + 1)e .(2.5)Рассмотрим теперь более общую по сравнению с формулами модель — модель схем из функциональных элементов(СФЭ), в которой последовательность операций суперпозиции базисных ФАЛ задается с помощью ориентированногоациклического графа, обобщающего дерево, и где возможномногократное использование промежуточных результатов.По существу СФЭ получается из системы деревьев (системы формул) в результате отождествления некоторых изоморфных поддеревьев (совпадающих подформул).Пусть Z — счетный упорядоченный алфавит (выходных)БП, который не имеет общих БП с алфавитом X.22Глава 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
