ОК_Часть_2_2015_(320-328)_v03-09 (1132806), страница 4
Текст из файла (страница 4)
Легко видеть, что с помощью тождеств де Моргана любую формулу из 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. Представим формулу§2. Формулы, их оптимизация по глубине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Глава 2. Основные классы управляющих системПусть теперь Φ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.Замечание. Доказательство теоремы дает индуктивный метод оптимизации формул с поднятыми отрицаниями по глубине с помощью преобразований подобия.§3. Эквивалентные преобразования формул§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Глава 2. Основные классы управляющих системдля ЭП формул над Б, если для любых двух эквивалентныхформул 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 ) ,§3. Эквивалентные преобразования формул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Глава 2. Основные классы управляющих системгде σ ∈ {0, 1}.
Завершая примеры выводимостей, докажем,что ΠK DK OΠt1,& , t&,∨ , tA|⇒ tΠ .∨ , t∨ , t∨Действительно,x1 ∨ x1 x2 7→ x1 (x2 ∨ x2 ) ∨ x1 x2 7→ x1 ((x2 ∨ x2 ) ∨ x2 )tΠK1,&tD&,∨|⇒ x1 ((x2 ∨ x2 ) ∨ x2 ) 7→ x1 (x2 ∨ x2 ) 7→ x1 .KtA∨ ,t∨tOΠ∨tΠK1,&ПоложимΠK ΠKM A K OΠ Dτ осн = tM& , t¬ , t& , t& , t& , t&,∨ , t1,& , t0,& ,Aτ A = tA& , t∨ ,Kτ K = tK& , t∨ ,OΠ,τ OΠ = tOΠ& , t∨DDDτ = t&,∨ , t∨,& ,ΠKΠK ΠK ΠKτ= tΠK0,& , t1,& , t0,∨ , t1,∨ ,τeосн = τ M , τ A , τ K , τ OΠ , τ D , τ ΠK , tΠ .Систему τ осн будем называть системой основных тождеств,а систему τeосн — расширенной системой основных тождеств.
Рассмотренные выше примеры выводимостей доказывают следующее утверждение.Лемма 3.1. Система τeосн выводима из системы τ осн .Покажем теперь, что с помощью ЭП на основе системытождеств τ осн из любой формулы можно получить совершенную ДНФ или формулу x1 x1 . Введем для этого некоторые понятия, характеризующие формулы, появляющиесяна промежуточных этапах указанного ЭП. Произвольную§3. Эквивалентные преобразования формул29конъюнкцию букв, содержащую, в общем случае, повторяющиеся или противоположные буквы, будем называть обобщенной ЭК (ОЭК), а дизъюнкцию таких конъюнкций, содержащую, в общем случае, повторяющиеся «слагаемые», —обобщенной ДНФ (ОДНФ). Обычную ЭК (ДНФ) и формулуx1 · x1 будем считать канонической ОЭК (соответственно канонической ОДНФ), а совершенную ДНФ и формулу x1 · x1— совершенными ОДНФ.
Напомним (см. §2), что формула,в которой все ФС ¬ применяются только к БП и нет двухпоследовательно применяемых ФС ¬, называется формулойс поднятыми отрицаниями.Пусть формула F (x1 , . . . , xn ) реализует ФАЛ f (x1 , . . . , xn ).Докажем существование ЭП видаF |⇒ F0τMbF00 |⇒ F|⇒{KtD&,∨ ,t&}τ ΠΠeF,|⇒{ΠΠtD&,∨ ,τ(3.2)}где τ ΠΠ = τ A , τ K , τ ΠK , τ OΠ , tΠ , F0 — формула с поднятыbиFe — каноними отрицаниями, F00 — обобщенная ДНФ, а Fческая и совершенная ОДНФ ФАЛ f соответственно.
Действительно, поднятие отрицаний, то есть переход от F к F0в (3.2) (см. §2) можно осуществить применением тождествMMtM¬ , t& и t∨ к подформулам вида (F1 ), (F1 · F2 ) и (F1 ∨ F2 )соответственно до тех пор, пока все такие подформулы небудут «устранены». Переход от F0 к F00 в (3.2), который называется раскрытиемno скобок, осуществляется применениемDKтождеств t&,∨ , t& к подформулам вида F1 · (F2 ∨ F3 ) или(F1 ∨ F2 ) · F3 до тех пор, пока они встречаются в преобразуемой формуле.b в (3.2), который называется привеПереход от F00 к Fдением подобных, выполняется в три этапа. На первом этапе каждая ОЭК K 00 из ОДНФ F00 преобразуетсяв канониnoOΠΠKK , аческую ОЭК K с помощью тождеств t& , t0,& , tA,t& &30Глава 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
