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

. . , xn ) и информационных БП y =(y0 , . . . , y2n−q −1 ) часто используют для разложения произвольной ФАЛ f (x1 , . . . , xn ) по БП x00 (см. разложение Шеннона (2.5) из §2 главы 1).§2. Формулы, их оптимизация по глубине15Схему, которая реализует систему ФАЛ 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) идопускается, в общем случае, наличие в нем равных ФАЛ.Чаще всего мы будем иметь дело с базисом Б0 = {&, ∨, ¬}.Любая переменная xj из X считается формулой глубины0 или, иначе, тривиальной формулой над базисом Б, которая реализует функцию xj . Если i ∈ [1, b] и для каждогоj, j ∈ [1, ki ], определена формула Fj глубины qj над Б, которая реализует ФАЛ fj , то запись F видаF = ϕi (F1 , .

. . , Fki )(2.1)16Глава 2. Основные классы управляющих системявляется формулой глубины q над Б, гдеq = max {q1 , . . . , qki } + 1,(2.2)которая реализует функцию 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§2. Формулы, их оптимизация по глубине17глубины 0 сопоставим «тривиальное» дерево с единственной вершиной, являющейся корнем и листом одновременно,которой приписана БП xj (см.

рис. 2.1a). Формуле F вида (2.1) сопоставим дерево D глубины q, определяемой равенством (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ΦБ входят не толькоотдельные формулы, но и упорядоченные системы (наборы)формул над базисом Б, что каждая такая система реализуетнабор, состоящий из ФАЛ, реализуемых ее формулами, и18Глава 2.

Основные классы управляющих системx1x2•1∨x1•x3•21•21•∨x3•¬11•1&•w2x1x2••••21•w2x111x2•∨••2&&•w•1 21 • 2∨222∨x2•2∨∨1•w•12•&x3•'•1 ••2∨1¬1z1 ∨∨a)b)Рис. 2.2: представление формулы (2.3) деревом иквазидеревомчто этой системе формул соответствует система из деревьев,сопоставленных ее формулам.Заметим, что ранг R (F) формулы F равен числу листьевсвязанного с ней дерева D, ее сложность L(F) равна числуостальных вершин 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)§2. Формулы, их оптимизация по глубине19где L&,∨ (F) — число ФС & и ∨ в формуле F.Доказательство. Сравнивая число ребер, входящих в вершины дерева (формулы) F с числом ребер, выходящих изего вершин, получим|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 , . . . , Fn ). Заметим, что формула F (F1 , . . . , Fn ) реализует ФАЛ f (f1 , . . . , fn ), где ФАЛ f (ФАЛ fj ) — ФАЛ, реализуемая формулой F (соответственно Fj , j = 1, . . . , n). Отсюда следует, что если указанную подстановку применитьк обеим частям тождества t : F0 = F00 , где F0 = F0 (x) иF00 = F00 (x), мы получим тождествоb0 = Fb 00 ,bt: F20Глава 2. Основные классы управляющих системb 0 = F0 (F1 , .

. . , Fn ) и Fb 00 = F00 (F1 , . . . , Fn ), которое нагде Fзывается подстановкой для тождества t.Из определений следует, что для формул имеет место такназываемый принцип эквивалентной замены. Это означает,b 0 (вида Fb 00 ) форчто если позиционную подформулу вида Fмулы F заменить, учитывая тождество bt, эквивалентной ейb 00 (соответственно Fb 0 ), то полученная в результаформулой Fте такой замены формула F̌ будет эквивалентна формуле F.Указанный переход от формулы F к формуле F̌ называется(однократным) эквивалентным преобразованием (ЭП) формулы F на основе тождества t, а последовательность однократных ЭП формулы F, выполняемых на основе тождествиз системы τ , считается её (многократным) ЭП на основеэтой системы.Формулы из UΦ , получающиеся друг из друга эквиваKлентными преобразованиями на основе тождеств tK& и t∨ ,AAа также тождеств t& и t∨ , называются подобными.

Легковидеть, что подобные формулы получаются друг из другаперестановкой аргументов и изменением порядка выполнения однотипных двуместных базисных операций, образующих соответствующую многоместную операцию, и поэтомумогут отличаться друг от друга только глубиной.Заметим, что сложность характеризует время вычисления формулы на одном процессоре, а глубина — время ее параллельного вычисления на неограниченном числе процессоров. Поэтому оптимизация подобных формул по глубинеявляется частным случаем «распараллеливания» вычислений.Формулы из UΦ можно оптимизировать также по числуотрицаний с помощью эквивалентных преобразований на основе тождествtM& : (x1 · x2 ) = x1 ∨ x2 ,tM∨: (x1 ∨ x2 ) = x1 · x2 ,§2.

Формулы, их оптимизация по глубине21tM¬ : (x1 ) = x1— тождеств де Моргана для конъюнкции, дизъюнкции иотрицания соответственно, а также преобразований подобия. Тождество tM¬ используется при этом для устранениянескольких последовательных вхождений ФС ¬ в оптимиMзируемой формуле, а тождества tM& , t∨ — для выполненияпереходаF0 = F1 ◦ · · · ◦ Ft = (F1 · · · Ft ),где (◦, ) ∈ {(&, ∨), (∨, &)} и t > 2, во всех ее максимальных по включению подформулах вида F0 , формируемых спомощью преобразований подобия.Формула, в которой все ФС ¬ встречаются только надБП, называется формулой с поднятыми отрицаниями. Легко видеть, что с помощью тождеств де Моргана любую формулу из UΦ можно преобразовать в формулу с поднятымиотрицаниями.