оки2 (С.А. Ложкин - Лекции по основам кибернетики (2014)), страница 4

Заметим, что преобразования подобия и эквивалентные преобразования формул на основе тождеств деМоргана не изменяют ранг этих формул и, следовательно,число ФС {&, ∨} в них.Определим альтернирование Alt (F) формулы F с поднятыми отрицаниями как максимальное число измененийтипов ФС & и ∨ в цепях дерева, соответствующего формулеF. Заметим, что альтернирование ЭК или ЭД равно нулю,а альтернирование любой (отличной от ЭК и ЭД) ДНФ илиКНФ равно 1.Теорема 2.1. Для любой формулы F с поднятыми отрицаниями из UΦ существует подобная ей формула F̌ такая,чтоD F̌ 6 dlog (L (F) + 1)e + Alt (F) .(2.6)Доказательство. Доказательство проведем индукцией порангу формулы F.

Если R (F) = 1, то формула F имеет видF = xσi , σ ∈ B, и сама удовлетворяет неравенству (2.6).22Глава 2. Основные классы управляющих системПусть неравенство (2.6) справедливо для любой подформулы F0 такой, что R(F0 ) 6 r − 1, где r > 2, и пусть формулаF имеет ранг r и альтернирование a. Представим формулуF в виде:F = Φ (F1 , . . . , Ft ) ,где t > 2, формула Φ(y1 , . . . , yt ) при некотором ◦, ◦ ∈ {&, ∨},имеет вид y1 ◦ . .

. ◦ yt , альтернирование подформул F1 , . . .. . . , Ft формулы F не больше, чем a0 , где a0 = max{0, (a − 1)},а их ранг не превосходит (r − 1). Положимd = dlog (L (F) + 1)e + a − a0и di = dlog (L (Fi ) + 1)e ,где i = 1, . . . , t, а затем для каждой формулы Fi построимпо индуктивному предположению подобную ей формулу F̌iтакую, чтоD F̌i 6 di + a0 .Заметим, что при этомtX2di 6 2d .(2.7)i=1Действительно, если a − a0 = 1, тоd2 > 2 (L (F) + 1) =tX2 (L (Fi ) + 1) >i=1tX2di ,i=1а если a = a0 = 0, то F = xσ1 1 ◦ · · · ◦ xσt t и, следовательно,tXi=12di=tX(L (xσi i ) + 1) = L (F) + 1 6 2d .i=1Заметим также,что перенумерацией формул F̌i , i = 1, . .

. , t,можно добиться выполнения неравенств:d1 > d2 > · · · > dt .(2.8)§2. Формулы, их оптимизация по глубине23Пусть теперь Φ0 — формула вида y1 ◦ · · · ◦ y2d , которой соответствует полное двоичное d-ярусное дерево, а формула Φ00 получается из Φ0 удалением последних q, где q =2d − 2d1 − · · · − 2dt и q > 0 в силу (2.7), вхождений БПвместе с теми ФС, которые с ними связаны.

В силу (2.8)первые 2d1 вхождений БП в Φ00 составляют подформулу Φ1 ,которой соответствует полное двоичное d1 -ярусное дерево,содержащее 2d1 вхождений БП в Φ00 , следующие 2d2 вхождений БП в Φ00 — подформулу Φ2 , которой соответствуетполное двоичное d2 -ярусное дерево, и так далее, вплоть допоследних 2dt вхождений БП в Φ00 , составляющих подформулу Φt , которой соответствует полное двоичное dt -ярусноедерево.Обозначим через F̌ формулу, которая получается из Φ00заменой подформулы Φi на формулу F̌i , i = 1, . . .

, t. Заметим, что F̌ подобна F, имеет глубину не больше,чемd + a0 = dlog (L (F) + 1)e + a,и поэтому удовлетворяет неравенству (2.6).Теорема доказана.Следствие 1. Для любой ЭК или ЭД Kсуществует подобная формула Ǩ такая, чтоD Ǩ = dlog (L(K) + 1)e ,(2.9)которая, в силу леммы 2.1, минимальна по глубине.Следствие 2. Для любой ДНФ или КНФ A существуетподобная ей формула Ǎ такая, чтоD Ǎ 6 dlog (L (A) + 1)e + 1.Замечание. Доказательство теоремы дает индуктивный метод оптимизации формул с поднятыми отрицаниями по глубине с помощью преобразований подобия.24Глава 2. Основные классы управляющих систем§3Задание формул графами, схемы из функциональных элементов.

Оценка числа формул и схем в базисе {&, ∨, ¬}Рассмотрим теперь более общую по сравнению с формулами модель — модель схем из функциональных элементов(СФЭ), в которой последовательность операций суперпозиции базисных ФАЛ задается с помощью ориентированногоациклического графа, обобщающего дерево, и где возможномногократное использование промежуточных результатов.По существу СФЭ получается из системы деревьев (системы формул) в результате отождествления некоторых изоморфных поддеревьев (совпадающих подформул).Пусть Z — счетный упорядоченный алфавит (выходных)БП, который не имеет общих БП с алфавитом X.

Сопоставим каждому функциональному символу (ФС) ϕi , i =1, . . . , b, функциональный элемент (ФЭ) Ei , имеющий ki входов, причем входу с номером j соответствует j-я БП xj ФАЛϕi , где j = 1, . . . , ki , и один выход, на котором эта ФАЛ реализуется (см. рис. 3.1a). Упрощенный вариант изображенияФЭ Ei в виде вершины графа с пометкой ϕi , в которую входят ki упорядоченных, то есть пронумерованных числами1, .

. . , ki дуг, показан на рис. 3.1b. При этом предполагается,что дуга с номером j, 1 6 j 6 ki , соответствует j-му входу ФЭ Ei . В дальнейшем мы, как правило, не будем делатьразличий между функциональным символом ϕi и функциональным элементом Ei .Определение. Схемой из функциональных элементов надбазисом Б называется ориентированная ациклическая упорядоченная сеть Σ, входная выборка которой состоит из всехистоков Σ, а вершины помечены следующим образом:1. каждому входу (выходу) Σ сопоставлена БП из X (соответственно Z), являющаяся пометкой связанной с§3. СФЭ, оценка числа формул и схемx1 . . .

xki••Eix1 . . . xk i••ϕia)25Eiki1•ϕib)Рис. 3.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. Заметим, что указанное квазидерево Σ одно-26Глава 2.

Основные классы управляющих системx1x2•1&x1•21 •2•{2∨x3# ∨•{ 2•2•1 1&1x2••1• ∨z1•#1¬&•u)∨x3•2∨∨&vu)∨u¬∨a)z1b)Рис. 3.2: СФЭ, полученная из квазидерева на рис. 2.2bзначно определяет формулу F и является СФЭ над базисомБ. Из этого квазидерева путем «отождествления» (наложения) его изоморфных квазиподдеревьев можно получать идругие СФЭ, задающие формулу F. На рис. 2.2b показаноквазидерево над базисом Б0 с входными БП x1 , x2 , x3 и выходной БП z1 , которое получено из дерева, сопоставленногоформуле (2.3) и изображенного на рис. 2.2a. На рис. 3.2aприведена СФЭ, полученная из данного квазидерева в результате отождествления двух его изоморфных квазиподдеревьев, а на рис. 3.2b дано более «наглядное» изображениеэтой СФЭ в виде системы соединенных соответствующимобразом ФЭ.Обозначим через UCБ множество всех СФЭ над базисомБ, и пусть UC = UC.Заметим,что система квазидеревьевБ0с общими входами, соответствующая системе формул над§3.

СФЭ, оценка числа формул и схем27базисом Б, является СФЭ над Б, если выходам этих квазидеревьев приписаны различные выходные БП. В связи сэтим формулы над Б и их системы будем считать частнымслучаем СФЭ над Б, полагая, что имеет место включение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 , . . .