OK_metodichka_part_2 (1132797), страница 3
Текст из файла (страница 3)
. . , vp0 и V 00 == v100 , . . . , vq00 из множества V (G) графа G определим матрицу достижимости выборки V 0 из выборки V 00 как матрицу M, M ∈ B p,q , для которой(1, если vj00 достижима из vi0 ,M hi, ji =0, в остальных случаях.Заметим, что в случае V 0 = V 00 матрица M является рефлексивной и транзитивной1 , а если, кроме того, G — неори1Матрица M, M ∈ B m,m , считается рефлексивной (транзитивной)14Глава 2. Основные классы управляющих систементированный граф, то и симметричной матрицей. Заметим также, что транзитивность рефлексивной матрицы 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 .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 вместо операциисложения используется операция дизъюнкции.§2. Формулы и СФЭ15вершине которой реализуется функция (столбец из функций) от этих переменных.
При этом считается, что самасхема реализует систему (матрицу), состоящую из функций (соответственно столбцов функций), реализованных наее выходах. В качестве выходных пометок схемы используются, как правило, специальные выходные переменные,а схема Σ с входными переменными (входами) x1 , . . . , xnи выходными переменными z1 , . . . , zm записывается в видеΣ = Σ(x1 , . .
. , xn ; z1 , . . . , zm ).Схему, которая реализует систему ФАЛ Qn (Jn , µn ) будем называть дешифратором (соответственно дизъюнктивным дешифратором, мультиплексором) порядка n. Схемы,реализующие равные системы функций, называются эквивалентными. Предполагается, что изоморфные схемы всегда эквивалентны, и поэтому для любого конечного множества схем 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) и16Глава 2. Основные классы управляющих системдопускается, в общем случае, наличие в нем равных ФАЛ.Чаще всего мы будем иметь дело с базисом Б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. Формулы и СФЭ17(см. рис. 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.18Глава 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. Формулы и СФЭ19Лемма 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.20Глава 2.
Основные классы управляющих системОпределение. Схемой из функциональных элементов надбазисом Б называется ориентированная ациклическая упорядоченная сеть Σ, входная выборка которой состоит из всехистоков Σ, а вершины помечены следующим образом:1. каждому входу (выходу) Σ сопоставлена БП из X (соответственно Z), являющаяся пометкой связанной сним вершины, причем различным входам (выходам)сопоставлены различные БП, а упорядоченность вершин во входной и выходной выборках Σ определяетсяупорядоченностью сопоставленных им БП;2.
каждая отличная от истока вершина v схемы Σ помечена ФС ϕi , где ki = d+Σ (v).Заметим, что в общем случае вершины в выходной выборке СФЭ могут повторяться, то есть одной и той же выходной вершине может быть сопоставлено несколько БП изZ.
Если множество X = {xi1 , . . . , xin } (Z = {zj1 , . . . , zjm }) состоит из всех входных (соответственно выходных) БП СФЭΣ, перечисленных в порядке возрастания их номеров в алфавите X (соответственно Z), то, в соответствии с §1, будемзаписывать СФЭ Σ в виде Σ = Σ (X; Z) или Σ = Σ (x; z),где x = (xi1 , . .
. , xin ) и z = (zj1 , . . . , zjm ) — наборы БП, соответствующие множествам X и Z.Схема Σ, которая получается из дерева D, связанного сформулой F из UΦБ , в результате отождествления листьев содинаковыми пометками и приписывания его корню выходной БП из Z, называется квазидеревом, соответствующимформуле F. Заметим, что указанное квазидерево Σ однозначно определяет формулу F и является СФЭ над базисомБ. Из этого квазидерева путем «отождествления» (наложения) его изоморфных квазиподдеревьев можно получать идругие СФЭ, задающие формулу F. На рис. 2.3b показаноквазидерево над базисом Б0 с входными БП x1 , x2 , x3 и вы-§2.
Формулы и СФЭxG1x2GG www• 2wwGG1ww GGx3*•{w * w2 1 G•G# ∨GG ww•GGww& **wG2**ww GGG 2w*w{11 •#•2 * ∨** &1** 1•4•¬∨ 4444 2 44 1• ∨•Gz1a)21x#S1xk•2SSSkkkkk ##11 ukkk S1S1 ) 11& 11∨ x311#S## SSSS kkkk•SkSkSk#11 ukk 1S1 ) 11& 11∨ 11nnjjj11 vnnn 11 ujjjj11∨ 11¬ 1:1:::: 11 11∨ 1•# SSSz1b)Рис. 2.4: СФЭ, полученная из квазидерева на рис. 2.3bходной БП z1 , которое получено из дерева, сопоставленногоформуле (2.3) и изображенного на рис. 2.3a. На рис.
2.4aприведена СФЭ, полученная из данного квазидерева в результате отождествления двух его изоморфных квазиподдеревьев, а на рис. 2.4b дано более «наглядное» изображениеэтой СФЭ в виде системы соединенных соответствующимобразом ФЭ.Обозначим через UCБ множество всех СФЭ над базисомБ, и пусть UC = UC.Заметим,что система квазидеревьевБ0с общими входами, соответствующая системе формул надбазисом Б, является СФЭ над Б, если выходам этих квазидеревьев приписаны различные выходные БП. В связи сэтим формулы над Б и их системы будем считать частнымслучаем СФЭ над Б, полагая, что имеет место включениеCCΦUΦБ ⊆ UБ . Заметим также, что СФЭ Σ, Σ ∈ UБ , входит в UБ22Глава 2. Основные классы управляющих системтогда и только тогда, когда все стоки Σ, и только они, являются ее выходами, а из каждой вершины Σ, отличной отее входов и выходов, исходит одна дуга.Определим теперь функционирование СФЭ Σ == Σ (x1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
