2 (1132838), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

. . , 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.Из определений следует, что для формул имеет место такназываемый принцип эквивалентной замены.

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

Легко видеть, что с помощью тождеств де Моргана любую формулу из UΦ можно преобразовать в формулу с поднятымиотрицаниями. Заметим, что преобразования подобия и эквивалентные преобразования формул на основе тождеств деМоргана не изменяют ранг этих формул и, следовательно,число ФС {&, ∨} в них.Определим альтернирование 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).Пусть неравенство (2.6) справедливо для любой подформулы F0 такой, что R(F0 ) 6 r − 1, где r > 2, и пусть формулаF имеет ранг r и альтернирование a. Представим формулуВведение23F в виде: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, то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 .(2.8)24ВведениеПусть теперь Φ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.Замечание.

Доказательство теоремы дает индуктивный метод оптимизации формул с поднятыми отрицаниями по глубине с помощью преобразований подобия.Введение§325Задача эквивалентных преобразований схемна примере формул. Полнота системы основных тождеств для эквивалентных преобразований формул базиса {&, ∨, ¬}Эквивалентные преобразования (ЭП), то есть преобразования, не изменяющие функционирования схем, играют важную роль при решении различных задач теории управляющих систем и, в частности, задачи синтеза схем (см.

§1 главы3). Следуя [30], изложим ряд вопросов ЭП схем из основныхклассов и рассмотрим сначала понятия, связанные с эквивалентными преобразованиями схем на основе тождеств напримере формул над базисом Б. Напомним, что некоторыеЭП формул базиса Б0 уже использовались для раскрытияскобок и приведения подобных при построении сокращеннойДНФ (см.

§3 главы 1), а также при оптимизации формул поглубине (см. §2).Однократное ЭП формулы F в формулу F̌ с помощьютождества t (см. §2) будем записывать в виде однократнойe в резульвыводимости вида F 7→ F̌. Аналогичное ЭП F в Ftтате применения одного из тождеств системы τ (несколькихпоследовательных применений тождеств из τ ) будем записывать в виде однократной (соответственно кратной) вывоe (соответственно F |⇒ F).e При этомдимости вида F 7→ Fττсчитается, что тождествоeet: F=Fвыводится из системы тождеств τ , и этот факт записывается в виде выводимости τ 7→ et или τ |⇒ et в зависимостиот числа использованных переходов.

Заметим, что в силуe следует обратнаяобратимости ЭП из выводимости F |⇒ Fτe |⇒ F. Система тождеств τ называется полнойвыводимость Fτ26Введениедля ЭП формул над Б, если для любых двух эквивалентныхформул F0 и F00 над Б имеет место выводимость F0 |⇒ F00 .τРассмотрим, в частности, систему τ , которая состоит изтождеств де Моргана и тождестваtПK1,& : x1 (x2 ∨ x2 ) = x1 ,— тождества подстановки константы 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)Далее будем рассматривать только формулы над базисомБ0 , называя их просто формулами. Заметим, что имеют место (см., в частности, §2 главы 1, а также §2) следующиетождества ассоциативностиtA◦ : x1 ◦ (x2 ◦ x3 ) = (x1 ◦ x2 ) ◦ x3 ,тождества коммутативности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 ) ,Введение27где (◦, ) ∈ {(&, ∨) , (∨, &)}, тождества подстановки констант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и другие.Докажем, что MMtM& , t¬ |⇒ t∨и K M t& , τ|⇒ tK∨ ,M Mгде τ M = tM& , t¬ , t∨ .

Действительно,x1 ∨ x2 |⇒ x1 ∨ x2 7→ (x1 ) · (x2 ) 7→ x1 · x2tM&tM¬tM¬иx1 ∨ x2 7→ x1 ∨ x2 7→ x1 · x2 7→ x2 · x1 |⇒ x2 ∨ x1 .tM¬tM∨tK&MtM& , t¬Аналогичным образом доказывается, что OΠ M MtA|⇒ tA|⇒ tOΠ,∨ , t& , τ∨&, τDΠKMt&,∨ , τ M |⇒ tD|⇒ tΠKσ,∨ ,∨,& и tσ,& , τ1В отличие от тождеств (2.1)–(2.2) главы 1 данные тождества подстановки констант ориентированы на базис Б0 , где роль константы 0(константы 1) играет формула вида xi · xi (соответственно xi ∨ xi ).28Введениегде σ ∈ {0, 1}.

Характеристики

Список файлов лекций