ОК_Часть_2_2015_(320-328)_v03-09 (1132806), страница 5
Текст из файла (страница 5)
Основные классы управляющих системтакже тождестваxi · xi = x1 · x1 ,(3.3)которое выводится из них следующим образом:xi · xi 7→ (x1 · x1 ) · (xi · xi ) 7→ (xi · xi ) · (x1 · x1 ) 7→ x1 · x1 .tΠK0,&tK&tΠK0,&bНа втором этапе полученная формула F̌ преобразуется в Fпутем «устранения» повторных вхождений равных элементарных конъюнкций или подформул x1 · x1 с помощью тождеств τ A , τ K , tOΠи, в случае f 6≡ 0, последующего«устра∨ A K ΠKнения» ОЭК x1 · x1 с помощью тождеств t∨ , t∨ , t0,∨ .Заметим, что первые два этапа приведения подобных,на которых происходит приведение повторений БП в ОЭК иb Однако, для уменьЭК, уже дают нам искомую формулу F.шения числа шагов в последующих ЭП можно выполнитьтретий этап приведения подобных — этап приведения поглощений ЭК.
На каждом шаге этогоэтапа в полученнойДНФ с помощью тождеств τ A , τ K выделяется подформула вида K 00 ∨ K 00 · K, где K 00 и K — некоторые ЭК, а затемЭК K 00 · K «устраняется» с помощью ЭПK 00 ∨ K 00 · K 7→ K 00 .tΠЗаметим также, что раскрытие скобок и различные этапыприведения подобных можно чередовать друг с другом приbЭП подформул формулы F0 или формул F00 , F.beПереход от F к F в (3.2) выполняется в два этапа. Сначаb которая имеет ранг r, где r = n − q <b из F,ла каждая ЭК Kn, и не содержит букв БП xi1 , .
. . , xiq , приводится к ее соe от БП X (n) в результате следующеговершенной ДНФ KЭП:b |⇒ Kb (xi ∨ xi ) · · · xiq ∨ xiq |⇒ K.eK11tΠK1,&tD&,∨§3. Эквивалентные преобразования формул31Затем в полученной ОДНФ устраняются повторные вхождения слагаемых так, как это делалось ранее при переходеb и в результате мы приходим к совершенной ОДНФот F̌ к F,e Таким образом, доказано следующее утверждение.F.Лемма 3.2. Любую формулу F (x1 , . .
. , xn ), реализующуюФАЛ f , с помощью ЭП на основе системы тождеств τ оснможно преобразовать в совершенную ОДНФ ФАЛ f от БПX (n).Рассмотрим описанные выше ЭП на примере формулыF = (x1 ∨ x2 ) · (x1 · x3 ) · (x2 ∨ x3 ) ,для которойF 7→ (x1 ∨ x2 ) · (x1 ∨ x3 ) · (x2 ∨ x3 )tM&F0|⇒{bFx1 x2 x3 ∨ x1 x2 ∨ x1 x2 x3 ∨ x2 x3ΠΠ \tΠtD&,∨ ,τ|⇒= F0 ,b= F̌ = F,}x1 x2 ∨ x2 x3b 0,=Fx1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3e= F.{τ A ,τ K ,tΠ }b0F|⇒{ΠΠtD&,∨ ,τ}Теорема 3.1. Система τ осн — полная система тождеств.Доказательство. Пусть F0 и F00 — эквивалентные формулы,реализующие равные ФАЛ f 0 и f 00 соответственно, а наборx (n) = x содержит все различные БП, встречающиеся в F0e — совершени F00 .
Пусть, далее, ФАЛ f (x) равна f 0 и f 00 , а Fная ОДНФ ФАЛ f от БП X (n). В силу леммы 3.2, имеетместо ЭПe |⇒ F00 ,F0 |⇒ Fτ оснкоторое доказывает теорему.τ осн32Глава 2. Основные классы управляющих систем§4Задание формул графами, схемы из функциональных элементов. Оценка числа формул и схем в базисе {&, ∨, ¬}Рассмотрим теперь более общую по сравнению с формулами модель — модель схем из функциональных элементов(СФЭ), в которой последовательность операций суперпозиции базисных ФАЛ задается с помощью ориентированногоациклического графа, обобщающего дерево, и где возможномногократное использование промежуточных результатов.По существу СФЭ получается из системы деревьев (системы формул) в результате отождествления некоторых изоморфных поддеревьев (совпадающих подформул).Пусть Z — счетный упорядоченный алфавит (выходных)БП, который не имеет общих БП с алфавитом X.
Сопоставим каждому функциональному символу (ФС) ϕi , i =1, . . . , b, функциональный элемент (ФЭ) Ei , имеющий ki входов, причем входу с номером j соответствует j-я БП xj ФАЛϕi , где j = 1, . . . , ki , и один выход, на котором эта ФАЛ реализуется (см. рис. 4.1a). Упрощенный вариант изображенияФЭ Ei в виде вершины графа с пометкой ϕi , в которую входят ki упорядоченных, то есть пронумерованных числами1, . . . , ki дуг, показан на рис. 4.1b.
При этом предполагается,что дуга с номером j, 1 6 j 6 ki , соответствует j-му входу ФЭ Ei . В дальнейшем мы, как правило, не будем делатьразличий между функциональным символом ϕi и функциональным элементом Ei .Определение. Схемой из функциональных элементов надбазисом Б называется ориентированная ациклическая упорядоченная сеть Σ, входная выборка которой состоит из всехистоков Σ, а вершины помечены следующим образом:1. каждому входу (выходу) Σ сопоставлена БП из X (соответственно Z), являющаяся пометкой связанной с§4.
СФЭ, оценка числа формул и схемx1 . . . xki••Eix1 . . . xk i••ϕia)33Eiki1•ϕib)Рис. 4.1: функциональный элемент Eiним вершины, причем различным входам (выходам)сопоставлены различные БП, а упорядоченность вершин во входной и выходной выборках Σ определяетсяупорядоченностью сопоставленных им БП;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. Заметим, что указанное квазидерево Σ одно-34Глава 2.
Основные классы управляющих системx1x2•1&x1•21 •2•{2∨x3# ∨•{ 2•2•1 1&1x2••1• ∨z1•#1¬&•u)∨x3•2∨∨&vu)∨u¬∨a)z1b)Рис. 4.2: СФЭ, полученная из квазидерева на рис. 2.2bзначно определяет формулу F и является СФЭ над базисомБ. Из этого квазидерева путем «отождествления» (наложения) его изоморфных квазиподдеревьев можно получать идругие СФЭ, задающие формулу F. На рис. 2.2b показаноквазидерево над базисом Б0 с входными БП x1 , x2 , x3 и выходной БП z1 , которое получено из дерева, сопоставленногоформуле (2.3) и изображенного на рис. 2.2a. На рис. 4.2aприведена СФЭ, полученная из данного квазидерева в результате отождествления двух его изоморфных квазиподдеревьев, а на рис.
4.2b дано более «наглядное» изображениеэтой СФЭ в виде системы соединенных соответствующимобразом ФЭ.Обозначим через UCБ множество всех СФЭ над базисомБ, и пусть UC = UC.Заметим,что система квазидеревьевБ0с общими входами, соответствующая системе формул над§4. СФЭ, оценка числа формул и схем35базисом Б, является СФЭ над Б, если выходам этих квазидеревьев приписаны различные выходные БП. В связи сэтим формулы над Б и их системы будем считать частнымслучаем СФЭ над Б, полагая, что имеет место включениеCCΦUΦБ ⊆ UБ . Заметим также, что СФЭ Σ, Σ ∈ UБ , входит в UБтогда и только тогда, когда все стоки Σ, и только они, являются ее выходами, а из каждой вершины Σ, отличной отее входов и выходов, исходит одна дуга.Определим теперь функционирование СФЭ Σ == Σ (x1 , .
. . , xn ; z1 , . . . , zm ) над базисом Б. Сначала индукцией по q, q = 0, 1, . . ., определим для каждой вершиныv глубины q в схеме Σ реализуемую в ней формулу Fv =Fv (x1 , . . . , xn ) глубины q над базисом Б. Если q = 0, то естьv — вход Σ, положим Fv = xj , где xj — входная БП, сопоставленная вершине v. Пусть теперь v — вершина глубиныq, q > 1, схемы Σ, которая имеет пометку ϕi и в которуювходит ki дуг, причем дуга с номером j, 1 6 j 6 ki , исходитиз вершины vj глубины qj , где уже реализована формулаFj = Fvj глубины qj , а для чисел q, q1 , .
. . , qki выполнено (2.2). Тогда в вершине v реализуется формула F = Fvвида (2.1), которая имеет глубину q. При этом считается,что в вершине v СФЭ Σ реализуется ФАЛ f (x1 , . . . , xn ),если ФАЛ f реализуется формулой Fv , и что СФЭ Σ реализует систему ФАЛ F, F = (f1 , . . . , fm ), или реализуетсистему булевых уравнений z1 = f1 , .
. . , zm = fm , еслиfj , j = 1, . . . , m, — ФАЛ, реализованная в той выходнойвершине СФЭ Σ, которой приписана БП zj .Заметим, что квазидерево, которое соответствует формуле F, реализующей ФАЛ f , а также любая СФЭ, полученная из него отождествлением изоморфных квазиподдеревьев, реализует и формулу F, и ФАЛ f . Так, СФЭ на рис.{0,2,3}4.2 реализует формулу (2.3) и ФАЛ s3(x1 , x2 , x3 ), или{0,2,3}уравнение z1 = s3(x1 , x2 , x3 ).36Глава 2. Основные классы управляющих системВ соответствии с §1 две СФЭ считаются изоморфными,если они изоморфны как помеченные графы, и эквивалентными, если они реализуют равные системы ФАЛ. Заметим,что СФЭ всегда эквивалентна системе формул, реализуемыхею на своих выходах.
Заметим также, что изменение нумерации дуг, входящих в такую вершину v СФЭ Σ, которойсопоставлен ФЭ Ei с симметрической ФАЛ ϕi , не изменяет ФАЛ, реализуемую в вершине v, а значит, не влияет нафункционирование Σ. Схемы, получающиеся друг из другав результате указанных преобразований, называются квазиизоморфными, а номера дуг, входящих в вершину v с симметрической ФАЛ, как правило, не указываются. Легко видеть, что в соответствующих друг другу вершинах изоморфных (квазиизоморфных) СФЭ реализуются одинаковые (соответственно подобные) формулы, а значит, и одинаковыеФАЛ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
