OK_metodichka_part_2 (1132797), страница 6
Текст из файла (страница 6)
Эквивалентные преобразования формул35Систему τ осн будем называть системой основных тождеств,а систему τeосн — расширенной системой основных тождеств. Рассмотренные выше примеры выводимостей доказывают следующее утверждение.Лемма 4.1. Система τeосн выводима из системы τ осн .Покажем теперь, что с помощью ЭП на основе системытождеств τ осн из любой формулы можно получить совершенную ДНФ или формулу x1 x1 .
Введем для этого некоторые понятия, характеризующие формулы, появляющиесяна промежуточных этапах указанного ЭП. Произвольнуюконъюнкцию букв, содержащую, в общем случае, повторяющиеся или противоположные буквы, будем называть обобщенной ЭК (ОЭК), а дизъюнкцию таких конъюнкций, содержащую, в общем случае, повторяющиеся «слагаемые», —обобщенной ДНФ (ОДНФ). Обычную ЭК (ДНФ) и формулуx1 · x1 будем считать канонической ОЭК (соответственно канонической ОДНФ), а совершенную ДНФ и формулу x1 · x1— совершенными ОДНФ. Напомним (см. §3), что формула,в которой все ФС ¬ применяются только к БП и нет двухпоследовательно применяемых ФС ¬, называется формулойс поднятыми отрицаниями.Пусть формула F (x1 , .
. . , xn ) реализует ФАЛ f (x1 , . . . , xn ).Докажем существование ЭП видаF |⇒ F0τMbF00 |⇒ F|⇒{KtD&,∨ ,t&}τ ΠΠeF,|⇒{ΠΠtD&,∨ ,τ(4.1)}где τ ΠΠ = τ A , τ K , τ ΠK , τ OΠ , tΠ , F0 — формула с поднятыbиFe — каноними отрицаниями, F00 — обобщенная ДНФ, а Fческая и совершенная ОДНФ ФАЛ f соответственно.
Действительно, поднятие отрицаний, то есть переход от F к F0в (4.1) (см. §3) можно осуществить применением тождествMMtM¬ , t& и t∨ к подформулам вида (F1 ), (F1 · F2 ) и (F1 ∨ F2 )36Глава 2. Основные классы управляющих системсоответственно до тех пор, пока все такие подформулы небудут «устранены». Переход от F0 к F00 в (4.1), который называется раскрытиемno скобок, осуществляется применениемDKтождеств t&,∨ , t& к подформулам вида F1 · (F2 ∨ F3 ) или(F1 ∨ F2 ) · F3 до тех пор, пока они встречаются в преобразуемой формуле.b в (4.1), который называется привеПереход от F00 к Fдением подобных, выполняется в три этапа.
На первом этапе каждая ОЭК K 00 из ОДНФ F00 преобразуетсяв канониonKΠKOΠческую ОЭК K с помощью тождеств t& , t0,& , tA& , t& , атакже тождестваxi · xi = x1 · x1 ,(4.2)которое выводится из них следующим образом:xi · xi 7→ (x1 · x1 ) · (xi · xi ) 7→ (xi · xi ) · (x1 · x1 ) 7→ x1 · x1 .tΠK0,&tK&tΠK0,&bНа втором этапе полученная формула F̌ преобразуется в Fпутем «устранения» повторных вхождений равных элементарных или подформул x1 · x1 с помощью тож конъюнкцийи, в случае f 6≡ 0, последующего«устрадеств τ A , τ K , tOΠ∨K , tΠK .нения» ОЭК x1 · x1 с помощью тождеств tA,t∨ ∨0,∨Заметим, что первые два этапа приведения подобных,на которых происходит приведение повторений БП в ОЭК иb Однако, для уменьЭК, уже дают нам искомую формулу F.шения числа шагов в последующих ЭП можно выполнитьтретий этап приведения подобных — этап приведения поглощений ЭК.
На каждом шаге этогоэтапа в полученнойДНФ с помощью тождеств τ A , τ K выделяется подформула вида K 00 ∨ K 00 · K, где K 00 и K — некоторые ЭК, а затемЭК K 00 · K «устраняется» с помощью ЭПK 00 ∨ K 00 · K 7→ K 00 .tΠ§4. Эквивалентные преобразования формул37Заметим также, что раскрытие скобок и различные этапыприведения подобных можно чередовать друг с другом приbЭП подформул формулы F0 или формул F00 , F.bкFe в (4.1) выполняется в два этапа. СначаПереход от Fb которая имеет ранг r, где r = n − q <bла каждая ЭК K из F,n, и не содержит букв БП xi1 , . .
. , xiq , приводится к ее соe от БП X (n) в результате следующеговершенной ДНФ KЭП:b (xi ∨ xi ) · · · xiq ∨ xiq |⇒ K.b |⇒ KeK11tΠK1,&tD&,∨Затем в полученной ОДНФ устраняются повторные вхождения слагаемых так, как это делалось ранее при переходеb и в результате мы приходим к совершенной ОДНФот F̌ к F,eF. Таким образом, доказано следующее утверждение.Лемма 4.2. Любую формулу F (x1 , . .
. , xn ), реализующуюФАЛ f , с помощью ЭП на основе системы тождеств τ оснможно преобразовать в совершенную ОДНФ ФАЛ f от БПX (n).Рассмотрим описанные выше ЭП на примере формулыF = (x1 ∨ x2 ) · (x1 · x3 ) · (x2 ∨ x3 ) ,для которойF 7→ (x1 ∨ x2 ) · (x1 ∨ x3 ) · (x2 ∨ x3 )tM&F0|⇒{bFx1 x2 x3 ∨ x1 x2 ∨ x1 x2 x3 ∨ x2 x3ΠΠ \tΠtD&,∨ ,τ|⇒= F0 ,b= F̌ = F,}x1 x2 ∨ x2 x3b 0,=Fx1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3 ∨ x1 x2 x3e= F.{τ A ,τ K ,tΠ }b0F|⇒{ΠΠtD&,∨ ,τ}38Глава 2. Основные классы управляющих системТеорема 4.1. Система τ осн — полная система тождеств.Доказательство.
Пусть F0 и F00 — эквивалентные формулы,реализующие равные ФАЛ f 0 и f 00 соответственно, а наборx (n) = x содержит все различные БП, встречающиеся в F0e — совершени F00 . Пусть, далее, ФАЛ f (x) равна f 0 и f 00 , а Fная ОДНФ ФАЛ f от БП X (n). В силу леммы 4.2, имеетместо ЭПe |⇒ F00 ,F0 |⇒ Fτ оснτ оснкоторое доказывает теорему.§5Эквивалентные преобразования схем из функциональных элементов и моделирование с ихпомощью формульных преобразований.
Моделирование эквивалентных преобразованийформул и схем в различных базисах, теорема переходаРаспространим введенные в §3 понятия и обозначения напроизвольный класс схем U. В соответствии с определениями из §3 эквивалентность схем Σ0 и Σ00 из U имеет местотогда и только тогда, когда Σ0 и Σ00 реализуют равные системы (матрицы) ФАЛ.
При этом, обычно, предполагается,что соответствующие друг другу полюса (выходы, входы) вΣ0 и Σ00 имеют одинаковые пометки, а эквивалентность Σ0 иΣ00 записывается в виде тождестваt : Σ0 ∼ Σ00 .Для схем из U, как и для формул, определяется ряд«простейших» преобразований, сохраняющих эквивалентностьсхем, которые называются подстановками. Тождествоb0 ∼ Σb 00 ,bt: Σ§5. Преобразования на основе тождеств39которое получается в результате применения одной и тойже подстановки к обеим частям тождества t : Σ0 ∼ Σ00 , называется подстановкой тождества t.
Схема Σ0 называетсяподсхемой схемы Σ, еслиV Σ0 ⊆ V (Σ) ,E Σ0 ⊆ E (Σ)и любая вершина v, v ∈ V (Σ0 ), которая либо относится кмножеству входов (выходов) Σ, либо служит конечной (соответственно начальной) вершиной некоторого ребра из E(Σ)\E(Σ0 ), является входом (соответственно выходом) Σ0 .Будем считать, что для схем из U, как и для формул,имеет место принцип эквивалентной замены, то есть замеb 0 схемы Σ эквивалентной ей схемой Σb 00 мыняя подсхему Σeполучаем схему Σ, которая эквивалентна схеме Σ. При этомвсе введенные в §3 для случая эквивалентных преобразований формул понятия (однократная и кратная выводимость,полнота системы тождеств и др.), а также связанные с ними обозначения переносятся на случай ЭП схем из U безизменений. Заметим, что вопрос о существовании конечнойполной системы тождеств (КПСТ) является одним из основных вопросов, связанных с изучением ЭП схем из заданногокласса U.Рассмотрим эти вопросы на примере ЭП СФЭ.
Мы будемиспользовать все введенные выше общие понятия и определения, касающиеся ЭП схем, считая подстановкой СФЭ переименование (с возможным отождествлением) ее входныхБП и переименование (с возможным дублированием и снятием1 ) ее выходных БП.Напомним, что формулы представляют собой частныйслучай СФЭ, и для определенности будем считать, что лю1Под дублированием (снятием) выхода zi СФЭ понимается нанесение на вершину с пометкой zi еще одной выходной БП (соответственноудаление с неё пометки zi )40Глава 2. Основные классы управляющих системx21x2•2•221 22 22•∼&¬ z•x+1x2•+•++++++•¬¬ •+++ 1 ++ 2+• ∨z11x1x2••• ¬&•yz1a)•{∨x1∼ z•1b)ΠKРис.
5.1: тождества tM& и t1,&бая формула F из UΦБ является формулой-словом (см. ?? части 1), а соответствующую ей формулу-граф, т. е. квазидерево (см. §2), будем обозначать через F. При этом тождествуt : F0 = F00 , где F0 и F00 —формулы из UΦБ , будет соответство000000вать тождество t : F ∼ F , где F и F — соответствующиеF0 и F00 схемы из UCБ , являющееся «схемным» аналогом тождества t. Множество СФЭ вида F, где F ∈ F ⊆ UΦБ , будемобозначать через F, а систему тождеств вида t, где t ∈ τ , аτ — система тождеств для UΦБ , — через τ . Так, на рис. 5.1aΠKи 5.1b приведены тождества tM& и t1,& , являющиеся схемными аналогами введенных выше формульных тождеств tM& иtПK.1,&На рис.
5.2a и 5.2b показаны тождество ветвления tBEiи тождество снятия tCдляфункциональногоэлементаE,i i∈Ei[1, b], соответственно, а на рис. 5.2c — тождество снятиявхода tCвх . Заметим, что применение тождества снятия равносильно выполнению операции удаления висячей вершинысоответствующего типа (см. §7). Заметим также, что тожCCдества tBEi , tEi , tвх не являются аналогами формульных тож-§5. Преобразования на основе тождествx*1 .
. . xki•*•****1 ** ki** *ϕi •z1 , z 2x:$141xki. . . •$$ :: $$ ::: ∼ 1 $$ ::: ki$$ :: :$ ϕi • ki 1 :• ϕi•$ :z1z2a)x*1 . . . xki•*•**** ** ** *ϕi •x1 . . . xki••∼b)x1•∼ ∅c)Рис. 5.2: тождества ветвления, снятия ФЭ и снятия входадеств и положим bτБB = tBEi i=1 , bCτБC = tCEi i=1 ∪ tвх .Очевидно, что с помощью этих тождеств можно избавитьсяот всех висячих вершин и всех внутренних ветвлений, имеющихся в СФЭ. Следовательно, для любой СФЭ Σ, Σ ∈ UCБ,существует ЭП вида Σ |⇒ F, где F — формула (система{τ C ,τ B }UΦБ.формул) изb — однократное ЭП для формул изПусть, далее, F 7→ FtUΦБ , где тождество t имеет видt : F0 (x1 , . . . , xn ) = F00 (x1 , . .
. , xn ) ,b получается из формулы F заменой подфора формула F0мулы F (F1 , . . . , Fn ) формулой F00 (F1 , . . . , Fn ). Сопоставим42Глава 2. Основные классы управляющих систем888888 8888 8888Fn 88Fn 88 88F1 88 88F1 88 88 88 88 88 88 88 @@ . . .88 @@ . . .~~~~ 88 @@@88 @@@→−~~~~t88 88@88 88@~~~~~~88 88F0 88 88F00 88 88 88 88 88 88 88 88 88 88 bFΣРис. 5.3: моделирование ЭП формул с помощью ЭП СФЭэтому ЭП «моделирующее» его однократное ЭП СФЭ виb (см. рис.
5.3). Заметим, что в том случае, когдада F 7→ Σtформулы F0 и F00 являются бесповторными формулами, аb совпадаБП x1 , . . . , xn — их существенными БП, СФЭ Σ00ет с СФЭ F . В остальных случаях из подформулы видаF0 (F1 , . . . , Fn ) формулы F необходимо с помощью тождествτБB сформировать сначала подсхему F0 (F1 , . . . , Fn ), а затемb могут появитьсяприменить тождество t. При этом в СФЭ Σвисячие вершины или внутренние «ветвления», и тогда дляb необходимо провести ЭП вида Σbb кFb |⇒ F.перехода от Σ{τ C ,τ B }b где F, Fb ∈ UΦ ,Следовательно, для любого ЭП вида F |⇒ F,Бτсуществует моделирующее его ЭП видаF|⇒bF.{τ ,τБB ,τБC }На рис. 5.4 показано ЭП СФЭ из UC , которое моделируетЭП (3.1) для формул из UΦ .Из описанного выше способа «моделирования» ЭП формул с помощью ЭП СФЭ, а также способа перехода от формул к СФЭ и обратно на основе ЭП с помощью тождествτБB , τБC вытекает справедливость следующего утверждения.§5.
Преобразования на основе тождествx1•x2x1x3•••¬ •#& •{x2••) && •u•¬•#∨ −→•••#{→¬ −tB&∨••{&∨z1z1•x3•tM&&x143x2x3••&•{#• ¬ −−→−→tΠK1,&tB&•&•{x1 x2• •z1x3•&•}!⇒τC•x1z1∨z1Рис. 5.4: пример моделирования ЭП формул с помощью ЭПСФЭ44Глава 2. Основные классы управляющих системТеорема 5.1. Если τ — конечная полная систематожCBΦ— конечнаядеств для ЭП формул из UБ , то τ , τ , τполная система тождеств для ЭП СФЭ из UCБ. осн B C — КПСТСледствие. Система тождеств τ , τ , τCдля ЭП СФЭ из U .Рассмотрим далее вопросы структурного моделированияформул в различных базисах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
