Lectionc2 (1132951), страница 5
Текст из файла (страница 5)
§1главы 3). Следуя [30], изложим в данной главе ряд вопросовЭП схем из основных классов и рассмотрим сначала понятия, связанные с эквивалентными преобразованиями схем28Глава 2. Основные классы управляющих системна основе тождеств на примере формул над базисом Б. Напомним, что некоторые ЭП формул базиса Б0 уже использовались для раскрытия скобок и приведения подобных припостроении сокращенной ДНФ (см. §3 главы 1).Для того чтобы выделить набор 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: Fb 0 = F0 (F1 , . . . , Fn ) и Fb 00 = F00 (F1 , .
. . , Fn ), которое нагде Fзывается подстановкой для тождества t.Напомним, что формулы, полученные в процессе индуктивного построения (см. §1 данной главы и §1 главы 1) формулы F, называются ее подформулами. Из определений следует, что для формул имеет место так называемый принципэквивалентной замены. Это означает, что если подформулуb 0 (подформулу Fb 00 ) формулы F заменить, учитывая тождеFb 00 (соответственно Fb 0 ),ство bt, эквивалентной ей формулой Fто полученная в результате такой замены формула F̌ будетэквивалентна формуле F, то есть будет справедливо тождествоť : F = F̌.§3.
Эквивалентные преобразования формул29Указанный переход от F к F̌ (от t к ť) будем записыватьв виде однократной выводимости вида F 7→ F̌ (соответственte в результате прино t 7→ ť). Аналогичный переход от F к Fменения одного из тождеств системы τ (нескольких последовательных применений тождеств из τ ) будем записыватьв виде однократной (соответственно кратной) выводимостиe (соответственно F |⇒ F).e При этом считается,вида F 7→ Fττчто тождествоeet: F=Fвыводится из системы тождеств τ , и этот факт записывается в виде выводимости τ 7→ et или τ |⇒ et в зависимости отe бучисла использованных переходов. Переход вида F |⇒ Fτдем называть также эквивалентным преобразованием форe на основе системы тождеств τ .
Замулы F в формулу Feметим, что в силу обратимости ЭП, из выводимости F |⇒ Fτe |⇒ F. Система тождествследует обратная выводимость Fττ называется полной для ЭП формул над Б, если для любых двух эквивалентных формул F0 и F00 над Б имеет местовыводимость F0 |⇒ F00 .τРассмотрим, в частности, систему, которая состоит изтождествtM& : (x1 · x2 ) = x1 ∨ x2 ,tM∨: (x1 ∨ x2 ) = x1 · x2 ,tM¬ : (x1 ) = x1— тождеств де Моргана для конъюнкции, дизъюнкции и отрицания соответственно, а также тождестваtПK1,& : x1 (x2 ∨ x2 ) = x1 ,30Глава 2. Основные классы управляющих систем— тождества подстановки константы 1 = x2 ∨ x2 в конъюнкцию (см.
тождества (2.2) из главы 1). Пример ЭП формулиз UΦ с помощью этой системы тождеств дает следующаяцепочка выводимостей:x1 (x2 x3 ∨ x2 ∨ x3 ) 7→ x1 (x2 x3 ∨ x2 · x3 ) 7→ x1 .tM&tΠK1,&(3.1)Формулы, получающиеся друг из друга эквивалентными преобразованиями на основе тождеств коммутативностиKtK& и t∨ [!!!тождества не определены в §2 главы 1], а такAже тождеств ассоциативности tA& и t∨ для конъюнкции идизъюнкции соответственно (см. §2 главы 1), называютсяподобными. Легко видеть, что подобные формулы получаются друг из друга перестановкой аргументов и изменениемпорядка выполнения однотипных двуместных базисных операций, образующих соответствующую многоместную операцию, и поэтому могут отличаться друг от друга только глубиной.Заметим, что сложность характеризует время вычисления формулы на одном процессоре, а глубина — время ее параллельного вычисления на неограниченном числе процессоров.
Поэтому оптимизация подобных формул по глубинеявляется частным случаем «распараллеливания» вычислений.Формулы из UΦ можно оптимизировать также по числуотрицаний с помощью эквивалентных преобразований на основе тождеств де Моргана и преобразований подобия. Тождество tM¬ используется при этом для устранения нескольких последовательных вхождений ФС ¬ в оптимизируемойMформуле, а тождества tM& , t∨ — для выполнения переходаF0 = F1 ◦ · · · ◦ Ft = (F1 · · · Ft ),где (◦, ) ∈ {(&, ∨), (∨, &)} и t > 2, во всех ее максимальных по включению подформулах вида F0 , формируемых с§3. Эквивалентные преобразования формул31помощью преобразований подобия.Формула, в которой все ФС ¬ встречаются только надБП, называется формулой с поднятыми отрицаниями.
Легко видеть, что с помощью тождеств де Моргана любую формулу из UΦ можно преобразовать в формулу с поднятымиотрицаниями. Заметим, что преобразования подобия и эквивалентные преобразования формул на основе тождеств деМоргана не изменяют ранг этих формул и, следовательно,число ФС {&, ∨} в них.Определим альтернирование Alt (F)) формулы F с поднятыми отрицаниями как максимальное число измененийтипов ФЭ & и ∨ в цепях дерева, соответствующего формулеF. Заметим, что альтернирование ЭК или ЭД равно нулю,а альтернирование любой (отличной от ЭК и ЭД) ДНФ илиКНФ равно 1.Теорема 3.1.
Для любой формулы F с поднятыми отрицаниями из UΦ существует подобная ей формула F̌ такая,чтоD F̌ 6 dlog (L (F) + 1)e + Alt (F) .(3.2)Доказательство. Доказательство проведем индукцией порангу формулы F. Если R (F) = 1, то формула F имеет видF = xσi , σ ∈ B, и сама удовлетворяет неравенству (3.2).Пусть неравенство (3.2) справедливо для любой подформулы F0 такой, что R(F0 ) 6 a−1, где a > 1, и пусть формулаF имеет ранг a. Представим формулу F в виде:F = Φ (F1 , . . . , Ft ) ,где t > 2, формула Φ(y1 , .
. . , yt ) при некотором ◦, ◦ ∈ {&, ∨},имеет вид y1 ◦ . . . ◦ yt , а альтернирование подформул F1 , . . .. . . , Ft формулы F не больше, чем a0 , где a0 = max{0, (a − 1)}.Положимd = dlog (L (F) + 1)e + a − a0и di = dlog (L (Fi ) + 1)e ,32Глава 2. Основные классы управляющих системгде i = 1, . . . , t, а затем для каждой формулы Fi построимпо индуктивному предположению подобную ей формулу F̌iтакую, чтоD F̌i 6 di + a0 .Заметим, что при этомtX2di 6 2d .(3.3)i=1Действительно, если a − a0 = 1, то2d > 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 .(3.4)Пусть теперь Φ0 — формула вида y1 ◦ · · · ◦ y2d , которой соответствует полное двоичное d-ярусное дерево, а формула Φ00 получается из Φ0 удалением последних q, где q =2d − 2d1 − · · · − 2dt и q > 0 в силу , вхождений БП вместес теми ФС, которые с ними связаны. В силу (3.4) первые 2d1вхождений БП в Φ00 составляют подформулу Φ1 , которойсоответствует полное двоичное d1 -ярусное дерево, содержащее 2d1 вхождений БП в Φ00 , следующие 2d2 вхождений БП вΦ00 — подформулу Φ2 , которой соответствует полное двоичное d2 -ярусное дерево, и так далее, вплоть до последних 2dt§4.
Эквивалентные преобразования формул33вхождений БП в Φ00 , составляющих подформулу Φt , которойсоответствует полное двоичное dt -ярусное дерево.Обозначим через F̌ формулу, которая получается из Φ00заменой подформулы Φi на формулу F̌i , i = 1, . . . , t.
Заметим, что F̌ подобна F, имеет глубину не больше,чемd + a0 = dlog (L (F) + 1)e + a,и поэтому удовлетворяет неравенству (3.2).Теорема доказана.Следствие 1. Для любой ЭК или ЭД Kсуществует подобная формула Ǩ такая, что(3.5)D Ǩ = dlog (L(K) + 1)e ,которая, в силу леммы 2.1, минимальна по глубине.Следствие 2. Для любой ДНФ или КНФ A существуетподобная ей формула Ǎ такая, чтоD Ǎ 6 dlog (L (A) + 1)e + 1.Замечание. Доказательство теоремы дает индуктивный метод оптимизации формул с поднятыми отрицаниями по глубине с помощью преобразований подобия.§4Полнота системы основных тождеств для эквивалентных преобразований формул базиса {&, ∨, ¬}В данном параграфе будем рассматривать только формулынад базисом Б0 , называя их просто формулами. Заметим,что имеют место (см., в частности, §2 главы 1, а также §3)следующие тождества ассоциативностиtA◦ : x1 ◦ (x2 ◦ x3 ) = (x1 ◦ x2 ) ◦ x3 ,34Глава 2.
Основные классы управляющих системтождества коммутативностиtK◦ : x1 ◦ x2 = x2 ◦ x2и тождества отождествления БПtOΠ: x ◦ x = x,◦где ◦ ∈ {&, ∨}, тождества дистрибутивности «◦» относительно «»tD◦, : x1 ◦ (x2 x3 ) = (x1 ◦ x2 ) (x1 ◦ x3 )и тождества («правила») де МорганаtM¬ : (x1 ) = x1 ,tM◦ : (x1 ◦ x2 ) = (x1 ) (x2 ) ,где (◦, ) ∈ {(&, ∨) , (∨, &)}, тождества подстановки констант1ΠKtΠK0,& : x1 (x2 · x2 ) = x2 · x2 , t1,& : x1 (x2 ∨ x2 ) = x1 ,tΠK0,∨ : x1 ∨ x2 · x2 = x1 ,tΠK1,∨ : x1 ∨ (x2 ∨ x2 ) = x2 ∨ x2 ,а также тождество поглощенияtΠ : x1 ∨ x1 x2 = x1 ,тождество обобщенного склеиванияtOC : x1 x2 ∨ x1 x3 = x1 x2 ∨ x1 x3 ∨ x2 x3и другие.Примером ЭП формул с помощью введенных тождествявляется ЭП (3.1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
